Chris@16: 
Chris@16: 
Chris@16: //
Chris@16: //=======================================================================
Chris@16: // Copyright (c) 2004 Kristopher Beevers
Chris@16: //
Chris@16: // Distributed under the Boost Software License, Version 1.0. (See
Chris@16: // accompanying file LICENSE_1_0.txt or copy at
Chris@16: // http://www.boost.org/LICENSE_1_0.txt)
Chris@16: //=======================================================================
Chris@16: //
Chris@16: 
Chris@16: #ifndef BOOST_GRAPH_ASTAR_SEARCH_HPP
Chris@16: #define BOOST_GRAPH_ASTAR_SEARCH_HPP
Chris@16: 
Chris@16: 
Chris@16: #include <functional>
Chris@16: #include <vector>
Chris@16: #include <boost/limits.hpp>
Chris@16: #include <boost/throw_exception.hpp>
Chris@16: #include <boost/graph/named_function_params.hpp>
Chris@16: #include <boost/graph/relax.hpp>
Chris@16: #include <boost/graph/exception.hpp>
Chris@16: #include <boost/graph/breadth_first_search.hpp>
Chris@16: #include <boost/graph/iteration_macros.hpp>
Chris@16: #include <boost/graph/detail/d_ary_heap.hpp>
Chris@16: #include <boost/graph/property_maps/constant_property_map.hpp>
Chris@16: #include <boost/property_map/property_map.hpp>
Chris@16: #include <boost/property_map/vector_property_map.hpp>
Chris@16: #include <boost/property_map/function_property_map.hpp>
Chris@16: #include <boost/concept/assert.hpp>
Chris@16: 
Chris@16: namespace boost {
Chris@16: 
Chris@16: 
Chris@16:   template <class Heuristic, class Graph>
Chris@16:   struct AStarHeuristicConcept {
Chris@16:     void constraints()
Chris@16:     {
Chris@16:       BOOST_CONCEPT_ASSERT(( CopyConstructibleConcept<Heuristic> ));
Chris@16:       h(u);
Chris@16:     }
Chris@16:     Heuristic h;
Chris@16:     typename graph_traits<Graph>::vertex_descriptor u;
Chris@16:   };
Chris@16: 
Chris@16: 
Chris@16:   template <class Graph, class CostType>
Chris@16:   class astar_heuristic : public std::unary_function<
Chris@16:     typename graph_traits<Graph>::vertex_descriptor, CostType>
Chris@16:   {
Chris@16:   public:
Chris@16:     typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
Chris@16:     astar_heuristic() {}
Chris@16:     CostType operator()(Vertex u) { return static_cast<CostType>(0); }
Chris@16:   };
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16:   template <class Visitor, class Graph>
Chris@16:   struct AStarVisitorConcept {
Chris@16:     void constraints()
Chris@16:     {
Chris@16:       BOOST_CONCEPT_ASSERT(( CopyConstructibleConcept<Visitor> ));
Chris@16:       vis.initialize_vertex(u, g);
Chris@16:       vis.discover_vertex(u, g);
Chris@16:       vis.examine_vertex(u, g);
Chris@16:       vis.examine_edge(e, g);
Chris@16:       vis.edge_relaxed(e, g);
Chris@16:       vis.edge_not_relaxed(e, g);
Chris@16:       vis.black_target(e, g);
Chris@16:       vis.finish_vertex(u, g);
Chris@16:     }
Chris@16:     Visitor vis;
Chris@16:     Graph g;
Chris@16:     typename graph_traits<Graph>::vertex_descriptor u;
Chris@16:     typename graph_traits<Graph>::edge_descriptor e;
Chris@16:   };
Chris@16: 
Chris@16: 
Chris@16:   template <class Visitors = null_visitor>
Chris@16:   class astar_visitor : public bfs_visitor<Visitors> {
Chris@16:   public:
Chris@16:     astar_visitor() {}
Chris@16:     astar_visitor(Visitors vis)
Chris@16:       : bfs_visitor<Visitors>(vis) {}
Chris@16: 
Chris@16:     template <class Edge, class Graph>
Chris@16:     void edge_relaxed(Edge e, const Graph& g) {
Chris@16:       invoke_visitors(this->m_vis, e, g, on_edge_relaxed());
Chris@16:     }
Chris@16:     template <class Edge, class Graph>
Chris@16:     void edge_not_relaxed(Edge e, const Graph& g) {
Chris@16:       invoke_visitors(this->m_vis, e, g, on_edge_not_relaxed());
Chris@16:     }
Chris@16:   private:
Chris@16:     template <class Edge, class Graph>
Chris@16:     void tree_edge(Edge e, const Graph& g) {}
Chris@16:     template <class Edge, class Graph>
Chris@16:     void non_tree_edge(Edge e, const Graph& g) {}
Chris@16:   };
Chris@16:   template <class Visitors>
Chris@16:   astar_visitor<Visitors>
Chris@16:   make_astar_visitor(Visitors vis) {
Chris@16:     return astar_visitor<Visitors>(vis);
Chris@16:   }
Chris@16:   typedef astar_visitor<> default_astar_visitor;
Chris@16: 
Chris@16: 
Chris@16:   namespace detail {
Chris@16: 
Chris@16:     template <class AStarHeuristic, class UniformCostVisitor,
Chris@16:               class UpdatableQueue, class PredecessorMap,
Chris@16:               class CostMap, class DistanceMap, class WeightMap,
Chris@16:               class ColorMap, class BinaryFunction,
Chris@16:               class BinaryPredicate>
Chris@16:     struct astar_bfs_visitor
Chris@16:     {
Chris@16: 
Chris@16:       typedef typename property_traits<CostMap>::value_type C;
Chris@16:       typedef typename property_traits<ColorMap>::value_type ColorValue;
Chris@16:       typedef color_traits<ColorValue> Color;
Chris@16:       typedef typename property_traits<DistanceMap>::value_type distance_type;
Chris@16: 
Chris@16:       astar_bfs_visitor(AStarHeuristic h, UniformCostVisitor vis,
Chris@16:                         UpdatableQueue& Q, PredecessorMap p,
Chris@16:                         CostMap c, DistanceMap d, WeightMap w,
Chris@16:                         ColorMap col, BinaryFunction combine,
Chris@16:                         BinaryPredicate compare, C zero)
Chris@16:         : m_h(h), m_vis(vis), m_Q(Q), m_predecessor(p), m_cost(c),
Chris@16:           m_distance(d), m_weight(w), m_color(col),
Chris@16:           m_combine(combine), m_compare(compare), m_zero(zero) {}
Chris@16: 
Chris@16: 
Chris@16:       template <class Vertex, class Graph>
Chris@16:       void initialize_vertex(Vertex u, const Graph& g) {
Chris@16:         m_vis.initialize_vertex(u, g);
Chris@16:       }
Chris@16:       template <class Vertex, class Graph>
Chris@16:       void discover_vertex(Vertex u, const Graph& g) {
Chris@16:         m_vis.discover_vertex(u, g);
Chris@16:       }
Chris@16:       template <class Vertex, class Graph>
Chris@16:       void examine_vertex(Vertex u, const Graph& g) {
Chris@16:         m_vis.examine_vertex(u, g);
Chris@16:       }
Chris@16:       template <class Vertex, class Graph>
Chris@16:       void finish_vertex(Vertex u, const Graph& g) {
Chris@16:         m_vis.finish_vertex(u, g);
Chris@16:       }
Chris@16:       template <class Edge, class Graph>
Chris@16:       void examine_edge(Edge e, const Graph& g) {
Chris@16:         if (m_compare(get(m_weight, e), m_zero))
Chris@16:           BOOST_THROW_EXCEPTION(negative_edge());
Chris@16:         m_vis.examine_edge(e, g);
Chris@16:       }
Chris@16:       template <class Edge, class Graph>
Chris@16:       void non_tree_edge(Edge, const Graph&) {}
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16:       template <class Edge, class Graph>
Chris@16:       void tree_edge(Edge e, const Graph& g) {
Chris@16:         using boost::get;
Chris@16:         bool m_decreased =
Chris@16:           relax(e, g, m_weight, m_predecessor, m_distance,
Chris@16:                 m_combine, m_compare);
Chris@16: 
Chris@16:         if(m_decreased) {
Chris@16:           m_vis.edge_relaxed(e, g);
Chris@16:           put(m_cost, target(e, g),
Chris@16:               m_combine(get(m_distance, target(e, g)),
Chris@16:                         m_h(target(e, g))));
Chris@16:         } else
Chris@16:           m_vis.edge_not_relaxed(e, g);
Chris@16:       }
Chris@16: 
Chris@16: 
Chris@16:       template <class Edge, class Graph>
Chris@16:       void gray_target(Edge e, const Graph& g) {
Chris@16:         using boost::get;
Chris@16:         bool m_decreased =
Chris@16:           relax(e, g, m_weight, m_predecessor, m_distance,
Chris@16:                 m_combine, m_compare);
Chris@16: 
Chris@16:         if(m_decreased) {
Chris@16:           put(m_cost, target(e, g),
Chris@16:               m_combine(get(m_distance, target(e, g)),
Chris@16:                         m_h(target(e, g))));
Chris@16:           m_Q.update(target(e, g));
Chris@16:           m_vis.edge_relaxed(e, g);
Chris@16:         } else
Chris@16:           m_vis.edge_not_relaxed(e, g);
Chris@16:       }
Chris@16: 
Chris@16: 
Chris@16:       template <class Edge, class Graph>
Chris@16:       void black_target(Edge e, const Graph& g) {
Chris@16:         using boost::get;
Chris@16:         bool m_decreased =
Chris@16:           relax(e, g, m_weight, m_predecessor, m_distance,
Chris@16:                 m_combine, m_compare);
Chris@16: 
Chris@16:         if(m_decreased) {
Chris@16:           m_vis.edge_relaxed(e, g);
Chris@16:           put(m_cost, target(e, g),
Chris@16:               m_combine(get(m_distance, target(e, g)),
Chris@16:                         m_h(target(e, g))));
Chris@16:           m_Q.push(target(e, g));
Chris@16:           put(m_color, target(e, g), Color::gray());
Chris@16:           m_vis.black_target(e, g);
Chris@16:         } else
Chris@16:           m_vis.edge_not_relaxed(e, g);
Chris@16:       }
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16:       AStarHeuristic m_h;
Chris@16:       UniformCostVisitor m_vis;
Chris@16:       UpdatableQueue& m_Q;
Chris@16:       PredecessorMap m_predecessor;
Chris@16:       CostMap m_cost;
Chris@16:       DistanceMap m_distance;
Chris@16:       WeightMap m_weight;
Chris@16:       ColorMap m_color;
Chris@16:       BinaryFunction m_combine;
Chris@16:       BinaryPredicate m_compare;
Chris@16:       C m_zero;
Chris@16: 
Chris@16:     };
Chris@16: 
Chris@16:   } // namespace detail
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16:   template <typename VertexListGraph, typename AStarHeuristic,
Chris@16:             typename AStarVisitor, typename PredecessorMap,
Chris@16:             typename CostMap, typename DistanceMap,
Chris@16:             typename WeightMap, typename ColorMap,
Chris@16:             typename VertexIndexMap,
Chris@16:             typename CompareFunction, typename CombineFunction,
Chris@16:             typename CostInf, typename CostZero>
Chris@16:   inline void
Chris@16:   astar_search_no_init
Chris@16:     (const VertexListGraph &g,
Chris@16:      typename graph_traits<VertexListGraph>::vertex_descriptor s,
Chris@16:      AStarHeuristic h, AStarVisitor vis,
Chris@16:      PredecessorMap predecessor, CostMap cost,
Chris@16:      DistanceMap distance, WeightMap weight,
Chris@16:      ColorMap color, VertexIndexMap index_map,
Chris@16:      CompareFunction compare, CombineFunction combine,
Chris@16:      CostInf /*inf*/, CostZero zero)
Chris@16:   {
Chris@16:     typedef typename graph_traits<VertexListGraph>::vertex_descriptor
Chris@16:       Vertex;
Chris@16:     typedef boost::vector_property_map<std::size_t, VertexIndexMap> IndexInHeapMap;
Chris@16:     IndexInHeapMap index_in_heap(index_map);
Chris@16:     typedef d_ary_heap_indirect<Vertex, 4, IndexInHeapMap, CostMap, CompareFunction>
Chris@16:       MutableQueue;
Chris@16:     MutableQueue Q(cost, index_in_heap, compare);
Chris@16: 
Chris@16:     detail::astar_bfs_visitor<AStarHeuristic, AStarVisitor,
Chris@16:         MutableQueue, PredecessorMap, CostMap, DistanceMap,
Chris@16:         WeightMap, ColorMap, CombineFunction, CompareFunction>
Chris@16:       bfs_vis(h, vis, Q, predecessor, cost, distance, weight,
Chris@16:               color, combine, compare, zero);
Chris@16: 
Chris@16:     breadth_first_visit(g, s, Q, bfs_vis, color);
Chris@16:   }
Chris@16: 
Chris@16:   namespace graph_detail {
Chris@16:     template <typename A, typename B>
Chris@16:     struct select1st {
Chris@16:       typedef std::pair<A, B> argument_type;
Chris@16:       typedef A result_type;
Chris@16:       A operator()(const std::pair<A, B>& p) const {return p.first;}
Chris@16:     };
Chris@16:   }
Chris@16: 
Chris@16:   template <typename VertexListGraph, typename AStarHeuristic,
Chris@16:             typename AStarVisitor, typename PredecessorMap,
Chris@16:             typename CostMap, typename DistanceMap,
Chris@16:             typename WeightMap,
Chris@16:             typename CompareFunction, typename CombineFunction,
Chris@16:             typename CostInf, typename CostZero>
Chris@16:   inline void
Chris@16:   astar_search_no_init_tree
Chris@16:     (const VertexListGraph &g,
Chris@16:      typename graph_traits<VertexListGraph>::vertex_descriptor s,
Chris@16:      AStarHeuristic h, AStarVisitor vis,
Chris@16:      PredecessorMap predecessor, CostMap cost,
Chris@16:      DistanceMap distance, WeightMap weight,
Chris@16:      CompareFunction compare, CombineFunction combine,
Chris@16:      CostInf /*inf*/, CostZero zero)
Chris@16:   {
Chris@16:     typedef typename graph_traits<VertexListGraph>::vertex_descriptor
Chris@16:       Vertex;
Chris@16:     typedef typename property_traits<DistanceMap>::value_type Distance;
Chris@16:     typedef d_ary_heap_indirect<
Chris@16:               std::pair<Distance, Vertex>,
Chris@16:               4,
Chris@16:               null_property_map<std::pair<Distance, Vertex>, std::size_t>,
Chris@16:               function_property_map<graph_detail::select1st<Distance, Vertex>, std::pair<Distance, Vertex> >,
Chris@16:               CompareFunction>
Chris@16:       MutableQueue;
Chris@16:     MutableQueue Q(
Chris@16:       make_function_property_map<std::pair<Distance, Vertex> >(graph_detail::select1st<Distance, Vertex>()),
Chris@16:       null_property_map<std::pair<Distance, Vertex>, std::size_t>(),
Chris@16:       compare);
Chris@16: 
Chris@16:     vis.discover_vertex(s, g);
Chris@16:     Q.push(std::make_pair(get(cost, s), s));
Chris@16:     while (!Q.empty()) {
Chris@16:       Vertex v;
Chris@16:       Distance v_rank;
Chris@16:       boost::tie(v_rank, v) = Q.top();
Chris@16:       Q.pop();
Chris@16:       vis.examine_vertex(v, g);
Chris@16:       BGL_FORALL_OUTEDGES_T(v, e, g, VertexListGraph) {
Chris@16:         Vertex w = target(e, g);
Chris@16:         vis.examine_edge(e, g);
Chris@16:         Distance e_weight = get(weight, e);
Chris@16:         if (compare(e_weight, zero))
Chris@16:           BOOST_THROW_EXCEPTION(negative_edge());
Chris@16:         bool decreased =
Chris@16:           relax(e, g, weight, predecessor, distance,
Chris@16:                 combine, compare);
Chris@16:         Distance w_d = combine(get(distance, v), e_weight);
Chris@16:         if (decreased) {
Chris@16:           vis.edge_relaxed(e, g);
Chris@16:           Distance w_rank = combine(get(distance, w), h(w));
Chris@16:           put(cost, w, w_rank);
Chris@16:           vis.discover_vertex(w, g);
Chris@16:           Q.push(std::make_pair(w_rank, w));
Chris@16:         } else {
Chris@16:           vis.edge_not_relaxed(e, g);
Chris@16:         }
Chris@16:       }
Chris@16:       vis.finish_vertex(v, g);
Chris@16:     }
Chris@16:   }
Chris@16: 
Chris@16:   // Non-named parameter interface
Chris@16:   template <typename VertexListGraph, typename AStarHeuristic,
Chris@16:             typename AStarVisitor, typename PredecessorMap,
Chris@16:             typename CostMap, typename DistanceMap,
Chris@16:             typename WeightMap, typename VertexIndexMap,
Chris@16:             typename ColorMap,
Chris@16:             typename CompareFunction, typename CombineFunction,
Chris@16:             typename CostInf, typename CostZero>
Chris@16:   inline void
Chris@16:   astar_search
Chris@16:     (const VertexListGraph &g,
Chris@16:      typename graph_traits<VertexListGraph>::vertex_descriptor s,
Chris@16:      AStarHeuristic h, AStarVisitor vis,
Chris@16:      PredecessorMap predecessor, CostMap cost,
Chris@16:      DistanceMap distance, WeightMap weight,
Chris@16:      VertexIndexMap index_map, ColorMap color,
Chris@16:      CompareFunction compare, CombineFunction combine,
Chris@16:      CostInf inf, CostZero zero)
Chris@16:   {
Chris@16: 
Chris@16:     typedef typename property_traits<ColorMap>::value_type ColorValue;
Chris@16:     typedef color_traits<ColorValue> Color;
Chris@16:     typename graph_traits<VertexListGraph>::vertex_iterator ui, ui_end;
Chris@16:     for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui) {
Chris@16:       put(color, *ui, Color::white());
Chris@16:       put(distance, *ui, inf);
Chris@16:       put(cost, *ui, inf);
Chris@16:       put(predecessor, *ui, *ui);
Chris@16:       vis.initialize_vertex(*ui, g);
Chris@16:     }
Chris@16:     put(distance, s, zero);
Chris@16:     put(cost, s, h(s));
Chris@16: 
Chris@16:     astar_search_no_init
Chris@16:       (g, s, h, vis, predecessor, cost, distance, weight,
Chris@16:        color, index_map, compare, combine, inf, zero);
Chris@16: 
Chris@16:   }
Chris@16: 
Chris@16:   // Non-named parameter interface
Chris@16:   template <typename VertexListGraph, typename AStarHeuristic,
Chris@16:             typename AStarVisitor, typename PredecessorMap,
Chris@16:             typename CostMap, typename DistanceMap,
Chris@16:             typename WeightMap,
Chris@16:             typename CompareFunction, typename CombineFunction,
Chris@16:             typename CostInf, typename CostZero>
Chris@16:   inline void
Chris@16:   astar_search_tree
Chris@16:     (const VertexListGraph &g,
Chris@16:      typename graph_traits<VertexListGraph>::vertex_descriptor s,
Chris@16:      AStarHeuristic h, AStarVisitor vis,
Chris@16:      PredecessorMap predecessor, CostMap cost,
Chris@16:      DistanceMap distance, WeightMap weight,
Chris@16:      CompareFunction compare, CombineFunction combine,
Chris@16:      CostInf inf, CostZero zero)
Chris@16:   {
Chris@16: 
Chris@16:     typename graph_traits<VertexListGraph>::vertex_iterator ui, ui_end;
Chris@16:     for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui) {
Chris@16:       put(distance, *ui, inf);
Chris@16:       put(cost, *ui, inf);
Chris@16:       put(predecessor, *ui, *ui);
Chris@16:       vis.initialize_vertex(*ui, g);
Chris@16:     }
Chris@16:     put(distance, s, zero);
Chris@16:     put(cost, s, h(s));
Chris@16: 
Chris@16:     astar_search_no_init_tree
Chris@16:       (g, s, h, vis, predecessor, cost, distance, weight,
Chris@16:        compare, combine, inf, zero);
Chris@16: 
Chris@16:   }
Chris@16: 
Chris@16:   // Named parameter interfaces
Chris@16:   template <typename VertexListGraph,
Chris@16:             typename AStarHeuristic,
Chris@16:             typename P, typename T, typename R>
Chris@16:   void
Chris@16:   astar_search
Chris@16:     (const VertexListGraph &g,
Chris@16:      typename graph_traits<VertexListGraph>::vertex_descriptor s,
Chris@16:      AStarHeuristic h, const bgl_named_params<P, T, R>& params)
Chris@16:   {
Chris@16:     using namespace boost::graph::keywords;
Chris@16:     typedef bgl_named_params<P, T, R> params_type;
Chris@16:     BOOST_GRAPH_DECLARE_CONVERTED_PARAMETERS(params_type, params)
Chris@16: 
Chris@16:     // Distance type is the value type of the distance map if there is one,
Chris@16:     // otherwise the value type of the weight map.
Chris@16:     typedef
Chris@16:       typename detail::override_const_property_result<
Chris@16:                  arg_pack_type, tag::weight_map, edge_weight_t, VertexListGraph>::type
Chris@16:       weight_map_type;
Chris@16:     typedef typename boost::property_traits<weight_map_type>::value_type W;
Chris@16:     typedef
Chris@16:       typename detail::map_maker<VertexListGraph, arg_pack_type, tag::distance_map, W>::map_type
Chris@16:       distance_map_type;
Chris@16:     typedef typename boost::property_traits<distance_map_type>::value_type D;
Chris@16:     const D inf = arg_pack[_distance_inf || detail::get_max<D>()];
Chris@16: 
Chris@16:     astar_search
Chris@16:       (g, s, h,
Chris@16:        arg_pack[_visitor | make_astar_visitor(null_visitor())],
Chris@16:        arg_pack[_predecessor_map | dummy_property_map()],
Chris@16:        detail::make_property_map_from_arg_pack_gen<tag::rank_map, D>(D())(g, arg_pack),
Chris@16:        detail::make_property_map_from_arg_pack_gen<tag::distance_map, W>(W())(g, arg_pack),
Chris@16:        detail::override_const_property(arg_pack, _weight_map, g, edge_weight),
Chris@16:        detail::override_const_property(arg_pack, _vertex_index_map, g, vertex_index),
Chris@16:        detail::make_color_map_from_arg_pack(g, arg_pack),
Chris@16:        arg_pack[_distance_compare | std::less<D>()],
Chris@16:        arg_pack[_distance_combine | closed_plus<D>(inf)],
Chris@16:        inf,
Chris@16:        arg_pack[_distance_zero | D()]);
Chris@16:   }
Chris@16: 
Chris@16:   // Named parameter interfaces
Chris@16:   template <typename VertexListGraph,
Chris@16:             typename AStarHeuristic,
Chris@16:             typename P, typename T, typename R>
Chris@16:   void
Chris@16:   astar_search_tree
Chris@16:     (const VertexListGraph &g,
Chris@16:      typename graph_traits<VertexListGraph>::vertex_descriptor s,
Chris@16:      AStarHeuristic h, const bgl_named_params<P, T, R>& params)
Chris@16:   {
Chris@16:     using namespace boost::graph::keywords;
Chris@16:     typedef bgl_named_params<P, T, R> params_type;
Chris@16:     BOOST_GRAPH_DECLARE_CONVERTED_PARAMETERS(params_type, params)
Chris@16: 
Chris@16:     // Distance type is the value type of the distance map if there is one,
Chris@16:     // otherwise the value type of the weight map.
Chris@16:     typedef
Chris@16:       typename detail::override_const_property_result<
Chris@16:                  arg_pack_type, tag::weight_map, edge_weight_t, VertexListGraph>::type
Chris@16:       weight_map_type;
Chris@16:     typedef typename boost::property_traits<weight_map_type>::value_type W;
Chris@16:     typedef
Chris@16:       typename detail::map_maker<VertexListGraph, arg_pack_type, tag::distance_map, W>::map_type
Chris@16:       distance_map_type;
Chris@16:     typedef typename boost::property_traits<distance_map_type>::value_type D;
Chris@16:     const D inf = arg_pack[_distance_inf || detail::get_max<D>()];
Chris@16: 
Chris@16:     astar_search_tree
Chris@16:       (g, s, h,
Chris@16:        arg_pack[_visitor | make_astar_visitor(null_visitor())],
Chris@16:        arg_pack[_predecessor_map | dummy_property_map()],
Chris@16:        detail::make_property_map_from_arg_pack_gen<tag::rank_map, D>(D())(g, arg_pack),
Chris@16:        detail::make_property_map_from_arg_pack_gen<tag::distance_map, W>(W())(g, arg_pack),
Chris@16:        detail::override_const_property(arg_pack, _weight_map, g, edge_weight),
Chris@16:        arg_pack[_distance_compare | std::less<D>()],
Chris@16:        arg_pack[_distance_combine | closed_plus<D>(inf)],
Chris@16:        inf,
Chris@16:        arg_pack[_distance_zero | D()]);
Chris@16:   }
Chris@16: 
Chris@16:   template <typename VertexListGraph,
Chris@16:             typename AStarHeuristic,
Chris@16:             typename P, typename T, typename R>
Chris@16:   void
Chris@16:   astar_search_no_init
Chris@16:     (const VertexListGraph &g,
Chris@16:      typename graph_traits<VertexListGraph>::vertex_descriptor s,
Chris@16:      AStarHeuristic h, const bgl_named_params<P, T, R>& params)
Chris@16:   {
Chris@16:     using namespace boost::graph::keywords;
Chris@16:     typedef bgl_named_params<P, T, R> params_type;
Chris@16:     BOOST_GRAPH_DECLARE_CONVERTED_PARAMETERS(params_type, params)
Chris@16:     typedef
Chris@16:       typename detail::override_const_property_result<
Chris@16:                  arg_pack_type, tag::weight_map, edge_weight_t, VertexListGraph>::type
Chris@16:                weight_map_type;
Chris@16:     typedef typename boost::property_traits<weight_map_type>::value_type D;
Chris@16:     const D inf = arg_pack[_distance_inf || detail::get_max<D>()];
Chris@16:     astar_search_no_init
Chris@16:       (g, s, h,
Chris@16:        arg_pack[_visitor | make_astar_visitor(null_visitor())],
Chris@16:        arg_pack[_predecessor_map | dummy_property_map()],
Chris@16:        detail::make_property_map_from_arg_pack_gen<tag::rank_map, D>(D())(g, arg_pack),
Chris@16:        detail::make_property_map_from_arg_pack_gen<tag::distance_map, D>(D())(g, arg_pack),
Chris@16:        detail::override_const_property(arg_pack, _weight_map, g, edge_weight),
Chris@16:        detail::make_color_map_from_arg_pack(g, arg_pack),
Chris@16:        detail::override_const_property(arg_pack, _vertex_index_map, g, vertex_index),
Chris@16:        arg_pack[_distance_compare | std::less<D>()],
Chris@16:        arg_pack[_distance_combine | closed_plus<D>(inf)],
Chris@16:        inf,
Chris@16:        arg_pack[_distance_zero | D()]);
Chris@16:   }
Chris@16: 
Chris@16:   template <typename VertexListGraph,
Chris@16:             typename AStarHeuristic,
Chris@16:             typename P, typename T, typename R>
Chris@16:   void
Chris@16:   astar_search_no_init_tree
Chris@16:     (const VertexListGraph &g,
Chris@16:      typename graph_traits<VertexListGraph>::vertex_descriptor s,
Chris@16:      AStarHeuristic h, const bgl_named_params<P, T, R>& params)
Chris@16:   {
Chris@16:     using namespace boost::graph::keywords;
Chris@16:     typedef bgl_named_params<P, T, R> params_type;
Chris@16:     BOOST_GRAPH_DECLARE_CONVERTED_PARAMETERS(params_type, params)
Chris@16:     typedef
Chris@16:       typename detail::override_const_property_result<
Chris@16:                  arg_pack_type, tag::weight_map, edge_weight_t, VertexListGraph>::type
Chris@16:                weight_map_type;
Chris@16:     typedef typename boost::property_traits<weight_map_type>::value_type D;
Chris@16:     const D inf = arg_pack[_distance_inf || detail::get_max<D>()];
Chris@16:     astar_search_no_init_tree
Chris@16:       (g, s, h,
Chris@16:        arg_pack[_visitor | make_astar_visitor(null_visitor())],
Chris@16:        arg_pack[_predecessor_map | dummy_property_map()],
Chris@16:        detail::make_property_map_from_arg_pack_gen<tag::rank_map, D>(D())(g, arg_pack),
Chris@16:        detail::make_property_map_from_arg_pack_gen<tag::distance_map, D>(D())(g, arg_pack),
Chris@16:        detail::override_const_property(arg_pack, _weight_map, g, edge_weight),
Chris@16:        arg_pack[_distance_compare | std::less<D>()],
Chris@16:        arg_pack[_distance_combine | closed_plus<D>(inf)],
Chris@16:        inf,
Chris@16:        arg_pack[_distance_zero | D()]);
Chris@16:   }
Chris@16: 
Chris@16: } // namespace boost
Chris@16: 
Chris@16: #endif // BOOST_GRAPH_ASTAR_SEARCH_HPP