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.