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 🔒
- 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.
Enums§
- 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.