Module petgraph::algo [−] [src]

Graph algorithms.

It is a goal to gradually migrate the algorithms to be based on graph traits so that they are generally applicable. For now, some of these still require the Graph type.

Structs

DfsSpace

Workspace for a graph traversal.

Functions

condensation	[Graph] Condense every strongly connected component into a single node and return the result.
connected_components	[Generic] Return the number of connected components of the graph.
dijkstra	[Generic] Dijkstra's shortest path algorithm.
has_path_connecting	[Generic] Check if there exists a path starting at `from` and reaching `to`.
is_cyclic_directed	[Generic] Return `true` if the input directed graph contains a cycle.
is_cyclic_undirected	[Generic] Return `true` if the input graph contains a cycle.
is_isomorphic	[Graph] Return `true` if the graphs `g0` and `g1` are isomorphic.
is_isomorphic_matching	[Graph] Return `true` if the graphs `g0` and `g1` are isomorphic.
min_spanning_tree	[Graph] Compute a minimum spanning tree of a graph.
scc	[Generic] Compute the strongly connected components using Kosaraju's algorithm.
tarjan_scc	[Generic] Compute the strongly connected components using Tarjan's algorithm.
toposort	[Generic] Perform a topological sort of a directed graph.