Объект TopologicalSorter модуля graphlib в Python

Методы ориентированного ациклического графа TopologicalSorter в Python

В разделе представлены описания методов объекта TopologicalSorter модуля graphlib в Python, который получается в результате создания экземпляра класса graphlib.TopologicalSorter(graph), где аргумент graph представляет собой ориентированный ациклический граф.

import graphlib
graph = graphlib.TopologicalSorter(graph=None)

Содержание:

• graph.add() - добавляет к графу новый узел,
• graph.prepare() - помечает граф как завершенный,
• graph.is_active() - проверяет, можно ли получить следующий узел,
• graph.done() - помечает набор возвращаемых узлов, как обработанные,
• graph.get_ready() - возвращает кортеж со всеми готовыми узлами,
• graph.static_order() - возвращает итерацию узлов в топологическом порядке.

graph.add(node, *predecessors):

Метод graph.add() добавляет к графу новый узел node и его предшественников *predecessors. И узел, и все элементы в предшественниках должны быть хешируемыми.

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

Можно добавить узел без зависимостей (предшественники predecessors не указываются) или предоставить зависимость дважды. Если узел, который не был предоставлен ранее и включен в число предшественников, он будет автоматически добавлен в граф без собственных предшественников.

Метод graph.add() вызывает ошибку ValueError, если вызывается после graph.prepare().

graph.prepare():

Метод graph.prepare() помечает граф как завершенный и проверяет наличие циклических связей на графе.

Если какая-либо циклическая связь обнаружена, то вызывается исключение CycleError, но метод graph.get_ready() все еще работает и может использоваться для получения как можно большего количества узлов, пока циклические связи не заблокируют дальнейший процесс.

После вызова функции graph.prepare(), граф не может быть изменен, следовательно нельзя больше добавить узлы с помощью метода graph.add().

graph.is_active():

Метод graph.is_active() возвращает True, если можно получить следующий узел, и False в противном случае.

Дальнейшее получение узлов может быть достигнуто,

• если циклические связи в графе не блокируют разрешение на получение узлов,
• есть готовые узлы, которые еще не были получены методом graph.get_ready(),
• количество узлов, отмеченных graph.done(), меньше количества, которое было возвращено graph.get_ready().

Метод __bool__() экземпляра класса отсылает к этой функции, поэтому:

if ts.is_active():
    ...

# можно просто сделать:
if ts:
    ...

Если метод graph.is_active() вызванный без предварительного вызова graph.prepare(), то бросается исключение ValueError.

graph.done(*nodes):

Метод graph.done() помечает набор узлов, возвращаемых методом graph.get_ready(), как обработанный, разблокируя любого преемника каждого узла в nodes для возврата в будущем вызовом graph.get_ready().

Метод graph.done() вызывает исключение ValueError:

• если какой-либо узел в nodes уже был помечен как обработанный предыдущим вызовом,
• если узел не был добавлен в граф с помощью graph.add(),
• если вызывается без предварительного вызова метода graph.prepare(),
• если узел пока еще не был возвращен методом graph.get_ready().

graph.get_ready():

Метод graph.get_ready() возвращает кортеж со всеми готовыми узлами.

Первоначально метод возвращает все узлы без предшественников, и как только они помечаются как обработанные путем вызова graph.done(), дальнейшие вызовы graph.get_ready() вернут все новые узлы, для которых их предшественники уже обработаны. Как только дальней получение узлов становиться невозможным, возвращаются пустые кортежи.

Метод graph.get_ready() вызывает ошибку ValueError, если вызывается без предварительного вызова метода graph.prepare().

graph.static_order():

Метод graph.static_order() возвращает итерацию узлов в топологическом порядке.

Использование этого метода не требует предварительного вызова методов graph.prepare(). или graph.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 находятся на одном уровне графа (они были бы возвращены в одном вызове graph.get_ready()) и порядок между ними определяется порядком вставки.

Если в графе будет обнаружена какая-либо циклическая связь, то метод graph.static_order() вызовет исключение CycleError