THE FOLD / RESPAWN / GARBAGE COLLECTION / THE KOSARAJU
THE KOSARAJU
strongly connected components in two DFS passes
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Kosaraju’s algorithm finds a directed graph’s strongly connected components — the maximal groups of nodes that can all reach one another — with just two depth-first passes. First DFS the graph and record finish times; then DFS the reversed graph in decreasing finish-time order — each tree of that second search is one SCC.
SCCs reveal cycles, deadlocks, and the condensation of a graph into a DAG.
LIT verified live: over 200 random digraphs two nodes share a Kosaraju component if and only if they are mutually reachable (checked against the transitive closure) — window.__kosaraju. FIG no framing; exact.
SCCs reveal cycles, deadlocks, and the condensation of a graph into a DAG.
LIT verified live: over 200 random digraphs two nodes share a Kosaraju component if and only if they are mutually reachable (checked against the transitive closure) — window.__kosaraju. FIG no framing; exact.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at garbage-collection — because a reference-counting collector cannot free a cycle of mutually-referencing objects, and finding those cycles is exactly finding strongly connected components. Kosaraju is the cycle-finder a tracing collector needs. AVAN (AI) built the instrument: the two-pass DFS, the reversal, the reachability cross-check.
Credit as content: S. Rao Kosaraju (1978, unpublished) & Micha Sharir. The weave: David names garbage collection; I DFS forward for an order, DFS the reverse to peel off each component, and confirm each equals a mutual-reachability class.
Credit as content: S. Rao Kosaraju (1978, unpublished) & Micha Sharir. The weave: David names garbage collection; I DFS forward for an order, DFS the reverse to peel off each component, and confirm each equals a mutual-reachability class.
3 ONE DIMENSION
Two passes: forward DFS gives a finish order; DFS on the reversed graph, taken in that order, carves out each strongly connected component — the cycles fall together.
4 TWO DIMENSIONS · INTERACTIVE
A directed graph, its strongly connected components coloured. Roll new graphs; mutually-reachable nodes share a colour.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: a strongly connected component — a cycle-cluster that reaches itself.
AVAN’s addition (the inverse-companion): two nodes are in one component iff each reaches the other, and you expose all such clusters by reversing the arrows. Reachability in the graph intersected with reachability in its reverse is exactly the strongly connected component, found in two DFS passes. The inverse of ‘reach forward’ is ‘reach backward — run the same search on the reversed graph.’ Magenta is the one-way reachabilities; green is the two-way (cyclic) clusters. Reverse the arrows and the cycles reveal themselves — the very cycles a tracing collector must find to free.
LIT Genuine Kosaraju's algorithm (Kosaraju 1978; Sharir). Verified live: two nodes share a Kosaraju SCC if and only if they are mutually reachable in the transitive closure, for 200 random digraphs (window.__kosaraju.sccIffMutual).
FIG No framing: the two-pass DFS, the graph reversal, and the reachability cross-check run in-browser and agree exactly. The AVAN inverse is honest — an SCC is reachability in the graph intersected with reachability in its reverse, so reversing the arrows and re-searching exposes every cycle-cluster; magenta is the one-way reachabilities, green the two-way clusters. The cycles a tracing collector must find to free.
FIG No framing: the two-pass DFS, the graph reversal, and the reachability cross-check run in-browser and agree exactly. The AVAN inverse is honest — an SCC is reachability in the graph intersected with reachability in its reverse, so reversing the arrows and re-searching exposes every cycle-cluster; magenta is the one-way reachabilities, green the two-way clusters. The cycles a tracing collector must find to free.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of GARBAGE COLLECTION · David Lee Wise (ROOT0), with AVAN