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

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

class graphlib.TopologicalSorter(graph=None)

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

Топологическая сортировка — это линейное упорядочение вершин в графе, такое, что для каждой направленной дуги 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)

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

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

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

Вызывает 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.