1
2
3 //
4 //=======================================================================
5 // Copyright (c) 2004 Kristopher Beevers
6 //
7 // Distributed under the Boost Software License, Version 1.0. (See
8 // accompanying file LICENSE_1_0.txt or copy at
9 // http://www.boost.org/LICENSE_1_0.txt)
10 //=======================================================================
11 //
12
13 #ifndef BOOST_GRAPH_ASTAR_SEARCH_HPP
14 #define BOOST_GRAPH_ASTAR_SEARCH_HPP
15
16 #include <functional>
17 #include <vector>
18 #include <boost/limits.hpp>
19 #include <boost/throw_exception.hpp>
20 #include <boost/graph/named_function_params.hpp>
21 #include <boost/graph/relax.hpp>
22 #include <boost/graph/exception.hpp>
23 #include <boost/graph/breadth_first_search.hpp>
24 #include <boost/graph/iteration_macros.hpp>
25 #include <boost/graph/detail/d_ary_heap.hpp>
26 #include <boost/graph/property_maps/constant_property_map.hpp>
27 #include <boost/property_map/property_map.hpp>
28 #include <boost/property_map/vector_property_map.hpp>
29 #include <boost/property_map/function_property_map.hpp>
30 #include <boost/concept/assert.hpp>
31
32 namespace boost
33 {
34
35 template < class Heuristic, class Graph > struct AStarHeuristicConcept
36 {
constraintsboost::AStarHeuristicConcept37 void constraints()
38 {
39 BOOST_CONCEPT_ASSERT((CopyConstructibleConcept< Heuristic >));
40 h(u);
41 }
42 Heuristic h;
43 typename graph_traits< Graph >::vertex_descriptor u;
44 };
45
46 template < class Graph, class CostType > class astar_heuristic
47 {
48 public:
49 typedef typename graph_traits< Graph >::vertex_descriptor Vertex;
50 typedef Vertex argument_type;
51 typedef CostType result_type;
astar_heuristic()52 astar_heuristic() {}
operator ()(Vertex u)53 CostType operator()(Vertex u) { return static_cast< CostType >(0); }
54 };
55
56 template < class Visitor, class Graph > struct AStarVisitorConcept
57 {
constraintsboost::AStarVisitorConcept58 void constraints()
59 {
60 BOOST_CONCEPT_ASSERT((CopyConstructibleConcept< Visitor >));
61 vis.initialize_vertex(u, g);
62 vis.discover_vertex(u, g);
63 vis.examine_vertex(u, g);
64 vis.examine_edge(e, g);
65 vis.edge_relaxed(e, g);
66 vis.edge_not_relaxed(e, g);
67 vis.black_target(e, g);
68 vis.finish_vertex(u, g);
69 }
70 Visitor vis;
71 Graph g;
72 typename graph_traits< Graph >::vertex_descriptor u;
73 typename graph_traits< Graph >::edge_descriptor e;
74 };
75
76 template < class Visitors = null_visitor >
77 class astar_visitor : public bfs_visitor< Visitors >
78 {
79 public:
astar_visitor()80 astar_visitor() {}
astar_visitor(Visitors vis)81 astar_visitor(Visitors vis) : bfs_visitor< Visitors >(vis) {}
82
83 template < class Edge, class Graph >
edge_relaxed(Edge e,const Graph & g)84 void edge_relaxed(Edge e, const Graph& g)
85 {
86 invoke_visitors(this->m_vis, e, g, on_edge_relaxed());
87 }
88 template < class Edge, class Graph >
edge_not_relaxed(Edge e,const Graph & g)89 void edge_not_relaxed(Edge e, const Graph& g)
90 {
91 invoke_visitors(this->m_vis, e, g, on_edge_not_relaxed());
92 }
93
94 private:
tree_edge(Edge e,const Graph & g)95 template < class Edge, class Graph > void tree_edge(Edge e, const Graph& g)
96 {
97 }
98 template < class Edge, class Graph >
non_tree_edge(Edge e,const Graph & g)99 void non_tree_edge(Edge e, const Graph& g)
100 {
101 }
102 };
103 template < class Visitors >
make_astar_visitor(Visitors vis)104 astar_visitor< Visitors > make_astar_visitor(Visitors vis)
105 {
106 return astar_visitor< Visitors >(vis);
107 }
108 typedef astar_visitor<> default_astar_visitor;
109
110 namespace detail
111 {
112
113 template < class AStarHeuristic, class UniformCostVisitor,
114 class UpdatableQueue, class PredecessorMap, class CostMap,
115 class DistanceMap, class WeightMap, class ColorMap,
116 class BinaryFunction, class BinaryPredicate >
117 struct astar_bfs_visitor
118 {
119
120 typedef typename property_traits< CostMap >::value_type C;
121 typedef typename property_traits< ColorMap >::value_type ColorValue;
122 typedef color_traits< ColorValue > Color;
123 typedef
124 typename property_traits< DistanceMap >::value_type distance_type;
125
astar_bfs_visitorboost::detail::astar_bfs_visitor126 astar_bfs_visitor(AStarHeuristic h, UniformCostVisitor vis,
127 UpdatableQueue& Q, PredecessorMap p, CostMap c, DistanceMap d,
128 WeightMap w, ColorMap col, BinaryFunction combine,
129 BinaryPredicate compare, C zero)
130 : m_h(h)
131 , m_vis(vis)
132 , m_Q(Q)
133 , m_predecessor(p)
134 , m_cost(c)
135 , m_distance(d)
136 , m_weight(w)
137 , m_color(col)
138 , m_combine(combine)
139 , m_compare(compare)
140 , m_zero(zero)
141 {
142 }
143
144 template < class Vertex, class Graph >
initialize_vertexboost::detail::astar_bfs_visitor145 void initialize_vertex(Vertex u, const Graph& g)
146 {
147 m_vis.initialize_vertex(u, g);
148 }
149 template < class Vertex, class Graph >
discover_vertexboost::detail::astar_bfs_visitor150 void discover_vertex(Vertex u, const Graph& g)
151 {
152 m_vis.discover_vertex(u, g);
153 }
154 template < class Vertex, class Graph >
examine_vertexboost::detail::astar_bfs_visitor155 void examine_vertex(Vertex u, const Graph& g)
156 {
157 m_vis.examine_vertex(u, g);
158 }
159 template < class Vertex, class Graph >
finish_vertexboost::detail::astar_bfs_visitor160 void finish_vertex(Vertex u, const Graph& g)
161 {
162 m_vis.finish_vertex(u, g);
163 }
164 template < class Edge, class Graph >
examine_edgeboost::detail::astar_bfs_visitor165 void examine_edge(Edge e, const Graph& g)
166 {
167 if (m_compare(get(m_weight, e), m_zero))
168 BOOST_THROW_EXCEPTION(negative_edge());
169 m_vis.examine_edge(e, g);
170 }
171 template < class Edge, class Graph >
non_tree_edgeboost::detail::astar_bfs_visitor172 void non_tree_edge(Edge, const Graph&)
173 {
174 }
175
176 template < class Edge, class Graph >
tree_edgeboost::detail::astar_bfs_visitor177 void tree_edge(Edge e, const Graph& g)
178 {
179 using boost::get;
180 bool m_decreased = relax(e, g, m_weight, m_predecessor, m_distance,
181 m_combine, m_compare);
182
183 if (m_decreased)
184 {
185 m_vis.edge_relaxed(e, g);
186 put(m_cost, target(e, g),
187 m_combine(
188 get(m_distance, target(e, g)), m_h(target(e, g))));
189 }
190 else
191 m_vis.edge_not_relaxed(e, g);
192 }
193
194 template < class Edge, class Graph >
gray_targetboost::detail::astar_bfs_visitor195 void gray_target(Edge e, const Graph& g)
196 {
197 using boost::get;
198 bool m_decreased = relax(e, g, m_weight, m_predecessor, m_distance,
199 m_combine, m_compare);
200
201 if (m_decreased)
202 {
203 put(m_cost, target(e, g),
204 m_combine(
205 get(m_distance, target(e, g)), m_h(target(e, g))));
206 m_Q.update(target(e, g));
207 m_vis.edge_relaxed(e, g);
208 }
209 else
210 m_vis.edge_not_relaxed(e, g);
211 }
212
213 template < class Edge, class Graph >
black_targetboost::detail::astar_bfs_visitor214 void black_target(Edge e, const Graph& g)
215 {
216 using boost::get;
217 bool m_decreased = relax(e, g, m_weight, m_predecessor, m_distance,
218 m_combine, m_compare);
219
220 if (m_decreased)
221 {
222 m_vis.edge_relaxed(e, g);
223 put(m_cost, target(e, g),
224 m_combine(
225 get(m_distance, target(e, g)), m_h(target(e, g))));
226 m_Q.push(target(e, g));
227 put(m_color, target(e, g), Color::gray());
228 m_vis.black_target(e, g);
229 }
230 else
231 m_vis.edge_not_relaxed(e, g);
232 }
233
234 AStarHeuristic m_h;
235 UniformCostVisitor m_vis;
236 UpdatableQueue& m_Q;
237 PredecessorMap m_predecessor;
238 CostMap m_cost;
239 DistanceMap m_distance;
240 WeightMap m_weight;
241 ColorMap m_color;
242 BinaryFunction m_combine;
243 BinaryPredicate m_compare;
244 C m_zero;
245 };
246
247 } // namespace detail
248
249 template < typename VertexListGraph, typename AStarHeuristic,
250 typename AStarVisitor, typename PredecessorMap, typename CostMap,
251 typename DistanceMap, typename WeightMap, typename ColorMap,
252 typename VertexIndexMap, typename CompareFunction, typename CombineFunction,
253 typename CostInf, typename CostZero >
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,CostZero zero)254 inline void astar_search_no_init(const VertexListGraph& g,
255 typename graph_traits< VertexListGraph >::vertex_descriptor s,
256 AStarHeuristic h, AStarVisitor vis, PredecessorMap predecessor,
257 CostMap cost, DistanceMap distance, WeightMap weight, ColorMap color,
258 VertexIndexMap index_map, CompareFunction compare, CombineFunction combine,
259 CostInf /*inf*/, CostZero zero)
260 {
261 typedef typename graph_traits< VertexListGraph >::vertex_descriptor Vertex;
262 typedef boost::vector_property_map< std::size_t, VertexIndexMap >
263 IndexInHeapMap;
264 IndexInHeapMap index_in_heap(index_map);
265 typedef d_ary_heap_indirect< Vertex, 4, IndexInHeapMap, CostMap,
266 CompareFunction >
267 MutableQueue;
268 MutableQueue Q(cost, index_in_heap, compare);
269
270 detail::astar_bfs_visitor< AStarHeuristic, AStarVisitor, MutableQueue,
271 PredecessorMap, CostMap, DistanceMap, WeightMap, ColorMap,
272 CombineFunction, CompareFunction >
273 bfs_vis(h, vis, Q, predecessor, cost, distance, weight, color, combine,
274 compare, zero);
275
276 breadth_first_visit(g, s, Q, bfs_vis, color);
277 }
278
279 namespace graph_detail
280 {
281 template < typename A, typename B > struct select1st
282 {
283 typedef std::pair< A, B > argument_type;
284 typedef A result_type;
operator ()boost::graph_detail::select1st285 A operator()(const std::pair< A, B >& p) const { return p.first; }
286 };
287 }
288
289 template < typename VertexListGraph, typename AStarHeuristic,
290 typename AStarVisitor, typename PredecessorMap, typename CostMap,
291 typename DistanceMap, typename WeightMap, typename CompareFunction,
292 typename CombineFunction, typename CostInf, typename CostZero >
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,CostZero zero)293 inline void astar_search_no_init_tree(const VertexListGraph& g,
294 typename graph_traits< VertexListGraph >::vertex_descriptor s,
295 AStarHeuristic h, AStarVisitor vis, PredecessorMap predecessor,
296 CostMap cost, DistanceMap distance, WeightMap weight,
297 CompareFunction compare, CombineFunction combine, CostInf /*inf*/,
298 CostZero zero)
299 {
300 typedef typename graph_traits< VertexListGraph >::vertex_descriptor Vertex;
301 typedef typename property_traits< DistanceMap >::value_type Distance;
302 typedef d_ary_heap_indirect< std::pair< Distance, Vertex >, 4,
303 null_property_map< std::pair< Distance, Vertex >, std::size_t >,
304 function_property_map< graph_detail::select1st< Distance, Vertex >,
305 std::pair< Distance, Vertex > >,
306 CompareFunction >
307 MutableQueue;
308 MutableQueue Q(make_function_property_map< std::pair< Distance, Vertex > >(
309 graph_detail::select1st< Distance, Vertex >()),
310 null_property_map< std::pair< Distance, Vertex >, std::size_t >(),
311 compare);
312
313 vis.discover_vertex(s, g);
314 Q.push(std::make_pair(get(cost, s), s));
315 while (!Q.empty())
316 {
317 Vertex v;
318 Distance v_rank;
319 boost::tie(v_rank, v) = Q.top();
320 Q.pop();
321 vis.examine_vertex(v, g);
322 BGL_FORALL_OUTEDGES_T(v, e, g, VertexListGraph)
323 {
324 Vertex w = target(e, g);
325 vis.examine_edge(e, g);
326 Distance e_weight = get(weight, e);
327 if (compare(e_weight, zero))
328 BOOST_THROW_EXCEPTION(negative_edge());
329 bool decreased
330 = relax(e, g, weight, predecessor, distance, combine, compare);
331 combine(get(distance, v), e_weight);
332 if (decreased)
333 {
334 vis.edge_relaxed(e, g);
335 Distance w_rank = combine(get(distance, w), h(w));
336 put(cost, w, w_rank);
337 vis.discover_vertex(w, g);
338 Q.push(std::make_pair(w_rank, w));
339 }
340 else
341 {
342 vis.edge_not_relaxed(e, g);
343 }
344 }
345 vis.finish_vertex(v, g);
346 }
347 }
348
349 // Non-named parameter interface
350 template < typename VertexListGraph, typename AStarHeuristic,
351 typename AStarVisitor, typename PredecessorMap, typename CostMap,
352 typename DistanceMap, typename WeightMap, typename VertexIndexMap,
353 typename ColorMap, typename CompareFunction, typename CombineFunction,
354 typename CostInf, typename CostZero >
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)355 inline void astar_search(const VertexListGraph& g,
356 typename graph_traits< VertexListGraph >::vertex_descriptor s,
357 AStarHeuristic h, AStarVisitor vis, PredecessorMap predecessor,
358 CostMap cost, DistanceMap distance, WeightMap weight,
359 VertexIndexMap index_map, ColorMap color, CompareFunction compare,
360 CombineFunction combine, CostInf inf, CostZero zero)
361 {
362
363 typedef typename property_traits< ColorMap >::value_type ColorValue;
364 typedef color_traits< ColorValue > Color;
365 typename graph_traits< VertexListGraph >::vertex_iterator ui, ui_end;
366 for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui)
367 {
368 put(color, *ui, Color::white());
369 put(distance, *ui, inf);
370 put(cost, *ui, inf);
371 put(predecessor, *ui, *ui);
372 vis.initialize_vertex(*ui, g);
373 }
374 put(distance, s, zero);
375 put(cost, s, h(s));
376
377 astar_search_no_init(g, s, h, vis, predecessor, cost, distance, weight,
378 color, index_map, compare, combine, inf, zero);
379 }
380
381 // Non-named parameter interface
382 template < typename VertexListGraph, typename AStarHeuristic,
383 typename AStarVisitor, typename PredecessorMap, typename CostMap,
384 typename DistanceMap, typename WeightMap, typename CompareFunction,
385 typename CombineFunction, typename CostInf, typename CostZero >
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)386 inline void astar_search_tree(const VertexListGraph& g,
387 typename graph_traits< VertexListGraph >::vertex_descriptor s,
388 AStarHeuristic h, AStarVisitor vis, PredecessorMap predecessor,
389 CostMap cost, DistanceMap distance, WeightMap weight,
390 CompareFunction compare, CombineFunction combine, CostInf inf,
391 CostZero zero)
392 {
393
394 typename graph_traits< VertexListGraph >::vertex_iterator ui, ui_end;
395 for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui)
396 {
397 put(distance, *ui, inf);
398 put(cost, *ui, inf);
399 put(predecessor, *ui, *ui);
400 vis.initialize_vertex(*ui, g);
401 }
402 put(distance, s, zero);
403 put(cost, s, h(s));
404
405 astar_search_no_init_tree(g, s, h, vis, predecessor, cost, distance, weight,
406 compare, combine, inf, zero);
407 }
408
409 // Named parameter interfaces
410 template < typename VertexListGraph, typename AStarHeuristic, typename P,
411 typename T, typename R >
astar_search(const VertexListGraph & g,typename graph_traits<VertexListGraph>::vertex_descriptor s,AStarHeuristic h,const bgl_named_params<P,T,R> & params)412 void astar_search(const VertexListGraph& g,
413 typename graph_traits< VertexListGraph >::vertex_descriptor s,
414 AStarHeuristic h, const bgl_named_params< P, T, R >& params)
415 {
416 using namespace boost::graph::keywords;
417 typedef bgl_named_params< P, T, R > params_type;
418 BOOST_GRAPH_DECLARE_CONVERTED_PARAMETERS(params_type, params)
419
420 // Distance type is the value type of the distance map if there is one,
421 // otherwise the value type of the weight map.
422 typedef
423 typename boost::detail::override_const_property_result< arg_pack_type,
424 boost::graph::keywords::tag::weight_map, edge_weight_t,
425 VertexListGraph >::type weight_map_type;
426 typedef typename boost::property_traits< weight_map_type >::value_type D;
427 const D inf = arg_pack[_distance_inf || detail::get_max< D >()];
428 const D zero_actual = D();
429 const D zero_d = arg_pack[_distance_zero | zero_actual];
430 null_visitor null_vis;
431 astar_visitor< null_visitor > default_visitor(null_vis);
432 typename boost::parameter::binding< arg_pack_type,
433 boost::graph::keywords::tag::visitor, dummy_property_map& >::type vis
434 = arg_pack[_visitor | default_visitor];
435 dummy_property_map dummy_prop;
436 typename boost::parameter::binding< arg_pack_type,
437 boost::graph::keywords::tag::predecessor_map,
438 dummy_property_map& >::type pred_map
439 = arg_pack[_predecessor_map | dummy_prop];
440 boost::detail::make_property_map_from_arg_pack_gen<
441 boost::graph::keywords::tag::rank_map, D >
442 rank_map_gen(zero_actual);
443 typename boost::detail::map_maker< VertexListGraph, arg_pack_type,
444 boost::graph::keywords::tag::rank_map, D >::map_type r_map
445 = rank_map_gen(g, arg_pack);
446 boost::detail::make_property_map_from_arg_pack_gen<
447 boost::graph::keywords::tag::distance_map, D >
448 dist_map_gen(zero_actual);
449 typename boost::detail::map_maker< VertexListGraph, arg_pack_type,
450 boost::graph::keywords::tag::distance_map, D >::map_type dist_map
451 = dist_map_gen(g, arg_pack);
452 weight_map_type w_map = detail::override_const_property(
453 arg_pack, _weight_map, g, edge_weight);
454 typename boost::detail::override_const_property_result< arg_pack_type,
455 boost::graph::keywords::tag::vertex_index_map, vertex_index_t,
456 VertexListGraph >::type v_i_map
457 = detail::override_const_property(
458 arg_pack, _vertex_index_map, g, vertex_index);
459 typename boost::detail::map_maker< VertexListGraph, arg_pack_type,
460 boost::graph::keywords::tag::color_map,
461 boost::default_color_type >::map_type c_map
462 = boost::detail::make_color_map_from_arg_pack(g, arg_pack);
463 std::less< D > default_compare;
464 typename boost::parameter::binding< arg_pack_type,
465 boost::graph::keywords::tag::distance_compare, std::less< D >& >::type
466 dist_comp
467 = arg_pack[_distance_compare | default_compare];
468 closed_plus< D > default_combine(inf);
469 typename boost::parameter::binding< arg_pack_type,
470 boost::graph::keywords::tag::distance_combine, closed_plus< D >& >::type
471 dist_comb
472 = arg_pack[_distance_combine | default_combine];
473 astar_search(g, s, h, vis, pred_map, r_map, dist_map, w_map, v_i_map, c_map,
474 dist_comp, dist_comb, inf, zero_d);
475 }
476
477 template < typename VertexListGraph, typename AStarHeuristic, typename P,
478 typename T, typename R >
astar_search_tree(const VertexListGraph & g,typename graph_traits<VertexListGraph>::vertex_descriptor s,AStarHeuristic h,const bgl_named_params<P,T,R> & params)479 void astar_search_tree(const VertexListGraph& g,
480 typename graph_traits< VertexListGraph >::vertex_descriptor s,
481 AStarHeuristic h, const bgl_named_params< P, T, R >& params)
482 {
483 using namespace boost::graph::keywords;
484 typedef bgl_named_params< P, T, R > params_type;
485 BOOST_GRAPH_DECLARE_CONVERTED_PARAMETERS(params_type, params)
486
487 // Distance type is the value type of the distance map if there is one,
488 // otherwise the value type of the weight map.
489 typedef
490 typename boost::detail::override_const_property_result< arg_pack_type,
491 boost::graph::keywords::tag::weight_map, edge_weight_t,
492 VertexListGraph >::type weight_map_type;
493 typedef typename boost::property_traits< weight_map_type >::value_type D;
494 const D inf = arg_pack[_distance_inf || detail::get_max< D >()];
495 const D zero_actual = D();
496 const D zero_d = arg_pack[_distance_zero | zero_actual];
497 null_visitor null_vis;
498 astar_visitor< null_visitor > default_visitor(null_vis);
499 typename boost::parameter::binding< arg_pack_type,
500 boost::graph::keywords::tag::visitor, dummy_property_map& >::type vis
501 = arg_pack[_visitor | default_visitor];
502 dummy_property_map dummy_prop;
503 typename boost::parameter::binding< arg_pack_type,
504 boost::graph::keywords::tag::predecessor_map,
505 dummy_property_map& >::type pred_map
506 = arg_pack[_predecessor_map | dummy_prop];
507 boost::detail::make_property_map_from_arg_pack_gen<
508 boost::graph::keywords::tag::rank_map, D >
509 rank_map_gen(zero_actual);
510 typename boost::detail::map_maker< VertexListGraph, arg_pack_type,
511 boost::graph::keywords::tag::rank_map, D >::map_type r_map
512 = rank_map_gen(g, arg_pack);
513 boost::detail::make_property_map_from_arg_pack_gen<
514 boost::graph::keywords::tag::distance_map, D >
515 dist_map_gen(zero_actual);
516 typename boost::detail::map_maker< VertexListGraph, arg_pack_type,
517 boost::graph::keywords::tag::distance_map, D >::map_type dist_map
518 = dist_map_gen(g, arg_pack);
519 weight_map_type w_map = detail::override_const_property(
520 arg_pack, _weight_map, g, edge_weight);
521 std::less< D > default_compare;
522 typename boost::parameter::binding< arg_pack_type,
523 boost::graph::keywords::tag::distance_compare, std::less< D >& >::type
524 dist_comp
525 = arg_pack[_distance_compare | default_compare];
526 closed_plus< D > default_combine(inf);
527 typename boost::parameter::binding< arg_pack_type,
528 boost::graph::keywords::tag::distance_combine, closed_plus< D >& >::type
529 dist_comb
530 = arg_pack[_distance_combine | default_combine];
531 astar_search_tree(g, s, h, vis, pred_map, r_map, dist_map, w_map, dist_comp,
532 dist_comb, inf, zero_d);
533 }
534
535 template < typename VertexListGraph, typename AStarHeuristic, typename P,
536 typename T, typename R >
astar_search_no_init(const VertexListGraph & g,typename graph_traits<VertexListGraph>::vertex_descriptor s,AStarHeuristic h,const bgl_named_params<P,T,R> & params)537 void astar_search_no_init(const VertexListGraph& g,
538 typename graph_traits< VertexListGraph >::vertex_descriptor s,
539 AStarHeuristic h, const bgl_named_params< P, T, R >& params)
540 {
541 using namespace boost::graph::keywords;
542 typedef bgl_named_params< P, T, R > params_type;
543 BOOST_GRAPH_DECLARE_CONVERTED_PARAMETERS(params_type, params)
544 typedef
545 typename boost::detail::override_const_property_result< arg_pack_type,
546 boost::graph::keywords::tag::weight_map, edge_weight_t,
547 VertexListGraph >::type weight_map_type;
548 typedef typename boost::property_traits< weight_map_type >::value_type D;
549 const D inf = arg_pack[_distance_inf || detail::get_max< D >()];
550 const D zero_actual = D();
551 const D zero_d = arg_pack[_distance_zero | zero_actual];
552 null_visitor null_vis;
553 astar_visitor< null_visitor > default_visitor(null_vis);
554 typename boost::parameter::binding< arg_pack_type,
555 boost::graph::keywords::tag::visitor, dummy_property_map& >::type vis
556 = arg_pack[_visitor | default_visitor];
557 dummy_property_map dummy_prop;
558 typename boost::parameter::binding< arg_pack_type,
559 boost::graph::keywords::tag::predecessor_map,
560 dummy_property_map& >::type pred_map
561 = arg_pack[_predecessor_map | dummy_prop];
562 boost::detail::make_property_map_from_arg_pack_gen<
563 boost::graph::keywords::tag::rank_map, D >
564 rank_map_gen(zero_actual);
565 typename boost::detail::map_maker< VertexListGraph, arg_pack_type,
566 boost::graph::keywords::tag::rank_map, D >::map_type r_map
567 = rank_map_gen(g, arg_pack);
568 boost::detail::make_property_map_from_arg_pack_gen<
569 boost::graph::keywords::tag::distance_map, D >
570 dist_map_gen(zero_actual);
571 typename boost::detail::map_maker< VertexListGraph, arg_pack_type,
572 boost::graph::keywords::tag::distance_map, D >::map_type dist_map
573 = dist_map_gen(g, arg_pack);
574 weight_map_type w_map = detail::override_const_property(
575 arg_pack, _weight_map, g, edge_weight);
576 typename boost::detail::map_maker< VertexListGraph, arg_pack_type,
577 boost::graph::keywords::tag::color_map,
578 boost::default_color_type >::map_type c_map
579 = boost::detail::make_color_map_from_arg_pack(g, arg_pack);
580 typename boost::detail::override_const_property_result< arg_pack_type,
581 boost::graph::keywords::tag::vertex_index_map, vertex_index_t,
582 VertexListGraph >::type v_i_map
583 = detail::override_const_property(
584 arg_pack, _vertex_index_map, g, vertex_index);
585 std::less< D > default_compare;
586 typename boost::parameter::binding< arg_pack_type,
587 boost::graph::keywords::tag::distance_compare, std::less< D >& >::type
588 dist_comp
589 = arg_pack[_distance_compare | default_compare];
590 closed_plus< D > default_combine(inf);
591 typename boost::parameter::binding< arg_pack_type,
592 boost::graph::keywords::tag::distance_combine, closed_plus< D >& >::type
593 dist_comb
594 = arg_pack[_distance_combine | default_combine];
595 astar_search_no_init(g, s, h, vis, pred_map, r_map, dist_map, w_map, c_map,
596 v_i_map, dist_comp, dist_comb, inf, zero_d);
597 }
598
599 template < typename VertexListGraph, typename AStarHeuristic, typename P,
600 typename T, typename R >
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)601 void astar_search_no_init_tree(const VertexListGraph& g,
602 typename graph_traits< VertexListGraph >::vertex_descriptor s,
603 AStarHeuristic h, const bgl_named_params< P, T, R >& params)
604 {
605 using namespace boost::graph::keywords;
606 typedef bgl_named_params< P, T, R > params_type;
607 BOOST_GRAPH_DECLARE_CONVERTED_PARAMETERS(params_type, params)
608 typedef
609 typename boost::detail::override_const_property_result< arg_pack_type,
610 boost::graph::keywords::tag::weight_map, edge_weight_t,
611 VertexListGraph >::type weight_map_type;
612 typedef typename boost::property_traits< weight_map_type >::value_type D;
613 const D inf = arg_pack[_distance_inf || detail::get_max< D >()];
614 const D zero_actual = D();
615 const D zero_d = arg_pack[_distance_zero | zero_actual];
616 null_visitor null_vis;
617 astar_visitor< null_visitor > default_visitor(null_vis);
618 typename boost::parameter::binding< arg_pack_type,
619 boost::graph::keywords::tag::visitor, dummy_property_map& >::type vis
620 = arg_pack[_visitor | default_visitor];
621 dummy_property_map dummy_prop;
622 typename boost::parameter::binding< arg_pack_type,
623 boost::graph::keywords::tag::predecessor_map,
624 dummy_property_map& >::type pred_map
625 = arg_pack[_predecessor_map | dummy_prop];
626 boost::detail::make_property_map_from_arg_pack_gen<
627 boost::graph::keywords::tag::rank_map, D >
628 rank_map_gen(zero_actual);
629 typename boost::detail::map_maker< VertexListGraph, arg_pack_type,
630 boost::graph::keywords::tag::rank_map, D >::map_type r_map
631 = rank_map_gen(g, arg_pack);
632 boost::detail::make_property_map_from_arg_pack_gen<
633 boost::graph::keywords::tag::distance_map, D >
634 dist_map_gen(zero_actual);
635 typename boost::detail::map_maker< VertexListGraph, arg_pack_type,
636 boost::graph::keywords::tag::distance_map, D >::map_type dist_map
637 = dist_map_gen(g, arg_pack);
638 weight_map_type w_map = detail::override_const_property(
639 arg_pack, _weight_map, g, edge_weight);
640 std::less< D > default_compare;
641 typename boost::parameter::binding< arg_pack_type,
642 boost::graph::keywords::tag::distance_compare, std::less< D >& >::type
643 dist_comp
644 = arg_pack[_distance_compare | default_compare];
645 closed_plus< D > default_combine(inf);
646 typename boost::parameter::binding< arg_pack_type,
647 boost::graph::keywords::tag::distance_combine, closed_plus< D >& >::type
648 dist_comb
649 = arg_pack[_distance_combine | default_combine];
650 astar_search_no_init_tree(g, s, h, vis, pred_map, r_map, dist_map, w_map,
651 dist_comp, dist_comb, inf, zero_d);
652 }
653
654 } // namespace boost
655
656 #endif // BOOST_GRAPH_ASTAR_SEARCH_HPP
657