]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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(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(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(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(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 |