Topological Sort, in depth: batch versus online, and keeping an order valid as edges arrive with Pearce-Kelly

Way one: sort a finished graph

Two O(V + E) algorithms do the batch job. Kahn's algorithm repeatedly outputs a node with no remaining incoming edges and decrements its successors' counts; nodes left over lie on or behind a cycle. DFS postorder records each node when its descendants are finished, and the reversed finishing sequence is the order; a back edge proves a cycle. The traversal mechanics are in BFS and DFS, in depth.

from collections import deque

def kahn(nodes, edges):
    indeg = {n: 0 for n in nodes}
    succ = {n: [] for n in nodes}
    for u, v in edges:
        succ[u].append(v); indeg[v] += 1
    ready = deque(n for n in nodes if indeg[n] == 0)
    order = []
    while ready:
        n = ready.popleft(); order.append(n)
        for w in succ[n]:
            indeg[w] -= 1
            if indeg[w] == 0:
                ready.append(w)
    if len(order) != len(indeg):
        stuck = [n for n in nodes if indeg[n] > 0]
        raise ValueError(f"cycle among or behind: {stuck}")
    return order

If you use DFS, write it with an explicit stack: a recursive DFS over a dependency chain a few thousand deep overflows Python's default stack. Kahn's form suits scheduling, because the queue at any moment holds exactly the tasks that could run in parallel. DFS suits the case where you want the cycle as a path rather than as a set of stuck nodes.

Way two: keep the order while the graph grows

Now suppose edges arrive one at a time and the system must answer after every insertion. A deadlock detector records that lock M1 was held while M2 was acquired, and must say immediately if some other thread has ever done the reverse. A spreadsheet must reject a formula that would make a cell depend on itself. An incremental build daemon must add a dependency discovered at compile time without rebuilding its whole plan.

Re-running Kahn after each of m insertions costs O(m (n + m)) in total: for 20,000 locks and 200,000 recorded orderings, over 4 x 10¹⁰ edge visits, inside mutex acquisition. Yet most insertions do not disturb the order at all, and the rest usually disturb only a small window of it.

Incremental topological ordering keeps a position for every node and repairs only the part of the order that a new edge invalidates. Of the several published algorithms, the one most often found in production code is that of David J. Pearce and Paul H. J. Kelly (ACM Journal of Experimental Algorithmics, 2006), because it is simple and does little work on the insertions that occur in practice.

The invariant

Keep a map ord from each node to a distinct integer position, such that for every edge u -> v we have ord[u] < ord[v]. Reading the nodes in increasing ord gives a topological order at any moment. A new node goes at the end, with a position larger than every existing one, which cannot violate anything because it has no edges yet.

Deleting an edge never breaks the invariant: removing a constraint leaves the remaining ones satisfied. So deletions are free, and all the work is in insertions. Inserting u -> v when ord[u] < ord[v] is also free: the edge already points forward. The only interesting case is ord[u] > ord[v], where the new edge points backward in the current order.

Pearce-Kelly, step by step

Call lb = ord[v] and ub = ord[u]. Only nodes whose positions lie in the window [lb, ub] can need to move. A node before the window already precedes everything involved, and a node after it already follows everything involved. The algorithm has three steps.

1. Forward search. Starting at v, follow outgoing edges, but only into nodes with ord <= ub. Call the visited set deltaF. These are the nodes that must come after u once the edge exists. If the search reaches u itself, then v already reaches u, the new edge would close a cycle, and the insertion is rejected. The search path is the cycle, which is exactly what a deadlock report needs.
2. Backward search. Starting at u, follow incoming edges, but only into nodes with ord >= lb. Call the visited set deltaB. These nodes must come before v.
3. Reassign. Pool the positions held by deltaB and deltaF and sort them. List deltaB by current position, then deltaF by current position, and hand out the pooled positions in that order. Every node in deltaB now precedes every node in deltaF, relative order inside each set is preserved, and no node outside the two sets moves.

A worked example

Start with four nodes inserted in the order a, b, c, d, so ord = {a: 0, b: 1, c: 2, d: 3}, and the edges a -> b and c -> d. Both point forward, so both insertions are free.

Insert d -> a. Now ord[d] = 3 > ord[a] = 0, so the window is [0, 3]. The forward search from a visits b (position 1, inside the window) and stops, so deltaF is {a, b}; it never meets d, so there is no cycle. The backward search from d visits c, so deltaB is {c, d}. The pooled positions are 0, 1, 2, 3. Sorted deltaB is c, d and sorted deltaF is a, b, so c takes 0, d takes 1, a takes 2 and b takes 3. The order is now c, d, a, b, and all three edges point forward.

Insert b -> c. Now ord[b] = 3 > ord[c] = 0. The forward search from c goes to d and then to a, and from a to b, which is u. The insertion is rejected with the cycle b, c, d, a, b. Nothing was modified, because the check runs before any position changes. Had the graph held a million other nodes outside the window, neither search would have touched them.

The code

The class below is a complete, tested implementation. It stores both adjacency directions, because the backward search needs predecessors, and it reports the cycle as a path.

from collections import defaultdict

class CycleError(Exception):
    pass

