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 | |
17 | #include <functional> |
18 | #include <vector> |
19 | #include <boost/limits.hpp> |
20 | #include <boost/throw_exception.hpp> |
21 | #include <boost/graph/named_function_params.hpp> |
22 | #include <boost/graph/relax.hpp> |
23 | #include <boost/graph/exception.hpp> |
24 | #include <boost/graph/breadth_first_search.hpp> |
25 | #include <boost/graph/iteration_macros.hpp> |
26 | #include <boost/graph/detail/d_ary_heap.hpp> |
27 | #include <boost/graph/property_maps/constant_property_map.hpp> |
28 | #include <boost/property_map/property_map.hpp> |
29 | #include <boost/property_map/vector_property_map.hpp> |
30 | #include <boost/property_map/function_property_map.hpp> |
31 | #include <boost/concept/assert.hpp> |
32 | |
33 | namespace boost { |
34 | |
35 | |
36 | template <class Heuristic, class Graph> |
37 | struct AStarHeuristicConcept { |
38 | void constraints() |
39 | { |
40 | BOOST_CONCEPT_ASSERT(( CopyConstructibleConcept<Heuristic> )); |
41 | h(u); |
42 | } |
43 | Heuristic h; |
44 | typename graph_traits<Graph>::vertex_descriptor u; |
45 | }; |
46 | |
47 | |
48 | template <class Graph, class CostType> |
49 | class astar_heuristic : public std::unary_function< |
50 | typename graph_traits<Graph>::vertex_descriptor, CostType> |
51 | { |
52 | public: |
53 | typedef typename graph_traits<Graph>::vertex_descriptor Vertex; |
54 | astar_heuristic() {} |
55 | CostType operator()(Vertex u) { return static_cast<CostType>(0); } |
56 | }; |
57 | |
58 | |
59 | |
60 | template <class Visitor, class Graph> |
61 | struct AStarVisitorConcept { |
62 | void constraints() |
63 | { |
64 | BOOST_CONCEPT_ASSERT(( CopyConstructibleConcept<Visitor> )); |
65 | vis.initialize_vertex(u, g); |
66 | vis.discover_vertex(u, g); |
67 | vis.examine_vertex(u, g); |
68 | vis.examine_edge(e, g); |
69 | vis.edge_relaxed(e, g); |
70 | vis.edge_not_relaxed(e, g); |
71 | vis.black_target(e, g); |
72 | vis.finish_vertex(u, g); |
73 | } |
74 | Visitor vis; |
75 | Graph g; |
76 | typename graph_traits<Graph>::vertex_descriptor u; |
77 | typename graph_traits<Graph>::edge_descriptor e; |
78 | }; |
79 | |
80 | |
81 | template <class Visitors = null_visitor> |
82 | class astar_visitor : public bfs_visitor<Visitors> { |
83 | public: |
84 | astar_visitor() {} |
85 | astar_visitor(Visitors vis) |
86 | : bfs_visitor<Visitors>(vis) {} |
87 | |
88 | template <class Edge, class Graph> |
89 | void edge_relaxed(Edge e, const Graph& g) { |
90 | invoke_visitors(this->m_vis, e, g, on_edge_relaxed()); |
91 | } |
92 | template <class Edge, class Graph> |
93 | void edge_not_relaxed(Edge e, const Graph& g) { |
94 | invoke_visitors(this->m_vis, e, g, on_edge_not_relaxed()); |
95 | } |
96 | private: |
97 | template <class Edge, class Graph> |
98 | void tree_edge(Edge e, const Graph& g) {} |
99 | template <class Edge, class Graph> |
100 | void non_tree_edge(Edge e, const Graph& g) {} |
101 | }; |
102 | template <class Visitors> |
103 | astar_visitor<Visitors> |
104 | make_astar_visitor(Visitors vis) { |
105 | return astar_visitor<Visitors>(vis); |
106 | } |
107 | typedef astar_visitor<> default_astar_visitor; |
108 | |
109 | |
110 | namespace detail { |
111 | |
112 | template <class AStarHeuristic, class UniformCostVisitor, |
113 | class UpdatableQueue, class PredecessorMap, |
114 | class CostMap, class DistanceMap, class WeightMap, |
115 | class ColorMap, class BinaryFunction, |
116 | 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 typename property_traits<DistanceMap>::value_type distance_type; |
124 | |
125 | astar_bfs_visitor(AStarHeuristic h, UniformCostVisitor vis, |
126 | UpdatableQueue& Q, PredecessorMap p, |
127 | CostMap c, DistanceMap d, WeightMap w, |
128 | ColorMap col, BinaryFunction combine, |
129 | BinaryPredicate compare, C zero) |
130 | : m_h(h), m_vis(vis), m_Q(Q), m_predecessor(p), m_cost(c), |
131 | m_distance(d), m_weight(w), m_color(col), |
132 | m_combine(combine), m_compare(compare), m_zero(zero) {} |
133 | |
134 | |
135 | template <class Vertex, class Graph> |
136 | void initialize_vertex(Vertex u, const Graph& g) { |
137 | m_vis.initialize_vertex(u, g); |
138 | } |
139 | template <class Vertex, class Graph> |
140 | void discover_vertex(Vertex u, const Graph& g) { |
141 | m_vis.discover_vertex(u, g); |
142 | } |
143 | template <class Vertex, class Graph> |
144 | void examine_vertex(Vertex u, const Graph& g) { |
145 | m_vis.examine_vertex(u, g); |
146 | } |
147 | template <class Vertex, class Graph> |
148 | void finish_vertex(Vertex u, const Graph& g) { |
149 | m_vis.finish_vertex(u, g); |
150 | } |
151 | template <class Edge, class Graph> |
152 | void examine_edge(Edge e, const Graph& g) { |
153 | if (m_compare(get(m_weight, e), m_zero)) |
154 | BOOST_THROW_EXCEPTION(negative_edge()); |
155 | m_vis.examine_edge(e, g); |
156 | } |
157 | template <class Edge, class Graph> |
158 | void non_tree_edge(Edge, const Graph&) {} |
159 | |
160 | |
161 | |
162 | template <class Edge, class Graph> |
163 | void tree_edge(Edge e, const Graph& g) { |
164 | using boost::get; |
165 | bool m_decreased = |
166 | relax(e, g, m_weight, m_predecessor, m_distance, |
167 | m_combine, m_compare); |
168 | |
169 | if(m_decreased) { |
170 | m_vis.edge_relaxed(e, g); |
171 | put(m_cost, target(e, g), |
172 | m_combine(get(m_distance, target(e, g)), |
173 | m_h(target(e, g)))); |
174 | } else |
175 | m_vis.edge_not_relaxed(e, g); |
176 | } |
177 | |
178 | |
179 | template <class Edge, class Graph> |
180 | void gray_target(Edge e, const Graph& g) { |
181 | using boost::get; |
182 | bool m_decreased = |
183 | relax(e, g, m_weight, m_predecessor, m_distance, |
184 | m_combine, m_compare); |
185 | |
186 | if(m_decreased) { |
187 | put(m_cost, target(e, g), |
188 | m_combine(get(m_distance, target(e, g)), |
189 | m_h(target(e, g)))); |
190 | m_Q.update(target(e, g)); |
191 | m_vis.edge_relaxed(e, g); |
192 | } else |
193 | m_vis.edge_not_relaxed(e, g); |
194 | } |
195 | |
196 | |
197 | template <class Edge, class Graph> |
198 | void black_target(Edge e, const Graph& g) { |
199 | using boost::get; |
200 | bool m_decreased = |
201 | relax(e, g, m_weight, m_predecessor, m_distance, |
202 | m_combine, m_compare); |
203 | |
204 | if(m_decreased) { |
205 | m_vis.edge_relaxed(e, g); |
206 | put(m_cost, target(e, g), |
207 | m_combine(get(m_distance, target(e, g)), |
208 | m_h(target(e, g)))); |
209 | m_Q.push(target(e, g)); |
210 | put(m_color, target(e, g), Color::gray()); |
211 | m_vis.black_target(e, g); |
212 | } else |
213 | m_vis.edge_not_relaxed(e, g); |
214 | } |
215 | |
216 | |
217 | |
218 | AStarHeuristic m_h; |
219 | UniformCostVisitor m_vis; |
220 | UpdatableQueue& m_Q; |
221 | PredecessorMap m_predecessor; |
222 | CostMap m_cost; |
223 | DistanceMap m_distance; |
224 | WeightMap m_weight; |
225 | ColorMap m_color; |
226 | BinaryFunction m_combine; |
227 | BinaryPredicate m_compare; |
228 | C m_zero; |
229 | |
230 | }; |
231 | |
232 | } // namespace detail |
233 | |
234 | |
235 | |
236 | template <typename VertexListGraph, typename AStarHeuristic, |
237 | typename AStarVisitor, typename PredecessorMap, |
238 | typename CostMap, typename DistanceMap, |
239 | typename WeightMap, typename ColorMap, |
240 | typename VertexIndexMap, |
241 | typename CompareFunction, typename CombineFunction, |
242 | typename CostInf, typename CostZero> |
243 | inline void |
244 | astar_search_no_init |
245 | (const VertexListGraph &g, |
246 | typename graph_traits<VertexListGraph>::vertex_descriptor s, |
247 | AStarHeuristic h, AStarVisitor vis, |
248 | PredecessorMap predecessor, CostMap cost, |
249 | DistanceMap distance, WeightMap weight, |
250 | ColorMap color, VertexIndexMap index_map, |
251 | CompareFunction compare, CombineFunction combine, |
252 | CostInf /*inf*/, CostZero zero) |
253 | { |
254 | typedef typename graph_traits<VertexListGraph>::vertex_descriptor |
255 | Vertex; |
256 | typedef boost::vector_property_map<std::size_t, VertexIndexMap> IndexInHeapMap; |
257 | IndexInHeapMap index_in_heap(index_map); |
258 | typedef d_ary_heap_indirect<Vertex, 4, IndexInHeapMap, CostMap, CompareFunction> |
259 | MutableQueue; |
260 | MutableQueue Q(cost, index_in_heap, compare); |
261 | |
262 | detail::astar_bfs_visitor<AStarHeuristic, AStarVisitor, |
263 | MutableQueue, PredecessorMap, CostMap, DistanceMap, |
264 | WeightMap, ColorMap, CombineFunction, CompareFunction> |
265 | bfs_vis(h, vis, Q, predecessor, cost, distance, weight, |
266 | color, combine, compare, zero); |
267 | |
268 | breadth_first_visit(g, s, Q, bfs_vis, color); |
269 | } |
270 | |
271 | namespace graph_detail { |
272 | template <typename A, typename B> |
273 | struct select1st { |
274 | typedef std::pair<A, B> argument_type; |
275 | typedef A result_type; |
276 | A operator()(const std::pair<A, B>& p) const {return p.first;} |
277 | }; |
278 | } |
279 | |
280 | template <typename VertexListGraph, typename AStarHeuristic, |
281 | typename AStarVisitor, typename PredecessorMap, |
282 | typename CostMap, typename DistanceMap, |
283 | typename WeightMap, |
284 | typename CompareFunction, typename CombineFunction, |
285 | typename CostInf, typename CostZero> |
286 | inline void |
287 | astar_search_no_init_tree |
288 | (const VertexListGraph &g, |
289 | typename graph_traits<VertexListGraph>::vertex_descriptor s, |
290 | AStarHeuristic h, AStarVisitor vis, |
291 | PredecessorMap predecessor, CostMap cost, |
292 | DistanceMap distance, WeightMap weight, |
293 | CompareFunction compare, CombineFunction combine, |
294 | CostInf /*inf*/, CostZero zero) |
295 | { |
296 | typedef typename graph_traits<VertexListGraph>::vertex_descriptor |
297 | Vertex; |
298 | typedef typename property_traits<DistanceMap>::value_type Distance; |
299 | typedef d_ary_heap_indirect< |
300 | std::pair<Distance, Vertex>, |
301 | 4, |
302 | null_property_map<std::pair<Distance, Vertex>, std::size_t>, |
303 | function_property_map<graph_detail::select1st<Distance, Vertex>, std::pair<Distance, Vertex> >, |
304 | CompareFunction> |
305 | MutableQueue; |
306 | MutableQueue Q( |
307 | make_function_property_map<std::pair<Distance, Vertex> >(graph_detail::select1st<Distance, Vertex>()), |
308 | null_property_map<std::pair<Distance, Vertex>, std::size_t>(), |
309 | compare); |
310 | |
311 | vis.discover_vertex(s, g); |
312 | Q.push(std::make_pair(get(cost, s), s)); |
313 | while (!Q.empty()) { |
314 | Vertex v; |
315 | Distance v_rank; |
316 | boost::tie(v_rank, v) = Q.top(); |
317 | Q.pop(); |
318 | vis.examine_vertex(v, g); |
319 | BGL_FORALL_OUTEDGES_T(v, e, g, VertexListGraph) { |
320 | Vertex w = target(e, g); |
321 | vis.examine_edge(e, g); |
322 | Distance e_weight = get(weight, e); |
323 | if (compare(e_weight, zero)) |
324 | BOOST_THROW_EXCEPTION(negative_edge()); |
325 | bool decreased = |
326 | relax(e, g, weight, predecessor, distance, |
327 | combine, compare); |
328 | Distance w_d = combine(get(distance, v), e_weight); |
329 | if (decreased) { |
330 | vis.edge_relaxed(e, g); |
331 | Distance w_rank = combine(get(distance, w), h(w)); |
332 | put(cost, w, w_rank); |
333 | vis.discover_vertex(w, g); |
334 | Q.push(std::make_pair(w_rank, w)); |
335 | } else { |
336 | vis.edge_not_relaxed(e, g); |
337 | } |
338 | } |
339 | vis.finish_vertex(v, g); |
340 | } |
341 | } |
342 | |
343 | // Non-named parameter interface |
344 | template <typename VertexListGraph, typename AStarHeuristic, |
345 | typename AStarVisitor, typename PredecessorMap, |
346 | typename CostMap, typename DistanceMap, |
347 | typename WeightMap, typename VertexIndexMap, |
348 | typename ColorMap, |
349 | typename CompareFunction, typename CombineFunction, |
350 | typename CostInf, typename CostZero> |
351 | inline void |
352 | astar_search |
353 | (const VertexListGraph &g, |
354 | typename graph_traits<VertexListGraph>::vertex_descriptor s, |
355 | AStarHeuristic h, AStarVisitor vis, |
356 | PredecessorMap predecessor, CostMap cost, |
357 | DistanceMap distance, WeightMap weight, |
358 | VertexIndexMap index_map, ColorMap color, |
359 | CompareFunction compare, CombineFunction combine, |
360 | 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 | put(color, *ui, Color::white()); |
368 | put(distance, *ui, inf); |
369 | put(cost, *ui, inf); |
370 | put(predecessor, *ui, *ui); |
371 | vis.initialize_vertex(*ui, g); |
372 | } |
373 | put(distance, s, zero); |
374 | put(cost, s, h(s)); |
375 | |
376 | astar_search_no_init |
377 | (g, s, h, vis, predecessor, cost, distance, weight, |
378 | color, index_map, compare, combine, inf, zero); |
379 | |
380 | } |
381 | |
382 | // Non-named parameter interface |
383 | template <typename VertexListGraph, typename AStarHeuristic, |
384 | typename AStarVisitor, typename PredecessorMap, |
385 | typename CostMap, typename DistanceMap, |
386 | typename WeightMap, |
387 | typename CompareFunction, typename CombineFunction, |
388 | typename CostInf, typename CostZero> |
389 | inline void |
390 | astar_search_tree |
391 | (const VertexListGraph &g, |
392 | typename graph_traits<VertexListGraph>::vertex_descriptor s, |
393 | AStarHeuristic h, AStarVisitor vis, |
394 | PredecessorMap predecessor, CostMap cost, |
395 | DistanceMap distance, WeightMap weight, |
396 | CompareFunction compare, CombineFunction combine, |
397 | CostInf inf, CostZero zero) |
398 | { |
399 | |
400 | typename graph_traits<VertexListGraph>::vertex_iterator ui, ui_end; |
401 | for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui) { |
402 | put(distance, *ui, inf); |
403 | put(cost, *ui, inf); |
404 | put(predecessor, *ui, *ui); |
405 | vis.initialize_vertex(*ui, g); |
406 | } |
407 | put(distance, s, zero); |
408 | put(cost, s, h(s)); |
409 | |
410 | astar_search_no_init_tree |
411 | (g, s, h, vis, predecessor, cost, distance, weight, |
412 | compare, combine, inf, zero); |
413 | |
414 | } |
415 | |
416 | // Named parameter interfaces |
417 | template <typename VertexListGraph, |
418 | typename AStarHeuristic, |
419 | typename P, typename T, typename R> |
420 | void |
421 | astar_search |
422 | (const VertexListGraph &g, |
423 | typename graph_traits<VertexListGraph>::vertex_descriptor s, |
424 | AStarHeuristic h, const bgl_named_params<P, T, R>& params) |
425 | { |
426 | using namespace boost::graph::keywords; |
427 | typedef bgl_named_params<P, T, R> params_type; |
428 | BOOST_GRAPH_DECLARE_CONVERTED_PARAMETERS(params_type, params) |
429 | |
430 | // Distance type is the value type of the distance map if there is one, |
431 | // otherwise the value type of the weight map. |
432 | typedef |
433 | typename detail::override_const_property_result< |
434 | arg_pack_type, tag::weight_map, edge_weight_t, VertexListGraph>::type |
435 | weight_map_type; |
436 | typedef typename boost::property_traits<weight_map_type>::value_type W; |
437 | typedef |
438 | typename detail::map_maker<VertexListGraph, arg_pack_type, tag::distance_map, W>::map_type |
439 | distance_map_type; |
440 | typedef typename boost::property_traits<distance_map_type>::value_type D; |
441 | const D inf = arg_pack[_distance_inf || detail::get_max<D>()]; |
442 | |
443 | astar_search |
444 | (g, s, h, |
445 | arg_pack[_visitor | make_astar_visitor(vis: null_visitor())], |
446 | arg_pack[_predecessor_map | dummy_property_map()], |
447 | detail::make_property_map_from_arg_pack_gen<tag::rank_map, D>(D())(g, arg_pack), |
448 | detail::make_property_map_from_arg_pack_gen<tag::distance_map, W>(W())(g, arg_pack), |
449 | detail::override_const_property(arg_pack, _weight_map, g, edge_weight), |
450 | detail::override_const_property(arg_pack, _vertex_index_map, g, vertex_index), |
451 | detail::make_color_map_from_arg_pack(g, arg_pack), |
452 | arg_pack[_distance_compare | std::less<D>()], |
453 | arg_pack[_distance_combine | closed_plus<D>(inf)], |
454 | inf, |
455 | arg_pack[_distance_zero | D()]); |
456 | } |
457 | |
458 | // Named parameter interfaces |
459 | template <typename VertexListGraph, |
460 | typename AStarHeuristic, |
461 | typename P, typename T, typename R> |
462 | void |
463 | astar_search_tree |
464 | (const VertexListGraph &g, |
465 | typename graph_traits<VertexListGraph>::vertex_descriptor s, |
466 | AStarHeuristic h, const bgl_named_params<P, T, R>& params) |
467 | { |
468 | using namespace boost::graph::keywords; |
469 | typedef bgl_named_params<P, T, R> params_type; |
470 | BOOST_GRAPH_DECLARE_CONVERTED_PARAMETERS(params_type, params) |
471 | |
472 | // Distance type is the value type of the distance map if there is one, |
473 | // otherwise the value type of the weight map. |
474 | typedef |
475 | typename detail::override_const_property_result< |
476 | arg_pack_type, tag::weight_map, edge_weight_t, VertexListGraph>::type |
477 | weight_map_type; |
478 | typedef typename boost::property_traits<weight_map_type>::value_type W; |
479 | typedef |
480 | typename detail::map_maker<VertexListGraph, arg_pack_type, tag::distance_map, W>::map_type |
481 | distance_map_type; |
482 | typedef typename boost::property_traits<distance_map_type>::value_type D; |
483 | const D inf = arg_pack[_distance_inf || detail::get_max<D>()]; |
484 | |
485 | astar_search_tree |
486 | (g, s, h, |
487 | arg_pack[_visitor | make_astar_visitor(vis: null_visitor())], |
488 | arg_pack[_predecessor_map | dummy_property_map()], |
489 | detail::make_property_map_from_arg_pack_gen<tag::rank_map, D>(D())(g, arg_pack), |
490 | detail::make_property_map_from_arg_pack_gen<tag::distance_map, W>(W())(g, arg_pack), |
491 | detail::override_const_property(arg_pack, _weight_map, g, edge_weight), |
492 | arg_pack[_distance_compare | std::less<D>()], |
493 | arg_pack[_distance_combine | closed_plus<D>(inf)], |
494 | inf, |
495 | arg_pack[_distance_zero | D()]); |
496 | } |
497 | |
498 | template <typename VertexListGraph, |
499 | typename AStarHeuristic, |
500 | typename P, typename T, typename R> |
501 | void |
502 | astar_search_no_init |
503 | (const VertexListGraph &g, |
504 | typename graph_traits<VertexListGraph>::vertex_descriptor s, |
505 | AStarHeuristic h, const bgl_named_params<P, T, R>& params) |
506 | { |
507 | using namespace boost::graph::keywords; |
508 | typedef bgl_named_params<P, T, R> params_type; |
509 | BOOST_GRAPH_DECLARE_CONVERTED_PARAMETERS(params_type, params) |
510 | typedef |
511 | typename detail::override_const_property_result< |
512 | arg_pack_type, tag::weight_map, edge_weight_t, VertexListGraph>::type |
513 | weight_map_type; |
514 | typedef typename boost::property_traits<weight_map_type>::value_type D; |
515 | const D inf = arg_pack[_distance_inf || detail::get_max<D>()]; |
516 | astar_search_no_init |
517 | (g, s, h, |
518 | arg_pack[_visitor | make_astar_visitor(vis: null_visitor())], |
519 | arg_pack[_predecessor_map | dummy_property_map()], |
520 | detail::make_property_map_from_arg_pack_gen<tag::rank_map, D>(D())(g, arg_pack), |
521 | detail::make_property_map_from_arg_pack_gen<tag::distance_map, D>(D())(g, arg_pack), |
522 | detail::override_const_property(arg_pack, _weight_map, g, edge_weight), |
523 | detail::make_color_map_from_arg_pack(g, arg_pack), |
524 | detail::override_const_property(arg_pack, _vertex_index_map, g, vertex_index), |
525 | arg_pack[_distance_compare | std::less<D>()], |
526 | arg_pack[_distance_combine | closed_plus<D>(inf)], |
527 | inf, |
528 | arg_pack[_distance_zero | D()]); |
529 | } |
530 | |
531 | template <typename VertexListGraph, |
532 | typename AStarHeuristic, |
533 | typename P, typename T, typename R> |
534 | void |
535 | astar_search_no_init_tree |
536 | (const VertexListGraph &g, |
537 | typename graph_traits<VertexListGraph>::vertex_descriptor s, |
538 | AStarHeuristic h, const bgl_named_params<P, T, R>& params) |
539 | { |
540 | using namespace boost::graph::keywords; |
541 | typedef bgl_named_params<P, T, R> params_type; |
542 | BOOST_GRAPH_DECLARE_CONVERTED_PARAMETERS(params_type, params) |
543 | typedef |
544 | typename detail::override_const_property_result< |
545 | arg_pack_type, tag::weight_map, edge_weight_t, VertexListGraph>::type |
546 | weight_map_type; |
547 | typedef typename boost::property_traits<weight_map_type>::value_type D; |
548 | const D inf = arg_pack[_distance_inf || detail::get_max<D>()]; |
549 | astar_search_no_init_tree |
550 | (g, s, h, |
551 | arg_pack[_visitor | make_astar_visitor(vis: null_visitor())], |
552 | arg_pack[_predecessor_map | dummy_property_map()], |
553 | detail::make_property_map_from_arg_pack_gen<tag::rank_map, D>(D())(g, arg_pack), |
554 | detail::make_property_map_from_arg_pack_gen<tag::distance_map, D>(D())(g, arg_pack), |
555 | detail::override_const_property(arg_pack, _weight_map, g, edge_weight), |
556 | arg_pack[_distance_compare | std::less<D>()], |
557 | arg_pack[_distance_combine | closed_plus<D>(inf)], |
558 | inf, |
559 | arg_pack[_distance_zero | D()]); |
560 | } |
561 | |
562 | } // namespace boost |
563 | |
564 | #endif // BOOST_GRAPH_ASTAR_SEARCH_HPP |
565 | |