Module rustc_data_structures::graph::scc
source · Expand description
Routine to compute the strongly connected components (SCCs) of a graph.
Also computes as the resulting DAG if each SCC is replaced with a node in the graph. This uses Tarjan’s algorithm that completes in O(n) time.
Structs
- Strongly connected components (SCC) of a graph. The type
N
is the index type for the graph nodes andS
is the index type for the SCCs. We can map from each node to the SCC that it participates in, and we also have the successors of each SCC.