Skip to content

StronglyConnectedComponents

Status: Stable

documented, exercised by the test suite and/or worked examples, with no known limitations recorded.

Description

StronglyConnectedComponents[g] gives the strongly connected components of g (following edge directions).

Examples

No verified examples yet for this function.

Algorithm

components.c - connected-component builtins.

  ConnectedComponents[g]          weak components (underlying undirected)
  WeaklyConnectedComponents[g]    same as ConnectedComponents
  StronglyConnectedComponents[g]  strong components (Tarjan) over directed
                                  adjacency; for undirected graphs this
                                  coincides with the weak components.

Each returns a List of Lists of vertices, components in first-appearance order, vertices within a component in canonical index order.

Memory (SPEC section 4): returns freshly-allocated lists; frees res.

Implementation notes

Attributes: Protected.

References