Two passes or one, and what the second one costs

A directed graph’s strongly connected components are its maximal sets of vertices in which every vertex can reach every other. They are what a cyclic dependency looks like when it is found rather than reported, they are what has to be contracted before an acyclic method can be used, and there are two classical ways to compute them.

Both are $O(V + E)$. Both are in every textbook. Both return the same partition on the same graph, which the gate here requires as a relabelling rather than as a count. And on the same graph one of them does 2.2 times the counted work of the other.

That is the shape this field is most interested in and the one a complexity class is worst at reporting. Two algorithms in the same class, on the same input, returning the same answer, and differing by a factor that stays constant across every size measured — so no sweep will ever separate them and no bound will ever mention the difference. Counting on a graph opened this field by adding three primitives precisely because the existing counters could not tell two graph algorithms apart; this is the case where the primitives earn their place.

What each of them does #

Kosaraju’s method is two depth-first passes with a reversal between them. The first pass walks the graph and pushes each vertex onto a list as it finishes. The second walks the reversed arcs, taking vertices in decreasing order of finishing time, and each tree it grows is one component.

The correctness argument is short and worth having: if two vertices are in the same component then each reaches the other in both the graph and its reverse, so they land in the same tree either way; and the finishing order guarantees that the second pass starts in a component with no incoming arcs from unprocessed material.

Tarjan’s method is one depth-first pass and a stack. Each vertex is given an index when it is discovered and a low-link — the smallest index reachable from its subtree by tree arcs and at most one back arc. A vertex whose low-link equals its own index is the root of a component, and the component is everything above it on an auxiliary stack of vertices not yet assigned.

One traversal, two integers per vertex, and a stack.

It is worth noticing what the two methods have in common before measuring what separates them. Both perform exactly one depth-first traversal of the graph as their first act. Both visit every vertex exactly once and the counter says so — 1,024 visits each at a thousand vertices, identical to the unit. Both produce their components in an order that is meaningful. The algorithms are far more alike than their descriptions suggest, and the whole of the measured difference is one structure that only one of them needs.

Where the factor of three is #

The count says the difference is in adjacency scanning, and the arithmetic of it is exactly three:

The middle row is the one nobody counts. “Two depth-first passes” suggests a factor of two, and the second pass needs a graph that does not exist yet: the transpose has to be built, and building it reads every arc of the original and writes every arc of the copy. That is a full pass over the graph in its own right, it happens between the two traversals, and it is invisible in every description of the algorithm because it is described as a precondition rather than as a step.

The factor of 2.2 on total work rather than 3 is because the visit count — one per vertex — is the same for both and dilutes the ratio. At a thousand vertices and 1,536 arcs, visits are 1,024 of Kosaraju’s 5,632 units and 1,024 of Tarjan’s 2,560, so the algorithm doing less work has proportionally more of it in the part that cannot be avoided.

There is a general lesson in the middle row and it is not about these two algorithms. A step described as a precondition is a step. “Run a depth-first search on the reversed graph” reads as one instruction about one traversal, and it contains a construction whose cost equals the traversal’s. The same shape appears wherever an algorithm is stated over a transformed input — sort the edges first, index the text first, transpose the matrix first — and in each case the transformation is charged to nobody. This field’s counter charges it because it counts arc slots examined rather than passes performed, and the two units disagree exactly here.

The space, which goes the other way #

Tarjan’s method holds a stack of vertices that have been discovered and not yet assigned to a component. On a graph that is one large component, that stack reaches nearly every vertex: measured at a thousand vertices in two components, its peak is 2,047 held items against Kosaraju’s list of finishing times, which is $V$.

So the trade is not one-sided, and the shape of it depends on the graph:

A graph with many small components lets Tarjan pop early and often; a graph that is one big cycle makes it hold everything. Kosaraju’s space is $V$ regardless — a list of finishing times and a component array — plus the transpose, which is a whole second copy of the graph and is $E$.

