Module 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.
Sccs
Strongly connected components (SCC) of a graph. The type N is the index type for the graph nodes and S 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.
SccsConstruction πŸ”’

Enums§

NodeState πŸ”’
WalkReturn πŸ”’
The state of walking a given node.

Traits§

Annotation
An annotation for an SCC. This can be a representative, the max/min element of the SCC, or all of the above.