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.

Modules

dominators

Compute dominators of a control-flow graph.

Structs

Cycle	An algorithm error: a cycle was found in the graph.
DfsSpace	Workspace for a graph traversal.
MinSpanningTree	An iterator producing a minimum spanning forest of a graph.
NegativeCycle	An algorithm error: a cycle of negative weights was found in the graph.

Traits

FloatMeasure	A floating-point measure.
Measure	Associated data that can be used for measures (such as length).

Functions

astar	[Generic] A* shortest path algorithm.
bellman_ford	[Generic] Compute shortest paths from node `source` to all other.
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.
kosaraju_scc	[Generic] Compute the strongly connected components using Kosaraju's algorithm.
min_spanning_tree	[Generic] Compute a minimum spanning tree of a graph.
scc	[ Deprecated ] Renamed to `kosaraju_scc`.
tarjan_scc	[Generic] Compute the strongly connected components using Tarjan's algorithm.
toposort	[Generic] Perform a topological sort of a directed graph.