graphlib — Функциональность для работы с графоподобными структурами¶

Исходный код: Lib/graphlib.py

class graphlib.TopologicalSorter(graph=None)¶

Предоставляет функциональные возможности для топологической сортировки графа из hashable узлов.

Топологический порядок - это линейное упорядочение вершин в графе таким образом, что для каждого направленного ребра u -> v из вершины u в вершину v вершина u стоит перед вершиной v в порядке упорядочения. Например, вершины графа могут представлять задачи, которые необходимо выполнить, а ребра могут представлять ограничения, согласно которым одна задача должна быть выполнена перед другой; в этом примере топологический порядок - это просто допустимая последовательность для задач. Полное топологическое упорядочение возможно тогда и только тогда, когда граф не имеет направленных циклов, то есть если это направленный ациклический граф.

Если указан необязательный аргумент graph, то это должен быть словарь, представляющий ориентированный ациклический граф, где ключами являются узлы, а значениями - повторяемые значения всех предшественников этого узла в графе (узлы, ребра которых указывают на значение в ключе). Дополнительные узлы могут быть добавлены к графу с помощью метода add().

В общем случае для выполнения сортировки данного графа требуются следующие шаги:

• Создайте экземпляр TopologicalSorter с необязательным начальным графиком.

• Добавьте дополнительные узлы к графику.

• Вызовите prepare() на графике.

• Пока is_active() равно True, выполните итерацию по узлам, возвращаемым get_ready(), и обработайте их. Вызовите done() на каждом узле по мере завершения обработки.

В случае, если требуется только немедленная сортировка узлов на графике и параллелизм не задействован, можно напрямую использовать удобный метод TopologicalSorter.static_order():

>>> graph = {"D": {"B", "C"}, "C": {"A"}, "B": {"A"}}
>>> ts = TopologicalSorter(graph)
>>> tuple(ts.static_order())
('A', 'C', 'B', 'D')

Класс разработан таким образом, чтобы легко поддерживать параллельную обработку узлов по мере их готовности. Например:

topological_sorter = TopologicalSorter()

# Add nodes to 'topological_sorter'...

topological_sorter.prepare()
while topological_sorter.is_active():
    for node in topological_sorter.get_ready():
        # Worker threads or processes take nodes to work on off the
        # 'task_queue' queue.
        task_queue.put(node)

    # When the work for a node is done, workers put the node in
    # 'finalized_tasks_queue' so we can get more nodes to work on.
    # The definition of 'is_active()' guarantees that, at this point, at
    # least one node has been placed on 'task_queue' that hasn't yet
    # been passed to 'done()', so this blocking 'get()' must (eventually)
    # succeed.  After calling 'done()', we loop back to call 'get_ready()'
    # again, so put newly freed nodes on 'task_queue' as soon as
    # logically possible.
    node = finalized_tasks_queue.get()
    topological_sorter.done(node)

add(node, *predecessors)¶

Добавьте в график новый узел и его предшественники. Как узел, так и все элементы в предшественниках должны быть hashable.

При многократном вызове с одним и тем же аргументом node набор зависимостей будет представлять собой объединение всех переданных зависимостей.

Можно добавить узел без зависимостей (предшественники не указаны) или указать зависимость дважды. Если узел, который не был указан ранее, включен в число предшественников, он будет автоматически добавлен в график без собственных предшественников.

Вызывает ValueError, если вызывается после prepare().

prepare()¶

Отметьте график как законченный и проверьте наличие циклов на графике. Если обнаружен какой-либо цикл, будет выведено значение CycleError, но get_ready() все еще можно использовать для получения как можно большего количества узлов, пока циклы не заблокируют дальнейший прогресс. После вызова этой функции график не может быть изменен, и поэтому больше никаких узлов нельзя добавить с помощью add().

is_active()¶

Возвращает True, если можно добиться большего прогресса, и False в противном случае. Прогресс может быть достигнут, если циклы не блокируют разрешение и либо все еще есть готовые узлы, которые еще не были возвращены с помощью TopologicalSorter.get_ready(), либо количество узлов, помеченных как TopologicalSorter.done(), меньше, чем количество узлов, возвращенных с помощью TopologicalSorter.get_ready().

Метод __bool__() этого класса подчиняется этой функции, поэтому вместо:

if ts.is_active():
    ...

это можно просто сделать:

if ts:
    ...

Вызывает ValueError, если вызывается без предварительного вызова prepare().

done(*nodes)¶

Помечает набор узлов, возвращенных TopologicalSorter.get_ready() как обработанные, разблокируя любого преемника каждого узла в nodes для возврата в будущем вызовом TopologicalSorter.get_ready().

Вызывает ValueError, если какой-либо узел в nodes уже был помечен как обработанный предыдущим вызовом этого метода, или если узел не был добавлен в график с помощью TopologicalSorter.add(), если он был вызван без вызова prepare() или если узел еще не был возвращен с помощью get_ready().

get_ready()¶

Возвращает tuple со всеми готовыми узлами. Первоначально он возвращает все узлы, не имеющие предшественников, и как только они помечены как обработанные вызовом TopologicalSorter.done(), дальнейшие вызовы будут возвращать все новые узлы, все предшественники которых уже обработаны. Как только дальнейший прогресс невозможен, возвращаются пустые кортежи.

Вызывает ValueError, если вызывается без предварительного вызова prepare().

static_order()¶

Возвращает объект-итератор, который выполняет итерацию по узлам в топологическом порядке. При использовании этого метода не следует вызывать prepare() и done(). Этот метод эквивалентен:

def static_order(self):
    self.prepare()
    while self.is_active():
        node_group = self.get_ready()
        yield from node_group
        self.done(*node_group)

Конкретный возвращаемый порядок может зависеть от конкретного порядка, в котором элементы были вставлены в график. Например:

>>> ts = TopologicalSorter()
>>> ts.add(3, 2, 1)
>>> ts.add(1, 0)
>>> print([*ts.static_order()])
[2, 0, 1, 3]

>>> ts2 = TopologicalSorter()
>>> ts2.add(1, 0)
>>> ts2.add(3, 2, 1)
>>> print([*ts2.static_order()])
[0, 2, 1, 3]

Это связано с тем, что «0» и «2» находятся на одном уровне в графе (они были бы возвращены при одном и том же вызове get_ready()), и порядок между ними определяется порядком вставки.

Если будет обнаружен какой-либо цикл, будет поднят CycleError.

Добавлено в версии 3.9.