Socks go on before shoes, and code compiles before its tests run. A topological sort lines up the nodes of a directed graph so every arrow points forward in the list. One exists exactly when the graph has no directed cycle, which makes it a DAG, and most DAGs allow many valid orders.
Each badge counts a node's incoming arrows, its in-degree. A node with in-degree 0 waits on nothing, so it can go next. Kahn's algorithm keeps a queue of those ready nodes. Each time it takes one out, it erases that node's outgoing arrows, and any neighbor whose count drops to 0 joins the queue. The vocabulary of nodes, directed edges and degree comes from 002 · Graphs.
How to read this: An arrow A → B means A must come before B. The number on each box counts arrows still pointing into it; at 0 it's ready.
Try this: Switch Take from to Back (stack) and compare the Output order.
A node enters the output only after every arrow into it has been erased, and an arrow is erased only when its tail is output. So every tail lands before its head.
Each node is queued and taken once, and each arrow is erased once, so the total work is V + E. The work counter ends at exactly that number.
Depth-first search starts from a node, follows an arrow as far as it can go, and only finishes a node once everything below it has finished. Nodes start white, turn gray while their call is on the stack, and turn black when the call returns. Read the finish order backwards and you have a topological order.
How to read this: When a node finishes it gets a number: its place in the final order. The Order row fills from the right, because the last to finish goes first. The code calls the three node states white, gray and black.
Try this: Switch Start searches to Reversed; the order changes but stays valid.
For any arrow u → v, the search finishes v before u: either the call on u visits v and waits for it, or v already finished. A gray v would mean v can reach u, which is a cycle.
Edit the graph. Click one node, then another, to add or remove the arrow between them. Add an arrow that closes a loop and no order can exist: Kahn's queue runs dry with nodes left over, and depth-first search walks into a gray node. While the graph stays acyclic, the page counts every valid order and lets you step through them.
Try this: Click deploy, then fetch, to add a backwards arrow and watch the cycle light up red.
def count(placed): # nodes already listed if placed == V: return 1 if placed in memo: return memo[placed] total = 0 for v not in placed: if preds(v) ⊆ placed: # v may go next total += count(placed ∪ {v}) memo[placed] = total return total
Backtracking tries every node that is free to go next. Many branches reach the same set of placed nodes, so the memo stores each set's count once, at most 2ⁿ of them. The same table picks out the k-th order directly, which is how Prev and Next jump around.
Counting the orders of a general DAG is #P-complete, so this table only scales to small graphs. Every preset here has at most 9 nodes.
On a cycle, every node waits on the one before it. None of them ever reaches in-degree 0, so Kahn's queue empties early. Nodes downstream of the loop are stuck too.
Depth-first search meets the same loop as an arrow into a gray node, one whose call is still open. Following the stack from that node back to the current one traces the cycle drawn in red.
The count drops to exactly 1 when each neighbor pair in the order is joined by an arrow. Then the arrows themselves spell out the order.