So on space the comparison inverts: Kosaraju needs $O(V + E)$ because it materialises the transpose, and Tarjan needs $O(V)$ because it does not. The measurements above charge the transpose in time and this paragraph charges it in space, and it is the same object both times. That is the pattern measuring what an algorithm keeps exists for: an auxiliary structure that no count of the primary work reports.

The second answer, which both of them give #

Both algorithms return a partition, and both return an ordering of it as well, for nothing.

Kosaraju’s second pass processes vertices in decreasing finishing order, and the components come out in topological order of the condensation — the acyclic graph obtained by contracting each component to a point — because the first tree the reversed walk grows is a component nothing points into. Tarjan’s components come out in reverse topological order, sinks first, which is the same information the other way round. (An earlier version of this page had the two directions swapped. The planted graphs settle it: their source component holds vertex 0, Kosaraju numbers it first and Tarjan numbers it last.)

Either way, that ordering is exactly the input the previous rung’s method wants. The precondition that removes the queue needs a topological order of an acyclic graph; a general directed graph does not have one; contracting its components produces one that does; and the component algorithm has already computed it.

So the two rungs compose into a pipeline that works on any directed graph whatever:

1. find the components — one pass, or three;
2. contract them, which is one more pass over the arcs;
3. relax in the order the first step already produced.

Every step is linear, so the whole is linear, and the shortest path through a general directed graph with arbitrary weights — the problem the bound with a precondition needed Bellman–Ford for — becomes a linear-time computation on the condensation plus whatever is needed inside each component. A precondition that seemed to exclude most graphs turns out to be reachable from any of them for the price of one more linear pass.

What the check is against #

Two algorithms agreeing is worth nothing if the agreement is a tautology, and there are two things that make it evidence here.

They share no code beyond the counted graph. One builds a transpose and runs two traversals; the other runs one traversal and maintains low-links. Neither consults the other, and a bug in either would have to be a bug that produced the other’s answer.

And both are checked against a planted truth. The graphs are built with their components decided in advance — $k$ cycles chained forwards, with every additional arc constrained to run forwards so that it cannot merge two components — so the number of components is known before either algorithm runs. components is a number an algorithm that stopped early would still report, and it would fit $V + E$ perfectly.

The agreement is also required as a partition rather than as a count. Two algorithms can agree that there are eight components and disagree about which vertex is in which, and comparing counts would not notice. The check maps one labelling onto the other and requires the map to be a bijection.

That is the same discipline this field has used since counting on a graph, where Prim and Kruskal are required to find spanning trees of identical weight — two algorithms with nothing in common agreeing on a number being the strongest evidence available.

What a component algorithm is actually for #

It is worth saying, because a partition of the vertices is not obviously useful on its own and the uses are what make the constant factor worth arguing about.

Deciding whether a directed graph has a cycle at all, and if so where. A component of size one with no self-loop is a vertex on no cycle; a component of size greater than one is a cycle, and everything in it is on one. That is what a build tool reports when it refuses a circular dependency, and it is why the report can name the whole cycle rather than one edge of it.

Contracting to an acyclic graph. Every problem that is invariant under merging mutually-reachable vertices — reachability, the existence of a path, a longest path over a scoring function that ignores cycles — becomes a problem on the condensation, which is acyclic and therefore admits the previous rung’s method.

And two-satisfiability, which is the classical application and the one that makes the algorithm famous outside graph theory. A formula of two-literal clauses is satisfiable exactly when no variable lies in the same component as its own negation, in an implication graph built from the clauses. That is a linear-time decision procedure for a problem whose three-literal cousin is NP-complete, and the whole of it is one component computation.

The third use is the one that decides which algorithm to prefer in a library, because it runs on graphs derived from formulas rather than from data — millions of vertices, built in memory, where a second copy of the arcs is the difference between running and not.

Which one to use, and why the answer is usually Tarjan #

The measurements say Tarjan does a third of the arc examinations and holds a stack that can reach $V$. That is a clear win on time and an unclear one on space, and in practice the answer is less balanced than that suggests.

