Topological ordering and cycle detection

Model prerequisites separately from runtime health

For a local setup, you may need to prepare the database before checking the application. Represent the input as task -> prerequisites, so check: [accounts, ledger] means both must precede the check. This representation is the reverse of the outgoing-edge model in the graph-traversal bite.

A topological ordering exists for a directed acyclic graph (DAG). There may be several valid orders. Dependency order does not establish readiness, successful execution, or safe teardown. Real runners also need timeouts, failure states, concurrency limits, and readiness checks.

Implement Kahn's algorithm

Save as dependency_order.py. The function returns task names in a valid order without executing commands.

from collections import deque


def dependency_order(prerequisites):
    incoming = {}
    dependents = {task: [] for task in prerequisites}
    for task, parents in prerequisites.items():
        parents = set(parents)
        if any(parent not in prerequisites for parent in parents):
            raise ValueError("Unknown prerequisite")
        incoming[task] = len(parents)
        for parent in parents:
            dependents[parent].append(task)
    ready = deque(task for task in prerequisites if incoming[task] == 0)
    result = []
    while ready:
        task = ready.popleft()
        result.append(task)
        for dependent in dependents[task]:
            incoming[dependent] -= 1
            if incoming[dependent] == 0:
                ready.append(dependent)
    if len(result) != len(prerequisites):
        raise ValueError("Dependency cycle: no complete ordering")
    return result


fixture = {
    "db": [], "broker": [],
    "accounts": ["db", "broker"],
    "ledger": ["db", "broker"],
    "check": ["accounts", "ledger"],
}
ordered = dependency_order(fixture)
positions = {task: i for i, task in enumerate(ordered)}
assert len(ordered) == len(fixture)
assert all(positions[parent] < positions[task]
           for task, parents in fixture.items() for parent in parents)

Each processed edge reduces one remaining prerequisite count. The work and auxiliary storage are O(V + E) under ordinary hashing assumptions. Tasks left blocked after a cycle is found may include downstream tasks; they are not necessarily all members of the cycle.

Trace when a task becomes ready

In the fixture, db and broker start with zero prerequisites. Processing db reduces the remaining counts for Accounts and Ledger from two to one. Processing broker reduces them to zero, so both become ready. Only after both are processed can check become ready. The queue stores tasks that have no remaining prerequisites, not tasks that are known healthy.

Run python3 dependency_order.py. Its property assertion should pass even when independent task order differs. For a scratch cycle a -> b and b -> a, neither reaches zero, so the result cannot cover all declared tasks. A downstream check waiting on b stays blocked too, although it is not itself part of the cycle.

Connect the model to the actual tool

Compare your result with graphlib.TopologicalSorter(fixture).static_order(), validating precedence rather than identical order. Python's helper raises CycleError for a cycle.

Terraform documents dependency-graph construction, cycle validation, and a parallel depth-first walk that waits for dependencies. Topological ordering explains the constraint, but this exercise is not a copy of Terraform's implementation. Kubernetes has no general built-in dependsOn relationship between arbitrary workloads; controller-specific fields require that controller's documented behavior.

Checkpoint and revision

Test empty input, an independent task, a duplicate prerequisite, an unknown prerequisite, a self-cycle, and a cycle with a downstream task. Explain why starting an application process and proving that its dependency is ready are distinct steps.

Checkpoint answers: empty input returns []; independent tasks are allowed anywhere consistent with edges; duplicate prerequisites are counted once; an unknown prerequisite or a cycle raises ValueError. Successful ordering still needs actual execution and readiness checks in a real runner. Next, heaps answer which available item ranks highest; they do not resolve dependency cycles.

Sources

Python graphlib↗, Terraform's dependency graph↗, and Kubernetes custom resources and controllers↗.