A build graph contains these edges:

parse -> typecheck -> bundle -> parse

Enter fullscreen mode Exit fullscreen mode

There is no valid first task. A topological sort should not return a partial list and quietly stop; it should explain why the graph cannot be ordered.

This project teaches two connected ideas:

  1. Kahn's algorithm produces an order for a directed acyclic graph (DAG).
  2. A separate depth-first search can turn “some cycle exists” into a concrete cycle a learner can inspect.

Prerequisites: Python 3.11+ and basic familiarity with dictionaries, sets, and queues. The code uses only the standard library.

Define the graph contract

We represent each task with the tasks it depends on:

graph = {
    "bundle": {"typecheck"},
    "typecheck": {"parse"},
    "parse": set(),
}

Enter fullscreen mode Exit fullscreen mode

An edge parse -> typecheck means parse must appear first. A dependency mentioned only inside a set is still a node, so normalization must add it.

Order the acyclic case

Kahn's algorithm tracks each node's in-degree: the number of prerequisites not yet removed.

from collections import deque


def normalize(graph):
    nodes = set(graph)
    for dependencies in graph.values():
        nodes.update(dependencies)
    return {node: set(graph.get(node, set())) for node in nodes}


def topological_order(graph):
    dependencies = normalize(graph)
    dependents = {node: set() for node in dependencies}

    for node, prerequisites in dependencies.items():
        for prerequisite in prerequisites:
            dependents[prerequisite].add(node)

    ready = deque(sorted(
        node for node, prerequisites in dependencies.items()
        if not prerequisites
    ))
    order = []

    while ready:
        node = ready.popleft()
        order.append(node)

        for dependent in sorted(dependents[node]):
            dependencies[dependent].remove(node)
            if not dependencies[dependent]:
                ready.append(dependent)

    remaining = {node for node, deps in dependencies.items() if deps}
    if remaining:
        return None, remaining
    return order, set()

Enter fullscreen mode Exit fullscreen mode

Try it:

graph = {
    "bundle": {"typecheck"},
    "typecheck": {"parse"},
    "parse": set(),
    "test": {"typecheck"},
}

print(topological_order(graph))

Enter fullscreen mode Exit fullscreen mode

Expected output (the exact order of equally ready tasks depends on queue policy):

(['parse', 'typecheck', 'bundle', 'test'], set())

Enter fullscreen mode Exit fullscreen mode

Sorting ready names makes this example deterministic. Real schedulers may instead prioritize cost, critical path, or resource availability.

Why a partial result is not enough

Now introduce a cycle:

cyclic = {
    "parse": {"bundle"},
    "typecheck": {"parse"},
    "bundle": {"typecheck"},
}

print(topological_order(cyclic))

Enter fullscreen mode Exit fullscreen mode

Expected result:

(None, {'parse', 'typecheck', 'bundle'})

Enter fullscreen mode Exit fullscreen mode

Kahn's algorithm proves ordering failed, but remaining can include nodes merely blocked by a cycle. It does not necessarily show cycle edges. We need a second pass.

Extract one concrete cycle

Depth-first search assigns three states:

  • unseen: not visited;
  • active: on the current recursion path;
  • done: fully explored.

An edge to an active node is a back edge and therefore closes a cycle.

def find_cycle(graph, candidates=None):
    graph = normalize(graph)
    allowed = set(graph) if candidates is None else set(candidates)
    state = {node: "unseen" for node in graph}
    stack = []
    position = {}

    def visit(node):
        state[node] = "active"
        position[node] = len(stack)
        stack.append(node)

        for dependency in sorted(graph[node]):
            if dependency not in allowed:
                continue
            if state[dependency] == "unseen":
                cycle = visit(dependency)
                if cycle:
                    return cycle
            elif state[dependency] == "active":
                start = position[dependency]
                return stack[start:] + [dependency]

        stack.pop()
        position.pop(node)
        state[node] = "done"
        return None

    for node in sorted(allowed):
        if state[node] == "unseen":
            cycle = visit(node)
            if cycle:
                return cycle
    return None

Enter fullscreen mode Exit fullscreen mode

Combine both stages:

def schedule(graph):
    order, remaining = topological_order(graph)
    if order is not None:
        return {"order": order, "cycle": None}
    return {"order": None, "cycle": find_cycle(graph, remaining)}

print(schedule(cyclic))

Enter fullscreen mode Exit fullscreen mode

Expected structure:

{'order': None, 'cycle': ['bundle', 'typecheck', 'parse', 'bundle']}

Enter fullscreen mode Exit fullscreen mode

The start node may vary, but the last item must equal the first, and every adjacent pair must be a real dependency edge.

Tests that verify meaning

Avoid testing only one exact printed cycle because several rotations can be correct.

def assert_valid_order(graph, order):
    index = {node: i for i, node in enumerate(order)}
    normalized = normalize(graph)
    assert set(order) == set(normalized)
    for node, dependencies in normalized.items():
        for dependency in dependencies:
            assert index[dependency] < index[node]


def assert_valid_cycle(graph, cycle):
    normalized = normalize(graph)
    assert cycle[0] == cycle[-1]
    for node, dependency in zip(cycle, cycle[1:]):
        assert dependency in normalized[node]


order, remaining = topological_order(graph)
assert remaining == set()
assert_valid_order(graph, order)

result = schedule(cyclic)
assert result["order"] is None
assert_valid_cycle(cyclic, result["cycle"])

Enter fullscreen mode Exit fullscreen mode

Add three error-shaped fixtures:

# Self-cycle
assert_valid_cycle({"a": {"a"}}, schedule({"a": {"a"}})["cycle"])

# A cycle plus a node blocked by it
blocked = {"a": {"b"}, "b": {"a"}, "deploy": {"a"}}
assert_valid_cycle(blocked, schedule(blocked)["cycle"])

# A disconnected valid component plus a cycle
mixed = {"lint": set(), "a": {"b"}, "b": {"a"}}
assert_valid_cycle(mixed, schedule(mixed)["cycle"])

Enter fullscreen mode Exit fullscreen mode

Complexity and limitations

Both passes are O(V + E) apart from sorting, which adds deterministic output at a cost. Recursive DFS can hit Python's recursion limit on very deep graphs; an iterative stack is safer for untrusted or huge input.

This scheduler also assumes dependencies are static and tasks consume no limited resources. A production build system must consider caching, parallelism, task failures, and changing inputs. Topological order answers only one question: which precedence constraints are mathematically possible?

What you should understand

Kahn's algorithm and DFS do different jobs. Kahn's algorithm constructs an order and detects that some dependency cannot be removed. DFS explains a specific contradiction in the graph. Combining them produces both a useful success result and a useful failure result.

As an extension, change find_cycle() to return every strongly connected component with more than one node. That leads naturally to Tarjan's or Kosaraju's algorithm—and to better diagnostics for real build graphs.