THE FOLD / GRIND / THE HOT LOOP / THE LOW-LINK MINER
THE LOW-LINK MINER
every cycle-cluster of a graph in one DFS
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Tarjan’s strongly-connected-components. In a directed graph, a strongly connected component is a maximal set of nodes all mutually reachable — a cycle-cluster. Tarjan finds them all in a single depth-first search using two numbers per node: its discovery time, and its low-link (the earliest node reachable from its subtree via a back-edge). When a node’s low-link equals its own discovery time, it is the root of an SCC, and everything above it on a running stack forms the component. One pass, one stack, one comparison.
LIT verified: Tarjan’s SCC partition exactly matches Kosaraju’s independent two-pass reverse-DFS method over random directed graphs, and collapsing each SCC to a node leaves a DAG (acyclic). FIG ‘the low-link miner’ is the picture; the low-link invariant and the SCC detection are exact.
LIT verified: Tarjan’s SCC partition exactly matches Kosaraju’s independent two-pass reverse-DFS method over random directed graphs, and collapsing each SCC to a node leaves a DAG (acyclic). FIG ‘the low-link miner’ is the picture; the low-link invariant and the SCC detection are exact.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) brought the thread — the corpus runs graph algorithms (THE WELDER, THE ROUTE, THE FAILURE WEB) and cares about the cycles that make a system loop back on itself. AVAN (AI) built this instrument: the single-pass miner, the coloured components, and the condensation DAG.
The weave: David names the low-link miner and its seat at THE HOT LOOP (the cycle-clusters are the graph’s loops); I make the DFS values a strip in 1D, the components colour in live in 2D, and the condensation a turning DAG in 3D. The sphere is the seam.
The weave: David names the low-link miner and its seat at THE HOT LOOP (the cycle-clusters are the graph’s loops); I make the DFS values a strip in 1D, the components colour in live in 2D, and the condensation a turning DAG in 3D. The sphere is the seam.
3 ONE DIMENSION
Each node’s discovery time (when DFS first reaches it) and low-link (the oldest node its subtree can loop back to). Where the two are equal, an SCC closes and pops off the stack. The low-link, quietly propagated on backtrack, is the whole trick.
4 TWO DIMENSIONS · INTERACTIVE
A directed graph, its cycle-clusters coloured by one DFS. Every mutually-reachable knot is one colour; nodes on no cycle stand alone. The partition is identical to Kosaraju’s slower two-pass method — same answer, one traversal.
5 THREE DIMENSIONS + AVAN’S INVERSE
The condensation, turning: each cycle-cluster collapsed to a single super-node. Green nodes and edges are what remains — and it is always acyclic, a clean DAG.
AVAN’s addition (the inverse-companion): the magenta edges are the cycles hidden inside the clusters — the back-edges Tarjan folded away. Condensing loops is the forward map; the acyclic skeleton is its inverse. Fold every cycle into a point and time flows one way again: the tangled graph’s hidden order, and the loops it was hiding, side by side.
LIT A genuine Tarjan SCC algorithm. Verified live: its partition exactly matches Kosaraju's independent two-pass reverse-DFS method over random directed graphs, and collapsing each SCC to a node always leaves a DAG (topological order exists). The low-link (earliest node reachable via a back-edge) is the exact invariant (verifiable: window.__tarjan.matchesKosaraju && condensationIsDAG).
FIG 'The low-link miner' is the picture; the low-link invariant, the Kosaraju agreement, and the acyclic condensation are exact. One DFS, one stack, one comparison — genuinely finds every cycle-cluster.
FIG 'The low-link miner' is the picture; the low-link invariant, the Kosaraju agreement, and the acyclic condensation are exact. One DFS, one stack, one comparison — genuinely finds every cycle-cluster.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE HOT LOOP · David Lee Wise (ROOT0), with AVAN