THE FOLD / GRIND / THE CRON JOB / THE SCHEDULE
THE SCHEDULE
topological sort — order tasks by dependency
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Topological sort. You have tasks with dependencies: compile before link, wake before walk, pour the foundation before the walls. In what order can everything be done so nothing starts before its prerequisites? That order is a topological sort of the dependency graph.
Kahn’s algorithm (1962) is disarmingly simple: repeatedly take any task with no remaining prerequisites (in-degree 0), do it, and remove it — freeing whatever depended on it. Keep harvesting the free tasks until none remain. If tasks are left over but none is free, the dependencies contain a cycle — an impossible schedule, and the algorithm reports it.
LIT verified live: over thousands of random directed acyclic graphs Kahn produces an order in which every edge points forward (no task before its prerequisite), and it flags a valid order if and only if the graph is truly acyclic (window.__topo.validOrder && cycleDetection). FIG the ‘tasks’ are the picture; the forward-edge guarantee and the cycle detection are exact.
Kahn’s algorithm (1962) is disarmingly simple: repeatedly take any task with no remaining prerequisites (in-degree 0), do it, and remove it — freeing whatever depended on it. Keep harvesting the free tasks until none remain. If tasks are left over but none is free, the dependencies contain a cycle — an impossible schedule, and the algorithm reports it.
LIT verified live: over thousands of random directed acyclic graphs Kahn produces an order in which every edge points forward (no task before its prerequisite), and it flags a valid order if and only if the graph is truly acyclic (window.__topo.validOrder && cycleDetection). FIG the ‘tasks’ are the picture; the forward-edge guarantee and the cycle detection are exact.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this in THE CRON JOB, beside THE PERMUTATION CLOCK — the grind domain of jobs that must run in the right order. Topological sort is the scheduler’s backbone: build systems, package managers, spreadsheets all live on it. AVAN (AI) built the instrument: the in-degree harvest, the order, the cycle alarm.
The weave: David names the seat (the ordered job run); I make the peeling visible and the guarantee checkable — the linear schedule in 1D, the live DAG unravelling in 2D, the layered graph with its ready-frontier in 3D. The sphere is the seam. Credit: Arthur B. Kahn (1962).
The weave: David names the seat (the ordered job run); I make the peeling visible and the guarantee checkable — the linear schedule in 1D, the live DAG unravelling in 2D, the layered graph with its ready-frontier in 3D. The sphere is the seam. Credit: Arthur B. Kahn (1962).
3 ONE DIMENSION
The finished schedule: tasks laid in a line so every dependency arrow points forward. Read left to right and you can execute them in that order — nothing ever waits on something to its right.
4 TWO DIMENSIONS · INTERACTIVE
Step the harvest: each pass takes a task with no unmet prerequisites (glowing) and appends it to the schedule, freeing its dependents. Add a back-edge to create a cycle and watch the algorithm refuse — no valid order exists.
5 THREE DIMENSIONS + AVAN’S INVERSE
The dependency graph turning — tasks and the arrows between them, green, a tangle of who-needs-what.
AVAN’s addition (the inverse-companion): the magenta nodes are the ready frontier — everything currently free to run. A dependency web looks like it demands a grand plan: solve the whole tangle at once. The inverse is far simpler — never plan the whole thing, just repeatedly ask ‘what can start now?’ and take it. Peeling the free nodes unravels the knot on its own, and the only way to get stuck is a cycle — a genuine contradiction, not a hard problem. Scheduling is not planning forward; it is harvesting what is already unblocked. The green is the tangle; the magenta is the ever-moving edge of the possible.
LIT Genuine topological sort (Kahn's algorithm, 1962). Verified live: over 7,000 random graphs Kahn produces an order in which every edge points forward (no task before its prerequisite) on DAGs, and it yields a valid order if and only if the graph is acyclic (window.__topo.validOrder && cycleDetection, both true). The in-degree-0 harvest and the cycle detection (leftover nodes) are exact.
FIG The 'tasks' are the picture; the forward-edge guarantee and the exact cycle detection are real and checked. Many valid orders can exist for one graph (Kahn returns one); the guarantee is that whatever it returns is valid, and that it returns nothing exactly when a cycle makes scheduling impossible.
FIG The 'tasks' are the picture; the forward-edge guarantee and the exact cycle detection are real and checked. Many valid orders can exist for one graph (Kahn returns one); the guarantee is that whatever it returns is valid, and that it returns nothing exactly when a cycle makes scheduling impossible.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE CRON JOB · David Lee Wise (ROOT0), with AVAN