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
18 #include <boost/limits.hpp>
19 #include <boost/graph/named_function_params.hpp>
20 #include <boost/pending/mutable_queue.hpp>
21 #include <boost/graph/relax.hpp>
22 #include <boost/pending/indirect_cmp.hpp>
23 #include <boost/graph/exception.hpp>
24 #include <boost/graph/breadth_first_search.hpp>
30 template <class Heuristic, class Graph>
31 struct AStarHeuristicConcept {
34 function_requires< CopyConstructibleConcept<Heuristic> >();
38 typename graph_traits<Graph>::vertex_descriptor u;
42 template <class Graph, class CostType>
43 class astar_heuristic : public std::unary_function<
44 typename graph_traits<Graph>::vertex_descriptor, CostType>
47 typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
49 CostType operator()(Vertex u) { return static_cast<CostType>(0); }
54 template <class Visitor, class Graph>
55 struct AStarVisitorConcept {
58 function_requires< CopyConstructibleConcept<Visitor> >();
59 vis.initialize_vertex(u, g);
60 vis.discover_vertex(u, g);
61 vis.examine_vertex(u, g);
62 vis.examine_edge(e, g);
63 vis.edge_relaxed(e, g);
64 vis.edge_not_relaxed(e, g);
65 vis.black_target(e, g);
66 vis.finish_vertex(u, g);
70 typename graph_traits<Graph>::vertex_descriptor u;
71 typename graph_traits<Graph>::edge_descriptor e;
75 template <class Visitors = null_visitor>
76 class astar_visitor : public bfs_visitor<Visitors> {
79 astar_visitor(Visitors vis)
80 : bfs_visitor<Visitors>(vis) {}
82 template <class Edge, class Graph>
83 void edge_relaxed(Edge e, Graph& g) {
84 invoke_visitors(this->m_vis, e, g, on_edge_relaxed());
86 template <class Edge, class Graph>
87 void edge_not_relaxed(Edge e, Graph& g) {
88 invoke_visitors(this->m_vis, e, g, on_edge_not_relaxed());
91 template <class Edge, class Graph>
92 void tree_edge(Edge e, Graph& g) {}
93 template <class Edge, class Graph>
94 void non_tree_edge(Edge e, Graph& g) {}
96 template <class Visitors>
97 astar_visitor<Visitors>
98 make_astar_visitor(Visitors vis) {
99 return astar_visitor<Visitors>(vis);
101 typedef astar_visitor<> default_astar_visitor;
106 template <class AStarHeuristic, class UniformCostVisitor,
107 class UpdatableQueue, class PredecessorMap,
108 class CostMap, class DistanceMap, class WeightMap,
109 class ColorMap, class BinaryFunction,
110 class BinaryPredicate>
111 struct astar_bfs_visitor
114 typedef typename property_traits<CostMap>::value_type C;
115 typedef typename property_traits<ColorMap>::value_type ColorValue;
116 typedef color_traits<ColorValue> Color;
117 typedef typename property_traits<DistanceMap>::value_type distance_type;
119 astar_bfs_visitor(AStarHeuristic h, UniformCostVisitor vis,
120 UpdatableQueue& Q, PredecessorMap p,
121 CostMap c, DistanceMap d, WeightMap w,
122 ColorMap col, BinaryFunction combine,
123 BinaryPredicate compare, C zero)
124 : m_h(h), m_vis(vis), m_Q(Q), m_predecessor(p), m_cost(c),
125 m_distance(d), m_weight(w), m_color(col),
126 m_combine(combine), m_compare(compare), m_zero(zero) {}
129 template <class Vertex, class Graph>
130 void initialize_vertex(Vertex u, Graph& g) {
131 m_vis.initialize_vertex(u, g);
133 template <class Vertex, class Graph>
134 void discover_vertex(Vertex u, Graph& g) {
135 m_vis.discover_vertex(u, g);
137 template <class Vertex, class Graph>
138 void examine_vertex(Vertex u, Graph& g) {
139 m_vis.examine_vertex(u, g);
141 template <class Vertex, class Graph>
142 void finish_vertex(Vertex u, Graph& g) {
143 m_vis.finish_vertex(u, g);
145 template <class Edge, class Graph>
146 void examine_edge(Edge e, Graph& g) {
147 if (m_compare(get(m_weight, e), m_zero))
148 throw negative_edge();
149 m_vis.examine_edge(e, g);
151 template <class Edge, class Graph>
152 void non_tree_edge(Edge, Graph&) {}
156 template <class Edge, class Graph>
157 void tree_edge(Edge e, Graph& g) {
158 m_decreased = relax(e, g, m_weight, m_predecessor, m_distance,
159 m_combine, m_compare);
162 m_vis.edge_relaxed(e, g);
163 put(m_cost, target(e, g),
164 m_combine(get(m_distance, target(e, g)),
167 m_vis.edge_not_relaxed(e, g);
171 template <class Edge, class Graph>
172 void gray_target(Edge e, Graph& g) {
173 distance_type old_distance = get(m_distance, target(e, g));
175 m_decreased = relax(e, g, m_weight, m_predecessor, m_distance,
176 m_combine, m_compare);
178 /* On x86 Linux with optimization, we sometimes get into a
179 horrible case where m_decreased is true but the distance hasn't
180 actually changed. This occurs when the comparison inside
181 relax() occurs with the 80-bit precision of the x87 floating
182 point unit, but the difference is lost when the resulting
183 values are written back to lower-precision memory (e.g., a
184 double). With the eager Dijkstra's implementation, this results
186 if(m_decreased && old_distance != get(m_distance, target(e, g))) {
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, Graph& g) {
199 distance_type old_distance = get(m_distance, target(e, g));
201 m_decreased = relax(e, g, m_weight, m_predecessor, m_distance,
202 m_combine, m_compare);
204 /* See comment in gray_target */
205 if(m_decreased && old_distance != get(m_distance, target(e, g))) {
206 m_vis.edge_relaxed(e, g);
207 put(m_cost, target(e, g),
208 m_combine(get(m_distance, target(e, g)),
210 m_Q.push(target(e, g));
211 put(m_color, target(e, g), Color::gray());
212 m_vis.black_target(e, g);
214 m_vis.edge_not_relaxed(e, g);
220 UniformCostVisitor m_vis;
222 PredecessorMap m_predecessor;
224 DistanceMap m_distance;
227 BinaryFunction m_combine;
228 BinaryPredicate m_compare;
234 } // namespace detail
238 template <typename VertexListGraph, typename AStarHeuristic,
239 typename AStarVisitor, typename PredecessorMap,
240 typename CostMap, typename DistanceMap,
241 typename WeightMap, typename ColorMap,
242 typename VertexIndexMap,
243 typename CompareFunction, typename CombineFunction,
244 typename CostInf, typename CostZero>
248 typename graph_traits<VertexListGraph>::vertex_descriptor s,
249 AStarHeuristic h, AStarVisitor vis,
250 PredecessorMap predecessor, CostMap cost,
251 DistanceMap distance, WeightMap weight,
252 ColorMap color, VertexIndexMap index_map,
253 CompareFunction compare, CombineFunction combine,
254 CostInf inf, CostZero zero)
256 typedef indirect_cmp<CostMap, CompareFunction> IndirectCmp;
257 IndirectCmp icmp(cost, compare);
259 typedef typename graph_traits<VertexListGraph>::vertex_descriptor
261 typedef mutable_queue<Vertex, std::vector<Vertex>,
262 IndirectCmp, VertexIndexMap>
264 MutableQueue Q(num_vertices(g), icmp, index_map);
266 detail::astar_bfs_visitor<AStarHeuristic, AStarVisitor,
267 MutableQueue, PredecessorMap, CostMap, DistanceMap,
268 WeightMap, ColorMap, CombineFunction, CompareFunction>
269 bfs_vis(h, vis, Q, predecessor, cost, distance, weight,
270 color, combine, compare, zero);
272 breadth_first_visit(g, s, Q, bfs_vis, color);
276 // Non-named parameter interface
277 template <typename VertexListGraph, typename AStarHeuristic,
278 typename AStarVisitor, typename PredecessorMap,
279 typename CostMap, typename DistanceMap,
280 typename WeightMap, typename VertexIndexMap,
282 typename CompareFunction, typename CombineFunction,
283 typename CostInf, typename CostZero>
287 typename graph_traits<VertexListGraph>::vertex_descriptor s,
288 AStarHeuristic h, AStarVisitor vis,
289 PredecessorMap predecessor, CostMap cost,
290 DistanceMap distance, WeightMap weight,
291 VertexIndexMap index_map, ColorMap color,
292 CompareFunction compare, CombineFunction combine,
293 CostInf inf, CostZero zero)
296 typedef typename property_traits<ColorMap>::value_type ColorValue;
297 typedef color_traits<ColorValue> Color;
298 typename graph_traits<VertexListGraph>::vertex_iterator ui, ui_end;
299 for (tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui) {
300 put(color, *ui, Color::white());
301 put(distance, *ui, inf);
303 put(predecessor, *ui, *ui);
304 vis.initialize_vertex(*ui, g);
306 put(distance, s, zero);
310 (g, s, h, vis, predecessor, cost, distance, weight,
311 color, index_map, compare, combine, inf, zero);
318 template <class VertexListGraph, class AStarHeuristic,
319 class CostMap, class DistanceMap, class WeightMap,
320 class IndexMap, class ColorMap, class Params>
324 typename graph_traits<VertexListGraph>::vertex_descriptor s,
325 AStarHeuristic h, CostMap cost, DistanceMap distance,
326 WeightMap weight, IndexMap index_map, ColorMap color,
327 const Params& params)
329 dummy_property_map p_map;
330 typedef typename property_traits<CostMap>::value_type C;
333 choose_param(get_param(params, graph_visitor),
334 make_astar_visitor(null_visitor())),
335 choose_param(get_param(params, vertex_predecessor), p_map),
336 cost, distance, weight, index_map, color,
337 choose_param(get_param(params, distance_compare_t()),
339 choose_param(get_param(params, distance_combine_t()),
341 choose_param(get_param(params, distance_inf_t()),
342 std::numeric_limits<C>::max BOOST_PREVENT_MACRO_SUBSTITUTION ()),
343 choose_param(get_param(params, distance_zero_t()),
347 template <class VertexListGraph, class AStarHeuristic,
348 class CostMap, class DistanceMap, class WeightMap,
349 class IndexMap, class ColorMap, class Params>
353 typename graph_traits<VertexListGraph>::vertex_descriptor s,
354 AStarHeuristic h, CostMap cost, DistanceMap distance,
355 WeightMap weight, IndexMap index_map, ColorMap color,
356 const Params& params)
358 typedef typename property_traits<WeightMap>::value_type D;
359 typename std::vector<D>::size_type
360 n = is_default_param(distance) ? num_vertices(g) : 1;
361 std::vector<D> distance_map(n);
362 n = is_default_param(cost) ? num_vertices(g) : 1;
363 std::vector<D> cost_map(n);
364 std::vector<default_color_type> color_map(num_vertices(g));
365 default_color_type c = white_color;
367 detail::astar_dispatch2
369 choose_param(cost, make_iterator_property_map
370 (cost_map.begin(), index_map,
372 choose_param(distance, make_iterator_property_map
373 (distance_map.begin(), index_map,
376 choose_param(color, make_iterator_property_map
377 (color_map.begin(), index_map, c)),
380 } // namespace detail
383 // Named parameter interface
384 template <typename VertexListGraph,
385 typename AStarHeuristic,
386 typename P, typename T, typename R>
390 typename graph_traits<VertexListGraph>::vertex_descriptor s,
391 AStarHeuristic h, const bgl_named_params<P, T, R>& params)
394 detail::astar_dispatch1
396 get_param(params, vertex_rank),
397 get_param(params, vertex_distance),
398 choose_const_pmap(get_param(params, edge_weight), g, edge_weight),
399 choose_const_pmap(get_param(params, vertex_index), g, vertex_index),
400 get_param(params, vertex_color),
407 #endif // BOOST_GRAPH_ASTAR_SEARCH_HPP