# Module bevy::utils::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.

## Functions

• Returns an 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, or limited by the graph’s order otherwise. The simple path is a path without repetitions.
• [Generic] A* shortest path algorithm.
• [Generic] Compute shortest paths from node `source` to all other.
• 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] Dijkstra’s shortest path algorithm.
• [Generic] Find the path of a negative cycle reachable from node `source`.
• [Generic] Floyd–Warshall algorithm is an algorithm for all pairs shortest path problem
• [Generic] Finds a feedback arc set: a set of edges in the given directed graph, which when removed, make the graph acyclic.
• [Generic] Compute a matching using a greedy heuristic.
• [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] Return `true` if the graphs `g0` and `g1` are isomorphic.
• [Generic] Return `true` if the graphs `g0` and `g1` are isomorphic.
• [Generic] Return `true` if `g0` is isomorphic to a subgraph of `g1`.
• [Generic] Return `true` if `g0` is isomorphic to a subgraph of `g1`.
• [Generic] k’th shortest path algorithm.
• [Generic] Compute the strongly connected components using Kosaraju’s algorithm.
• [Generic] Compute the maximum matching using Gabow’s algorithm.
• [Generic] Compute a minimum spanning tree of a graph.
• sccDeprecated
Renamed to `kosaraju_scc`.
• Using the VF2 algorithm, examine both syntactic and semantic graph isomorphism (graph structure and matching node and edge weights) and, if `g0` is isomorphic to a subgraph of `g1`, return the mappings between them.
• [Generic] Compute the strongly connected components using Tarjan’s algorithm.
• [Generic] Perform a topological sort of a directed graph.