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 должны быть хешируемыми.

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

Можно добавить узел без зависимостей (аргумент 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.