«Топологическая» сортировка графа с циклами
Полное название статьи должно было звучать как «Устойчивая «топологическая» сортировка графа с циклами за O(|V| + |e| log |e|) по времени и O(|V|) по памяти без рекурсии», но мне сказали что это перебор.
Disclaimer: я программист, а не математик, поэтому местами возможны неточные формулировки, за которые можно и нужно пинать.
Суть задачи
Разберу формулировку задачи, решением которой я хочу поделиться, по частям.
Топологическая сортировка — это такое упорядочивание вершин направленного ациклического графа, в котором каждая из вершин, из которой выходит ребро, идёт раньше чем вершина, в которую это ребро входит. Здесь есть два важных нюанса: таких упорядочиваний у графа может быть больше одного и она применима только к ациклическим графам. Математиков это не беспокоит, а вот программистам бывает хочется детерминизма и чуточку большего, чем «извините, у вас тут цикл, не будет вам никакой сортировки».
Поэтому добавляем требование устойчивости: пара вершин, порядок между которыми не задан рёбрами графа, должен определяться порядком, в котором эти самые вершины поступили на вход алгоритма.
С отсутствием рекурсии всё просто, компьютер существенно слабее машины Тьюринга и память (а в особенности стэк) имеет ограниченную. Поэтому в прикладном программировании обычно итеративные алгоритмы предпочтительнее рекурсивных.
И, наконец, определю, что я называю «топологической» сортировкой в случае наличия циклов в графе. Это такое упорядочивание вершин, которое совпадает с истинной топологической сортировкой, если каждый из циклов заменить одной вершиной, а вершины самого цикла в соответствии с требованием устойчивости расположены относительно друг друга в изначальном порядке.
А теперь со всей этой фигнёй мы попытаемся взлететь я это всё проделаю в рамках, указанных в начале поста ограничений по времени и памяти.
Поиск решения
Если посмотреть на существующие алгоритмы топологической сортировки (алгоритм Кана, поиск в глубину), то окажется, что они все в случае наличия цикла, говорят «не могу» и прекращают работу.
Поэтому зайдём с другой стороны, с алгоритмов которые могут с циклами сделать что-то вразумительное. Например, найти их. Среди перечисленных в Википедии алгоритмов по поиску циклов в графах, внимание привлёк алгоритм Тарьяна. Он содержит интересную ремарку о том, что в качестве побочного продукта алгоритм выдаёт обратную топологическую сортировку графа:
While there is nothing special about the order of the nodes within each strongly connected component, one useful property of the algorithm is that no strongly connected component will be identified before any of its successors. Therefore, the order in which the strongly connected components are identified constitutes a reverse topological sort of the DAG formed by the strongly connected components.
Правда, алгоритм ресурсивный и непонятно, что у него с устойчивостью, но это явно движение в нужном направлении. При более внимательном чтении Википедии, в ней обнаруживается отсылка к статье A space-efficient algorithm for finding strongly connected components за авторством товарища Дэвида Пирса, в которой мало того, что есть императивный алгоритм, так ещё и с уменьшенными требованиями по памяти по сравнению с классическим алгоритмом Тарьяна. Бонусом идёт реализация алгоритма на Java. Надо брать!
Итак, у нас есть список вершин на входе и (благодаря Пирсу) некий индекс компонента сильной связности, к которому принадлежит эта вершина на выходе. Следующий шаг — устойчиво отсортировать вершины в соответствии с порядковым номером их компонента. Алгоритм для такой задачи есть, он называется сортировка подсчётом, выполняющая это O(n) времени.
В процессе собирания алгоритма в кучу выяснилось, что из Тарьяна действительно сильно прёт наружу тот факт, что ему естественно отдавать всё-таки обратную топологическую сортировку — то соседние ветви графа (не имеющие между собой отношения порядка) пронумерует задом наперёд, то куски графа, не имеющие между собой каких либо связей, оказываются в обратном порядке…
Ответ
Итак, финальное решение:
- Пронумеровываем вершины исходного списка.
O(|V|) - Сортируем рёбра каждой из вершин в соответствии с номером вершины, в которую идёт ребро.
O(|e| log |e|) - При помощи алгоритма Пирса находим и нумеруем компоненты сильной связности.
O(|V|) - При помощи сортировки подсчётом сортируем вершины на базе полученных ими номеров компонент сильной связности.
O(|V|)
Код на GitHub, Java, public domain. Можно обратить внимание, что для обеспечения стабильности сортировки алгоритм Пирса немного модифицирован и обходит вершины в обратном порядке.
Но зачем???
А теперь предыстория, зачем это всё понадобилось. При загрузке/выгрузке динамических библиотек (.so), glibc необходимо решить, в каком порядке инициализировать статические переменные. Переменные зависят друг от друга, зависят от разных функций и т.п. В общем всё это образует тот самый граф, в котором бывают циклы и который надо отсортировать.
Когда-то давно этой задачей занимался довольно неоптимальный код, выполнявший задачу за O(n^2). И в общем-то никого это не особо не беспокоило, пока в 2012-ом году не обнаружилось, что код работает некорректно и в некоторых случаях ошибается.
Суровые мужики из RedHat подумали-подумали и навернули сверху ещё немного циклов. Проблемные случаи починились, однако алгоритм стал уже работать за O(n^3), а это уже стало заметно и на некоторых приложениях стало занимать единицы-десятки секунд, о чём в 2013-ом году и был заведён баг. Так же автор бага обнаружил случаи, в которых алгоритм с O(n^3) тоже ошибался. Он же предложил использовать алгоритм Тарьяна, правда патч с исправлениями так никогда и не оформил.
А время шло, glibc нещадно тормозила и в 2015-ом году происходит ещё одна попытка починить алгоритм. К сожалению неудачная, алгоритм был выбран O(n^2), к тому же путавший местами ветки графа, между которыми не определён порядок.
Сегодня на дворе 2019-ый год, glibc всё так же тормозит. Судя по тому, сколько у меня уже ушло времени на исправление задачи, шансы на то, что я доведу её до конца, существенно ниже 100%. Всё усугубляется ещё тем, что дело происходит на C, без поддержки IDE, в коде с GNU стилем кодирования, безумным запускатором тестов («а если вы хотите запустить тест снова, просто удалите соответствующий .out-файл»). А ещё для того, чтобы в glibc вообще взглянули на ваш патч, необходимо пройти процедуру copyright assignment’а, правильно оформить патч и чёрт знает что ещё. Поэтому, дабы хотя бы снять вопрос с придумыванием алгоритма, решающего задачу, и был написан этот пост.
