Resolving Dependency Graphs

Python
from graphlib import TopologicalSorter, CycleError

graph = {
    "deploy": {"test", "build"},
    "test": {"build"},
    "build": {"lint"},
    "lint": set(),
}

ts = TopologicalSorter(graph)
print(list(ts.static_order()))
# ['lint', 'build', 'test', 'deploy']

graph[node] = {dependencies} — keys depend on their values (values must be resolved first).

Progress:

• Build the dependency dict: {node: set_of_prerequisites}
• Choose API: static_order() for a simple full sort, or the manual protocol for streaming/parallel execution
• Handle CycleError if the graph might contain cycles
• (If parallel) drive the sorter manually with prepare()/get_ready()/done()

Simple case — full ordering:

Python
ts = TopologicalSorter(graph)
order = list(ts.static_order())

Parallel/streaming case — process ready nodes as they unblock:

Python
ts = TopologicalSorter(graph)
ts.prepare()  # raises CycleError here if cyclic
while ts.is_active():
    ready = ts.get_ready()      # tuple of nodes with no unresolved deps
    for node in ready:
        do_work(node)
        ts.done(node)           # mark complete, unblocks dependents

get_ready() returns all currently unblocked nodes — dispatch them concurrently (thread pool, async tasks, subprocess batch) for real parallelism.

Adding edges incrementally:

Python
ts = TopologicalSorter()
ts.add(node, *predecessors)   # can call repeatedly to build up graph
ts.add("build", "lint")
ts.add("test", "build")

Example 1: Detecting a cycle Input:

Python
graph = {"a": {"b"}, "b": {"c"}, "c": {"a"}}
ts = TopologicalSorter(graph)
ts.static_order()

Output:

graphlib.CycleError: ('nodes are in a cycle', ['a', 'b', 'c', 'a'])

Example 2: Parallel build batches Input:

Python
graph = {"link": {"a.o", "b.o"}, "a.o": {"a.c"}, "b.o": {"b.c"}, "a.c": set(), "b.c": set()}
ts = TopologicalSorter(graph)
ts.prepare()
batches = []
while ts.is_active():
    ready = ts.get_ready()
    batches.append(sorted(ready))
    for n in ready:
        ts.done(n)

Output:

batches == [['a.c', 'b.c'], ['a.o', 'b.o'], ['link']]

Example 3: Independent nodes (no dependencies) Input:

Python
graph = {"x": set(), "y": set()}
list(TopologicalSorter(graph).static_order())

Output: ['x', 'y'] (order among unrelated nodes is arbitrary but valid)