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 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ยง

Traitsยง

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