On Thu, 8 Oct 2009, Dan Bailey wrote:
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.
Could you please try: depth_first_visit( g, your_start_vertex, boost::topo_sort_visitor<YourOutputIterator>(your_output_iterator), color); (with color as a color map for your graph set to all white)? That should match what topological sort does but starting at a single vertex rather than all roots. -- Jeremiah Willcock