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.

Added in version 3.9.

Исключения

Модуль graphlib определяет следующие классы исключений:

exception graphlib.CycleError

Подкласс ValueError, вызываемый TopologicalSorter.prepare(), если в рабочем графе существуют циклы. Если существует несколько циклов, только один неопределенный выбор из них будет сообщен и включен в исключение.

Обнаруженный цикл доступен через второй элемент в атрибуте args экземпляра исключения и представляет собой список узлов, причем каждый узел является в графе непосредственным предшественником следующего узла в списке. В представленном списке первый и последний узел будут одинаковыми, чтобы было понятно, что он циклический.