boost::graph astar algorithm without exceptions

Question

I'm reading boost::graph documentation for future usage. I'm particularly interested in A* algorithm.

Having a look to boost::graph::astar_search usage example, it seems the way to stop the algorithm is throwing an exception and catching it ouside the algorithm.

Since I don't want to throw any exception, cause exceptions handling in C++ is really complex and not very efficient, I wonder if boost::graph proposes another way to stop the algorithm when the goal has been reached.

Did anyone have an alternative example not using any exceptions ?

Answer 1

According to the FAQ, the only way to exit early from a BFS is by throwing an Exception and "see the boost mailing list for details", but I never found such details.

To not use Exceptions with the A*, you have to modify the algorithm and introduce your own visitor with a stop condition:

#include <boost/graph/astar_search.hpp>


namespace boost { namespace graph {

template < class Visitors = null_visitor >
struct stopable_astar_visitor : public astar_visitor<Visitors> {
    stopable_astar_visitor() {}
    stopable_astar_visitor(Visitors vis) : astar_visitor<Visitors>(vis) {}

    template < class Vertex, class Graph >
    bool should_stop(Vertex &v, Graph &g) {
        return true;
    }
};

template <typename VertexListGraph, typename AStarHeuristic,
          typename AStarVisitor, typename PredecessorMap,
          typename CostMap, typename DistanceMap,
          typename WeightMap,
          typename CompareFunction, typename CombineFunction,
          typename CostZero>
inline void
stoppable_astar_search_no_init_tree
  (const VertexListGraph &g,
   typename graph_traits<VertexListGraph>::vertex_descriptor s,
   AStarHeuristic h, AStarVisitor vis,
   PredecessorMap predecessor, CostMap cost,
   DistanceMap distance, WeightMap weight,
   CompareFunction compare, CombineFunction combine,
   CostZero zero)
{
  typedef typename graph_traits<VertexListGraph>::vertex_descriptor
    Vertex;
  typedef typename property_traits<DistanceMap>::value_type Distance;
  typedef d_ary_heap_indirect<
            std::pair<Distance, Vertex>,
            4,
            null_property_map<std::pair<Distance, Vertex>, std::size_t>,
            function_property_map<graph_detail::select1st<Distance, Vertex>, std::pair<Distance, Vertex> >,
            CompareFunction>
    MutableQueue;
  MutableQueue Q(
    make_function_property_map<std::pair<Distance, Vertex> >(graph_detail::select1st<Distance, Vertex>()),
    null_property_map<std::pair<Distance, Vertex>, std::size_t>(),
    compare);
    int counter = 0;
  vis.discover_vertex(s, g);
  Q.push(std::make_pair(get(cost, s), s));
  while (!Q.empty()) {
      counter++;
    Vertex v;
    Distance v_rank;
    boost::tie(v_rank, v) = Q.top();
    Q.pop();
    if (vis.should_stop(v, g)) {
        return;
    }
    vis.examine_vertex(v, g);
    BGL_FORALL_OUTEDGES_T(v, e, g, VertexListGraph) {
      Vertex w = target(e, g);
      vis.examine_edge(e, g);
      Distance e_weight = get(weight, e);
      if (compare(e_weight, zero))
        BOOST_THROW_EXCEPTION(negative_edge());
      bool decreased =
        relax(e, g, weight, predecessor, distance,
              combine, compare);
      Distance w_d = combine(get(distance, v), e_weight);
      if (decreased) {
        vis.edge_relaxed(e, g);
        Distance w_rank = combine(get(distance, w), h(w));
        put(cost, w, w_rank);
        vis.discover_vertex(w, g);
        Q.push(std::make_pair(w_rank, w));
      } else {
        vis.edge_not_relaxed(e, g);
      }
    }
    vis.finish_vertex(v, g);
  }
}
}} // end namespace boost::graph