Поиск алгоритма для инвертирования (обратное? Зеркало? Вывернуть наизнанку) DAG

Question

Я ищу алгоритм для "инвертирования" (обратного? Вывернуть наизнанку?) DAG:

       A*      # I can't ascii-art the arrows, so just
      / \      # pretend the slashes are all pointing
     B   C     # "down" (south-east or south-west)
    /   / \    # e.g. 
   G   E   D   # A -> (B -> G, C -> (E -> F, D -> F))
        \ /
         F

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

         F*
        / \
   G*  E   D   # F -> (E -> C -> A, D -> C -> A), G -> B -> A
    \   \ /    # 
     B   C     # Again, arrows point "down"
      \ /      # 
       A       # 

Таким образом, входные данные представляют собой набор «корней» (здесь {A}). Выход должен быть множество «корней» в графе результатов: {G, F}. (Под корнем я имею в виду узел без входящих ссылок. Лист - это узел без исходящих ссылки.)

Корнями ввода становятся листья выхода и визы наоборот. Преобразование должно быть обратным самому себе.

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

Answer 1

Пройдите по графику, построив набор перевернутых ребер и список листовых узлов.

Выполните топологическую сортировку перевернутых ребер, используя для начала листовые (теперь корневые) узлы.

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

Это либо O (N), если вы используете структуры для своего промежуточного представления, которые отслеживают все ссылки в обоих направлениях, связанных с узлом, либо O (NlnN), если вы используете сортировку, чтобы найти все ссылки узла. Для небольших графов или языков, которые не страдают от переполнения стека, вы можете просто построить график лениво, а не явно выполнять топологическую сортировку. Так что от того, как все это будет отличаться, зависит немного, что вы реализуете.

A -> (B -> G, C -> (E -> F, D -> F))

original roots: [ A ]
original links: [ AB, BG, AC, CE, EF, CD, DF ] 
reversed links: [ BA, GB, CA, EC, FE, DC, FD ]
reversed roots: [ G, F ]
reversed links: [ BA, CA, DC, EC, FE, FD, GB ] (in order of source)
topologically sorted: [ G, B, F, E, D, C, A ]
construction order : A, C->A, D->C, E->C, F->(D,E), B->A, G->B

Answer 2

Просто сделайте отметку поиска в глубину, где вы уже были, и каждый раз, когда вы перемещаетесь по стрелке, вы добавляете обратную сторону к вашему DAG результата. Добавьте листья как корни.

Answer 3

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

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

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

Answer 4

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

Я использовал список смежности, но вы можете сделать то же самое с матрицей смежности.

В Python это выглядит так:

# Basic Graph Structure
g = {}
g[vertex] = [v1, v2, v3] # Each vertex contains a lists of its edges

Чтобы найти все ребра для v, вы затем пересекаете список g [v], и это даст вам все (v, u) ребра.

Чтобы построить перевернутый граф, создайте новый словарь и создайте его примерно так:

    reversed = {}
    for v in g:
        for e in g[v]:
            if e not in reversed:
                reversed[e] = []
            reversed[e].append(v)

Это большой объем памяти для больших графиков (удваивает использование памяти), но это очень простой и быстрый способ работы с ними. Могут быть и более умные решения, связанные с созданием генератора и использованием какого-либо алгоритма dfs, но я не особо задумывался над этим.

Answer 5

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