1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/epoc32/include/stdapis/boost/graph/astar_search.hpp Tue Mar 16 16:12:26 2010 +0000
1.3 @@ -0,0 +1,407 @@
1.4 +
1.5 +
1.6 +//
1.7 +//=======================================================================
1.8 +// Copyright (c) 2004 Kristopher Beevers
1.9 +//
1.10 +// Distributed under the Boost Software License, Version 1.0. (See
1.11 +// accompanying file LICENSE_1_0.txt or copy at
1.12 +// http://www.boost.org/LICENSE_1_0.txt)
1.13 +//=======================================================================
1.14 +//
1.15 +
1.16 +#ifndef BOOST_GRAPH_ASTAR_SEARCH_HPP
1.17 +#define BOOST_GRAPH_ASTAR_SEARCH_HPP
1.18 +
1.19 +
1.20 +#include <functional>
1.21 +#include <boost/limits.hpp>
1.22 +#include <boost/graph/named_function_params.hpp>
1.23 +#include <boost/pending/mutable_queue.hpp>
1.24 +#include <boost/graph/relax.hpp>
1.25 +#include <boost/pending/indirect_cmp.hpp>
1.26 +#include <boost/graph/exception.hpp>
1.27 +#include <boost/graph/breadth_first_search.hpp>
1.28 +
1.29 +
1.30 +namespace boost {
1.31 +
1.32 +
1.33 + template <class Heuristic, class Graph>
1.34 + struct AStarHeuristicConcept {
1.35 + void constraints()
1.36 + {
1.37 + function_requires< CopyConstructibleConcept<Heuristic> >();
1.38 + h(u);
1.39 + }
1.40 + Heuristic h;
1.41 + typename graph_traits<Graph>::vertex_descriptor u;
1.42 + };
1.43 +
1.44 +
1.45 + template <class Graph, class CostType>
1.46 + class astar_heuristic : public std::unary_function<
1.47 + typename graph_traits<Graph>::vertex_descriptor, CostType>
1.48 + {
1.49 + public:
1.50 + typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
1.51 + astar_heuristic() {}
1.52 + CostType operator()(Vertex u) { return static_cast<CostType>(0); }
1.53 + };
1.54 +
1.55 +
1.56 +
1.57 + template <class Visitor, class Graph>
1.58 + struct AStarVisitorConcept {
1.59 + void constraints()
1.60 + {
1.61 + function_requires< CopyConstructibleConcept<Visitor> >();
1.62 + vis.initialize_vertex(u, g);
1.63 + vis.discover_vertex(u, g);
1.64 + vis.examine_vertex(u, g);
1.65 + vis.examine_edge(e, g);
1.66 + vis.edge_relaxed(e, g);
1.67 + vis.edge_not_relaxed(e, g);
1.68 + vis.black_target(e, g);
1.69 + vis.finish_vertex(u, g);
1.70 + }
1.71 + Visitor vis;
1.72 + Graph g;
1.73 + typename graph_traits<Graph>::vertex_descriptor u;
1.74 + typename graph_traits<Graph>::edge_descriptor e;
1.75 + };
1.76 +
1.77 +
1.78 + template <class Visitors = null_visitor>
1.79 + class astar_visitor : public bfs_visitor<Visitors> {
1.80 + public:
1.81 + astar_visitor() {}
1.82 + astar_visitor(Visitors vis)
1.83 + : bfs_visitor<Visitors>(vis) {}
1.84 +
1.85 + template <class Edge, class Graph>
1.86 + void edge_relaxed(Edge e, Graph& g) {
1.87 + invoke_visitors(this->m_vis, e, g, on_edge_relaxed());
1.88 + }
1.89 + template <class Edge, class Graph>
1.90 + void edge_not_relaxed(Edge e, Graph& g) {
1.91 + invoke_visitors(this->m_vis, e, g, on_edge_not_relaxed());
1.92 + }
1.93 + private:
1.94 + template <class Edge, class Graph>
1.95 + void tree_edge(Edge e, Graph& g) {}
1.96 + template <class Edge, class Graph>
1.97 + void non_tree_edge(Edge e, Graph& g) {}
1.98 + };
1.99 + template <class Visitors>
1.100 + astar_visitor<Visitors>
1.101 + make_astar_visitor(Visitors vis) {
1.102 + return astar_visitor<Visitors>(vis);
1.103 + }
1.104 + typedef astar_visitor<> default_astar_visitor;
1.105 +
1.106 +
1.107 + namespace detail {
1.108 +
1.109 + template <class AStarHeuristic, class UniformCostVisitor,
1.110 + class UpdatableQueue, class PredecessorMap,
1.111 + class CostMap, class DistanceMap, class WeightMap,
1.112 + class ColorMap, class BinaryFunction,
1.113 + class BinaryPredicate>
1.114 + struct astar_bfs_visitor
1.115 + {
1.116 +
1.117 + typedef typename property_traits<CostMap>::value_type C;
1.118 + typedef typename property_traits<ColorMap>::value_type ColorValue;
1.119 + typedef color_traits<ColorValue> Color;
1.120 + typedef typename property_traits<DistanceMap>::value_type distance_type;
1.121 +
1.122 + astar_bfs_visitor(AStarHeuristic h, UniformCostVisitor vis,
1.123 + UpdatableQueue& Q, PredecessorMap p,
1.124 + CostMap c, DistanceMap d, WeightMap w,
1.125 + ColorMap col, BinaryFunction combine,
1.126 + BinaryPredicate compare, C zero)
1.127 + : m_h(h), m_vis(vis), m_Q(Q), m_predecessor(p), m_cost(c),
1.128 + m_distance(d), m_weight(w), m_color(col),
1.129 + m_combine(combine), m_compare(compare), m_zero(zero) {}
1.130 +
1.131 +
1.132 + template <class Vertex, class Graph>
1.133 + void initialize_vertex(Vertex u, Graph& g) {
1.134 + m_vis.initialize_vertex(u, g);
1.135 + }
1.136 + template <class Vertex, class Graph>
1.137 + void discover_vertex(Vertex u, Graph& g) {
1.138 + m_vis.discover_vertex(u, g);
1.139 + }
1.140 + template <class Vertex, class Graph>
1.141 + void examine_vertex(Vertex u, Graph& g) {
1.142 + m_vis.examine_vertex(u, g);
1.143 + }
1.144 + template <class Vertex, class Graph>
1.145 + void finish_vertex(Vertex u, Graph& g) {
1.146 + m_vis.finish_vertex(u, g);
1.147 + }
1.148 + template <class Edge, class Graph>
1.149 + void examine_edge(Edge e, Graph& g) {
1.150 + if (m_compare(get(m_weight, e), m_zero))
1.151 + throw negative_edge();
1.152 + m_vis.examine_edge(e, g);
1.153 + }
1.154 + template <class Edge, class Graph>
1.155 + void non_tree_edge(Edge, Graph&) {}
1.156 +
1.157 +
1.158 +
1.159 + template <class Edge, class Graph>
1.160 + void tree_edge(Edge e, Graph& g) {
1.161 + m_decreased = relax(e, g, m_weight, m_predecessor, m_distance,
1.162 + m_combine, m_compare);
1.163 +
1.164 + if(m_decreased) {
1.165 + m_vis.edge_relaxed(e, g);
1.166 + put(m_cost, target(e, g),
1.167 + m_combine(get(m_distance, target(e, g)),
1.168 + m_h(target(e, g))));
1.169 + } else
1.170 + m_vis.edge_not_relaxed(e, g);
1.171 + }
1.172 +
1.173 +
1.174 + template <class Edge, class Graph>
1.175 + void gray_target(Edge e, Graph& g) {
1.176 + distance_type old_distance = get(m_distance, target(e, g));
1.177 +
1.178 + m_decreased = relax(e, g, m_weight, m_predecessor, m_distance,
1.179 + m_combine, m_compare);
1.180 +
1.181 + /* On x86 Linux with optimization, we sometimes get into a
1.182 + horrible case where m_decreased is true but the distance hasn't
1.183 + actually changed. This occurs when the comparison inside
1.184 + relax() occurs with the 80-bit precision of the x87 floating
1.185 + point unit, but the difference is lost when the resulting
1.186 + values are written back to lower-precision memory (e.g., a
1.187 + double). With the eager Dijkstra's implementation, this results
1.188 + in looping. */
1.189 + if(m_decreased && old_distance != get(m_distance, target(e, g))) {
1.190 + put(m_cost, target(e, g),
1.191 + m_combine(get(m_distance, target(e, g)),
1.192 + m_h(target(e, g))));
1.193 + m_Q.update(target(e, g));
1.194 + m_vis.edge_relaxed(e, g);
1.195 + } else
1.196 + m_vis.edge_not_relaxed(e, g);
1.197 + }
1.198 +
1.199 +
1.200 + template <class Edge, class Graph>
1.201 + void black_target(Edge e, Graph& g) {
1.202 + distance_type old_distance = get(m_distance, target(e, g));
1.203 +
1.204 + m_decreased = relax(e, g, m_weight, m_predecessor, m_distance,
1.205 + m_combine, m_compare);
1.206 +
1.207 + /* See comment in gray_target */
1.208 + if(m_decreased && old_distance != get(m_distance, target(e, g))) {
1.209 + m_vis.edge_relaxed(e, g);
1.210 + put(m_cost, target(e, g),
1.211 + m_combine(get(m_distance, target(e, g)),
1.212 + m_h(target(e, g))));
1.213 + m_Q.push(target(e, g));
1.214 + put(m_color, target(e, g), Color::gray());
1.215 + m_vis.black_target(e, g);
1.216 + } else
1.217 + m_vis.edge_not_relaxed(e, g);
1.218 + }
1.219 +
1.220 +
1.221 +
1.222 + AStarHeuristic m_h;
1.223 + UniformCostVisitor m_vis;
1.224 + UpdatableQueue& m_Q;
1.225 + PredecessorMap m_predecessor;
1.226 + CostMap m_cost;
1.227 + DistanceMap m_distance;
1.228 + WeightMap m_weight;
1.229 + ColorMap m_color;
1.230 + BinaryFunction m_combine;
1.231 + BinaryPredicate m_compare;
1.232 + bool m_decreased;
1.233 + C m_zero;
1.234 +
1.235 + };
1.236 +
1.237 + } // namespace detail
1.238 +
1.239 +
1.240 +
1.241 + template <typename VertexListGraph, typename AStarHeuristic,
1.242 + typename AStarVisitor, typename PredecessorMap,
1.243 + typename CostMap, typename DistanceMap,
1.244 + typename WeightMap, typename ColorMap,
1.245 + typename VertexIndexMap,
1.246 + typename CompareFunction, typename CombineFunction,
1.247 + typename CostInf, typename CostZero>
1.248 + inline void
1.249 + astar_search_no_init
1.250 + (VertexListGraph &g,
1.251 + typename graph_traits<VertexListGraph>::vertex_descriptor s,
1.252 + AStarHeuristic h, AStarVisitor vis,
1.253 + PredecessorMap predecessor, CostMap cost,
1.254 + DistanceMap distance, WeightMap weight,
1.255 + ColorMap color, VertexIndexMap index_map,
1.256 + CompareFunction compare, CombineFunction combine,
1.257 + CostInf inf, CostZero zero)
1.258 + {
1.259 + typedef indirect_cmp<CostMap, CompareFunction> IndirectCmp;
1.260 + IndirectCmp icmp(cost, compare);
1.261 +
1.262 + typedef typename graph_traits<VertexListGraph>::vertex_descriptor
1.263 + Vertex;
1.264 + typedef mutable_queue<Vertex, std::vector<Vertex>,
1.265 + IndirectCmp, VertexIndexMap>
1.266 + MutableQueue;
1.267 + MutableQueue Q(num_vertices(g), icmp, index_map);
1.268 +
1.269 + detail::astar_bfs_visitor<AStarHeuristic, AStarVisitor,
1.270 + MutableQueue, PredecessorMap, CostMap, DistanceMap,
1.271 + WeightMap, ColorMap, CombineFunction, CompareFunction>
1.272 + bfs_vis(h, vis, Q, predecessor, cost, distance, weight,
1.273 + color, combine, compare, zero);
1.274 +
1.275 + breadth_first_visit(g, s, Q, bfs_vis, color);
1.276 + }
1.277 +
1.278 +
1.279 + // Non-named parameter interface
1.280 + template <typename VertexListGraph, typename AStarHeuristic,
1.281 + typename AStarVisitor, typename PredecessorMap,
1.282 + typename CostMap, typename DistanceMap,
1.283 + typename WeightMap, typename VertexIndexMap,
1.284 + typename ColorMap,
1.285 + typename CompareFunction, typename CombineFunction,
1.286 + typename CostInf, typename CostZero>
1.287 + inline void
1.288 + astar_search
1.289 + (VertexListGraph &g,
1.290 + typename graph_traits<VertexListGraph>::vertex_descriptor s,
1.291 + AStarHeuristic h, AStarVisitor vis,
1.292 + PredecessorMap predecessor, CostMap cost,
1.293 + DistanceMap distance, WeightMap weight,
1.294 + VertexIndexMap index_map, ColorMap color,
1.295 + CompareFunction compare, CombineFunction combine,
1.296 + CostInf inf, CostZero zero)
1.297 + {
1.298 +
1.299 + typedef typename property_traits<ColorMap>::value_type ColorValue;
1.300 + typedef color_traits<ColorValue> Color;
1.301 + typename graph_traits<VertexListGraph>::vertex_iterator ui, ui_end;
1.302 + for (tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui) {
1.303 + put(color, *ui, Color::white());
1.304 + put(distance, *ui, inf);
1.305 + put(cost, *ui, inf);
1.306 + put(predecessor, *ui, *ui);
1.307 + vis.initialize_vertex(*ui, g);
1.308 + }
1.309 + put(distance, s, zero);
1.310 + put(cost, s, h(s));
1.311 +
1.312 + astar_search_no_init
1.313 + (g, s, h, vis, predecessor, cost, distance, weight,
1.314 + color, index_map, compare, combine, inf, zero);
1.315 +
1.316 + }
1.317 +
1.318 +
1.319 +
1.320 + namespace detail {
1.321 + template <class VertexListGraph, class AStarHeuristic,
1.322 + class CostMap, class DistanceMap, class WeightMap,
1.323 + class IndexMap, class ColorMap, class Params>
1.324 + inline void
1.325 + astar_dispatch2
1.326 + (VertexListGraph& g,
1.327 + typename graph_traits<VertexListGraph>::vertex_descriptor s,
1.328 + AStarHeuristic h, CostMap cost, DistanceMap distance,
1.329 + WeightMap weight, IndexMap index_map, ColorMap color,
1.330 + const Params& params)
1.331 + {
1.332 + dummy_property_map p_map;
1.333 + typedef typename property_traits<CostMap>::value_type C;
1.334 + astar_search
1.335 + (g, s, h,
1.336 + choose_param(get_param(params, graph_visitor),
1.337 + make_astar_visitor(null_visitor())),
1.338 + choose_param(get_param(params, vertex_predecessor), p_map),
1.339 + cost, distance, weight, index_map, color,
1.340 + choose_param(get_param(params, distance_compare_t()),
1.341 + std::less<C>()),
1.342 + choose_param(get_param(params, distance_combine_t()),
1.343 + closed_plus<C>()),
1.344 + choose_param(get_param(params, distance_inf_t()),
1.345 + std::numeric_limits<C>::max BOOST_PREVENT_MACRO_SUBSTITUTION ()),
1.346 + choose_param(get_param(params, distance_zero_t()),
1.347 + C()));
1.348 + }
1.349 +
1.350 + template <class VertexListGraph, class AStarHeuristic,
1.351 + class CostMap, class DistanceMap, class WeightMap,
1.352 + class IndexMap, class ColorMap, class Params>
1.353 + inline void
1.354 + astar_dispatch1
1.355 + (VertexListGraph& g,
1.356 + typename graph_traits<VertexListGraph>::vertex_descriptor s,
1.357 + AStarHeuristic h, CostMap cost, DistanceMap distance,
1.358 + WeightMap weight, IndexMap index_map, ColorMap color,
1.359 + const Params& params)
1.360 + {
1.361 + typedef typename property_traits<WeightMap>::value_type D;
1.362 + typename std::vector<D>::size_type
1.363 + n = is_default_param(distance) ? num_vertices(g) : 1;
1.364 + std::vector<D> distance_map(n);
1.365 + n = is_default_param(cost) ? num_vertices(g) : 1;
1.366 + std::vector<D> cost_map(n);
1.367 + std::vector<default_color_type> color_map(num_vertices(g));
1.368 + default_color_type c = white_color;
1.369 +
1.370 + detail::astar_dispatch2
1.371 + (g, s, h,
1.372 + choose_param(cost, make_iterator_property_map
1.373 + (cost_map.begin(), index_map,
1.374 + cost_map[0])),
1.375 + choose_param(distance, make_iterator_property_map
1.376 + (distance_map.begin(), index_map,
1.377 + distance_map[0])),
1.378 + weight, index_map,
1.379 + choose_param(color, make_iterator_property_map
1.380 + (color_map.begin(), index_map, c)),
1.381 + params);
1.382 + }
1.383 + } // namespace detail
1.384 +
1.385 +
1.386 + // Named parameter interface
1.387 + template <typename VertexListGraph,
1.388 + typename AStarHeuristic,
1.389 + typename P, typename T, typename R>
1.390 + void
1.391 + astar_search
1.392 + (VertexListGraph &g,
1.393 + typename graph_traits<VertexListGraph>::vertex_descriptor s,
1.394 + AStarHeuristic h, const bgl_named_params<P, T, R>& params)
1.395 + {
1.396 +
1.397 + detail::astar_dispatch1
1.398 + (g, s, h,
1.399 + get_param(params, vertex_rank),
1.400 + get_param(params, vertex_distance),
1.401 + choose_const_pmap(get_param(params, edge_weight), g, edge_weight),
1.402 + choose_const_pmap(get_param(params, vertex_index), g, vertex_index),
1.403 + get_param(params, vertex_color),
1.404 + params);
1.405 +
1.406 + }
1.407 +
1.408 +} // namespace boost
1.409 +
1.410 +#endif // BOOST_GRAPH_ASTAR_SEARCH_HPP