· Development

Topological Sort and Cycle Detection: Ordering by In-Degree and Finding What Got Stuck

Implement topological sort by counting in-degrees, see what is left over when the graph has a cycle, and learn how Python's graphlib TopologicalSorter and CycleError behave.

algorithmsgraphtopological-sortpython

Build steps, package installs, and database migrations all come with constraints of the form “A has to finish before B can start.” Once several of these overlap, you need one execution order that respects all of them. Finding that order is topological sorting. If the constraints loop back on themselves, no such order exists, so in practice topological sorting and cycle detection belong together.

This post implements topological sort by counting in-degrees, looks at where the algorithm stops when there is a cycle, and then covers how Python’s standard graphlib.TopologicalSorter exposes the same problem. Python behavior is based on the official documentation for 3.13, 3.14, and 3.15.

What a topological order is

In a directed graph, a topological order is a linear ordering of the vertices such that for every edge u → v, u comes before v. A complete topological order exists only when the graph has no directed cycle, that is, when it is a DAG (directed acyclic graph).

Two points are worth fixing up front:

  • The answer is not necessarily unique. Two tasks that do not depend on each other can appear in either order.
  • Decide what an edge means before writing any code. In this post, u → v means “u must come before v.”

Implementing it with in-degrees

A vertex with in-degree 0 has nothing left to wait for, so it can be emitted right away. When you emit a vertex and remove its outgoing edges, some other vertices may drop to in-degree 0. Repeat until there is nothing left to emit.

from collections import deque

def topo_sort(nodes, edges):
    # (u, v) in edges means "u before v"
    indegree = {n: 0 for n in nodes}
    succ = {n: [] for n in nodes}
    for u, v in edges:
        succ[u].append(v)
        indegree[v] += 1

    queue = deque(n for n in nodes if indegree[n] == 0)
    order = []
    while queue:
        u = queue.popleft()
        order.append(u)
        for v in succ[u]:
            indegree[v] -= 1
            if indegree[v] == 0:
                queue.append(v)
    return order  # if len(order) < len(nodes), there is a cycle

Each vertex enters the queue at most once, and each edge decrements an in-degree exactly once, so the running time is O(V + E). The extra space for the in-degree table and adjacency lists is also O(V + E).

Where it stops when there is a cycle

Vertices on a cycle wait on each other, so none of them can reach in-degree 0. The queue empties early, and order ends up shorter than the number of vertices. The code above can use that difference to detect a cycle. Conversely, if there is no cycle, at least one remaining vertex always has in-degree 0, so every vertex gets emitted.

Not every leftover vertex is on a cycle, though. If a and b wait on each other and there is an edge b → c, then c is also left over, but c is not part of the cycle; it is just blocked behind it. If you want to tell users “these nodes form a cycle,” you need a separate step that finds an actual cycle among the leftovers.

That step is short. Every leftover vertex has at least one leftover predecessor, because its in-degree is still above 0. So if you start from any leftover vertex and keep walking to a leftover predecessor, you must eventually revisit a vertex, since there are only finitely many. The stretch between the two visits is a cycle.

def find_cycle(nodes, edges, order):
    done = set(order)
    preds = {n: [] for n in nodes}
    for u, v in edges:
        if u not in done and v not in done:
            preds[v].append(u)

    n = next(x for x in nodes if x not in done)
    seen = {}
    path = []
    while n not in seen:
        seen[n] = len(path)
        path.append(n)
        n = preds[n][0]
    # path was built walking backwards along predecessors, so reverse it
    return (path[seen[n]:] + [n])[::-1]

The result is a list whose first and last elements are the same, and where each element is an immediate predecessor of the next. That matches the convention graphlib uses when it reports a cycle, covered below.

Python’s graphlib.TopologicalSorter

Since Python 3.9, the standard library has a graphlib module with a TopologicalSorter class for topological sorting. Nodes must be hashable.

The first thing that trips people up is the direction of the input. In the dictionary you pass to the constructor, each key is a node and each value is that node’s predecessors. This is the opposite of the common “node → successors” adjacency list, and passing one in unchanged gives you a reversed order.

from graphlib import TopologicalSorter

# key: a task, value: tasks that must finish before it
deps = {
    "test": {"build"},
    "build": {"codegen", "fetch"},
    "codegen": {"fetch"},
}
print(list(TopologicalSorter(deps).static_order()))
# ['fetch', 'codegen', 'build', 'test']

This graph has only one valid topological order, so the output is fixed. That changes once some nodes are independent. The official documentation states that the order returned may depend on the order in which items were inserted into the graph, and shows an example where only the order of add() calls differs and the result changes. In tests, check “for every edge u → v, u comes first” rather than comparing against one specific order.

The API for parallel work

static_order() gives you the order in one call. For running tasks in parallel, you use prepare(), get_ready(), and done() directly.

ts = TopologicalSorter(deps)
ts.prepare()
while ts.is_active():
    for task in ts.get_ready():
        run(task)      # in real code, put it on a work queue
        ts.done(task)  # successors are only released after done()

get_ready() returns a tuple of every node that is ready right now. At first that is all nodes with no predecessors; after that, it returns nodes whose predecessors have all been marked with done(). Nodes returned by the same call do not wait on each other, so they can run concurrently. The example in the official documentation puts the results of get_ready() on a task queue and calls done() when a worker reports a node as finished. The code above calls done() in place only to keep the flow visible.

is_active() returns True if more progress can be made. As the documentation defines it, that means cycles do not block the resolution, and either there are ready nodes not yet returned by get_ready(), or fewer nodes have been marked done() than have been returned by get_ready().

CycleError

If the graph contains a cycle, prepare() raises graphlib.CycleError, a subclass of ValueError. The same happens when you iterate with static_order().

from graphlib import TopologicalSorter, CycleError

deps = {"a": {"b"}, "b": {"c"}, "c": {"a"}}
try:
    list(TopologicalSorter(deps).static_order())
except CycleError as e:
    print(e.args[1])

The cycle is stored as a list of nodes in the second element of the exception’s args. Each node in the list is an immediate predecessor of the next one, and the first and last nodes are the same so that it is clearly a cycle. If there are several cycles, only one is reported, and which one is undefined. Even in the example above, the documentation does not guarantee which node the list starts from, so do not hard-code the output in a test.

After prepare() raises CycleError, you can still call get_ready() and get as many nodes as possible until the cycle blocks further progress. Nodes that are blocked behind a cycle, as described earlier, will never come out this way either.

Version differences

  • graphlib was added in Python 3.9.
  • After prepare(), the graph can no longer be modified, and calling add() raises ValueError.
  • Starting with Python 3.14, prepare() can be called more than once as long as sorting has not started. In earlier versions, the second call raised ValueError. Calling prepare() after sorting has started via static_order() or get_ready() still raises ValueError in 3.14 and later.

Things to check when you implement this

  • Edge direction: in the hand-written version, an edge means “u before v”; in graphlib, a key’s value holds its predecessors. Mixing the two gives you a reversed result.
  • Cycle detection: if fewer vertices are emitted than exist, there is a cycle. Reporting the full leftover list as “the cycle” also includes vertices that are merely blocked behind it.
  • Output order: the order between independent nodes can depend on input order, so tests should check that the constraints hold rather than compare one specific order.

Back to the blog