Topological sort

Some jobs must wait for others. A pizza can't go in the oven before the toppings are on, a course can't start before its prerequisites, and a program can't be built before the libraries it uses. These are directed graphs, where an edge from a to b says "a comes before b". An order of all the vertices in which every edge points forward, from earlier to later, is a topological order, and finding one is a topological sort.

It exists exactly when the graph has no directed cycle: in a, b, c, a, each of them would have to come before itself. A directed graph without cycles is a DAG, a directed acyclic graph.

Kahn's algorithm

The in-degree of a vertex, the number of edges coming in, is here the number of jobs it still waits for. A job with in-degree 0 waits for nothing and can go now. Kahn's algorithm works from that:

1. Count every vertex's in-degree, in one pass over the edges.
2. Put the vertices with in-degree 0 in a queue.
3. Take a vertex from the queue and add it to the order. Its edges are now done, so lower the in-degree of the vertex at the other end of each one by 1. A vertex whose in-degree reaches 0 has nothing left to wait for, and joins the queue.
4. When the queue is empty, the order holds every vertex, unless the graph has a cycle.

from collections import deque


def topological_order(graph):
    indegree = {v: 0 for v in graph}
    for v in graph:
        for w in graph[v]:
            indegree[w] += 1
    queue = deque([v for v in graph if indegree[v] == 0])
    order = []
    while queue:
        v = queue.popleft()
        order.append(v)
        for w in graph[v]:
            indegree[w] -= 1
            if indegree[w] == 0:
                queue.append(w)
    return order


pizza = {
    "make dough": ["roll out"],
    "make sauce": ["add toppings"],
    "grate cheese": ["add toppings"],
    "roll out": ["add toppings"],
    "add toppings": ["bake"],
    "heat oven": ["bake"],
    "bake": [],
}
print(topological_order(pizza))

['make dough', 'make sauce', 'grate cheese', 'heat oven', 'roll out', 'add toppings', 'bake']

Why it's right: a vertex joins the queue only when its in-degree reaches 0, that is, once every vertex with an edge into it is already in the order. So every edge points forward. Often many orders are right (the oven could be heated first), and Kahn's algorithm gives one of them. When a task wants one particular order, such as the smallest number first whenever there's a choice, use a heap from heapq in place of the deque.

Finding a cycle

On a cycle, each vertex waits for the one before it, so none of them ever reaches in-degree 0, and neither does anything that waits for them. The queue runs empty early, and the order comes out short:

from collections import deque


def topological_order(graph):
    indegree = {v: 0 for v in graph}
    for v in graph:
        for w in graph[v]:
            indegree[w] += 1
    queue = deque([v for v in graph if indegree[v] == 0])
    order = []
    while queue:
        v = queue.popleft()
        order.append(v)
        for w in graph[v]:
            indegree[w] -= 1
            if indegree[w] == 0:
                queue.append(w)
    return order


loop = {"a": ["b"], "b": ["c"], "c": ["a", "d"], "d": [], "e": ["d"]}
order = topological_order(loop)
print(order)
if len(order) < len(loop):
    done = set(order)
    print("stuck:", [v for v in loop if v not in done])

['e']
stuck: ['a', 'b', 'c', 'd']

a, b and c are a cycle. d isn't on it, but it waits for c, so it's stuck too. Only e gets done.

So never take a short order for a finished one: compare its length with the number of vertices. The vertices left out are the ones on a cycle or behind one. (Another classic way to find a cycle is a DFS that marks each vertex "in progress" until everything after it is done: an edge back to a vertex in progress closes a cycle. Kahn's algorithm finds it without any recursion.)

What it costs

Counting the in-degrees is one pass over the edges. After that, each vertex joins and leaves the queue once, and each edge lowers an in-degree once: O(V + E) time, and O(V + E) memory for the adjacency lists and the counts. With a heap instead of the deque, each vertex costs O(log V) more: O(V log V + E).

The tempting way is to look for a job that has nothing left to wait for, take it, and look again. Each look scans the vertices, once for every vertex taken: O(V²), billions of steps for 100,000 packages. Kahn's queue already holds the jobs that are ready, so nothing is ever searched for.