Dependency graphs: topological order and cycle rejection

Last updated: 5 Oct 20269 min read

tutorial

A directed dependency graph puts an edge from each prerequisite to the task that needs it. A topological order lists every task only after its prerequisites. Incoming-edge counts make the condition explicit: tasks with count zero are ready; removing one ready task reduces the counts of its dependents. If the queue becomes empty before all tasks are emitted, at least one directed cycle prevents a complete order. This program deduplicates repeated prerequisite names, rejects names missing from the task map, and raises on a cycle. It returns one valid order, not the only possible order and not an execution schedule with resource constraints.

Operational case

A warehouse plan stocks inventory, reserves it, picks and packs goods, prints a label, then ships. Shipping depends on both pack and label. The shown input yields stock, reserve, pick, label, pack, ship; swapping independent pick and label can still be valid. A second plan makes receive depend on audit and audit depend on receive. Neither can reach incoming count zero, so the method reports a dependency cycle instead of returning a partial plan as if it were complete. A production planner might report the specific cycle and isolate affected tasks, which requires an additional traversal.

Working Python program

from collections import deque


def execution_order(requirements):
    successors = {task: [] for task in requirements}
    incoming = {task: 0 for task in requirements}
    for task, prerequisites in requirements.items():
        for prerequisite in dict.fromkeys(prerequisites):
            if prerequisite not in requirements:
                raise ValueError(f"unknown prerequisite: {prerequisite}")
            successors[prerequisite].append(task)
            incoming[task] += 1

    ready = deque(task for task in requirements if incoming[task] == 0)
    order = []
    while ready:
        task = ready.popleft()
        order.append(task)
        for dependent in successors[task]:
            incoming[dependent] -= 1
            if incoming[dependent] == 0:
                ready.append(dependent)
    if len(order) != len(requirements):
        raise ValueError("dependency cycle")
    return order


warehouse_jobs = {
    "stock": [],
    "reserve": ["stock"],
    "pick": ["reserve"],
    "pack": ["pick"],
    "label": ["reserve"],
    "ship": ["pack", "label"],
}
print(execution_order(warehouse_jobs))
try:
    execution_order({"receive": ["audit"], "audit": ["receive"]})
except ValueError as error:
    print(str(error))

Output

['stock', 'reserve', 'pick', 'label', 'pack', 'ship']
dependency cycle

Time, space, and tradeoff

Building successor lists and incoming counts takes O(V + E) expected time for V tasks and E distinct prerequisite edges, and the queue removes each task once while scanning each edge once. The graph, counts, queue, and result use O(V + E) space. Hash-map operations are assumed expected O(1). This implementation preserves the task insertion order among initially ready tasks and follows dependent insertion order, but that is only a deterministic tie policy for a fixed input map. Changing the input order can change the valid result. Topological order alone says nothing about durations, parallel capacity, retries, or durable job completion.

Common Mistakes

Do not reverse the prerequisite edge and accidentally run dependent work first.
Do not return a partial ordering as success when a cycle remains.
Do not count a repeated prerequisite twice while storing only one edge.
Do not treat a valid order as a full scheduler or a proof that jobs completed.

Connected lessons

Apply this operation in the warehouse release project, then check the deletion and dependency quiz.

data structures

range-query-structures