class DynamicTopo:
    """Pearce-Kelly: keep a valid topological order while edges are added."""

    def __init__(self):
        self.ord = {}                      # node -> position (unique ints)
        self.out = defaultdict(set)
        self.inc = defaultdict(set)
        self.next = 0                      # monotonic, so removals leave gaps

    def add_node(self, n):
        if n not in self.ord:
            self.ord[n] = self.next        # new nodes go to the end
            self.next += 1

    def add_edge(self, u, v):
        self.add_node(u); self.add_node(v)
        if v in self.out[u]:
            return
        if u == v:
            raise CycleError([u, u])
        lb, ub = self.ord[v], self.ord[u]
        if lb > ub:                        # already consistent: ord[u] < ord[v]
            self._link(u, v)
            return
        fwd = self._search(v, self.out, lambda w: self.ord[w] <= ub, stop=u)
        bwd = self._search(u, self.inc, lambda w: self.ord[w] >= lb)
        self._reorder(bwd, fwd)
        self._link(u, v)

    def _search(self, start, adj, inside, stop=None):
        seen, stack, parent = {start}, [start], {start: None}
        while stack:
            x = stack.pop()
            for w in adj[x]:
                if w == stop:              # v reaches u: u -> v closes a cycle
                    path, y = [w], x
                    while y is not None:
                        path.append(y); y = parent[y]
                    raise CycleError([w] + path[::-1])
                if w not in seen and inside(w):
                    seen.add(w); parent[w] = x; stack.append(w)
        return seen

    def _reorder(self, bwd, fwd):
        key = self.ord.__getitem__
        nodes = sorted(bwd, key=key) + sorted(fwd, key=key)
        slots = sorted(self.ord[n] for n in nodes)
        for n, s in zip(nodes, slots):
            self.ord[n] = s

    def _link(self, u, v):
        self.out[u].add(v); self.inc[v].add(u)

    def order(self):
        return sorted(self.ord, key=self.ord.__getitem__)

The cycle check runs inside the forward search, before _reorder, so a rejected edge leaves the structure untouched. order() sorts on demand; callers that read the order often should keep a position-indexed array alongside the map.

Testing it against an oracle

A reordering that fixes the new edge but quietly breaks an old one passes every hand-written example, so test randomly. Generate random insertion sequences, including self-loops and duplicates. For each insertion, compute the truth with a plain reachability search (the edge closes a cycle exactly when u == v or v already reaches u). Then assert three things: the rejection decision matches the oracle, every accepted edge satisfies ord[u] < ord[v], and the positions are still a permutation of 0..n-1. The class above passes this check on thousands of random sequences of up to forty insertions over twelve nodes, which is small enough to hit every branch often.

What it costs

A backward insertion costs time proportional to deltaF and deltaB plus their incident edges, plus a sort of those nodes: the affected region, not the graph. The worst case is still linear per insertion: an edge from the last node to the first can drag the whole graph through the window. If adversarial insertion orders are realistic for you, the algorithms of Bender, Fineman, Gilbert and Tarjan give better amortised worst-case guarantees at the price of more complicated code.

Memory is two adjacency structures and one integer per node. Deletions cost only the adjacency update, and node removal is cheap if you tolerate gaps in the positions, since the invariant needs them distinct, not dense.

Where online ordering runs

The best-known production use is lock-order checking. Abseil's mutex deadlock detection keeps an acquires-before graph in which an edge from one mutex to another means the first was held when the second was acquired, and its internal GraphCycles class cites the Pearce-Kelly paper as its algorithm. An acquisition that would close a cycle is reported as a potential deadlock, with the cycle as evidence, long before two threads actually block each other. The general idea is covered in deadlock detection.

Pearce's work was also applied to online cycle detection in pointer analysis. Workflow orchestrators usually validate a declared DAG once, which is way one, and move toward way two when tasks can add dependencies at run time. If cycles are legitimate, order the strongly connected components instead with Tarjan's SCC algorithm.

Failure modes

• Repairing only for the new edge. Moving u just before v without carrying deltaB and deltaF breaks edges that ran through them. Always move the whole sets.
• Unbounded searches. Forgetting the position filter turns every repair into a full traversal and silently destroys the performance argument. The result is still correct, which is why only profiling finds it.
• Recursion in the hot path. A recursive search on a long chain overflows the stack inside a lock-acquisition path. Use an explicit stack, as above.
• Concurrent mutation. The structure is not thread-safe. Lock-order checkers serialise insertions behind their own internal lock; do the same, or confine the graph to one thread.
• Reporting a set instead of a cycle. Kahn's leftover nodes include nodes merely downstream of a cycle. Users need the path, so recover it from the search parents.

Choosing a way

What to do next

1. Decide which way your problem is: sort once, or maintain online. If you re-sort on every change today, measure how often and over how many nodes.
2. For batch use, write DFS with an explicit stack and make the cycle error print a path.
3. For online use, copy DynamicTopo, write the randomised oracle test before changing anything, and keep it in CI.
4. Instrument the window: log the sizes of deltaF and deltaB per insertion and alert when the average grows, which signals insertion orders that defeat locality.
5. Serialise insertions behind one lock or one owner thread.
6. If your graph legitimately contains cycles, move to strongly connected components instead of fighting the error.