graphlib — Functionality to operate with graph-like structures

Вихідний код: Lib/graphlib.py

---

class graphlib.TopologicalSorter(graph=None)

Provides functionality to topologically sort a graph of hashable nodes.

Топологічний порядок — це лінійне впорядкування вершин графа таким чином, що для кожного спрямованого ребра 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)

Add a new node and its predecessors to the graph. Both the node and all elements in predecessors must be hashable.

Якщо викликати кілька разів з тим самим аргументом node, набір залежностей буде об’єднанням усіх переданих залежностей.

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

Викликає ValueError, якщо викликається після prepare().

prepare()

Позначте графік як готовий і перевірте наявність циклів у ньому. Якщо буде виявлено будь-який цикл, CycleError буде викликано, але get_ready() все ще можна використовувати для отримання якомога більшої кількості вузлів, доки цикли не заблокують подальший прогрес. Після виклику цієї функції граф не можна змінити, і тому більше вузлів не можна додавати за допомогою add().

is_active()

Повертає True, якщо можна досягти більшого прогресу, і False в іншому випадку. Прогрес може бути досягнутий, якщо цикли не блокують розв’язку та або ще є готові вузли, які ще не повернув TopologicalSorter.get_ready(), або кількість вузлів, позначених TopologicalSorter.done(), менша ніж число, яке повернув TopologicalSorter.get_ready().

The __bool__() method of this class defers to this function, so instead of:

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

Повертає кортеж з усіма готовими вузлами. Спочатку він повертає всі вузли без попередників, і коли вони позначаються як оброблені за допомогою виклику 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.

Винятки

Модуль graphlib визначає такі класи винятків:

exception graphlib.CycleError

Підклас ValueError, створений TopologicalSorter.prepare(), якщо в робочому графі існують цикли. Якщо існує кілька циклів, лише один невизначений вибір серед них буде повідомлено та включено до винятку.

The detected cycle can be accessed via the second element in the args attribute of the exception instance and consists in a list of nodes, such that each node is, in the graph, an immediate predecessor of the next node in the list. In the reported list, the first and the last node will be the same, to make it clear that it is cyclic.