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