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 ?

`cause exceptions handling in C++ is really complex and not very efficient` Where did you get this from? — Collin Dauphinee, Apr 26 '13 at 21:54
@dauphic Had a look of what really happens in assembly when an exception is caught (really lots of code runs !). Also made test some "return code VS exception" for performance comparison. Exceptions should remain exceptional, and I think using it for algorithm purpose is not a very good idea. — neodelphi, Apr 26 '13 at 22:11

score 6 · Accepted Answer · answered May 29 '13 at 13:50

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

Thanks for mentionning the FAQ. Came to the same conclusion that it is required to modify the algorithm. — neodelphi, May 30 '13 at 20:13

boost::graph astar algorithm without exceptions

1 Answers1

Linked