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

Полное название статьи должно было звучать как «Устойчивая „топологическая“ сортировка графа с циклами за 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. Надо брать!

Алгоритм 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 необходимо решить, в каком порядке инициализировать статические переменные. Переменные зависят друг от друга, зависят от разных функций и т.п. В общем всё это образует тот самый граф, в котором бывают циклы и который надо отсортировать.

Когда-то давно этой задачей занимался довольно неоптимальный код, выполнявший задачу за 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'а, правильно оформить патч и чёрт знает что ещё. Поэтому, дабы хотя бы снять вопрос с придумыванием алгоритма, решающего задачу, и был написан этот пост.
Поделиться публикацией

Комментарии 15

    0
    Спасибо за статью. Вот описание алгоритма Тарьяна на русском. И почему вы вспомнили про сортировку подсчетом когда сортируете вершины, но забыли когда сортируете ребра? Можно например завести массив пар (из, в) и отсортировать подсчетом (по 2 элементу) все за O(|V| + |E|) времени. Потом их всех запихать назад. Также непонятно почему у вас O(|V|) памяти (ребра не храним?)?
      0
      1. Классический алгоритм Тарьяна меня не устраивал по причине его рекурсивности, это указано в тексте. Хотя ссылка полезная, в той же русскоязычной Википедии алгоритмы над графами описаны довольно слабо.
      2. Про сортировку рёбер подумаю. Пока непонятно почему то что вы говорите должно сработать.
      3. Память под рёбра я не считаю потому что они уже где-то хранятся откуда их мне подали на вход. Если в реальном применении граф совсем нельзя будет менять (ни сохранить в вершине её индекс, ни переупорядочить рёбра), то будут проблемы и некоторые big-O подрастут. Здесь же предполагается что граф можно портить, при условии что его структура не нарушается (не добавляются/удаляются вершины/рёбра).
      4. Другое вот подумал. Нет необходимости в отдельном этапе «считаем сколько вершин в каждом из компонентов» в рамках сортировки подсчётом. Это прекрасно можно сделать в процессе Тарьяна.
        0
        Да, про алгоритм Тарьяна я написал чтобы те кто не могут в английский прочитали на русском. Действительно ваш алгоритм можно реализовать так что-бы ребра не хранились в памяти. Но если их сохранить то можно отсортировать за O(|V| + |E|). Например так.
        std::vector<std::vector<size_t>> graph(n);
        std::vector<std::vector<size_t>> transponed(n);
        for (size_t from = 0; from < n; from++)
        	for (size_t to: graph[from])
        		transponed[to].push_back(from);
        graph.clear();
        for (size_t to = 0; to < n; to++)
        	for (size_t from: transponed[to])
        		graph[from].push_back(to);
        
          0
          Так же можно заметить что, то чего вы хотите добиться в практической части это не стабильная сортировка, а одинаковое поведение в не зависимости от того в каком порядке стоят ребра в вершине графа(в представлении графа). А это как раз алгоритм Тарьяна с предварительной сортировкой рёбер.
            0
            Я не просто так взял слово «топологическая» в кавычки, потому что насколько мне известно, никакого термина для того что я делаю нет. Да, по условиям задачи важен порядок вершин, а не рёбер.

            Алгоритм пытается решить две проблемы: неоднозначность топологической сортировки плюс её несуществование для графов с циклами. К математике это имеет слабое отношение. Оно решает проблемы несовершенного мира, пытаясь среди неооднозначности топологической сортировки выбрать единственный вариант, удобный на практике и (надеюсь) легко вычисляемый в голове.
              0
              То что вы хотите, называется топологическая сортировка сконденсированного графа. Алгоритм Тарьяна это алгоритм конденсации. И он детерминированный. Разница в работе может быть вызвана только тем в каком порядке лежат ребра в вершине(в представлении графа)
            0
            Вектора — это фрагментация, cache miss'ы, аллокация памяти в heap'е и вот это вот всё. Напомню что предметная область для которой придумывался алгоритм — C плюс крайне низкоуровневый код (ld.so), выполняемый очень часто — любой вызов exec(3). А если ограничиться только массивами, то памяти O(|e|^2), для стэка это уже неприемлемо. Бенчмаркать надо. Но до решения практической задачи руки идут медленно и тяжко.
              +1
              Я не согласен, все можно реализовать на массивах. Как в старые добрые паскалевские времена, например можно хранить массив «голов» и массив ребер. Головы указывают где начинается кусок памяти ребер данной вершины.Я переписал свой код без векторов.
              void transpose_graph(size_t vsize, size_t *graph, size_t *heads, size_t *tgraph, size_t *theads)
              {
              	for (size_t from = 0; from < vsize; ++from)
              		for (size_t j = heads[from]; j < heads[from]; ++j)
              			if (graph[j] != 0)
              				++theads[graph[j] + 1];
              	for (size_t i = 1; i < vsize; i++)
              		theads[i + 1] += theads[i];
              	for (size_t from = 0; from < vsize; ++from)
              		for (size_t j = heads[from]; j < heads[from]; ++j)
              		{
              			tgraph[theads[graph[j]]] = from;
              			++theads[graph[j]];
              		}
              }
              
              int main()
              {
              	size_t vsize, esize;
              	size_t graph[esize];
              	size_t heads[vsize + 1];
              	//  заполняем граф
              	size_t tgraph[esize];
              	size_t theads[vsize + 1];
              	transpose_graph(vsize, graph, heads, tgraph, theads);
                      for (size_t i = 0; i < vsize + 1; i++)
                            heads[i] = 0;
              	transpose_graph(vsize, tgraph, theads, graph, heads);
              }
              
                0

                Согласен. Ваше кунг-фу сильнее моего кунг-фу :) Не хотите патч в glibc запилить?)

                  0
                  Можете скинуть то место которое надо поменять?
                    0
                    sourceware.org/git/?p=glibc.git;a=blob;f=elf/dl-sort-maps.c;h=26b3fd93a387ba1314df1b98dc1d54cb44cd3594;hb=HEAD

                    Пояснения особенностей предметной области:
                    • maps — это массив вершин размером nmaps
                    • maps[i]->l_initfini — null-terminated массив рёбер
                    • maps[i]->l_idx — место куда можно запомнить индекс вершины. Если там -1, его портить нельзя и эту вершину нужно пропустить
                    • maps[i]->l_reldeps — еще рёбра, так называемые «dynamic». Обращать на них внимание только если на входе for_fini=true. Суть этих рёбер в рамках задачи в том что если цикл образован с их участием, то на них можно забить. Товарищ который заходил на эту тему в 2015-ом (и я с ним согласен) пришли к мысли что сортировать надо дважды. Сначала с учётом всех ребер, потом (если обнаружены циклы), повторно но уже только учитывая l_initfini и игнорируя l_reldeps
                    • used — некий массив, элементы которого надо расставить в том же порядке в котором в результате расставлены вершины. Т.е. maps[i] связан с used[i]
                      0
                      Спасибо, если что-то выйдет, то напишу статью на хабр.
                        0
                        Вопрос про maps[i]->l_reldeps. Что значит что на них можно забить? Можно ли не забивать? Просто не сильно понятно как строго сформулировать задачу с этими ребрами.
                          0
                          Формально:

                          1. Выполняем сортировку
                          2. Если были циклы, то повторно выполняем сортировку того что получилось на предыдущем шаге делая вид что l_reldeps не существует.

                          Это просто некий hint из предметной области относительно того какие рёбра пойдут «под нож» в ситуации когда мы не можем удовлетворить их все. Задачи минимизации количества нарушенных рёбер не стоит, ибо там подстерегает NP.

                          Думаю, имеет смысл посмотреть релевантные багрепорты:

                          sourceware.org/bugzilla/show_bug.cgi?id=15310
                          sourceware.org/bugzilla/show_bug.cgi?id=15311
                          sourceware.org/bugzilla/show_bug.cgi?id=17645
          0

          Я делал бандлер js модулей, где, опять же, могут быть циклические зависимости. К сожалению, просто оставить в порядке поступления — не вариант, так как поступают модули вразнобой. А, например, если исполнить модуль, расширяющий базовый класс, до модуля, где этот базовый класс определяется, то это приведёт к падению. Поэтому для каждой зависимости задаётся её вес. 0 — максимальный вес, жёсткая зависимость. минус бесконечность — самая слабая зависимость. Алгоритм получился такой: https://github.com/eigenmethod/mol/blob/master/graph/graph.ts
          cut_cycles разрезает циклы в наиболее слабом месте за O(число узлов + число связей), а sorted — сериализует ациклический граф за O(число узлов), если поменять массивы на хеш-сеты, конечно.
          У меня используется рекурсия, она ни чем не хуже ручной реализации стека так-то.
          Суть алгоритма проста: идём от узла по зависимостям в глубину, запоминая путь. Обнаружив цикл, смотрим где в пути был наименьший вес, раскручиваем стек до него, разрезаем, и переходим к следующей его зависимости. Если мы прошли по всем зависимостям узла, то помечаем его проверенным и не заходим в него больше. И так для всех узлов в качестве стартовых.

          Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

          Самое читаемое