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.