Использование Boost Graph для поиска по DAG-графику? - PullRequest
Новая
       12

Использование Boost Graph для поиска по DAG-графику?

1 голос
/ 07 октября 2009

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

Существует ли существующий алгоритм для обработки этой конкретной ситуации, поиск в глубину и поиск в выдохе не работают для этого порядка обхода.

Т.е.: 

A -> B
B -> C
C -> D
A -> C

Я не хочу когда-либо достигать D до того, как увидел B и C.

Ответы [ 5 ]

2 голосов
/ 25 сентября 2011

То, что вы ищете, - это алгоритм топологической сортировки Кана (1962). Это не алгоритм топологической сортировки, который в настоящее время реализован в BGL, который основан на DFS, посещает все вершины и выводит результаты в обратном топологическом порядке, а скорее очень похож на BFS и посещает вершины точно так, как вы описываете в своем первый параграф. Вам придется написать обход самостоятельно, но алгоритм прост.

См. Первый алгоритм, указанный в записи Википедии о топологической сортировке: http://en.wikipedia.org/wiki/Topological_sorting. Также см. Программу 19.8 в «Алгоритмах С» Седжвика.

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

Подсказка 2. Для работающего примера с GPLV3 вы можете взглянуть на реализацию алгоритма Кана в моем проекте генерации и анализа графов потоков управления CoFlo, в частности файл topological_visit_kahn.h здесь: http://coflo.svn.sourceforge.net/viewvc/coflo/trunk/src/controlflowgraph/topological_visit_kahn.h?view=log

1 голос
/ 08 октября 2009

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

Затем я сначала выполняю модифицированный поиск в ширину (в соответствии с предложением chaos) и в следующем псевдокоде bfs модифицирую строку: 

for each vertex v in Adj[u]

будет: 

for each vertex v in OrderedAdj[u]

псевдокод: 

BFS(G, s)
  for each vertex u in V[G]
    color[u] := WHITE 
    d[u] := infinity 
    p[u] := u 
  end for
  color[s] := GRAY 
  d[s] := 0 
  ENQUEUE(Q, s)
  while (Q != Ø) 
    u := DEQUEUE(Q)
    for each vertex v in Adj[u]
      if (color[v] = WHITE)
        color[v] := GRAY 
        d[v] := d[u] + 1  
        p[v] := u  
        ENQUEUE(Q, v)
      else
        if (color[v] = GRAY) 
          ...
        else 
          ...
    end for
    color[u] := BLACK
  end while
  return (d, p)

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

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

0 голосов
/ 07 октября 2009

Как насчет того, чтобы сначала выполнить топологическую сортировку, а затем выполнить поиск в глубину по отсортированному графику?

Будет ли это работать?

0 голосов
/ 08 октября 2009

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

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

0 голосов
/ 07 октября 2009

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

...