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

StackOverflow https://stackoverflow.com/questions/1532550

  •  20-09-2019
  •  | 
  •  

Вопрос

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

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

Ie:

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

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

Это было полезно?

Решение 2

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

Затем я выполняю модифицированный поиск в ширину (как предложено 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 visitor для поиска порядка и сохранения этого на узлах на этапе кэширования.

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

Другие советы

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

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

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

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

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

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

Сработает ли это?

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

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top