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() будет невозможно.

Будет вызвано исключение ValueError, если сортировка уже начата с помощью static_order() или get_ready().

Изменено в версии 3.14: prepare() теперь можно вызывать несколько раз, если сортировка ещё не началась. Ранее это приводило к вызову исключения ValueError.

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.