graphlib – Функциональность для работы с графоподобными структурами¶graphlib – Functionality to operate with graph-like structures

Исходный код: 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()

# Добавить узлы в 'topological_sorter'...

topological_sorter.prepare()
while topological_sorter.is_active():
    for node in topological_sorter.get_ready():
        # Рабочие потоки или процессы берут узлы для работы из
        # очереди 'task_queue'.
        task_queue.put(node)

    # Когда работа над узлом завершена, рабочие помещают узел в
    # 'finalized_tasks_queue', чтобы можно было получить больше узлов для работы.
    # Определение 'is_active()' гарантирует, что на этом этапе по крайней мере
    # один узел был помещён в 'task_queue', который ещё не
    # был передан в 'done()', поэтому этот блокирующий вызов 'get()' должен (в конечном итоге)
    # выполниться успешно. После вызова 'done()' мы возвращаемся к вызову 'get_ready()'
    # снова, чтобы поместить освобождённые узлы в 'task_queue' как только
    # это логически возможно.
    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.