Function petgraph::algo::tarjan_scc
source · pub fn tarjan_scc<G>(g: G) -> Vec<Vec<G::NodeId>>Expand description
[Generic] Compute the strongly connected components using Tarjan’s algorithm.
Return a vector where each element is a strongly connected component (scc). The order of node ids within each scc is arbitrary, but the order of the sccs is their postorder (reverse topological sort).
For an undirected graph, the sccs are simply the connected components.
This implementation is recursive and does one pass over the nodes. It is based on A Space-Efficient Algorithm for Finding Strongly Connected Components by David J. Pierce, to provide a memory-efficient implementation of Tarjan’s algorithm.