Topological Sorting

Before you can compute a spreadsheet cell, every cell it references must already be computed. Before you can build a piece of software, every module it imports must already be compiled. Before you can price a derivative that's built on top of another model's output, that other model has to run first. All three are the same problem: you have a set of tasks, some tasks depend on others, and you need one valid order to do them in. Topological sorting is the algorithm that produces that order.

The idea: peel off nodes with nothing left pointing at them

Picture the tasks as a directed graph: an arrow from A to B means "A must happen before B." A valid order is any sequence where every arrow points forward. The graph only has such an order if it has no cycles — a cycle would mean some task depends on itself, directly or indirectly, which is impossible to satisfy.

The cleanest way to build the order is Kahn's algorithm:

1. Compute each node's in-degree — how many arrows point into it (how many prerequisites it has).
2. Put every node with in-degree 0 (no prerequisites) into a queue.
3. Repeatedly pop a node from the queue, add it to the output, and decrement the in-degree of everything it points to. Any neighbor that drops to in-degree 0 joins the queue.
4. If the output ends up shorter than the total node count, a cycle exists and no valid order is possible.

Each node and each edge is touched once, so this is $O(V + E)$ — linear in the size of the graph.

Worked example 1: build dependencies

Modules with dependency arrows: utils → parser, utils → executor, parser → compiler, executor → compiler. In-degrees: utils=0, parser=1, executor=1, compiler=2.

• Queue starts with [utils] (only node at in-degree 0).
• Pop utils, output [utils]. Decrement parser to 0 and executor to 0 — both join the queue: [parser, executor].
• Pop parser, output [utils, parser]. Decrement compiler to 1 — not yet 0, stays out.
• Pop executor, output [utils, parser, executor]. Decrement compiler to 0 — joins the queue.
• Pop compiler, output [utils, parser, executor, compiler]. Queue empty, all 4 nodes placed — valid order.

Worked example 2: catching a cycle

Add one more arrow to the same graph: compiler → utils. Now utils has in-degree 1, not 0, so the initial queue is empty — nothing has zero prerequisites, because everything (indirectly) depends on everything else. Kahn's algorithm outputs 0 nodes, which is less than the 4 nodes in the graph, so it correctly reports a cycle instead of silently producing a wrong order.

from collections import deque

def topo_sort(num_nodes, edges):          # O(V + E)
    indeg = [0] * num_nodes
    adj = [[] for _ in range(num_nodes)]
    for u, v in edges:                     # u must come before v
        adj[u].append(v)
        indeg[v] += 1

    q = deque(n for n in range(num_nodes) if indeg[n] == 0)
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)

    if len(order) != num_nodes:
        raise ValueError("cycle detected — no valid order")
    return order

Where it shows up

In interviews: course schedule, alien dictionary, build order, and any "can these tasks be completed given these dependencies" problem is topological sort with dressing. Interviewers often also want depth-first-search-based topological sort (post-order DFS reversed), which is worth knowing as an alternative to Kahn's queue-based version.

In quant systems, this is how a research pipeline or spreadsheet-style calculation engine decides execution order for interdependent factors and models — signal B that consumes signal A's output must run after A, and a dependency-graph scheduler computes that order automatically instead of hardcoding it. It is also exactly the check a build system or CI pipeline runs to detect a circular import before wasting a compile.