Strongly Connected Components Finder

Description

Partition a bounded directed graph into canonical strongly connected components and return vertex memberships plus its deduplicated condensation edges using iterative Kosaraju–Sharir searches.

Strongly connected components partition a directed graph into maximal groups whose vertices can reach one another in both directions. Collapsing each group gives a condensation graph; one-way reachability between groups does not merge them.

Partition a bounded directed graph into canonical strongly connected components and return vertex memberships plus its deduplicated condensation edges using iterative Kosaraju–Sharir searches.

When to use this tool

Use this tool when you need the stated calculation or classification with explicit inputs, intermediate evidence, and boundary conventions.

How to use the tool and how it works

Supply edges, nodeCount in the field shapes below.
Run the calculation. Correct format, shape, range, or undefined-statistic errors before interpreting a result.
Read componentCount, components, condensationEdges, membership. Use the conventions below.

Run iterative depth-first searches on reversed edges to collect finishing order, then on original edges in reverse finishing order to find mutually reachable groups. Sort members and components by smallest vertex, assign membership IDs, and deduplicate cross-component condensation edges.^[1]

Input field	Meaning and units	Accepted input
edges	Edges	Optional. Array of Array of Safe integer; minimum 0; maximum 511.; minimum items 2; maximum items 2.; maximum items 4096; default [].
nodeCount	Vertices are integer indices 0 through nodeCount - 1; isolated vertices remain in the result.	Required. Safe integer; minimum 0; maximum 512.

Output field	Interpretation	Returned shape
componentCount	Component Count	Required. Safe integer; minimum 0; maximum 512.
components	Member lists sorted numerically; component order follows smallest member.	Required. Array of Array of Safe integer; minimum 0; maximum 511.; minimum items 1; maximum items 512.; maximum items 512.
condensationEdges	Distinct directed pairs of canonical component IDs; internal edges are omitted.	Required. Array of Array of Safe integer; minimum 0; maximum 511.; minimum items 2; maximum items 2.; maximum items 4096.
membership	Component ID for each vertex in numeric vertex order.	Required. Array of Safe integer; minimum 0; maximum 511.; maximum items 512.

json

{
  "input": {
    "nodeCount": 7,
    "edges": [
      [
        0,
        1
      ],
      [
        1,
        2
      ],
      [
        2,
        0
      ],
      [
        2,
        3
      ],
      [
        3,
        4
      ],
      [
        4,
        3
      ],
      [
        4,
        5
      ],
      [
        5,
        6
      ]
    ]
  },
  "output": {
    "componentCount": 4,
    "components": [
      [
        0,
        1,
        2
      ],
      [
        3,
        4
      ],
      [
        5
      ],
      [
        6
      ]
    ],
    "condensationEdges": [
      [
        0,
        1
      ],
      [
        1,
        2
      ],
      [
        2,
        3
      ]
    ],
    "membership": [
      0,
      0,
      0,
      1,
      1,
      2,
      3
    ]
  }
}

Limitations and assumptions

Component IDs are canonical by smallest member, not topological order. Isolated vertices and self-loops remain valid; repeated edges do not duplicate condensation links. Endpoint IDs must be within nodeCount and zero nodes yields empty outputs.
The field tables state structural bounds; cross-field constraints and bounded search or output budgets also apply. Unknown keys are rejected where the object contract disallows them. Input errors are distinct from null fields and deliberate invalid controls in a successful output.

Alternative or Complementary methods

Choose the statistic according to the question and data conventions. Inspect the supplied series or matrix and the stated assumptions before comparing outputs from implementations with different defaults.

References

Tool behavior and example: Strongly Connected Components Finder — tool.io

Similar or alternative tools

Connected components
Label the weakly connected components of a graph over an adjacency map.
Topological sort
Order the nodes of a directed acyclic graph with Kahn's algorithm, always emitting the lexicographically smallest available node first.