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.