Хабрахабр

«Топологическая» сортировка графа с циклами

Полное название статьи должно было звучать как «Устойчивая „топологическая“ сортировка графа с циклами за O(|V| + |e| log |e|) по времени и O(|V|) по памяти без рекурсии», но мне сказали, что это перебор.
Disclaimer: я программист, а не математик, поэтому местами возможны неточные формулировки, за которые можно и нужно пинать.

Суть задачи

Разберу формулировку задачи, решением которой я хочу поделиться, по частям.

Здесь есть два важных нюанса: таких упорядочиваний у графа может быть больше одного и она применима только к ациклическим графам. Топологическая сортировка — это такое упорядочивание вершин направленного ациклического графа, в котором каждая из вершин, из которой выходит ребро, идёт раньше чем вершина, в которую это ребро входит. Математиков это не беспокоит, а вот программистам бывает хочется детерминизма и чуточку большего, чем «извините, у вас тут цикл, не будет вам никакой сортировки».

Поэтому добавляем требование устойчивости: пара вершин, порядок между которыми не задан рёбрами графа, должен определяться порядком, в котором эти самые вершины поступили на вход алгоритма.

Поэтому в прикладном программировании обычно итеративные алгоритмы предпочтительнее рекурсивных. С отсутствием рекурсии всё просто, компьютер существенно слабее машины Тьюринга и память (а в особенности стэк) имеет ограниченную.

Это такое упорядочивание вершин, которое совпадает с истинной топологической сортировкой, если каждый из циклов заменить одной вершиной, а вершины самого цикла в соответствии с требованием устойчивости расположены относительно друг друга в изначальном порядке. И, наконец, определю, что я называю «топологической» сортировкой в случае наличия циклов в графе.

А теперь со всей этой фигнёй мы попытаемся взлететь я это всё проделаю в рамках, указанных в начале поста ограничений по времени и памяти.

Поиск решения

Если посмотреть на существующие алгоритмы топологической сортировки (алгоритм Кана, поиск в глубину), то окажется, что они все в случае наличия цикла, говорят «не могу» и прекращают работу.

Например, найти их. Поэтому зайдём с другой стороны, с алгоритмов которые могут с циклами сделать что-то вразумительное. Он содержит интересную ремарку о том, что в качестве побочного продукта алгоритм выдаёт обратную топологическую сортировку графа:
Среди перечисленных в Википедии алгоритмов по поиску циклов в графах, внимание привлёк алгоритм Тарьяна.

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. 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.

Правда, алгоритм ресурсивный и непонятно, что у него с устойчивостью, но это явно движение в нужном направлении. При более внимательном чтении Википедии, в ней обнаруживается отсылка к статье A space-efficient algorithm for finding strongly connected components за авторством товарища Дэвида Пирса, в которой мало того, что есть императивный алгоритм, так ещё и с уменьшенными требованиями по памяти по сравнению с классическим алгоритмом Тарьяна. Бонусом идёт реализация алгоритма на Java. Надо брать!

Алгоритм PEA_FIND_SCC3(V,E) из статьи Пирса

Итак, у нас есть список вершин на входе и (благодаря Пирсу) некий индекс компонента сильной связности, к которому принадлежит эта вершина на выходе. Следующий шаг — устойчиво отсортировать вершины в соответствии с порядковым номером их компонента. Алгоритм для такой задачи есть, он называется сортировка подсчётом, выполняющая это O(n) времени.

В процессе собирания алгоритма в кучу выяснилось, что из Тарьяна действительно сильно прёт наружу тот факт, что ему естественно отдавать всё-таки обратную топологическую сортировку — то соседние ветви графа (не имеющие между собой отношения порядка) пронумерует задом наперёд, то куски графа, не имеющие между собой каких либо связей, оказываются в обратном порядке…

Ответ

Итак, финальное решение:

  1. Пронумеровываем вершины исходного списка. O(|V|)
  2. Сортируем рёбра каждой из вершин в соответствии с номером вершины, в которую идёт ребро. O(|e| log |e|)
  3. При помощи алгоритма Пирса находим и нумеруем компоненты сильной связности. O(|V|)
  4. При помощи сортировки подсчётом сортируем вершины на базе полученных ими номеров компонент сильной связности. O(|V|)

Код на GitHub, Java, public domain. Можно обратить внимание, что для обеспечения стабильности сортировки алгоритм Пирса немного модифицирован и обходит вершины в обратном порядке.

Но зачем???

А теперь предыстория, зачем это всё понадобилось. При загрузке/выгрузке динамических библиотек (.so), glibc необходимо решить, в каком порядке инициализировать статические переменные. Переменные зависят друг от друга, зависят от разных функций и т.п. В общем всё это образует тот самый граф, в котором бывают циклы и который надо отсортировать.

И в общем-то никого это не особо не беспокоило, пока в 2012-ом году не обнаружилось, что код работает некорректно и в некоторых случаях ошибается. Когда-то давно этой задачей занимался довольно неоптимальный код, выполнявший задачу за O(n^2).

Проблемные случаи починились, однако алгоритм стал уже работать за O(n^3), а это уже стало заметно и на некоторых приложениях стало занимать единицы-десятки секунд, о чём в 2013-ом году и был заведён баг. Суровые мужики из RedHat подумали-подумали и навернули сверху ещё немного циклов. Он же предложил использовать алгоритм Тарьяна, правда патч с исправлениями так никогда и не оформил. Так же автор бага обнаружил случаи, в которых алгоритм с O(n^3) тоже ошибался.

К сожалению неудачная, алгоритм был выбран O(n^2), к тому же путавший местами ветки графа, между которыми не определён порядок. А время шло, glibc нещадно тормозила и в 2015-ом году происходит ещё одна попытка починить алгоритм.

Судя по тому, сколько у меня уже ушло времени на исправление задачи, шансы на то, что я доведу её до конца, существенно ниже 100%. Сегодня на дворе 2019-ый год, glibc всё так же тормозит. А ещё для того, чтобы в glibc вообще взглянули на ваш патч, необходимо пройти процедуру copyright assignment'а, правильно оформить патч и чёрт знает что ещё. Всё усугубляется ещё тем, что дело происходит на C, без поддержки IDE, в коде с GNU стилем кодирования, безумным запускатором тестов («а если вы хотите запустить тест снова, просто удалите соответствующий .out-файл»). Поэтому, дабы хотя бы снять вопрос с придумыванием алгоритма, решающего задачу, и был написан этот пост.

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть