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)

Добавьте новый узел и его предшественников в граф. И узел, и все элементы в 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.