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)¶

Добавить в граф новый узел и его предшественников. И узел, и все элементы в предшественниках должны быть хэшируемыми.

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

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

Повышает 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.