Инструментарий DAG All-in-One

• Эта публикация - перевод статьи. Ее автор - Vaibhav Sagar. Оригинал доступен по ссылке ниже:

  An All-in-One DAG Toolkit

Я хотел бы рассказать вам об алгоритме, который, честно говоря, досадно, что я не обнаружил его раньше.

Это алгоритм Tarjan's Strongly Connected Components (или SCCs), и, как следует из названия, он разлагает направленный граф на его сильно связанные компоненты. Направленный граф](https://en.wikipedia.org/wiki/Directed_graph) - это граф, в котором ребра имеют направление, а сильно связный компонент графа - это подграф, в котором каждый узел может быть достигнут из любого другого узла, т.е. где-то в этом подграфе есть направленный цикл.

Сильно связанные компоненты

Почему это важно? Я не помню, чтобы у меня когда-либо возникало желание глубоко изучить SCC конкретного графа.

Давайте рассмотрим другую проблему. Если дан направленный граф, как узнать, является ли он ациклическим? В данном случае я задался вопросом, насколько сложно будет буквально нарисовать историю коммитов в Git в виде графа и отобразить её в репозитории. Коммиты Git образуют направленный ациклический граф (DAG), который представляет собой направленный граф без циклов, и я хотел проверить нарисованный пользователем граф, а также обработать его.

Направленный ациклический граф

Обращение к оракулу дало понятие топологической сортировки, в которой вершины упорядочиваются так, что для всех вершин u и v, если есть ребро от u к v, u появляется раньше, чем v в отсортированном выводе. Направленные ребра для графа коммитов Git имеют противоположное направление от того, что мы хотим, потому что они направлены от детей к родителям. На самом деле нам нужна обратная топологическая сортировка. Также было бы неплохо, если бы я мог как-то выделить подграфы недействительного графа, которые ответственны за то, что он недействителен.

Топологическая сортировка

Здесь мы возвращаемся к SCC графа. Если есть какие-либо SCC более чем одной вершины, то граф не является DAG, и эти SCC являются причиной этого. Свертывание SCC направленного графа до одной вершины всегда приводит к DAG, и это известно как конденсация направленного графа, что, на мой взгляд, является хорошим способом визуализировать связь между SCC и DAG.

Конденсация

Итак, мы действительно хотим узнать SCC этого графа, но сначала мы хотим попытаться отсортировать его топологически и изменить порядок, если это возможно, иначе мы вычислим SCC и определим нарушителей. Это кажется немного беспорядочным для свойств графа, которые кажутся несколько связанными. Как было бы здорово, если бы существовал алгоритм, который мог бы вычислять ССС и обратную топологическую сортировку для нас одновременно?

Оказывается, алгоритм SCCs Тарджана делает именно это! Можно подумать, что его производительность невелика, поскольку он делает две вещи одновременно, но он линеен по числу ребер и вершин и имеет лучшие постоянные коэффициенты, чем алгоритм Косараджу, который вычисляет только SCC. Вот он в виде псевдокода:

     algorithm tarjan is
      input: graph G = (V, E)
      output: set of strongly connected components (sets of vertices)
    
      index := 0
      S := empty array
      for each v in V do
        if (v.index is undefined) then
          strongconnect(v)
        end if
      end for
    
      function strongconnect(v)
        // Set the depth index for v to the smallest unused index
        v.index := index
        v.lowlink := index
        index := index + 1
        S.push(v)
        v.onStack := true
    
        // Consider successors of v
        for each (v, w) in E do
          if (w.index is undefined) then
            // Successor w has not yet been visited; recurse on it
            strongconnect(w)
            v.lowlink  := min(v.lowlink, w.lowlink)
          else if (w.onStack) then
            // Successor w is in stack S and hence in the current SCC
            // Note: The next line may look odd - but is correct.
            // It says w.index not w.lowlink; that is deliberate and from the original paper
            v.lowlink  := min(v.lowlink, w.index)
          end if
        end for
    
        // If v is a root node, pop the stack and generate an SCC
        if (v.lowlink = v.index) then
          start a new strongly connected component
          repeat
            w := S.pop()
            w.onStack := false
            add w to current strongly connected component
          while (w != v)
          output the current strongly connected component
        end if
      end function

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

В представленном виде это очень императивный язык, а я люблю Haskell, но, к счастью, императивный Haskell довольно прост, и у меня есть реализация здесь.

Это кажется невероятно нишевым случаем использования, но проверка и обработка DAG таким образом происходит удивительно часто. Рассмотрим процесс сборки, в котором входы и выходы являются узлами, а их связи - направленными ребрами. Наличие SCC с более чем одной вершиной указывает на циклическую зависимость, и зависимости должны быть построены до узлов, которые от них зависят, что подразумевает обратную топологическую сортировку. Это обобщается на программирование потока данных, где необходимо выявлять (и обычно устранять) циклы. Мне нравится думать об этом алгоритме как об универсальном наборе инструментов для работы с DAG.

Мы также можем использовать его для решения 2SAT - задачи определения того, можно ли присвоить булевым переменным в серии ограничений вида a || b такие значения T и F, чтобы все ограничения выполнялись. Это обсуждается здесь, но сводится к кодированию ограничений в виде узлов и ребер, вычислению SCC и обработке результатов в обратном топологически отсортированном порядке. Преимущество такого способа в том, что процесс может остановиться на первом SCC, который указывает на неудовлетворительность. У меня есть реализация этого алгоритма здесь.

Открытие этого алгоритма заставило меня увлечься теоретической информатикой и напомнило мне, что алгоритмы могут быть веселыми, интересными и давать возможность восхищаться музыкой сфер. Мне интересно узнать, какие еще существуют столь же замечательные алгоритмы. Какой из них вам нравится больше всего?

Спасибо Annie Cherkaev за название и отзывы, а также Iain McCoy за предложение более функционального подхода.