The transpose is the problem. Building it is not merely a pass; it is an allocation of a second graph, which on a large graph is the difference between fitting in memory and not. The external-memory field’s arithmetic applies directly: a transpose is a permutation of the arc list, and permuting is the harder problem there — so on a graph that does not fit, Kosaraju’s middle pass is not a scan at all but a sort.

And Tarjan’s stack is bounded by something useful. It holds vertices discovered and not yet assigned, which is at most the current path plus the components partly explored — bounded by $V$, and in the common case of many small components, far below it. The table above is the measured version: sixty-four components put the peak at 300 of 1,024.

The one case for Kosaraju is clarity. Its correctness argument is two paragraphs and Tarjan’s low-link invariant is the kind of thing that takes a page and is easy to implement subtly wrong. That is a real consideration and it is not one this site can measure.

Why a low-link is hard to get right and a transpose is not #

The clarity argument deserves more than a sentence, because it is the reason the slower algorithm survives.

Kosaraju’s method is made of parts that are already trusted. A depth-first traversal recording finishing times is the traversal this field has measured since its first plate. A transpose is a loop. A second traversal in a given order is the first traversal with a different starting sequence. Every piece is separately checkable, and a bug in any of them shows up as a wrong partition rather than as a subtly wrong one.

Tarjan’s method has an invariant that must hold at every step and cannot be checked at any single one. A vertex’s low-link is the smallest index reachable from its subtree using tree arcs and at most one back arc — at most one, and the arc must go to a vertex still on the stack. Getting either of those conditions slightly wrong produces an algorithm that is right on most graphs. Using the neighbour’s low-link where the neighbour’s index is wanted, or updating from a cross arc into a finished component, both give correct answers on graphs with a single component and wrong ones on graphs with several.

That is the failure mode this collection is most concerned with and the reason the check here is against a planted truth rather than against the other algorithm alone. Two implementations of the same subtle invariant can be wrong together; an implementation and a generator that decided the answer in advance cannot.

What is not measured here #

The graphs are built rather than sampled. Every component here is a planted cycle with forward arcs added between components, which is what makes the truth known and what makes the measurement checkable. It is not what a real directed graph looks like — a web graph or a call graph has one enormous component and a long tail of singletons — and the component-size distribution decides Tarjan’s stack peak entirely.

Neither is run recursively. Both implementations here use an explicit stack, because a recursive depth-first search on a graph of a million vertices exhausts the interpreter’s own stack, which is the failure the stack nobody counts is about. A recursive Tarjan is what most textbooks give and what most implementations ship, and its frame count is a resource neither of these bars reports.

The components are all the same size. The generator makes $k$ cycles of nearly equal length, and the size distribution is exactly the thing Tarjan’s stack peak is a function of. A measurement on a realistic size distribution — one giant component and thousands of singletons, which is what a real corpus looks like in every field this site has one for — would give a different peak and the same arc counts.

And the transpose is charged as arcs read. Building it also writes every arc, and this field’s counter has no write primitive — it counts adjacency scans, visits, relaxations and queue comparisons, and none of those is an allocation. So Kosaraju’s middle pass is charged at half of what it costs, and the factor of three is a lower bound on the real difference.

Where this ladder goes next: the function the caller supplies #

Both preconditions this ladder has measured are properties of the graph: non-negative weights, acyclicity. Each is checkable, at least in principle, by looking at the input.

There is a third kind, and it is stranger. A heuristic search is given a function that estimates the remaining distance from any vertex to the goal — written by the caller, not derived from the graph — and its guarantee holds provided that function never overestimates. That is a precondition on a piece of the caller’s own code, it cannot be checked by inspecting the graph, and checking it by inspecting the function is undecidable in general.

What makes it worth a rung rather than a paragraph is that the trade is continuous. An estimate that is admissible gives the shortest path and expands fewer vertices; an estimate scaled past admissibility expands fewer still and returns a path that is longer by a bounded factor; and the bound is exactly the scaling. So the precondition is not a cliff but a dial, and the measurement that matters is how many vertices each setting expands and how much longer the path it returns is.