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}}
    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.

>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.