> **Источник:** https://python-all.ru/3.11/library/graphlib.html > > «Документация Python на русском» – неофициальный перевод официальной документации Python: версии от 2.6 до 3.16, полнотекстовый поиск, английский оригинал рядом с переводом. Эта Markdown-версия страницы предназначена для работы с LLM: вставьте её в ChatGPT, Claude или Cursor. --- # [`graphlib`](https://python-all.ru/3.11/library/graphlib.html#module-graphlib) – Функциональность для работы с графоподобными структурами **Исходный код:** [Lib/graphlib.py](https://python-all.ru/src/3.11/Lib/graphlib.py) --- #### `class graphlib.TopologicalSorter(graph=None)` Предоставляет функциональность для топологической сортировки графа из [хешируемых](https://python-all.ru/3.11/glossary.html#term-hashable) узлов. Топологический порядок – это линейное упорядочение вершин графа, при котором для каждого направленного ребра u -\> v от вершины u к вершине v вершина u находится перед вершиной v. Например, вершины графа могут представлять задачи, которые нужно выполнить, а рёбра – ограничения, согласно которым одна задача должна быть выполнена перед другой; в этом примере топологическое упорядочение – это просто допустимая последовательность задач. Полное топологическое упорядочение возможно тогда и только тогда, когда граф не содержит направленных циклов, то есть является направленным ациклическим графом. Если указан необязательный аргумент *graph*, он должен быть словарём, представляющим направленный ациклический граф, где ключи – это узлы, а значения – итерируемые объекты со всеми предшественниками этого узла в графе (узлы, ребра которых указывают на значение ключа). Дополнительные узлы можно добавить в граф с помощью метода [`add()`](https://python-all.ru/3.11/library/graphlib.html#graphlib.TopologicalSorter.add). В общем случае для сортировки заданного графа необходимо выполнить следующие шаги: - Создайте экземпляр [`TopologicalSorter`](https://python-all.ru/3.11/library/graphlib.html#graphlib.TopologicalSorter) с необязательным начальным графом. - Добавьте дополнительные узлы в граф. - Вызовите [`prepare()`](https://python-all.ru/3.11/library/graphlib.html#graphlib.TopologicalSorter.prepare) для графа. - Пока [`is_active()`](https://python-all.ru/3.11/library/graphlib.html#graphlib.TopologicalSorter.is_active) возвращает `True`, перебирайте узлы, возвращаемые [`get_ready()`](https://python-all.ru/3.11/library/graphlib.html#graphlib.TopologicalSorter.get_ready), и обрабатывайте их. Вызывайте [`done()`](https://python-all.ru/3.11/library/graphlib.html#graphlib.TopologicalSorter.done) для каждого узла после завершения его обработки. Если требуется лишь немедленная сортировка узлов графа и параллелизм не нужен, можно напрямую использовать удобный метод [`TopologicalSorter.static_order()`](https://python-all.ru/3.11/library/graphlib.html#graphlib.TopologicalSorter.static_order): ```pycon >>> graph = {"D": {"B", "C"}, "C": {"A"}, "B": {"A"}} >>> ts = TopologicalSorter(graph) >>> tuple(ts.static_order()) ('A', 'C', 'B', 'D') ``` Класс спроектирован так, чтобы легко поддерживать параллельную обработку узлов по мере их готовности. Например: ```python 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* должны быть [хешируемыми](https://python-all.ru/3.11/glossary.html#term-hashable). При многократном вызове с одним и тем же узлом набор зависимостей будет объединением всех переданных зависимостей. Можно добавить узел без зависимостей (*predecessors* не указан) или указать зависимость дважды. Если среди *predecessors* есть узел, который ранее не был добавлен, он будет автоматически добавлен в граф без собственных предшественников. Вызывает [`ValueError`](https://python-all.ru/3.11/library/exceptions.html#ValueError), если вызывается после [`prepare()`](https://python-all.ru/3.11/library/graphlib.html#graphlib.TopologicalSorter.prepare). #### `prepare()` Помечает граф как завершённый и проверяет его на наличие циклов. Если обнаружен цикл, будет вызвано [`CycleError`](https://python-all.ru/3.11/library/graphlib.html#graphlib.CycleError), но [`get_ready()`](https://python-all.ru/3.11/library/graphlib.html#graphlib.TopologicalSorter.get_ready) всё ещё можно использовать, чтобы получить как можно больше узлов, пока циклы не заблокируют дальнейший прогресс. После вызова этой функции граф нельзя изменить, поэтому больше узлов нельзя добавить с помощью [`add()`](https://python-all.ru/3.11/library/graphlib.html#graphlib.TopologicalSorter.add). #### `is_active()` Возвращает `True`, если можно продолжить работу, и `False` в противном случае. Работа возможна, если циклы не блокируют разрешение и либо ещё есть готовые узлы, которые ещё не были возвращены [`TopologicalSorter.get_ready()`](https://python-all.ru/3.11/library/graphlib.html#graphlib.TopologicalSorter.get_ready), либо количество узлов, помеченных как [`TopologicalSorter.done()`](https://python-all.ru/3.11/library/graphlib.html#graphlib.TopologicalSorter.done), меньше числа возвращённых [`TopologicalSorter.get_ready()`](https://python-all.ru/3.11/library/graphlib.html#graphlib.TopologicalSorter.get_ready). Метод [`__bool__()`](https://python-all.ru/3.11/reference/datamodel.html#object.__bool__) этого класса делегирует выполнение этой функции, поэтому вместо: ```python if ts.is_active(): ... ``` можно просто сделать: ```python if ts: ... ``` Возбуждает [`ValueError`](https://python-all.ru/3.11/library/exceptions.html#ValueError), если вызван без предварительного вызова [`prepare()`](https://python-all.ru/3.11/library/graphlib.html#graphlib.TopologicalSorter.prepare). #### `done(*nodes)` Помечает набор узлов, возвращённый [`TopologicalSorter.get_ready()`](https://python-all.ru/3.11/library/graphlib.html#graphlib.TopologicalSorter.get_ready), как обработанный, разблокируя тем самым преемников каждого узла из *nodes* для последующего возврата вызовом [`TopologicalSorter.get_ready()`](https://python-all.ru/3.11/library/graphlib.html#graphlib.TopologicalSorter.get_ready). Вызывает [`ValueError`](https://python-all.ru/3.11/library/exceptions.html#ValueError), если какой-либо узел из *nodes* уже был помечен как обработанный предыдущим вызовом этого метода, или если узел не был добавлен в граф с помощью [`TopologicalSorter.add()`](https://python-all.ru/3.11/library/graphlib.html#graphlib.TopologicalSorter.add), если метод вызван без вызова [`prepare()`](https://python-all.ru/3.11/library/graphlib.html#graphlib.TopologicalSorter.prepare), или если узел ещё не был возвращён [`get_ready()`](https://python-all.ru/3.11/library/graphlib.html#graphlib.TopologicalSorter.get_ready). #### `get_ready()` Возвращает объект `tuple` со всеми узлами, которые готовы. Изначально он возвращает все узлы без предшественников, а после того, как они помечены как обработанные вызовом [`TopologicalSorter.done()`](https://python-all.ru/3.11/library/graphlib.html#graphlib.TopologicalSorter.done), последующие вызовы будут возвращать все новые узлы, все предшественники которых уже обработаны. Когда дальнейшее продвижение невозможно, возвращаются пустые кортежи. Возбуждает [`ValueError`](https://python-all.ru/3.11/library/exceptions.html#ValueError), если вызван без предварительного вызова [`prepare()`](https://python-all.ru/3.11/library/graphlib.html#graphlib.TopologicalSorter.prepare). #### `static_order()` Возвращает объект-итератор, который перебирает узлы в топологическом порядке. При использовании этого метода [`prepare()`](https://python-all.ru/3.11/library/graphlib.html#graphlib.TopologicalSorter.prepare) и [`done()`](https://python-all.ru/3.11/library/graphlib.html#graphlib.TopologicalSorter.done) вызывать не следует. Этот метод эквивалентен: ```python def static_order(self): self.prepare() while self.is_active(): node_group = self.get_ready() yield from node_group self.done(*node_group) ``` Конкретный возвращаемый порядок может зависеть от порядка, в котором элементы были вставлены в граф. Например: ```pycon >>> 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()`](https://python-all.ru/3.11/library/graphlib.html#graphlib.TopologicalSorter.get_ready)), и порядок между ними определяется порядком вставки. Если обнаружен какой-либо цикл, будет возбуждено [`CycleError`](https://python-all.ru/3.11/library/graphlib.html#graphlib.CycleError). Новое в версии 3.9. ## Исключения Модуль [`graphlib`](https://python-all.ru/3.11/library/graphlib.html#module-graphlib) определяет следующие классы исключений: #### `exception graphlib.CycleError` Подкласс [`ValueError`](https://python-all.ru/3.11/library/exceptions.html#ValueError), возбуждаемый [`TopologicalSorter.prepare()`](https://python-all.ru/3.11/library/graphlib.html#graphlib.TopologicalSorter.prepare) при наличии циклов в рабочем графе. Если существует несколько циклов, будет сообщено только об одном неопределённом выборе среди них, который будет включён в исключение. Обнаруженный цикл можно получить через второй элемент атрибута [`args`](https://python-all.ru/3.11/library/exceptions.html#BaseException.args) экземпляра исключения; он представляет собой список узлов, в котором каждый узел является непосредственным предшественником следующего узла в списке. В сообщаемом списке первый и последний узлы будут совпадать, чтобы было ясно, что он циклический.