Boost Depth First Visit with avoidance and early exit

Consider the following (directed) tree

    0
|
1
/|\
/ | \
2' 3' 4'
|  |
5' 6'

where all edges are directed downward.

The goal is to traverse this tree starting at 0 in a depth-first manner and return the first vertex with a pebble (indicated by an apostrophe ') and terminate the traversal. Furthermore, I would also like to avoid a given vertex.

For example, I want to find a pebble by avoiding the vertex 2. In that case the order of visiting is: 0 to 1, 1 to 2 (avoid, return to 1); 1 to 3 (pebble found, end). There should be no attempt to discover 5, 6, and 4.

I have implemented this with boost BGL via depth_first_visit. I can get the correct output to display on the console, for example:

Discover vertex  0
Discover vertex  1
Discover vertex  2
Avoiding vertex  2
Finished vertex  2
Discover vertex  3
Found a pebble on vertex 3 and stopping dfs.

However, the issue is that the depth_first_visit doesn't really stop at vertex 3. While I can make it not examine the edges 25 and 36 (and hence not discover 5 and 6) via a terminator function, the edge 14 will be examined (because examine_edge was invoked an all outgoing edges of 1 as soon as 1 was discovered) and therefore 4 will be discovered.

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_utility.hpp>
#include <iostream>
struct pebbles{
int num_pebbles = 1;
};
using Graph = boost::adjacency_list<boost::listS, boost::vecS, boost::directedS,pebbles>;
struct Visitor : boost::default_dfs_visitor
{		
using Vertex = boost::graph_traits<Graph>::vertex_descriptor;
using Edge = boost::graph_traits<Graph>::edge_descriptor;
boost::optional<Vertex> avoid;
void discover_vertex(Vertex s, Graph const &g){
if (stop_dfs) return;
std::cerr << "Discover vertex:   " << s << std::endl;
if (s==avoid) {std::cerr << "Avoiding vertex:   " << s << std::endl; return; }
if (g
展开收缩
.num_pebbles != 0 ){
stop_dfs = true;
std::cerr << "Found a pebble on vertex: " << s << " and stopping dfs." << std::endl;
return;
}
}
//void examine_edge(Edge e, Graph const& ) const { std::cerr << "Examining edge:  " << e << std::endl; }
void finish_vertex(Vertex s, Graph const&) const {
if (stop_dfs) return;
std::cerr << "Finished vertex:   " << s << std::endl;    		
}
//terminator function
bool operator()(Vertex s, Graph const& g) const {
return ((s == avoid) || (g
展开收缩
.num_pebbles != 0));
};
private:
bool stop_dfs = false;
};
int main(){
Graph g;
//test graph g = {{0,1,2,3,4,5,6},{01,12,13,14,25,36}}
boost::add_edge(0,1,g);
boost::add_edge(1,2,g);
boost::add_edge(1,3,g);
boost::add_edge(1,4,g);
boost::add_edge(2,5,g);
boost::add_edge(3,6,g);
g[0].num_pebbles = 0;
g[1].num_pebbles = 0;    
Visitor peb_vis_termfunc;
std::vector<boost::default_color_type> colormap(num_vertices(g));
peb_vis_termfunc.avoid = 2; //avoid vertex 2
boost::depth_first_visit(g,0,peb_vis_termfunc,colormap.data(),peb_vis_termfunc);
return 0;
}

It's easy to verify that the edge (1,4) is indeed examined by uncommenting the examine_edge function. I would like to not have to examine (1,4) at all and completely exit depth_first_visitor once a pebble is found.

I have read in the documentation that the intended way to force an early exit is to throw an exception, however I don't understand how to do that in this case (I'm a relative novice with C++ and STL/Boost).

I would also greatly appreciate any comments on style, good practice or improvements of the code above.

I'm pretty sure you can just throw an exception like this:

if (g
展开收缩
.num_pebbles != 0 ) {
std::cerr << "Found a pebble on vertex: " << s << " and stopping dfs." << std::endl;
throw std::exception();
}

and then:

try {
boost::depth_first_visit(g,0,peb_vis_termfunc,colormap.data(),peb_vis_termfunc);
}
catch (std::exception) {
std::cout <<  "finished searching." << std::endl;
}

And I don't have any suggestions about style, code looks reasonable, however, I did notice that the compile time was large for such a small example (as is usually the case with Boost library), and unless you are planning to add a lot more functionality within the same context, my only suggestion would be to write it yourself since it will be much leaner.

On the topic of style, I love your code. It has many subtle choices that lead to good, readable code. Cleverly combining the visitor and termination function works well due the well-timed comment.

Most notable feedback I would have is that you include the wrong header for depth_first_visit

Personally, I favour brief code. So, I'd leverage ADL a bit more and avoid going through the graph traits unless you need to support user-defined/adapted graphs. Note that there's a null vertex for most graph types. Here's a simplified version that also limits the scope of the visitor.

Live On Coliru

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/depth_first_search.hpp>
#include <iostream>
struct Node {
int num_pebbles = 1;
};
using Graph = boost::adjacency_list<boost::listS, boost::vecS, boost::directedS, Node>;
int main() {
Graph g;
add_edge(0, 1, g);
add_edge(1, 2, g);
add_edge(1, 3, g);
add_edge(1, 4, g);
add_edge(2, 5, g);
add_edge(3, 6, g);
g[0].num_pebbles = 0;
g[1].num_pebbles = 0;
struct Visitor : boost::default_dfs_visitor {
using Vertex = Graph::vertex_descriptor;
struct Hit { Vertex v; };
Vertex avoid = Graph::null_vertex();
void discover_vertex(Vertex v, Graph const& g) const {
std::cerr << "Visit vertex:   " << v << std::endl;
if (v == avoid)
std::cerr << "Avoided vertex: " << v << std::endl;
else if (g[v].num_pebbles)
throw Hit{v};
}
};
try {
std::vector<boost::default_color_type> colormap(num_vertices(g));
depth_first_visit(g, 0, Visitor{.avoid = 2}, colormap.data());
} catch (Visitor::Hit hit) {
std::cerr << "Hit a pebble on vertex: " << hit.v << std::endl;
}
}

Printing

Visit vertex:   0
Visit vertex:   1
Visit vertex:   2
Avoided vertex: 2
Visit vertex:   5
Hit a pebble on vertex: 5