Module petgraph::algo

source ·
Expand description

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.


pub use astar::astar;
pub use bellman_ford::bellman_ford;
pub use bellman_ford::find_negative_cycle;
pub use dijkstra::dijkstra;
pub use feedback_arc_set::greedy_feedback_arc_set;
pub use floyd_warshall::floyd_warshall;
pub use isomorphism::is_isomorphic;
pub use isomorphism::is_isomorphic_matching;
pub use isomorphism::is_isomorphic_subgraph;
pub use isomorphism::is_isomorphic_subgraph_matching;
pub use isomorphism::subgraph_isomorphisms_iter;
pub use k_shortest_path::k_shortest_path;
pub use matching::greedy_matching;
pub use matching::maximum_matching;
pub use matching::Matching;
pub use simple_paths::all_simple_paths;


Bellman-Ford algorithms.
Compute dominators of a control-flow graph.
Compute the transitive reduction and closure of a directed acyclic graph


An algorithm error: a cycle was found in the graph.
Workspace for a graph traversal.
An iterator producing a minimum spanning forest of a graph.
An algorithm error: a cycle of negative weights was found in the graph.
A reusable state for computing the strongly connected components using Tarjan’s algorithm.


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


Graph Condense every strongly connected component into a single node and return the result.
[Generic] Return the number of connected components of the graph.
[Generic] Check if there exists a path starting at from and reaching to.
Return true if the graph is bipartite. A graph is bipartite if its nodes can be divided into two disjoint and indepedent sets U and V such that every edge connects U to one in V. This algorithm implements 2-coloring algorithm based on the BFS algorithm.
[Generic] Return true if the input directed graph contains a cycle.
[Generic] Return true if the input graph contains a cycle.
[Generic] Compute the strongly connected components using Kosaraju’s algorithm.
[Generic] Compute a minimum spanning tree of a graph.
Renamed to kosaraju_scc.
[Generic] Compute the strongly connected components using Tarjan’s algorithm.
[Generic] Perform a topological sort of a directed graph.