4 //=======================================================================
5 // Copyright (c) 2004 Kristopher Beevers
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 //=======================================================================
13 #ifndef BOOST_GRAPH_ASTAR_SEARCH_HPP
14 #define BOOST_GRAPH_ASTAR_SEARCH_HPP
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>
36 template <class Heuristic, class Graph>
37 struct AStarHeuristicConcept {
40 BOOST_CONCEPT_ASSERT(( CopyConstructibleConcept<Heuristic> ));
44 typename graph_traits<Graph>::vertex_descriptor u;
48 template <class Graph, class CostType>
49 class astar_heuristic : public std::unary_function<
50 typename graph_traits<Graph>::vertex_descriptor, CostType>
53 typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
55 CostType operator()(Vertex u) { return static_cast<CostType>(0); }
60 template <class Visitor, class Graph>
61 struct AStarVisitorConcept {
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);
76 typename graph_traits<Graph>::vertex_descriptor u;
77 typename graph_traits<Graph>::edge_descriptor e;
81 template <class Visitors = null_visitor>
82 class astar_visitor : public bfs_visitor<Visitors> {
85 astar_visitor(Visitors vis)
86 : bfs_visitor<Visitors>(vis) {}
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());
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());
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) {}
102 template <class Visitors>
103 astar_visitor<Visitors>
104 make_astar_visitor(Visitors vis) {
105 return astar_visitor<Visitors>(vis);
107 typedef astar_visitor<> default_astar_visitor;
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
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;
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) {}
135 template <class Vertex, class Graph>
136 void initialize_vertex(Vertex u, const Graph& g) {
137 m_vis.initialize_vertex(u, g);
139 template <class Vertex, class Graph>
140 void discover_vertex(Vertex u, const Graph& g) {
141 m_vis.discover_vertex(u, g);
143 template <class Vertex, class Graph>
144 void examine_vertex(Vertex u, const Graph& g) {
145 m_vis.examine_vertex(u, g);
147 template <class Vertex, class Graph>
148 void finish_vertex(Vertex u, const Graph& g) {
149 m_vis.finish_vertex(u, g);
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);
157 template <class Edge, class Graph>
158 void non_tree_edge(Edge, const Graph&) {}
162 template <class Edge, class Graph>
163 void tree_edge(Edge e, const Graph& g) {
166 relax(e, g, m_weight, m_predecessor, m_distance,
167 m_combine, m_compare);
170 m_vis.edge_relaxed(e, g);
171 put(m_cost, target(e, g),
172 m_combine(get(m_distance, target(e, g)),
175 m_vis.edge_not_relaxed(e, g);
179 template <class Edge, class Graph>
180 void gray_target(Edge e, const Graph& g) {
183 relax(e, g, m_weight, m_predecessor, m_distance,
184 m_combine, m_compare);
187 put(m_cost, target(e, g),
188 m_combine(get(m_distance, target(e, g)),
190 m_Q.update(target(e, g));
191 m_vis.edge_relaxed(e, g);
193 m_vis.edge_not_relaxed(e, g);
197 template <class Edge, class Graph>
198 void black_target(Edge e, const Graph& g) {
201 relax(e, g, m_weight, m_predecessor, m_distance,
202 m_combine, m_compare);
205 m_vis.edge_relaxed(e, g);
206 put(m_cost, target(e, g),
207 m_combine(get(m_distance, 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);
213 m_vis.edge_not_relaxed(e, g);
219 UniformCostVisitor m_vis;
221 PredecessorMap m_predecessor;
223 DistanceMap m_distance;
226 BinaryFunction m_combine;
227 BinaryPredicate m_compare;
232 } // namespace detail
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>
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)
254 typedef typename graph_traits<VertexListGraph>::vertex_descriptor
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>
260 MutableQueue Q(cost, index_in_heap, compare);
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);
268 breadth_first_visit(g, s, Q, bfs_vis, color);
271 namespace graph_detail {
272 template <typename A, typename B>
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;}
280 template <typename VertexListGraph, typename AStarHeuristic,
281 typename AStarVisitor, typename PredecessorMap,
282 typename CostMap, typename DistanceMap,
284 typename CompareFunction, typename CombineFunction,
285 typename CostInf, typename CostZero>
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)
296 typedef typename graph_traits<VertexListGraph>::vertex_descriptor
298 typedef typename property_traits<DistanceMap>::value_type Distance;
299 typedef d_ary_heap_indirect<
300 std::pair<Distance, Vertex>,
302 null_property_map<std::pair<Distance, Vertex>, std::size_t>,
303 function_property_map<graph_detail::select1st<Distance, Vertex>, std::pair<Distance, Vertex> >,
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>(),
311 vis.discover_vertex(s, g);
312 Q.push(std::make_pair(get(cost, s), s));
316 boost::tie(v_rank, v) = Q.top();
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());
326 relax(e, g, weight, predecessor, distance,
328 Distance w_d = combine(get(distance, v), e_weight);
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));
336 vis.edge_not_relaxed(e, g);
339 vis.finish_vertex(v, g);
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,
349 typename CompareFunction, typename CombineFunction,
350 typename CostInf, typename CostZero>
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)
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);
370 put(predecessor, *ui, *ui);
371 vis.initialize_vertex(*ui, g);
373 put(distance, s, zero);
377 (g, s, h, vis, predecessor, cost, distance, weight,
378 color, index_map, compare, combine, inf, zero);
382 // Non-named parameter interface
383 template <typename VertexListGraph, typename AStarHeuristic,
384 typename AStarVisitor, typename PredecessorMap,
385 typename CostMap, typename DistanceMap,
387 typename CompareFunction, typename CombineFunction,
388 typename CostInf, typename CostZero>
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)
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);
404 put(predecessor, *ui, *ui);
405 vis.initialize_vertex(*ui, g);
407 put(distance, s, zero);
410 astar_search_no_init_tree
411 (g, s, h, vis, predecessor, cost, distance, weight,
412 compare, combine, inf, zero);
416 // Named parameter interfaces
417 template <typename VertexListGraph,
418 typename AStarHeuristic,
419 typename P, typename T, typename R>
422 (const VertexListGraph &g,
423 typename graph_traits<VertexListGraph>::vertex_descriptor s,
424 AStarHeuristic h, const bgl_named_params<P, T, R>& params)
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)
430 // Distance type is the value type of the distance map if there is one,
431 // otherwise the value type of the weight map.
433 typename detail::override_const_property_result<
434 arg_pack_type, tag::weight_map, edge_weight_t, VertexListGraph>::type
436 typedef typename boost::property_traits<weight_map_type>::value_type W;
438 typename detail::map_maker<VertexListGraph, arg_pack_type, tag::distance_map, W>::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>()];
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)],
455 arg_pack[_distance_zero | D()]);
458 // Named parameter interfaces
459 template <typename VertexListGraph,
460 typename AStarHeuristic,
461 typename P, typename T, typename R>
464 (const VertexListGraph &g,
465 typename graph_traits<VertexListGraph>::vertex_descriptor s,
466 AStarHeuristic h, const bgl_named_params<P, T, R>& params)
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)
472 // Distance type is the value type of the distance map if there is one,
473 // otherwise the value type of the weight map.
475 typename detail::override_const_property_result<
476 arg_pack_type, tag::weight_map, edge_weight_t, VertexListGraph>::type
478 typedef typename boost::property_traits<weight_map_type>::value_type W;
480 typename detail::map_maker<VertexListGraph, arg_pack_type, tag::distance_map, W>::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>()];
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)],
495 arg_pack[_distance_zero | D()]);
498 template <typename VertexListGraph,
499 typename AStarHeuristic,
500 typename P, typename T, typename R>
503 (const VertexListGraph &g,
504 typename graph_traits<VertexListGraph>::vertex_descriptor s,
505 AStarHeuristic h, const bgl_named_params<P, T, R>& params)
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)
511 typename detail::override_const_property_result<
512 arg_pack_type, tag::weight_map, edge_weight_t, VertexListGraph>::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>()];
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)],
528 arg_pack[_distance_zero | D()]);
531 template <typename VertexListGraph,
532 typename AStarHeuristic,
533 typename P, typename T, typename R>
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)
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)
544 typename detail::override_const_property_result<
545 arg_pack_type, tag::weight_map, edge_weight_t, VertexListGraph>::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
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)],
559 arg_pack[_distance_zero | D()]);
564 #endif // BOOST_GRAPH_ASTAR_SEARCH_HPP