Putting dependencies in order

Courses with prerequisites. Build steps. Tasks where some must finish before others start. The question is always the same: in what order can these be done.

The requirement

The dependencies must form a directed acyclic graph. Directed, because "A before B" is not symmetric. Acyclic, because if A needs B and B needs A there is no order and the correct answer is to say so.

A topological order is any sequence where every edge points forwards.

Kahn's algorithm

Count how many things each task waits for. Start with those waiting for nothing.

from collections import deque

def topological_sort(graph, n):
    indegree = [0] * n
    for node in graph:
        for nxt in graph[node]:
            indegree[nxt] += 1

    queue = deque([i for i in range(n) if indegree[i] == 0])
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for nxt in graph[node]:
            indegree[nxt] -= 1        # one prerequisite satisfied
            if indegree[nxt] == 0:
                queue.append(nxt)

    return order if len(order) == n else None   # None means a cycle

O(V + E), and the cycle detection is free: if the loop ends with tasks unplaced, those tasks are waiting on each other.

That last line is the part worth keeping. Returning a partial order silently would be worse than an error, and here the check costs one comparison.

The DFS version

Run depth first search and prepend each node as it finishes. A node finishes only after everything it depends on, so prepending puts it before them. It needs a separate check for a back edge to detect cycles, which makes Kahn's version the easier one to get right.

Where it turns up

The circular import error from a build tool and the circular reference warning in a spreadsheet are both this algorithm reporting a cycle.

Not unique

Several valid orders usually exist, and which one you get depends on the order the queue happens to hold. If a deterministic result is needed, use a priority queue instead and you get the lexicographically smallest, which is a common follow up.