Topological sort

A course has prerequisites, a build has steps that need other steps, a timetable has trains that must wait for connections. Each rule says “this before that”. Is there an order of everything that keeps every rule, and how do you find one? This lesson answers both, with two different methods.

An order that keeps every rule

Draw each rule “u before v” as an edge u → v. A topological order is a list of all the vertices in which every edge points forward: for each edge u → v, u comes earlier than v. It is usually not unique. With rules A → C and B → C, both A, B, C and B, A, C are topological orders.

DYNP-3 met this idea already: a DP table must be filled in an order where every cell comes after the cells it reads, and that order is a topological order of the graph of “reads from” edges.

When an order exists

A directed graph with no cycle is called a DAG (directed acyclic graph).

A cycle makes it impossible. Going round a cycle, each vertex must come before the next, so the first vertex of the cycle must come before itself.

With no cycle, an order exists. First, a DAG always has a vertex with no edges coming in. Start at any vertex and walk backwards along an incoming edge, again and again. Without a cycle you can never meet a vertex twice, so after at most V steps the walk stops, at a vertex with in-degree 0. Put that vertex first: it breaks no rule. Remove it with its edges; what is left is still a DAG, so repeat. Every vertex gets placed, and every edge points forward.

Kahn’s method

The proof is already an algorithm. Kahn’s method (1962) keeps each vertex’s in-degree (lesson 1): the number of edges still coming in. Vertices at 0 are ready. Take any ready vertex, put it next in the order, and remove its outgoing edges by lowering its neighbours’ counts. A neighbour whose count reaches 0 becomes ready.

from collections import deque

def topo_order(n, edges):
    adj = [[] for _ in range(n)]
    indeg = [0] * n
    for u, v in edges:
        adj[u].append(v)
        indeg[v] += 1
    ready = deque(v for v in range(n) if indeg[v] == 0)
    order = []
    while ready:
        u = ready.popleft()
        order.append(u)
        for v in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                ready.append(v)
    return order if len(order) == n else None   # None: a cycle

Each vertex is placed once and each edge lowers one count once: O(V + E). If the graph has a cycle, the vertices on it never reach 0, so the method stops early with fewer than n vertices placed. The same loop therefore orders a DAG and detects a cycle.

You may take any ready vertex. Taking them in queue order gives one valid order. Taking the smallest ready vertex each time gives the smallest order (compared as Python compares lists); that needs a heap of ready vertices (HEAP), so it costs O((V + E) log V), where log V is the number of times V can be halved. P5 asks for it.

Finish order, reversed

The second method uses depth-first search and lesson 3’s finish times.

When the search looks along u → v, u is on the path. If v is not reached yet, it is searched below u and finishes first. If v is already finished, it finished first. And v cannot be on the path, because then u → v would be a back edge, which means a cycle (lesson 4). So listing the vertices in reverse finish order puts every u before its v. In code: run DFS from every vertex, append each vertex to a list when it finishes, then reverse the list (P3 builds the finish order). Like Kahn’s method this is O(V + E), and the back edge test finds a cycle along the way.

The two methods usually give different orders, and both are right. Kahn’s method is easy to control (smallest first, or in rounds of tasks that can run at the same time); the DFS method needs no in-degree counts and costs nothing extra when a DFS is running anyway.

graphlib, and what orders are for

Python’s standard library has a topological sort in graphlib. Its input is a dict that maps each vertex to the vertices that must come before it, the reverse of our edges:

from graphlib import TopologicalSorter, CycleError

needs = {"deploy": {"test", "docs"}, "test": {"build"},
         "docs": {"build"}, "build": set()}
print(list(TopologicalSorter(needs).static_order()))
# ['build', 'test', 'docs', 'deploy'] (test and docs may swap)

try:
    list(TopologicalSorter({"a": {"b"}, "b": {"a"}}).static_order())
except CycleError as e:
    print(e.args[1])            # ['a', 'b', 'a']: the cycle

For running tasks in parallel, prepare(), get_ready() and done() hand out every task whose prerequisites are finished, in rounds. The order of tasks inside a set is not fixed, because sets of strings have no fixed order.

• Work along a DAG in order. Once vertices are in topological order, anything that depends only on earlier vertices can be computed in one pass. For the longest chain of tasks, go through the order and set best[v] = max(best[v], best[u] + 1) for each edge u → v. With task lengths this is the critical path: the shortest time the whole project can take. ADDP-2 does DP on DAGs in general, and PATH-6 finds shortest paths this way.
• Counting orders is hard. Finding one order takes O(V + E), but counting all of them has no known fast method for general graphs.

Now try GRPH-P5, The smallest order.