THE FOLD / CO-OP / SHARED MEMORY / THE GABOW
THE GABOW
one DFS with two stacks finds every cycle-cluster
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Gabow’s algorithm finds the strongly-connected components of a directed graph — the maximal clusters where every node can reach every other node — in a single depth-first pass, using two stacks instead of the low-link numbers that Tarjan tracks. One stack (S) holds the vertices of the current path; the other (P) holds candidate component roots. When a back-edge is found, P is popped down to the earliest reachable vertex, merging the cycle. When a vertex finishes as the top of P, it and everything above it on S form one component. It is arguably the most elegant of the linear-time SCC algorithms — no auxiliary numbering, just two stacks.
LIT verified live: over 1500 random digraphs, Gabow’s partition exactly matches a brute-force mutual-reachability partition (u~v iff u→v and v→u), component-for-component, and the component counts agree (window.__gabow). FIG no framing; the two-stack DFS and the brute reference both run in-browser.
LIT verified live: over 1500 random digraphs, Gabow’s partition exactly matches a brute-force mutual-reachability partition (u~v iff u→v and v→u), component-for-component, and the component counts agree (window.__gabow). FIG no framing; the two-stack DFS and the brute reference both run in-browser.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at shared-memory — a strongly-connected component is a set of nodes that all share reach: whatever one can touch, all can touch. AVAN (AI) built the instrument: the single-DFS two-stack SCC, a brute mutual-reachability reference, the set-partition comparison, and the condensation view.
Credit as content: Harold N. Gabow (2000, path-based SCC). The weave: David names shared memory; I confirm the two-stack partition matches brute mutual reachability on every random graph tested.
Credit as content: Harold N. Gabow (2000, path-based SCC). The weave: David names shared memory; I confirm the two-stack partition matches brute mutual reachability on every random graph tested.
3 ONE DIMENSION
A directed graph; nodes are colored by strongly-connected component — each color is a maximal all-reach-all cluster.
4 TWO DIMENSIONS · INTERACTIVE
Regenerate the graph or verify: Gabow’s partition is checked against brute mutual-reachability.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the condensation — collapse each component to a point.
AVAN’s addition (the inverse-companion): don’t chase every cycle — fold each cluster to a point. The inverse of ‘a tangle of directed cycles’ is ‘the condensation: one node per SCC, and it is always a DAG.’ Magenta is the cycles hidden inside each component; green is the acyclic map of components. Fold the tangle into an order.
LIT Genuine Gabow path-based SCC algorithm (Harold N. Gabow, 2000). Verified live: over 1500 random digraphs the single-DFS two-stack partition exactly matches a brute-force mutual-reachability partition (u~v iff u→v and v→u), component-for-component, and the component counts agree (window.__gabow.matches, .countMatches).
FIG No framing; the two-stack DFS and the brute reference both run in-browser. The AVAN inverse is honest — instead of chasing every cycle, collapse each cluster to a point: the condensation is one node per SCC and is always a DAG. Magenta is the cycles hidden inside each component; green is the acyclic map of components. Fold the tangle into an order.
FIG No framing; the two-stack DFS and the brute reference both run in-browser. The AVAN inverse is honest — instead of chasing every cycle, collapse each cluster to a point: the condensation is one node per SCC and is always a DAG. Magenta is the cycles hidden inside each component; green is the acyclic map of components. Fold the tangle into an order.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of SHARED MEMORY · David Lee Wise (ROOT0), with AVAN