Detecting Cycles and Loops in a Dependency Graph

#ai #machinelearning #tutorial #llm

A cycle in a build graph, an import graph or a task DAG turns a topological sort into an error message that usually does not say which edges are at fault. Getting the path out is not much harder than getting the boolean, and it is the only version anyone can act on.

The version that looks right and is not

The first attempt almost everyone writes keeps a single visited set and reports a cycle when it reaches a node already in it:

# WRONG
def has_cycle(graph):
    visited = set()
    def dfs(node):
        if node in visited:
            return True          # <-- this is the bug
        visited.add(node)
        return any(dfs(n) for n in graph.get(node, ()))
    return any(dfs(n) for n in graph)

Consider a -> b, a -> c, b -> d, c -> d. That is a diamond, and a diamond is perfectly acyclic — every dependency resolver in the world handles it. The code above visits d through b, then reaches d again through c, finds it in visited, and reports a cycle that does not exist.

The mistake is conflating two different questions. Have I ever seen this node is reachability. Is this node on the path I am currently standing on is a cycle. Only the second one implies a back edge, and you need both facts: the first to avoid re-exploring a diamond’s shared tail exponentially, the second to detect the cycle.

Three colours, one rule

Give every node one of three states, the classical formulation from the depth-first search literature:

WHITE — not yet visited.
GREY — visit started, not finished. The grey nodes are exactly the current recursion stack, in order.
BLACK — visit finished, along with everything reachable from it.

The rule is one line: an edge to a GREY node is a cycle. An edge to a BLACK node is a shortcut into an already-cleared region and is fine. The diamond above hits d GREY-then-BLACK on the first path and BLACK on the second, and reports nothing. Because the grey set is the stack in order, the cycle path is a slice of it, which is what makes the error message useful.

Build the detector

Work on this graph, which is a plausible module dependency set with one genuine cycle and one diamond:

Write the graph down as an adjacency mapping. Keys are nodes, values are lists of nodes the key depends on. Sort the values — a detector whose output depends on dict ordering reports a different cycle on every run, which makes it useless in CI.
```
graph = {
    "app":     ["auth", "billing"],
    "auth":    ["db", "config"],
    "billing": ["db", "invoice"],
    "invoice": ["billing"],          # <-- cycle: billing -> invoice -> billing
    "db":      ["config"],
    "config":  [],
}
```

Walk it iteratively with an explicit stack. Each stack frame holds a node and an iterator over its remaining neighbours, so popping a frame is exactly the moment the node turns BLACK.

WHITE, GREY, BLACK = 0, 1, 2

def find_cycle(graph):
    """Return one cycle as a list of nodes, or None if the graph is acyclic."""
    colour = {n: WHITE for n in graph}
    for n in graph:
        for m in graph[n]:
            colour.setdefault(m, WHITE)   # nodes that only appear as targets

    for root in sorted(colour):
        if colour[root] != WHITE:
            continue
        colour[root] = GREY
        path = [root]
        stack = [(root, iter(sorted(graph.get(root, ()))))]

        while stack:
            node, it = stack[-1]
            nxt = next(it, None)
            if nxt is None:
                colour[node] = BLACK
                stack.pop()
                path.pop()
                continue
            if colour[nxt] == GREY:
                return path[path.index(nxt):] + [nxt]
            if colour[nxt] == WHITE:
                colour[nxt] = GREY
                path.append(nxt)
                stack.append((nxt, iter(sorted(graph.get(nxt, ())))))
    return None

Run it and print something an engineer can fix.

cycle = find_cycle(graph)
if cycle:
    print("dependency cycle:", " -> ".join(cycle))
else:
    print("acyclic")

# dependency cycle: billing -> invoice -> billing

Check it does not fire on the diamond. Delete the invoice entry’s back edge by setting graph["invoice"] = [] and rerun. It prints acyclic, even though db and config are each reached by two distinct paths. That is the test that separates this from the wrong version above.
Wire it into CI as a non-zero exit. Return 1 when find_cycle returns a path. A cycle detector that logs a warning nobody reads is a cycle detector that lets the cycle land.

When the graph is deep

The recursive form of this algorithm is shorter and it will raise RecursionError: maximum recursion depth exceeded on a long dependency chain, because CPython’s default recursion limit is 1,000 frames and each node on the path costs one. A monorepo import graph reaches that. The iterative version above has no such limit — its stack is a list on the heap — which is the reason to write it that way even though it is a dozen lines longer.

Complexity is O(V + E) either way: every node is coloured once and every edge is examined once. On a graph with a million edges this is milliseconds, so there is no performance argument for the shortcut.

When there are many cycles

find_cycle returns the first cycle it meets. If the graph is badly tangled, fixing that one just reveals the next, and iterating is slow. Two better tools:

Strongly connected components. Robert Tarjan’s algorithm, from Depth-First Search and Linear Graph Algorithms (SIAM Journal on Computing, 1972), partitions the graph in one O(V + E) pass. Every component with more than one node is a tangle of mutually reachable nodes, and every cycle lies entirely inside one component. That gives you all the trouble at once, grouped, and it is what a good dependency linter reports.

Topological sort as the check. Kahn’s algorithm repeatedly removes nodes with in-degree zero. Whatever remains when nothing has in-degree zero is precisely the set of nodes involved in cycles. It gives you the build order and the cycle membership from one run, though not an ordered path — use it when you wanted the order anyway. Python’s standard library ships this as graphlib.TopologicalSorter, which raises graphlib.CycleError with a cycle in its args.

A practical note on reporting. When you do find strongly connected components, sort them by size and report the largest first, and inside each one report the edge whose removal breaks the most cycles rather than an arbitrary path. Engineers act on “delete this one import”; they do not act on a twelve-node cycle listing. Counting how many of the component’s cycles each edge participates in is expensive in general, but a cheap approximation — the edge in the component with the highest product of endpoint degrees — picks the right one often enough to be worth printing.

One judgement call worth making explicit: not every cycle is a bug. Mutual recursion between two functions is a cycle in the call graph and entirely correct. Cycles are fatal specifically where the graph is consumed by something that needs a linear order — build steps, module initialisation, migrations, task scheduling. Decide which graph you are checking before you fail a build over it, and see building a graph from tabular data for getting the adjacency mapping out of a real system in the first place.