# Module petgraph::algo

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.

## Re-exports

• `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;`

## Structs

• 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.

## Functions

• 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.
• sccDeprecated
Renamed to `kosaraju_scc`.
• [Generic] Compute the strongly connected components using Tarjan’s algorithm.
• [Generic] Perform a topological sort of a directed graph.