Strongly connected components

Read first: Visiting a graph

On a cycle, each statement's result feeds the next and the last feeds the first, so no order puts every statement after everything that feeds it. Which statements belong to one cycle is a question about pairs: does X reach Y, and Y reach X? Asked directly, that is a walk from every statement, each going over the same arrows again.

On this page's seven paragraphs, one depth-first walk from ENTRY-PARA gives each paragraph two numbers, an index and a low, and pops four groups off a stack: {Exit}, {D, E}, {A, B, C}, {Entry}. Each group comes off after every group it leads to, which is the order a tool needs to solve them in.

A component here is a strongly connected component: a largest set of nodes that all reach each other. Path, back edge and preorder are as in visiting a graph.

The example

Seven paragraphs, one node each, with an arrow for every fall-through and every GO TO. A, B and C form a three-paragraph ring; D and E a two-paragraph loop after it:

flowchart LR
    Entry --> A
    A --> B
    B --> C
    C -->|"GO TO A-PARA"| A
    C --> D
    D --> E
    E -->|"GO TO D-PARA"| D
    E --> Exit

The answer: four components, one chip each. Every paragraph is in exactly one; Entry and Exit sit on no cycle, so each is a component on its own.

The paragraphs behind the picture, a fragment constructed for this page. ENTRY-PARA is Entry, A-PARA is A, and so on down to EXIT-PARA, which is Exit:

       ENTRY-PARA.
           MOVE 0 TO WS-TRIES.
       A-PARA.
           ADD 1 TO WS-TRIES.
       B-PARA.
           CALL 'CONNECT' USING WS-STATUS.
       C-PARA.
           IF WS-STATUS NOT = '00' AND WS-TRIES < 3
               GO TO A-PARA.
       D-PARA.
           ADD 1 TO WS-COUNT.
       E-PARA.
           IF WS-COUNT < 10
               GO TO D-PARA.
       EXIT-PARA.
           STOP RUN.

Each paragraph above EXIT-PARA falls through to the next, which gives the six downward arrows. C-PARA's GO TO gives C → A, the retry ring; E-PARA's gives E → D, the counting loop. Those are the picture's eight arrows, and no others.

The walk below tries each paragraph's arrows in the order drawn: the GO TO before the fall-through. So C tries C → A before C → D, and E tries E → D before E → Exit. Every index, low and component below follows from that order:

Step by step

This is Tarjan's algorithm.^[1] It is the depth-first walk, with three additions. Each paragraph gets an index, the order it was first visited, counting from 0. It also gets a low, the smallest index it is known to get back to; this starts equal to its index. And beside the path there is a stack, holding every visited paragraph not yet in a finished component.

In each step's picture, the amber paragraph is the one the walk is at, the amber arrow is the one it just tried, and a dashed outline marks a paragraph already in a finished component. In each table, amber cells are the ones that step changed.

The walk's last table holds the whole result. Every row has a component, and the four components came off the stack in the order of the last step's chips: {Exit}, {D, E}, {A, B, C}, {Entry}.

Why one walk is enough

The walk visited each paragraph once and tried each arrow once: 1 first visit, 8 arrows and 7 back-outs make the 16 steps. Here is where each happened:

Two facts make that enough. The first is what a low below the index means. At step 5, C tried C → A and found A still on the stack. Look at the path chips at that step: Entry A B C. A is above C on the path, so A reaches C along it, and C reaches A by the arrow. So A, B and C all lie on one cycle, and C's low of 1 records it. Step 13 passed that 1 up to B, and here are the final numbers:

The second fact is when a component is complete. A paragraph that backs out with low equal to index reaches nothing older still on the stack. So nothing it reaches can get back above it, and it is the first paragraph of its component that the walk visited, the component's root. Its component is everything on the stack from it upwards: the paragraphs visited after it that are not yet in a finished component. In the table, the amber rows are the four roots, and each root's rows below it share its popped-at step.

That is why the walk needs the stack as well as the path. At step 11, E backed out and left the path, but its low, 4, said it gets back to D, so it stayed on the stack:

Path at step 11

Stack at step 11

