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...