Python 3.9+graphlibterm

graphlib.TopologicalSorter

topological sorting

Topological sorting of a dependency graph: yields nodes so that each comes after everything it depends on.

Syntax

ts = graphlib.TopologicalSorter(graph=None)

The graph maps each node to its PREDECESSORS, not its successors: {'b': {'a'}} means 'b after a'. Swap the direction and you get the reverse order with no error at all. static_order() yields one order; prepare(), get_ready() and done() support parallel processing. A cycle is detected only at prepare() or static_order(), not at add().

Examples

from graphlib import TopologicalSorter
deps = {'app': {'db', 'cache'}, 'db': {'config'}, 'cache': {'config'}}
order = list(TopologicalSorter(deps).static_order())
print(order[0], order[-1])  # → config app

from graphlib import TopologicalSorter
ts = TopologicalSorter({'z': {'x'}, 'x': set(), 'y': set()})
ts.prepare()
print(ts.get_ready())  # → ('x', 'y') — можно делать параллельно
ts.done('x', 'y')
print(ts.get_ready())  # → ('z',)

See also

Common errors

Open in the full glossarydocs.python.orgReport an inaccuracy