An order of tasks that respects every dependency — if one exists at all. A directed acyclic graph is flattened into a line where every edge points forward. Kahn's engine peels off vertices with nothing left to wait on, and refuses to invent an order when a cycle makes one impossible. Rendered, not quoted.
SOURCE A. B. Kahn, "Topological sorting of large networks," Communications of the ACM 5(11):558–562, 1962. doi:10.1145/368996.369025
Tasks are vertices; a directed edge u → v reads “u must come before v.” A vertex's in-degree is its count of unmet prerequisites.
A topological order is a linear arrangement in which every edge points forward. Kahn's claim: repeatedly remove any vertex of in-degree 0, decrement its successors, repeat. What is emitted is a valid order — and it exists iff the graph is a DAG.
Constructed input: 7 tasks A–G, 8 edges. A frontier of in-degree-0 vertices; ties broken by lowest index for a deterministic run.
Scheduling under dependencies — Kahn 1962. The order a DAG admits is the backbone of build systems (make), spreadsheet recalculation, package managers, and course prerequisites: each says “do the things you depend on first.”
Neighbour in the corpus: the-shortest-path (Dijkstra 1959). Both walk a graph by a frontier and a relaxation step; there, edge weights accumulate a distance — here, an in-degree counts down to release. Same graph, different invariant.
Live re-check of the order now on the panel: for every edge u→v, is pos(u) < pos(v)? Green only when all 8 edges point forward. Trip the Tamper (window 6) and this flips red the instant an edge points backward.
Directed acyclic graph, 7 tasks · 8 dependencies:
Initial in-degrees (unmet prerequisites):
Removal order — each chip left with in-degree 0 at that step:
Cycle probe — input X→Y→Z→X:
Proven result: the emitted order respects all 8 edges, and it is one of the graph's valid linear extensions — checked against a brute-force enumeration of every valid order (exact, no float). A cyclic graph yields zero orders and is detected.
“Give me an order” is the attack. If the graph has a cycle, no linear order exists — any code that returns one is lying. The honest engine must stall: vertices remain with non-zero in-degree and none is emittable.
Second cut: emit a vertex while a prerequisite is still pending and some downstream edge now points backward. The output still “looks like” an order but silently breaks a dependency — exactly the planted void in window 6.
Disclosed planted void: emit vertices ignoring the in-degree count (largest index first), so a prerequisite is released too early and an edge points backward. The engine still emits all 7 — it just emits a wrong order. The Witness (7) catches it live.