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

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

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

Алгоритм этот - Тарджан с сильно связанными компонентами (или SCC). Как следует из названия, он разлагает ориентированный граф на его компоненты. Ориентированный граф один, и ребра имеют направление, связанное с ними, а также компонент связности графа 0 он называется подграф, - где каждый узел может быть достигнут от любого другого узла.

Сильно соединенные компоненты

Сильно соединенные компоненты

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

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

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

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

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

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

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

Здесь мы возвращаемся к ГТК графика. Если есть какие-либо 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, но, к счастью, Hassell очень прост, и у меня есть реализация здесь.

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

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

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

Благодарю Энни Черкаев за название и отзывы и Иэн Маккой за предложение более функционального подхода.