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)

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

Если вызывается несколько раз с одним и тем же аргументом 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.