Topological sort: putting the dependencies of a DAG in order

Getting dressed in the morning means respecting a few constraints: socks before shoes, shirt before tie, trousers before belt. Other items are independent: the watch can go on whenever you like. Finding a sequence that respects every constraint is a topological sort.

The same problem appears wherever there are dependencies: a build system must compile libraries before the programs that use them, a package manager must install dependencies before the requested package, a spreadsheet must recalculate cells in the right order, a study plan must respect course prerequisites.

The model: a directed acyclic graph

We build a directed graph with one vertex per task and an edge (A, B) when A must come before B. A topological sort is an arrangement of the vertices in a row in which every edge points from left to right.

It exists if and only if the graph has no directed cycles, that is, if it is a DAG. The reason is intuitive: if A precedes B, B precedes C and C precedes A, no sequence can satisfy everyone. A well-written topological sort algorithm therefore always does a second job too: reporting cycles when they exist.

There are usually many valid orders. In the clothing example, the watch can go anywhere. Algorithms produce one of them; if a particular order is needed (for example alphabetical among equally constrained tasks), you choose carefully which vertex to take out first.

Kahn's algorithm

It is the most intuitive method and the one worth implementing first.

1. Compute the in-degree of each vertex, that is, how many unsatisfied dependencies it has.
2. Put all vertices with in-degree zero in a queue: these are the tasks that can be done right away.
3. Take a vertex out of the queue, append it to the result and «delete» its outgoing edges, decreasing the in-degree of its neighbours by one. Every neighbour that reaches zero enters the queue.
4. Repeat until the queue is empty.

from collections import deque

def kahn(n, edges):
    adj = [[] for _ in range(n)]
    indegree = [0] * n
    for a, b in edges:
        adj[a].append(b)
        indegree[b] += 1
    queue = deque(v for v in range(n) if indegree[v] == 0)
    order = []
    while queue:
        u = queue.popleft()
        order.append(u)
        for v in adj[u]:
            indegree[v] -= 1
            if indegree[v] == 0:
                queue.append(v)
    if len(order) < n:
        raise ValueError("the graph contains a cycle")
    return order

If the result ends up with fewer vertices than the total, the remaining vertices are part of a cycle or depend on one. This is valuable diagnostic information: instead of a generic «error», you can list the set of blocked vertices.

The cost is proportional to n + m.

The DFS version

A second method uses depth-first search. Run a complete DFS and, each time a vertex is finished (all its descendants have been explored), add it to the front of a list. At the end, the list is a topological order.

It works because, in a DAG, if there is an edge (u, v) then v always finishes before u. By placing vertices at the front as they finish, u ends up ahead of v. Cycles are detected with the usual three-colour scheme: an edge towards a vertex still being visited indicates a circular dependency.

The DFS version is handy when you only want to order what a specific goal needs: launching the traversal from the requested vertex alone yields exclusively its dependencies, just as a package manager installs one program and nothing else.

Parallelism by levels

Kahn's algorithm offers a bonus. If instead of taking out one vertex at a time you take out all vertices with in-degree zero, you get levels: all tasks in a level are independent of each other and can run in parallel. This is how a build system with several processors decides which files to compile at the same time. The number of levels gives the minimum time with unlimited resources, measured in «rounds».

Critical path

If each task has a duration, you can compute the critical path on the DAG: the longest chain of dependencies in terms of time. Walk through the topological order and, for each task, compute the earliest moment it can start, that is, the maximum finish time of its predecessors.

The project takes 14 units and the critical path is Foundations → Walls → Roof → Finishing. Delaying the utilities by a few units changes nothing; delaying the walls shifts the entire delivery. This analysis, known in project management as the critical path method, is nothing more than a topological sort followed by a simple dynamic programming pass.

In short

• A topological sort lines up tasks while respecting all dependencies.
• It exists only in directed acyclic graphs; a good algorithm also reports cycles.
• Kahn's algorithm uses in-degrees and a queue, at linear cost.
• The DFS version orders vertices by decreasing finish time.
• Parallel levels and the critical path follow directly from the order.