epoc32/include/stdapis/boost/graph/astar_search.hpp
author William Roberts <williamr@symbian.org>
Wed, 31 Mar 2010 12:33:34 +0100
branchSymbian3
changeset 4 837f303aceeb
permissions -rw-r--r--
Current Symbian^3 public API header files (from PDK 3.0.h)
This is the epoc32/include tree with the "platform" subtrees removed, and
all but a selected few mbg and rsg files removed.
     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 <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>
    25 
    26 
    27 namespace boost {
    28 
    29   
    30   template <class Heuristic, class Graph>
    31   struct AStarHeuristicConcept {
    32     void constraints()
    33     {
    34       function_requires< CopyConstructibleConcept<Heuristic> >();
    35       h(u);
    36     }
    37     Heuristic h;
    38     typename graph_traits<Graph>::vertex_descriptor u;
    39   };
    40   
    41   
    42   template <class Graph, class CostType>
    43   class astar_heuristic : public std::unary_function<
    44     typename graph_traits<Graph>::vertex_descriptor, CostType>
    45   {
    46   public:
    47     typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
    48     astar_heuristic() {}
    49     CostType operator()(Vertex u) { return static_cast<CostType>(0); }
    50   };
    51   
    52 
    53   
    54   template <class Visitor, class Graph>
    55   struct AStarVisitorConcept {
    56     void constraints()
    57     {
    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);
    67     }
    68     Visitor vis;
    69     Graph g;
    70     typename graph_traits<Graph>::vertex_descriptor u;
    71     typename graph_traits<Graph>::edge_descriptor e;
    72   };
    73   
    74   
    75   template <class Visitors = null_visitor>
    76   class astar_visitor : public bfs_visitor<Visitors> {
    77   public:
    78     astar_visitor() {}
    79     astar_visitor(Visitors vis)
    80       : bfs_visitor<Visitors>(vis) {}
    81   
    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());
    85     }
    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());      
    89     }
    90   private:
    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) {}
    95   };
    96   template <class Visitors>
    97   astar_visitor<Visitors>
    98   make_astar_visitor(Visitors vis) {
    99     return astar_visitor<Visitors>(vis);
   100   }
   101   typedef astar_visitor<> default_astar_visitor;
   102   
   103 
   104   namespace detail {
   105     
   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
   112     {
   113       
   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;
   118       
   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) {}
   127       
   128       
   129       template <class Vertex, class Graph>
   130       void initialize_vertex(Vertex u, Graph& g) {
   131         m_vis.initialize_vertex(u, g);
   132       }
   133       template <class Vertex, class Graph>
   134       void discover_vertex(Vertex u, Graph& g) {
   135         m_vis.discover_vertex(u, g);
   136       }
   137       template <class Vertex, class Graph>
   138       void examine_vertex(Vertex u, Graph& g) {
   139         m_vis.examine_vertex(u, g);
   140       }
   141       template <class Vertex, class Graph>
   142       void finish_vertex(Vertex u, Graph& g) {
   143         m_vis.finish_vertex(u, g);
   144       }
   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);
   150       }
   151       template <class Edge, class Graph>
   152       void non_tree_edge(Edge, Graph&) {}
   153       
   154       
   155       
   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);
   160 
   161         if(m_decreased) {
   162           m_vis.edge_relaxed(e, g);
   163           put(m_cost, target(e, g),
   164               m_combine(get(m_distance, target(e, g)),
   165                         m_h(target(e, g))));
   166         } else
   167           m_vis.edge_not_relaxed(e, g);
   168       }
   169       
   170       
   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));
   174 
   175         m_decreased = relax(e, g, m_weight, m_predecessor, m_distance,
   176                             m_combine, m_compare);
   177 
   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
   185            in looping. */
   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)),
   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, Graph& g) {
   199         distance_type old_distance = get(m_distance, target(e, g));
   200 
   201         m_decreased = relax(e, g, m_weight, m_predecessor, m_distance,
   202                             m_combine, m_compare);
   203 
   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)),
   209                         m_h(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);
   213         } else
   214           m_vis.edge_not_relaxed(e, g);
   215       }
   216       
   217       
   218       
   219       AStarHeuristic m_h;
   220       UniformCostVisitor m_vis;
   221       UpdatableQueue& m_Q;
   222       PredecessorMap m_predecessor;
   223       CostMap m_cost;
   224       DistanceMap m_distance;
   225       WeightMap m_weight;
   226       ColorMap m_color;
   227       BinaryFunction m_combine;
   228       BinaryPredicate m_compare;
   229       bool m_decreased;
   230       C m_zero;
   231       
   232     };
   233     
   234   } // namespace detail
   235 
   236   
   237   
   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>
   245   inline void
   246   astar_search_no_init
   247     (VertexListGraph &g,
   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)
   255   {
   256     typedef indirect_cmp<CostMap, CompareFunction> IndirectCmp;
   257     IndirectCmp icmp(cost, compare);
   258   
   259     typedef typename graph_traits<VertexListGraph>::vertex_descriptor
   260       Vertex;
   261     typedef mutable_queue<Vertex, std::vector<Vertex>,
   262         IndirectCmp, VertexIndexMap>
   263       MutableQueue;
   264     MutableQueue Q(num_vertices(g), icmp, index_map);
   265   
   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);
   271   
   272     breadth_first_visit(g, s, Q, bfs_vis, color);
   273   }
   274   
   275   
   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,
   281             typename ColorMap,
   282             typename CompareFunction, typename CombineFunction,
   283             typename CostInf, typename CostZero>
   284   inline void
   285   astar_search
   286     (VertexListGraph &g,
   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)
   294   {
   295     
   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);
   302       put(cost, *ui, inf);
   303       put(predecessor, *ui, *ui);
   304       vis.initialize_vertex(*ui, g);
   305     }
   306     put(distance, s, zero);
   307     put(cost, s, h(s));
   308     
   309     astar_search_no_init
   310       (g, s, h, vis, predecessor, cost, distance, weight,
   311        color, index_map, compare, combine, inf, zero);
   312     
   313   }
   314   
   315   
   316   
   317   namespace detail {
   318     template <class VertexListGraph, class AStarHeuristic,
   319               class CostMap, class DistanceMap, class WeightMap,
   320               class IndexMap, class ColorMap, class Params>
   321     inline void
   322     astar_dispatch2
   323       (VertexListGraph& g,
   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)
   328     {
   329       dummy_property_map p_map;
   330       typedef typename property_traits<CostMap>::value_type C;
   331       astar_search
   332         (g, s, h,
   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()),
   338                       std::less<C>()),
   339          choose_param(get_param(params, distance_combine_t()),
   340                       closed_plus<C>()),
   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()),
   344                       C()));
   345     }
   346   
   347     template <class VertexListGraph, class AStarHeuristic,
   348               class CostMap, class DistanceMap, class WeightMap,
   349               class IndexMap, class ColorMap, class Params>
   350     inline void
   351     astar_dispatch1
   352       (VertexListGraph& g,
   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)
   357     {
   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;
   366   
   367       detail::astar_dispatch2
   368         (g, s, h,
   369          choose_param(cost, make_iterator_property_map
   370                       (cost_map.begin(), index_map,
   371                        cost_map[0])),
   372          choose_param(distance, make_iterator_property_map
   373                       (distance_map.begin(), index_map, 
   374                        distance_map[0])),
   375          weight, index_map,
   376          choose_param(color, make_iterator_property_map
   377                       (color_map.begin(), index_map, c)),
   378          params);
   379     }
   380   } // namespace detail
   381   
   382   
   383   // Named parameter interface
   384   template <typename VertexListGraph,
   385             typename AStarHeuristic,
   386             typename P, typename T, typename R>
   387   void
   388   astar_search
   389     (VertexListGraph &g,
   390      typename graph_traits<VertexListGraph>::vertex_descriptor s,
   391      AStarHeuristic h, const bgl_named_params<P, T, R>& params)
   392   {
   393     
   394     detail::astar_dispatch1
   395       (g, s, h,
   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),
   401        params);
   402     
   403   }
   404   
   405 } // namespace boost
   406 
   407 #endif // BOOST_GRAPH_ASTAR_SEARCH_HPP