Using Boost Graph to search through a DAG Graph?

Question

I need to search through a DAG graph, but I don't want to advance past a node before I have seen all of the other nodes that have directed links pointing to it.

Is there an existing algorithm to handle this particular situation, the depth first search and breath first search don't work for this order of traversal.

Ie:

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

I don't want to ever reach D before having seen both B and C.

Answer 1

So my latest thoughts are to do a topological sort over the entire graph whenever an edge is added or removed and store the order of immediate child nodes to be traversed for each node (which may be a bit of a tricky algorithm to write).

Then I do a modified breadth first search (as suggested by chaos), and in the following bfs pseudo-code, modify the line:

for each vertex v in Adj[u]

to be:

for each vertex v in OrderedAdj[u]

pseudocode:

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)

I believe this is the most optimal way of achieving this, but does involve me writing my own bfs traversal algorithm, plus storing the order of nodes on each node (an overhead in memory I was hoping to avoid), and writing my own dfs visitor for finding the order and storing this on the nodes in the caching stage.

I am surprised that there isn't an existing way of doing this though, as it seems to me a fairly common way of navigating a dag graph...

Answer 2

What you're looking for is Kahn's (1962) topological sorting algorithm. This is not the topological sort algorithm currently implemented in BGL, which is DFS-based, visits all vertices, and outputs the results in reverse topological order, but rather is very similar to a BFS and visits vertices in exactly the manner you describe in your first paragraph. You will have to write the traversal yourself, but the algorithm is straightforward.

See the first algorithm listed in the topological sorting Wikipedia entry: http://en.wikipedia.org/wiki/Topological_sorting . Also see Program 19.8 in Sedgewick's "Algorithms in C".

Hint 1: Use an auxilliary data structure to maintain the number of in edges for each vertex, don't actually do the "remove edge from graph" part.

Hint 2: For a working GPLV3'ed example, you can take a look at the implementation of Kahn's algorithm in my CoFlo control flow graph generation and analysis project, specifically the file topological_visit_kahn.h here: http://coflo.svn.sourceforge.net/viewvc/coflo/trunk/src/controlflowgraph/topological_visit_kahn.h?view=log

Answer 3

You can't do that with an ordinary graph traversal algorithm because you're requiring that the algorithm magically have knowledge of graph structure that it can't have traversed without potentially violating its own requirements. You would have to use a two-pass approach that first builds backward trees telling you which nodes have connections in from which other nodes, then do a modified breadth-first search that uses the information from the first pass to delay traversal as appropriate. And I suspect that some graph structures might deadlock the second pass.

Answer 4

What about doing a topological sort first, then doing a depth first search over the sorted graph?

Would that work?

Answer 5

Any DAG has at least one leaf node. Removing any leaf node node and all incoming arcs leaves another DAG. Recursively, this smaller DAG also has at least one leaf node. By recursively removing all nodes in this fashion, eventually the root node becomes a leaf node.

If you now reverse the order in which you removed the nodes, you have a traversal order which has the desired properties. By visiting leaf nodes last, you guarantee to have seen all parent nodes first.