epoc32/include/stdapis/boost/graph/astar_search.hpp
branchSymbian2
changeset 2 2fe1408b6811
     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