Is it possible to change breadth first search termination condition in BGL?

Question

I am new to BGL(boost graph library). I am learning the breadth_first_search interface and it looks handy. However, in my application, I need to cut the breadth_first_search when some other termination condition is meet such as the search space node count meets the maximum.

Could I add new termination condition with the BFSVisitors or is there any other trick?

Thanks!

Answer 1

Following (a bit late) on @yuyoyuppe comment, you can make a proxy visitor that will wrap an actual visitor and throw when a given predicate is met. The implementation I chose to tackle offers you the ability to run predicates on discover_vertex and examine_edge. First we define a default predicate returning always false:

namespace details {

struct no_halting {
    template <typename GraphElement, typename Graph>
    bool operator()(GraphElement const&, Graph const&) {
        return false;
    }
};
} // namespace details

Then, the template itself.

template <typename VertexPredicate = details::no_halting,
          typename EdgePredicate = details::no_halting,
          typename BFSVisitor = boost::default_bfs_visitor>
struct bfs_halting_visitor : public BFSVisitor {
    // ... Actual implementation ...
private:
    VertexPredicate vpred;
    EdgePredicate epred;
};

It will take 3 templates arguments:

1. A vertex predicate applied on each call to discover_vertex (at most once per vertex)
2. An edge predicate, applied on each call to examine_edge (at most once per edge)
3. An actual visitor implementation from which we will inherit

To build it, we simply initialize the base visitor and our two predicates:

template <typename VPred, typename EPred, typename ... VisArgs>
bfs_halting_visitor(VPred&& vpred, EPred&& epred, VisArgs&&... args) :
                    BFSVisitor(std::forward<VisArgs>(args)...),
                    vpred(vpred), epred(epred) {}

Then, we must make a (private) proxy function to perform the appropriate call to the base implementation and check the predicate:

template <typename Pred, typename R, typename ... FArgs, typename ... Args>
void throw_on_predicate(R (BFSVisitor::*base_fct)(FArgs...), Pred&& pred, Args&&... args) {
    bool result = pred(args...);
    (this->*base_fct)(std::forward<Args>(args)...);
    if (result) {
        throw std::runtime_error("A predicate returned true");
    }
}

Of course, I lazily used std::runtime_error but you should define your own exception type, derived from std::exception or whatever base exception class you use.

Now we can easily define our two callbacks:

template <typename Edge, typename Graph>
void examine_edge(Edge&& e, Graph&& g) {
    throw_on_predicate(&BFSVisitor::template examine_edge<Edge, Graph>, epred,
                       std::forward<Edge>(e), std::forward<Graph>(g));
}

template <typename Vertex, typename Graph>
void discover_vertex(Vertex&& v, Graph&& g) {
    throw_on_predicate(&BFSVisitor::template discover_vertex<Vertex, Graph>, vpred,
                       std::forward<Vertex>(v), std::forward<Graph>(g));
}

We will test our facility on a custom vertex predicate that returns true on the discovery of the N-th vertex.

struct VertexCounter {
    VertexCounter(std::size_t limit) : count(0), limit(limit) {}
    VertexCounter() : VertexCounter(0) {}

    template <typename V, typename G>
    bool operator()(V&&, G&&) {
        return ((++count) > limit);
    }
private:
    std::size_t count;
    std::size_t const limit;
};

To perform the bfs on a given graph, it will be easy:

Graph graph = get_graph();
Vertex start_vertex;
bfs_halting_visitor<VertexCounter> vis(VertexCounter(2), details::no_halting());
try {
    boost::breadth_first_search(graph, start_vertex, boost::visitor(vis));
} catch (std::runtime_error& e) {
    std::cout << e.what() << std::endl;
}

A live demo on Coliru is available to help you see all the pieces in action.