graphlib.md
1> **Источник:** https://python-all.ru/3/library/graphlib.html2>3> «Документация Python на русском» – неофициальный перевод официальной документации Python: версии от 2.6 до 3.16, полнотекстовый поиск, английский оригинал рядом с переводом. Эта Markdown-версия страницы предназначена для работы с LLM: вставьте её в ChatGPT, Claude или Cursor.45---67# `graphlib` – Функциональность для работы с графоподобными структурами89**Исходный код:** [Lib/graphlib.py](https://python-all.ru/src/3.14/Lib/graphlib.py)1011---1213#### `class graphlib.TopologicalSorter(graph=None)`1415Предоставляет функциональность для топологической сортировки графа из [хешируемых](https://python-all.ru/3/glossary.html#term-hashable) узлов.1617Топологический порядок – это линейное упорядочение вершин графа, при котором для каждого направленного ребра u -\> v от вершины u к вершине v вершина u находится перед вершиной v. Например, вершины графа могут представлять задачи, которые нужно выполнить, а рёбра – ограничения, согласно которым одна задача должна быть выполнена перед другой; в этом примере топологическое упорядочение – это просто допустимая последовательность задач. Полное топологическое упорядочение возможно тогда и только тогда, когда граф не содержит направленных циклов, то есть является направленным ациклическим графом.1819Если указан необязательный аргумент *graph*, он должен быть словарём, представляющим направленный ациклический граф, где ключи – это узлы, а значения – итерируемые объекты со всеми предшественниками этого узла в графе (узлы, ребра которых указывают на значение ключа). Дополнительные узлы можно добавить в граф с помощью метода [`add()`](https://python-all.ru/3/library/graphlib.html#graphlib.TopologicalSorter.add).2021В общем случае для сортировки заданного графа необходимо выполнить следующие шаги:2223- Создайте экземпляр `TopologicalSorter` с необязательным начальным графом.24- Добавьте дополнительные узлы в граф.25- Вызовите [`prepare()`](https://python-all.ru/3/library/graphlib.html#graphlib.TopologicalSorter.prepare) для графа.26- Пока [`is_active()`](https://python-all.ru/3/library/graphlib.html#graphlib.TopologicalSorter.is_active) возвращает `True`, перебирайте узлы, возвращаемые [`get_ready()`](https://python-all.ru/3/library/graphlib.html#graphlib.TopologicalSorter.get_ready), и обрабатывайте их. Вызывайте [`done()`](https://python-all.ru/3/library/graphlib.html#graphlib.TopologicalSorter.done) для каждого узла после завершения его обработки.2728Если требуется лишь немедленная сортировка узлов графа и параллелизм не нужен, можно напрямую использовать удобный метод [`TopologicalSorter.static_order()`](https://python-all.ru/3/library/graphlib.html#graphlib.TopologicalSorter.static_order):2930```pycon31>>> graph = {"D": {"B", "C"}, "C": {"A"}, "B": {"A"}}32>>> ts = TopologicalSorter(graph)33>>> tuple(ts.static_order())34('A', 'C', 'B', 'D')35```3637Класс спроектирован так, чтобы легко поддерживать параллельную обработку узлов по мере их готовности. Например:3839```python40topological_sorter = TopologicalSorter()4142# Добавить узлы в 'topological_sorter'...4344topological_sorter.prepare()45while topological_sorter.is_active():46 for node in topological_sorter.get_ready():47 # Рабочие потоки или процессы берут узлы для работы из48 # очереди 'task_queue'.49 task_queue.put(node)5051 # Когда работа над узлом завершена, рабочие помещают узел в52 # 'finalized_tasks_queue', чтобы можно было получить больше узлов для работы.53 # Определение 'is_active()' гарантирует, что на этом этапе по крайней мере54 # один узел был помещён в 'task_queue', который ещё не55 # был передан в 'done()', поэтому этот блокирующий вызов 'get()' должен (в конечном итоге)56 # выполниться успешно. После вызова 'done()' мы возвращаемся к вызову 'get_ready()'57 # снова, чтобы поместить освобождённые узлы в 'task_queue' как только58 # это логически возможно.59 node = finalized_tasks_queue.get()60 topological_sorter.done(node)61```6263#### `add(node, *predecessors)`6465Добавляет новый узел и его предшественников в граф. Как *node*, так и все элементы в *predecessors* должны быть [хешируемыми](https://python-all.ru/3/glossary.html#term-hashable).6667При многократном вызове с одним и тем же узлом набор зависимостей будет объединением всех переданных зависимостей.6869Можно добавить узел без зависимостей (*predecessors* не указан) или указать зависимость дважды. Если среди *predecessors* есть узел, который ранее не был добавлен, он будет автоматически добавлен в граф без собственных предшественников.7071Вызывает [`ValueError`](https://python-all.ru/3/library/exceptions.html#ValueError), если вызывается после [`prepare()`](https://python-all.ru/3/library/graphlib.html#graphlib.TopologicalSorter.prepare).7273#### `prepare()`7475Помечает граф как завершённый и проверяет его на наличие циклов. Если обнаружен цикл, будет вызвано [`CycleError`](https://python-all.ru/3/library/graphlib.html#graphlib.CycleError), но [`get_ready()`](https://python-all.ru/3/library/graphlib.html#graphlib.TopologicalSorter.get_ready) всё ещё можно использовать, чтобы получить как можно больше узлов, пока циклы не заблокируют дальнейший прогресс. После вызова этой функции граф нельзя изменить, поэтому больше узлов нельзя добавить с помощью [`add()`](https://python-all.ru/3/library/graphlib.html#graphlib.TopologicalSorter.add).7677Будет вызвано [`ValueError`](https://python-all.ru/3/library/exceptions.html#ValueError), если сортировка уже запущена [`static_order()`](https://python-all.ru/3/library/graphlib.html#graphlib.TopologicalSorter.static_order) или [`get_ready()`](https://python-all.ru/3/library/graphlib.html#graphlib.TopologicalSorter.get_ready).7879Изменено в версии 3.14: `prepare()` теперь можно вызывать несколько раз, если сортировка ещё не началась. Ранее это вызывало [`ValueError`](https://python-all.ru/3/library/exceptions.html#ValueError).8081#### `is_active()`8283Возвращает `True`, если можно продолжить работу, и `False` в противном случае. Работа возможна, если циклы не блокируют разрешение и либо ещё есть готовые узлы, которые ещё не были возвращены [`TopologicalSorter.get_ready()`](https://python-all.ru/3/library/graphlib.html#graphlib.TopologicalSorter.get_ready), либо количество узлов, помеченных как [`TopologicalSorter.done()`](https://python-all.ru/3/library/graphlib.html#graphlib.TopologicalSorter.done), меньше числа возвращённых `TopologicalSorter.get_ready()`.8485Метод [`__bool__()`](https://python-all.ru/3/reference/datamodel.html#object.__bool__) этого класса делегирует выполнение этой функции, поэтому вместо:8687```python88if ts.is_active():89 ...90```9192можно просто сделать:9394```python95if ts:96 ...97```9899Вызывает [`ValueError`](https://python-all.ru/3/library/exceptions.html#ValueError), если вызывается без предварительного вызова [`prepare()`](https://python-all.ru/3/library/graphlib.html#graphlib.TopologicalSorter.prepare).100101#### `done(*nodes)`102103Помечает набор узлов, возвращённый [`TopologicalSorter.get_ready()`](https://python-all.ru/3/library/graphlib.html#graphlib.TopologicalSorter.get_ready), как обработанный, разблокируя тем самым преемников каждого узла из *nodes* для последующего возврата вызовом `TopologicalSorter.get_ready()`.104105Вызывает [`ValueError`](https://python-all.ru/3/library/exceptions.html#ValueError), если какой-либо узел из *nodes* уже был помечен как обработанный предыдущим вызовом этого метода, или если узел не был добавлен в граф с помощью [`TopologicalSorter.add()`](https://python-all.ru/3/library/graphlib.html#graphlib.TopologicalSorter.add), если метод вызван без вызова [`prepare()`](https://python-all.ru/3/library/graphlib.html#graphlib.TopologicalSorter.prepare), или если узел ещё не был возвращён [`get_ready()`](https://python-all.ru/3/library/graphlib.html#graphlib.TopologicalSorter.get_ready).106107#### `get_ready()`108109Возвращает объект `tuple` со всеми узлами, которые готовы. Изначально он возвращает все узлы без предшественников, а после того, как они помечены как обработанные вызовом [`TopologicalSorter.done()`](https://python-all.ru/3/library/graphlib.html#graphlib.TopologicalSorter.done), последующие вызовы будут возвращать все новые узлы, все предшественники которых уже обработаны. Когда дальнейшее продвижение невозможно, возвращаются пустые кортежи.110111Возбуждает [`ValueError`](https://python-all.ru/3/library/exceptions.html#ValueError), если вызван без предварительного вызова [`prepare()`](https://python-all.ru/3/library/graphlib.html#graphlib.TopologicalSorter.prepare).112113#### `static_order()`114115Возвращает объект-итератор, который перебирает узлы в топологическом порядке. При использовании этого метода [`prepare()`](https://python-all.ru/3/library/graphlib.html#graphlib.TopologicalSorter.prepare) и [`done()`](https://python-all.ru/3/library/graphlib.html#graphlib.TopologicalSorter.done) вызывать не следует. Этот метод эквивалентен:116117```python118def static_order(self):119 self.prepare()120 while self.is_active():121 node_group = self.get_ready()122 yield from node_group123 self.done(*node_group)124```125126Конкретный возвращаемый порядок может зависеть от порядка, в котором элементы были вставлены в граф. Например:127128```pycon129>>> ts = TopologicalSorter()130>>> ts.add(3, 2, 1)131>>> ts.add(1, 0)132>>> print([*ts.static_order()])133[2, 0, 1, 3]134135>>> ts2 = TopologicalSorter()136>>> ts2.add(1, 0)137>>> ts2.add(3, 2, 1)138>>> print([*ts2.static_order()])139[0, 2, 1, 3]140```141142Это связано с тем, что «0» и «2» находятся на одном уровне в графе (они были бы возвращены одним вызовом [`get_ready()`](https://python-all.ru/3/library/graphlib.html#graphlib.TopologicalSorter.get_ready)), и порядок между ними определяется порядком вставки.143144Если обнаружен какой-либо цикл, будет возбуждено [`CycleError`](https://python-all.ru/3/library/graphlib.html#graphlib.CycleError).145146Добавлено в версии 3.9.147148## Исключения149150Модуль `graphlib` определяет следующие классы исключений:151152#### `exception graphlib.CycleError`153154Подкласс [`ValueError`](https://python-all.ru/3/library/exceptions.html#ValueError), возбуждаемый [`TopologicalSorter.prepare()`](https://python-all.ru/3/library/graphlib.html#graphlib.TopologicalSorter.prepare) при наличии циклов в рабочем графе. Если существует несколько циклов, будет сообщено только об одном неопределённом выборе среди них, который будет включён в исключение.155156Обнаруженный цикл можно получить через второй элемент атрибута [`args`](https://python-all.ru/3/library/exceptions.html#BaseException.args) экземпляра исключения; он представляет собой список узлов, в котором каждый узел является непосредственным предшественником следующего узла в списке. В сообщаемом списке первый и последний узлы будут совпадать, чтобы было ясно, что он циклический.157