One step later D, the root, backed out and took E off the stack with it. Had the walk kept only the path, E would have been lost at step 11 and {D, E} would have come out as {D}.

The order components finish in

The components came off the stack in this order, numbered as in the walk's component column:

Shrink each component to one node and keep the arrows between components. The result is the condensation. It never has a cycle: if two components led to each other, their members would all reach each other, and they would be one component. Here it is, each box labelled with its finish position, each arrow with the original arrow it stands for:

flowchart TD
    S["{Entry} · 4th"] -->|"Entry → A"| R["{A, B, C} · 3rd"]
    R -->|"C → D"| L["{D, E} · 2nd"]
    L -->|"E → Exit"| X["{Exit} · 1st"]

Every arrow points from a later finish to an earlier one. That holds for every graph, not just this one. A root backs out only after everything it reaches has been visited and has backed out. Each component it leads to has therefore been popped already, either earlier in the walk or inside the root's own part of it, as {D, E} was at step 12, inside A's. So the finish order is a reverse topological order of the condensation. Each arrow of the condensation, with its two ends' positions:

Both directions are useful. An answer built from what a node leads to, such as where a value could have come from, is filled in the finish order, so each component's answer is ready before anything that leads into it asks. A forward analysis reads the chips right to left, {Entry}, {A, B, C}, {D, E}, {Exit}, and goes round each loop until it settles before moving on.

The rule

Each line, and the steps of the walk that applied it:

Where this is used

Three pages build on these components. Each row says what that page does with them, worked on this page's graph:

In the first row, memoised reachability's place graph plays the role of the paragraphs here: its ring of three places is popped in one step, as {A, B, C} is at step 15. The second row is checked against the condensation's picture: one arrow enters each box.

What goes wrong

• Comparing with a finished node's index. The rule ignores an arrow to a node that is visited but off the stack. Treat it like an on-stack node instead, and a node can take a low from a component that is already finished. It then never sees low equal to index, and gets merged into the wrong component. Three nodes, arrows tried in the order drawn:

  flowchart LR
      X --> Y
      X --> Z
      Z --> Y
      linkStyle 2 stroke:#f5b041,stroke-width:3px
  

  X gets index 0, and Y index 1; Y has no arrows, so it pops as {Y}. Z gets index 2, then tries Z → Y (amber). Y is visited but off the stack:

  	low(Z) after Z → Y	Z backs out	components
  ignore Y (the rule)	2	low = index: pops {Z}	{Y}, {Z}, {X}
  use index(Y)	1	1 ≠ 2: stays on the stack	{Y}, {Z, X}

  Z cannot reach X, so {Z, X} is wrong. On the walk above it never arises: every arrow there leads to a new node or one still on the stack.
• Recursing once per node. Written as a function that calls itself for each new node, the walk nests one call per node on the path. A long chain makes a deep path:

  flowchart LR
      N1["S1"] --> N2["S2"] --> N3["S3"] --> N4["…"] --> N5["Sn"]
  

  Python allows a thousand nested calls by default (sys.getrecursionlimit() is 1000). Run on chains like this one, a recursive Python version of the rule and a Python version that keeps its own lists, as cobble's does, gave:

  chain of n nodes	recursive	own lists
  990	990 components	990 components
  1,000	RecursionError	1,000 components
  5,000	RecursionError	5,000 components
  100,000	not run	100,000 components

  These are runs of short Python scripts written for this page, not of cobble; the recursive one fails at 1,000 because of that default limit. Memoised reachability records that cobble's combine had already crashed once on Python's recursion limit, and that a walk across a corpus can be millions of places deep.
• Reading "reachable from" as "in the same component". A reaches D, E and Exit, but none of them reaches back. A component needs both directions:

  paragraph	reaches	is reached from	both: its component
  A	A, B, C, D, E, Exit	Entry, A, B, C	A, B, C
  D	D, E, Exit	Entry, A, B, C, D, E	D, E

  Call everything A reaches "A's loop" and the amber paragraphs, the counting loop and EXIT-PARA, land inside the retry ring. A tool reporting loop bodies would print six paragraphs for a three-paragraph loop.
