Python topological sort: dependency order and cycle rejection

Operation contract

The pipeline graph lists all operations explicitly. The sorter computes indegrees and takes ready operations from a min-heap, giving a reproducible lexical tie rule. Removing an operation decrements the indegree of its dependents. If fewer operations are emitted than were declared, a cycle prevented a valid complete ordering.

Failure and ownership boundary

The function rejects undeclared endpoints, duplicate edges and oversized graphs before scheduling. A cycle rejection occurs before any application task runs: this program only returns a plan. A valid order does not imply a task will succeed or that executing every ready task concurrently is safe. Python asyncio.Queue: backpressure and completion accounting needs a separate execution policy.

Working program

import heapq

def dependency_order(graph):
    if len(graph) > 64 or any(type(node) is not str or len(edges) > 64 for node, edges in graph.items()):
        raise ValueError("graph budget")
    indegree = dict.fromkeys(graph, 0)
    for edges in graph.values():
        if len(edges) != len(set(edges)) or any(target not in graph for target in edges):
            raise ValueError("invalid dependency")
        for target in edges:
            indegree[target] += 1
    ready = [node for node, count in indegree.items() if count == 0]
    heapq.heapify(ready)
    ordered = []
    while ready:
        node = heapq.heappop(ready)
        ordered.append(node)
        for target in graph[node]:
            indegree[target] -= 1
            if indegree[target] == 0:
                heapq.heappush(ready, target)
    if len(ordered) != len(graph):
        raise ValueError("dependency cycle")
    return ordered

print(dependency_order({"import": ["validate"], "validate": ["publish"], "publish": []}))
try:
    dependency_order({"import": ["publish"], "publish": ["import"]})
except ValueError:
    print("cycle rejected")

Output

['import', 'validate', 'publish']
cycle rejected

Costs and limits

For V nodes and E edges, validation and indegrees take O(V+E) expected hash work; heap tie ordering adds O(V log V). Retained bookkeeping is O(V), excluding the caller’s graph.

Common Mistakes

• A missing endpoint is invalid input, not an invisible extra node.
• A topological plan does not provide transaction rollback for failing tasks.

Connected lessons

Python graph BFS: mark a vertex when it enters the queue, Python asyncio.Queue: backpressure and completion accounting, Python Dijkstra: nonnegative weights and stale heap entries.

Check the next state boundary

Python strongly connected components: partition a directed dependency graph.

Follow the service contract

Python graph condensation: collapse directed cycles into an acyclic component graph.

Trace the related workflow

Python exercise: verify a dependency order without confusing it with reachability.