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. Optionally, also annotate the SCC nodes with some commutative data. Typical examples would include: minimum element in SCC, maximum element reachable from it, etc.
Structsยง
- SccData ๐
- SccDetails ๐Information about an invidividual SCC node.
- 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. - Sccs
Construction ๐
Enumsยง
- Node
State ๐ - Walk
Return ๐The state of walking a given node.
Traitsยง
- An annotation for an SCC. This can be a representative, the max/min element of the SCC, or all of the above.