• Taking every one-member component as loop-free. {Entry} and {Exit} sit on no cycle, but a paragraph that jumps to itself is also a component of one member, and it is a loop:

         R-PARA.
             ADD 1 TO WS-COUNT.
             IF WS-COUNT < 10
                 GO TO R-PARA.

  flowchart LR
      Entry --> R
      R --> R
      R --> Exit
      linkStyle 1 stroke:#f5b041,stroke-width:3px
  

  The walk on it: R gets index 1, and R → R finds R on the stack, so its low becomes min(1, 1) = 1. Nothing changes, and R pops alone:

  component	members	on a cycle?
  {Exit}	1	no
  {R}	1	yes: the amber self-loop
  {Entry}	1	no

  "More than one member" finds {A, B, C} and {D, E} on the main example but misses {R}. A one-member component is a loop exactly when it has an arrow to itself.

In cobble and cobol-rekt

Cobble finds components in its combine with Tarjan's algorithm, written out by hand in Closures._solve in cobble/cobble/dataflow/combine/closures.py. Its docstring says "Tarjan's algorithm with an explicit stack". It does not recurse: visiting is the walk's Path row, positions says which arrow each paragraph on it tries next, and stack is the Stack row. Abridged, with comments added:

while visiting:
    vertex = visiting[-1]
    position = positions[-1]
    nexts = local[vertex][1]
    if position < len(nexts):
        positions[-1] = position + 1
        following = nexts[position]
        if following in self._answers:   # settled by an earlier solve
            continue
        if following not in index:       # not yet visited
            visit(following)
        elif following in on_stack:      # steps 5 and 8
            low[vertex] = min(low[vertex], index[following])
        continue
    visiting.pop()                       # backs out
    positions.pop()
    if visiting:
        parent = visiting[-1]
        low[parent] = min(low[parent], low[vertex])
    if low[vertex] == index[vertex]:     # steps 10, 12, 15, 16
        self._settle(vertex, stack, on_stack, local)

Two things differ from the rule box. A successor already answered by an earlier solve is skipped before it is looked at, which is how a second walk stops at the first one's answers. And a visited successor off the stack falls through every branch, which is the rule's "ignore it". _settle gives the popped component one answer. Its _mark flags every member of a component of two or more as revisiting, and a one-member component when, among other cases, vertex in nexts: the self-loop of the last bullet above.

Elsewhere cobble calls networkx's strongly_connected_components: in _cycle_sizes in cobble/cobble/dataflow/fixpoint/diagnose.py, and in cobble/scripts/cycle_sizes.py, which report component sizes. networkx's documentation for that function, in the version installed locally (3.6.1), says it uses Tarjan's algorithm with Nuutila's modifications, in a non-recursive version.

cobol-rekt takes its components from JGraphT. Its reducibility and loop tasks live in the mojo-common submodule. IrreducibleStronglyConnectedComponentsTask and LoopBodyDetectionTask, in src/main/java/com/mojo/algorithms/task/, both build a KosarajuStrongConnectivityInspector:

StrongConnectivityAlgorithm<V, E> scAlg =
    new KosarajuStrongConnectivityInspector<>(flowgraph);
List<Graph<V, E>> stronglyConnectedComponents =
    scAlg.getStronglyConnectedComponents();

The first task then collects, for each component, the edges into it from outside. It reports the component as improper when those edges land on more than one distinct node, which is the check in the second row of the where this is used table. The second task runs the inspector on the subgraph at an irreducible level, as in the third row. The README says the same: components are detected with JGraphT's built-in Kosaraju inspector.

Kosaraju's algorithm, published by Sharir,^[2] gets the same components by a different route: two depth-first passes instead of one.

References

1. R. Tarjan. "Depth-First Search and Linear Graph Algorithms." SIAM Journal on Computing, 1(2), 1972, pp. 146–160. The one-walk algorithm with index, low and a stack that this page walks through.
2. M. Sharir. "A Strong-Connectivity Algorithm and Its Applications in Data Flow Analysis." Computers & Mathematics with Applications, 7(1), 1981, pp. 67–72. The two-pass algorithm usually credited to Kosaraju and Sharir, which cobol-rekt uses through JGraphT.