I'm having a few problems getting the depth_first_visit to work at all. I've been through the examples and can't find anything useful, here's what I'm currently trying: #include using namespace boost; typedef adjacency_list Graph; Graph graph(2); add_edge(1, 2, graph); add_edge(2, 3, graph); depth_first_visit(graph, 0, dfs_visitor<>(), color_map(get(vertex_color, Graph))); Can you make any suggestion as to why this might not work? Thanks, Dan Jeremiah Willcock wrote:

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 _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

Jeremiah Willcock wrote:

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 _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

This seems to have worked well for my graph, which is relatively small. It also requires really fast traversal and doesn't care about the time to add or remove an edge. The solution I have opted for is as follows: - cache the topological order into a vector - iterate through the vector removing and adding each edge in turn (in topological order) - perform a breadth first search on the resulting graph (which is now ordered by topological order) Though this could clearly be optimized to speed it up if necessary, feel free to explain to me why this approach might be a bad idea. One thing I'd like to do is halt the search of a particular branch of the graph if a certain condition is true, what would be the best way of accomplishing this? Using predicates or pre-computing the color map to satisfy this condition? In my graph, it's often the case that a node may not have any edges at all, which seems to crash the bgl. I've put in this little test to ensure this never happens, but is this a common problem to have to work around? std::pair edges = out_edges(index, graph); if (edges.first == edges.second) return true; Thanks, Dan