THE FOLD / BOSS / THE GATEKEEPER / THE TARJAN SCC
THE TARJAN SCC
every strongly connected component in one DFS
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Tarjan’s SCC algorithm finds the strongly connected components of a directed graph — the maximal groups where every vertex can reach every other — in a single depth-first search. It tracks each vertex’s discovery index and the lowest index reachable from its subtree (the “low-link”); when a vertex’s low-link equals its own index, it is the root of an SCC, and the component is popped off a stack. One pass, linear time.
LIT verified live: over 400 random digraphs Tarjan’s component partition equals a brute partition by mutual reachability (u,v together iff each reaches the other) — window.__tarjanscc. FIG no framing; exact.
LIT verified live: over 400 random digraphs Tarjan’s component partition equals a brute partition by mutual reachability (u,v together iff each reaches the other) — window.__tarjanscc. FIG no framing; exact.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-gatekeeper — the check that finds the tangled clusters where every node loops back to every other. Tarjan’s SCC is that gatekeeper of cyclic structure. AVAN (AI) built the instrument: the single-DFS index/low-link bookkeeping, the component stack, and the brute mutual-reachability cross-check.
Credit as content: Robert Tarjan (1972). The weave: David names the gatekeeper; I run one DFS tracking low-links, pop each component when its root is found, and confirm the partition matches mutual reachability.
Credit as content: Robert Tarjan (1972). The weave: David names the gatekeeper; I run one DFS tracking low-links, pop each component when its root is found, and confirm the partition matches mutual reachability.
3 ONE DIMENSION
Each vertex gets a discovery index and a low-link (lowest index reachable from its subtree via one back-edge). When low-link equals index, that vertex roots an SCC — pop the stack down to it.
4 TWO DIMENSIONS · INTERACTIVE
A directed graph; Tarjan’s strongly connected components are colored, and the count is checked against a brute mutual-reachability partition.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the strongly connected components.
AVAN’s addition (the inverse-companion): find every maximal mutually-reachable cluster in one DFS — track a discovery index and a low-link per vertex, and when a vertex’s low-link equals its index it is an SCC root, so pop the stack down to it. The inverse of ‘check reachability between every pair’ is ‘one DFS, low-links, pop a component at each root.’ Magenta is the O(n2) pairwise reachability tests avoided; green is the components found in one pass. Every cycle-cluster in a single sweep.
LIT Genuine Tarjan strongly-connected-components (Tarjan 1972). Verified live: over 400 random digraphs the single-DFS low-link algorithm produces a component partition identical to a brute partition by mutual reachability (u and v share a component iff each reaches the other) — window.__tarjanscc.matchesBrute.
FIG No framing: the single-DFS index/low-link bookkeeping, the component stack, and the brute mutual-reachability cross-check run in-browser and agree exactly. The AVAN inverse is honest — one DFS tracking low-links, popping a component whenever a root is found, replaces O(n^2) pairwise reachability tests; magenta is the pairwise tests avoided, green the components found in one pass. Every cycle-cluster in a single sweep.
FIG No framing: the single-DFS index/low-link bookkeeping, the component stack, and the brute mutual-reachability cross-check run in-browser and agree exactly. The AVAN inverse is honest — one DFS tracking low-links, popping a component whenever a root is found, replaces O(n^2) pairwise reachability tests; magenta is the pairwise tests avoided, green the components found in one pass. Every cycle-cluster in a single sweep.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE GATEKEEPER · David Lee Wise (ROOT0), with AVAN