Python 3.9+graphlibпонятие

graphlib.TopologicalSorter

топологическая сортировка

Топологическая сортировка графа зависимостей: выдаёт узлы так, что каждый идёт после всех, от которых зависит.

Синтаксис

ts = graphlib.TopologicalSorter(graph=None)

Граф задаётся словарём «узел → его ПРЕДШЕСТВЕННИКИ», а не последователи: {'b': {'a'}} значит «b после a». Перепутав направление, получите обратный порядок без всякой ошибки. static_order() даёт один порядок; для параллельной обработки служат prepare(), get_ready() и done(). Цикл обнаруживается только при prepare() или static_order(), а не при add().

Примеры

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',)

См. также

Частые ошибки

Открыть в полном глоссарииdocs.python.orgСообщить о неточности