🔀 Topological Sort — Ordering a DAG

Every node is given a fixed index from 0 to N−1, and candidate edges are only ever added from a lower index to a higher index (i to j only when i < j). Because an edge can never point backward under this indexing, following any chain of edges always increases the index, so it is impossible to loop back to a node you started from — the graph is acyclic by construction, before Kahn's algorithm even runs.

The "in:" badge shows a node's current indegree, the number of edges still pointing into it. A green ring means indegree zero — the node has no unmet dependencies and sits in the queue ready to be placed. Solid purple marks the node just removed on this step, faded purple marks nodes placed on earlier steps, and plain grey nodes still have at least one unmet dependency.

Add edge inserts one new random edge and restarts the algorithm from scratch. About 60% of the time it chooses a forward edge (lower index to higher index), which keeps the graph a valid DAG. The rest of the time, or whenever no forward edge is left to add, it chooses a backward edge instead, which creates a cycle so you can watch the simulation's cycle detection react to it.

It runs Kahn's algorithm to completion, dequeuing and placing nodes until the queue empties. If every node has been placed, the sort succeeded. If the queue empties early while nodes remain unplaced, those nodes must lie on a cycle, since a cycle's indegree can never fall to zero, and the simulation lists them under "Cycle among" with a red banner drawn on the canvas.

Step performs exactly one iteration of Kahn's algorithm: dequeue one indegree-zero node, append it to the order, and decrement the indegree of its successors. Play repeats that same step automatically, advancing roughly every 28 animation frames divided by the Speed slider value, until the queue is empty. Regenerate discards the current graph and draws a brand-new random DAG at the current Nodes N setting, resetting the algorithm state.