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[s].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[s].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}}

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.

>Solution :

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

``````if (g[s].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.