TOPOLOGICAL SORT order the dependencies — everything after what it needs
A topological sort lines up the nodes of a directed acyclic graph so that every edge points forward — each task after all its prerequisites. Kahn’s algorithm builds it by repeatedly removing a node with in-degree zero (no unmet dependencies), which frees others to follow. It exists if and only if the graph is acyclic — a cycle is a circular dependency with no valid order, so a failed topological sort is itself a cycle detector. It is how build systems, package managers, spreadsheets, and course prerequisites decide what to do first. In the DAG 0→1, 0→2, 1→3, 2→3, node 0 has in-degree 0 (a valid source) and node 3 has in-degree 2 (comes last).
THE TECHNIQUE repeatedly remove an in-degree-0 node — a linear order iff acyclic
The demo checks the DAG 0→1,0→2,1→3,2→3: node 0 has in-degree 0 (a source), node 3 has in-degree 2 (last): live demo
HISTORY & CREDIT Kahn · 1962
“Dependencies sort themselves.” — only if acyclic; a cycle is a circular dependency with no valid order, and topo-sort detects it. cited
the rule · remove a node with in-degree 0, repeat — each freed node has its prerequisites met. the condition · a full ordering exists iff the graph is acyclic — a cycle leaves nodes stuck. 1962 · Kahn — build systems, package managers, spreadsheets, course plans.
Tasks lined up so each follows its prerequisites — a forward order, possible exactly when there is no cycle. DAG order
RECOMMEND FOR I-13 the in-degrees, on the compiler
On the canonical compiler, in the DAG node 0 has in-degree 0 (a valid first) and node 3 has in-degree 2 (last):
$ i13 run nw_topologicalsort.i13 # in-degrees of the DAG
RUN OK · 299 step(s) · peak stack 16 · call depth 5
in0 = 0 -- a source (no prerequisites)
in3 = 2 -- last (two prerequisites)
zero_indegree_source = 1
Recommend as a NULL — an ordering, existence tied to acyclicity. Topological sort computes a valid dependency order (a resource/algorithmic result, B40); its existence is a theorem (iff the DAG is acyclic, B39), and choosing among valid orders is a tie-breaking freedom (B44, cf. dart 511’s stability). No new invariant. NULL — the order that respects every dependency.