Топологическая сортировка
Также: Topological sort · topological ordering · алгоритм Кана · Kahn's algorithm · tsort
Как выстроить зависимости в ряд, чтобы каждая шла после всего, что ей нужно: пакеты перед программой, главы перед главой, формулы перед ячейкой. Два способа — очередь готовых и поиск в глубину, — оба линейные, и оба сразу замечают цикл, при котором порядка нет.
Команда go build не может скомпилировать пакет, пока не скомпилированы все пакеты, которые он импортирует. В стандартной библиотеке Go 379 пакетов и 2790 импортов. В каком порядке их собирать? И сколько тактов займёт сборка, если ядер у машины сколько угодно? Ниже — настоящий граф стандартной библиотеки, и по нему идёт алгоритм Кана: сначала собирается всё, что ничего не импортирует, потом всё, что стало готово, и так волна за волной.
Волн 29. Сколько ядер ни дай, быстрее не выйдет: в библиотеке есть цепочка из 29 пакетов, где каждый импортирует следующий, — от net/http/fcgi через net/http, crypto/tls, crypto/x509, sync и runtime до unsafe. Нажмите «Самая длинная цепочка», чтобы её увидеть. А теперь нажмите unsafe → fmt: самый нижний пакет начнёт импортировать пакет, который сам от него зависит. Алгоритм застрянет, и go build ответил бы так же — ошибкой import cycle not allowed.
Идея
Пусть ребро u → v значит «u нужно раньше v». Топологический порядок — ряд из всех вершин, где каждое ребро ведёт слева направо. Он есть не всегда: если u нужно раньше v, а v раньше u, ни одна из них не может стоять первой. Оказывается, циклы — единственное препятствие.
Вершина, в которую не входит ни одно ребро, может стоять первой. Поставим её, вычеркнем вместе с рёбрами и повторим. Если вершин без входящих рёбер не осталось, а граф не пуст, в нём есть цикл. Это алгоритм Кана. Второй способ — поиск в глубину: вершина, из которой вышли, уже никого не ждёт впереди, и порядок выхода, прочитанный задом наперёд, топологический.
Как это работает: pip ставит пакеты
В песочнице, где запускается код этого каталога, установлены numpy, matplotlib и mypy, а с ними ещё двенадцать пакетов, которые они требуют. С версии 6.1 pip ставит зависимости раньше тех, кому они нужны; в журнале изменений pip этот порядок так и называется — topological installation order. Вот этот граф. Стрелка ведёт от пакета к тому, что ему нужно, поэтому здесь «раньше» — в конце стрелки. Пройдите оба способа по шагам.
У Кана у каждого пакета счётчик: сколько его зависимостей ещё не поставлено. Пакеты с нулём — в очереди. Поставили пакет — у всех, кто его ждал, счётчик уменьшается, и те, у кого он дошёл до нуля, встают в очередь. matplotlib ждёт девять пакетов и встаёт последним.
Поиск в глубину идёт иначе. Он спускается от пакета к его зависимостям, от них — к их зависимостям, и записывает пакет в момент выхода, когда всё под ним уже записано. Порядки получаются разные — у Кана numpy пятый, у поиска в глубину первый, — и оба правильные. Правильных порядков для этих пятнадцати пакетов 7 429 968 000.
Почему это работает
Ориентированный граф можно топологически упорядочить тогда и только тогда, когда в нём нет циклов. Алгоритм Кана либо выдаёт порядок из всех вершин, либо останавливается, и тогда среди невыданных вершин есть цикл.
Если цикл есть, порядка нет: в ряду какая-то вершина цикла стоит левее всех остальных его вершин, и ребро цикла, которое в неё входит, ведёт справа налево.
Каждая выданная Каном вершина стоит после всех, кто нужен ей раньше: её выдают, только когда её счётчик стал нулём, то есть все входящие рёбра пришли от уже выданных. Пусть алгоритм остановился, а вершины остались. У каждой оставшейся счётчик не ноль, значит, в неё входит ребро от другой оставшейся. Пойдём от любой оставшейся вершины против рёбер: к той, что нужна ей раньше, от неё — к следующей. Вершин конечное число, поэтому мы вернёмся туда, где уже были, — это цикл. Значит, в графе без циклов Кан выдаёт все вершины.
Для поиска в глубину доказательство короче, если знать теорему о цикле: в графе без циклов нет обратных рёбер. Для ребра u → v вершина v в момент просмотра либо белая — тогда она станет потомком u, и выйдем из неё раньше, — либо чёрная, и из неё уже вышли. В обоих случаях выход из v раньше выхода из u. Поэтому в порядке убывания времени выхода каждое ребро ведёт слева направо. А в нашем графе стрелки смотрят от пакета к зависимости, поэтому разворачивать порядок не нужно: пакет записан после всего, на что указывают его стрелки.
Код
Оба способа на тех же пакетах. Кан хранит словарь счётчиков и очередь готовых; поиск в глубину — множество открытых вершин, чтобы заметить цикл: встретить открытую вершину — значит прийти в неё по кругу. В конце пусть numpy потребует matplotlib — и посмотрим, что скажут оба.
Кан ставит двенадцать пакетов и останавливается: contourpy, matplotlib и numpy ждут друг друга. Поиск в глубину находит сам круг: contourpy → numpy → matplotlib → contourpy. В Python есть готовый graphlib.TopologicalSorter: static_order() выдаёт порядок, а get_ready() и done() отдают вершины волнами, как для параллельной сборки, и при цикле бросают CycleError с самим кругом. В стандартной библиотеке Go такого нет — пишут сами.
А это граф стандартной библиотеки Go из сцены. Пакеты в данных лежат в том порядке, в каком их печатает go list -deps, и программа проверяет утверждение из справки Go: этот порядок — обход в глубину с выдачей при выходе, «пакет печатается только после всех своих зависимостей».
Волны и самая длинная цепочка
Кан с очередью выдаёт вершины волнами: сначала все, кому ничего не нужно, потом все, кто освободился после них, и так далее. Внутри волны вершины друг от друга не зависят, их можно делать одновременно. Номер волны вершины — на единицу больше самой поздней волны среди тех, кто нужен ей раньше, а число волн — число вершин на самой длинной цепочке зависимостей. Эту цепочку в планировании называют критическим путём: если задержать любую работу на ней, задержится всё.
У стандартной библиотеки Go волн 29, а самая широкая — 48 пакетов. Одним ядром сборка займёт 379 шагов, 48 ядрами — 29, и больше ядер уже не помогут. Если работы неодинаковы по длительности, волна работы — это самый поздний момент окончания её предшественников, и та же логика даёт самый ранний срок окончания проекта: один проход в топологическом порядке, динамика по графу без циклов. Ровно это в 1962 году понадобилось Артуру Кану для больших сетевых графиков PERT.
Где ломается: циклы в жизни
Go запрещает циклические импорты, поэтому граф его пакетов всегда без циклов. Пакетный менеджер Debian такой роскоши лишён. Вот 93 пакета той же песочницы и их зависимости. Кан начинает настраивать пакеты и почти сразу останавливается.
В Debian 13 стандартная библиотека Си libc6 зависит от libgcc-s1, а libgcc-s1 — от libc6. От libc6 зависит почти всё, поэтому Кан успевает настроить всего 12 пакетов из 93: те, что не зависят от Си вообще, вроде часовых поясов tzdata. Вторая петля — libssl3t64 и openssl-provider-legacy. Правила Debian, раздел 7.2, говорят прямо: при циклической зависимости петлю приходится где-то разорвать и нарушить зависимость хотя бы одного пакета. Сам dpkg старается рвать её на пакете, у которого нет скрипта настройки postinst: тогда все скрипты настройки запускаются с уже настроенными зависимостями. У libgcc-s1 такого скрипта нет, у libc6 есть. Нажмите «Разорвать циклы, как dpkg» — и все 93 пакета настроятся за 10 волн.
Общий рецепт для графа с циклами — склеить каждую петлю в одну вершину. Петли — это компоненты сильной связности, и граф из них всегда без циклов, его уже можно упорядочить. Сцена так и рисует: пакеты одной петли стоят в одном столбце.
Сколько всего порядков
Порядок единственный, только если на каждом шаге Кана в очереди ровно одна вершина. Тогда соседние вершины порядка соединены рёбрами, и порядок — путь через все вершины графа. Обычно порядков много, и считать их трудно: Грэм Брайтуэлл и Питер Винклер в 1991 году доказали, что подсчёт порядков #P-полон, — для таких задач быстрых алгоритмов не ждут. Для небольших графов годится динамика по множествам уже выданных вершин. Так для пятнадцати пакетов pip получается 7 429 968 000 порядков установки, а для 66 глав базового курса этого сайта — около 4,6 · 1045 порядков чтения. Нумерация глав в оглавлении — один из них.
Сколько это стоит
Кан: каждая вершина один раз встаёт в очередь и выходит из неё, каждое ребро один раз уменьшает счётчик — O(V + E) времени, O(V) памяти на счётчики и очередь, плюс списки «кто меня ждёт». Поиск в глубину — те же O(V + E), но глубина рекурсии может дойти до V; на длинных цепочках лучше свой стек кадров, как в статье о поиске в глубину. Если нужен не любой порядок, а лексикографически наименьший, очередь заменяют кучей, и время становится O((V + E) log V).
Кан удобнее, когда нужны волны, счётчики «сколько ещё ждать» или работа по мере готовности, как в параллельной сборке. Поиск в глубину удобнее, когда граф и так обходят в глубину или нужен сам цикл, а не только факт, что он есть.
История
Статья Артура Кана из Westinghouse «Topological sorting of large networks» вышла в Communications of the ACM в 1962 году; как ему понадобился алгоритм для сетевых графиков PERT, рассказано в главе курса о графах. Дональд Кнут включил топологическую сортировку в первый том «Искусства программирования» (1968), в раздел о связных списках. Вариант на поиске в глубину впервые появился в печати, по-видимому, у Роберта Тарьяна в 1976 году.
В Unix седьмой версии (1979) появилась команда tsort: на вход пары «что раньше чего», на выход — порядок. Она нужна была для библиотек: тогдашний компоновщик читал архив объектных файлов один раз и по порядку, и файлы приходилось расставлять так, чтобы зависимые шли раньше тех, от кого зависят. В разделе «ошибки» её страница руководства честно признавалась, что алгоритм квадратичный, но для упорядочивания архивов исправлять это не стоит.
Задачи
В первой задаче нужны волны Кана, и среди тестов — главы курса этого сайта, стандартная библиотека Go и петли Debian. Во второй естественная жадность ошибается, и порядок приходится строить с конца.
Сколько семестров Нумерация главДанные: Стандартная библиотека Go (BSD), go list Пакеты Debian 13: метаданные архива Debian