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
33namespace 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

source code of boost/boost/graph/astar_search.hpp