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