# [−][src]Module petgraph::algo

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

 all_simple_paths Returns iterator that produces all simple paths from `from` node to `to`, which contains at least `min_intermediate_nodes` nodes and at most `max_intermediate_nodes`, if given, limited by graph's order otherwise Simple path is path without repetitions Algorithm is adopted from https://networkx.github.io/documentation/stable/reference/algorithms/generated/networkx.algorithms.simple_paths.all_simple_paths.html 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_bipartite_undirected Return `true` if the graph is bipartite. A graph is bipartite if it's 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. 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 DeprecatedRenamed 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.