[Boost-users] DAG Graph Search

Subject: [Boost-users] DAG Graph Search
From: Dan Bailey (drb_at_[hidden])
Date: 2009-10-08 05:06:21

Hi,

I'm looking to do a downstream search over a DAG graph where I never 
advance past a node until all of the nodes linking to it have been seen.

Clearly a breadth first search won't work, but using a topological sort, 
 I can get a list of all the nodes in the correct order. However I only 
wish to search over the nodes downstream from any particular node (until 
I reach the leaf nodes), which doesn't work as this is the entire 
network even if it contains various sub-graphs.

Is there a better algorithm or approach I can use to do this?

Here's a simple example:

a -> b
b -> c
c -> d
a -> c

I wouldn't ever want to look at c before b, but if I started at b for 
example, I would only want to see downstream of this.

Any help would be appreciated,

Cheers,
Dan