root/tags/release-1.0-beta/shooting_star_search.hpp

Revision 39, 18.9 KB (checked in by anton, 3 years ago)

1.0.0b tag added
Line 
1//
2//=======================================================================
3// Copyright (c) 2004 Kristopher Beevers
4//               2007 Anton A. Patrushev, Orkney Inc.
5//
6// Distributed under the Boost Software License, Version 1.0. (See
7// accompanying file LICENSE_1_0.txt or copy at
8// http://www.boost.org/LICENSE_1_0.txt)
9//=======================================================================
10//
11
12#ifndef BOOST_GRAPH_SHOOTING_STAR_SEARCH_HPP
13#define BOOST_GRAPH_SHOOTING_STAR_SEARCH_HPP
14
15#define MAX_RULE_LENGTH 5
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/pending/relaxed_heap.hpp>
22#include <shooting_star_relax.hpp>
23#include <boost/pending/indirect_cmp.hpp>
24#include <boost/graph/exception.hpp>
25#include <boost/graph/breadth_first_search.hpp>
26
27#include <queue>
28#include "edge_visitors.hpp"
29
30#include <iostream>
31#include <fstream>
32
33  template <class Edge>
34  struct EdgeRankCompare {
35    bool operator()(const Edge& LHS, const Edge& RHS) {
36      return (LHS.rank < RHS.rank);
37    }
38               
39  };
40
41  template <class Edge, class Container, class Cmp>
42      class edge_queue : public std::priority_queue<Edge, Container, Cmp>
43  {
44  protected:
45    using std::priority_queue< Edge, Container, Cmp >::c;
46    using std::priority_queue< Edge, Container, Cmp >::comp;
47   
48  public:
49      void sort()
50      {
51        sort_heap(c.begin(), c.end(), comp);
52      }   
53  };
54
55namespace boost {
56
57 
58  template <class Heuristic, class Graph>
59  struct AStarHeuristicConcept {
60    void constraints()
61    {
62      function_requires< CopyConstructibleConcept<Heuristic> >();
63      h(u);
64    }
65    Heuristic h;
66    typename graph_traits<Graph>::vertex_descriptor u;
67  };
68 
69   
70
71  template <class Graph, class CostType>
72      class astar_heuristic : public std::unary_function<
73    typename graph_traits<Graph>::vertex_descriptor, CostType>
74  {
75  public:
76    typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
77    astar_heuristic() {}
78    CostType operator()(Vertex u) { return static_cast<CostType>(0); }
79  };
80 
81
82 
83  template <class Visitor, class Graph>
84  struct ShootingStarVisitorConcept {
85    void constraints()
86    {
87      function_requires< CopyConstructibleConcept<Visitor> >();
88      vis.initialize_vertex(u, g);
89      vis.discover_vertex(u, g);
90      vis.examine_vertex(u, g);
91      vis.examine_edge(e, g);
92      vis.black_target(e, pe, g, e_max_id);
93      vis.gray_target(e, pe, g, e_max_id);
94      vis.finish_vertex(u, g);
95     
96      vis.tree_edge(e, pe, g, e_max_id);
97
98      vis.initialize_edge(e, g);
99      vis.discover_edge(e, g);
100      vis.finish_edge(e, g);
101
102    }
103    Visitor vis;
104    Graph g;
105    typename graph_traits<Graph>::vertex_descriptor u;
106    typename graph_traits<Graph>::edge_descriptor e, pe;
107    int e_max_id;
108  };
109 
110
111  template <class IncidenceGraph, class Buffer, class BFSVisitor,
112            class ColorMap, class EdgeColorMap, class HistoryMap>
113  void shooting_star_edges_visit (const IncidenceGraph& g,
114                            typename graph_traits<IncidenceGraph>::edge_descriptor s,
115                            Buffer& Q, BFSVisitor vis, ColorMap color, EdgeColorMap edge_color,
116                            HistoryMap history, int e_max_id)
117  {
118    function_requires< IncidenceGraphConcept<IncidenceGraph> >();
119    typedef graph_traits<IncidenceGraph> GTraits;
120    typedef typename GTraits::vertex_descriptor Vertex;
121    typedef typename GTraits::edge_descriptor Edge;
122    function_requires< ShootingStarVisitorConcept<BFSVisitor, IncidenceGraph> >();
123    function_requires< ReadWritePropertyMapConcept<ColorMap, Vertex> >();
124    function_requires< ReadWritePropertyMapConcept<EdgeColorMap, Edge> >();
125   
126    typedef typename property_traits<ColorMap>::value_type ColorValue;
127    typedef color_traits<ColorValue> Color;
128
129    typedef typename property_traits<EdgeColorMap>::value_type EdgeColorValue;
130    typedef color_traits<EdgeColorValue> EdgeColor;
131
132    typename GTraits::out_edge_iterator ei, ei_end;
133                                                                   
134    put(edge_color, s, EdgeColor::gray());         vis.discover_edge(s, g);
135    Q.push(s);
136   
137    while (! Q.empty()) {
138      Edge e = Q.top();  Q.pop();            vis.examine_edge(e, g);
139     
140      for (tie(ei, ei_end) = out_edges(target(e, g), g); ei != ei_end; ++ei) {
141     
142        EdgeColorValue e_color = get(edge_color, *ei);
143
144        if (e_color == EdgeColor::white()) {         vis.tree_edge(*ei, e, g, e_max_id);
145          put(edge_color, *ei, EdgeColor::gray());   vis.discover_edge(*ei, g);
146          Q.push(*ei);
147         
148        } else {                                     vis.non_tree_edge(*ei, g);
149          if (e_color == EdgeColor::gray()){         vis.gray_target(*ei, e, g, e_max_id);
150          }
151          else{                                      vis.black_target(*ei, e, g, e_max_id);
152          }
153        }
154       
155      } // end for
156
157      put(edge_color, e, EdgeColor::black());        vis.finish_edge(e, g);
158     
159    } // end while
160   
161  }
162                                                                                                                                                                                             
163 
164  template <class Visitors = null_visitor>
165  class shooting_star_visitor : public bfs_visitor<Visitors> {
166  public:
167    shooting_star_visitor() {}
168    shooting_star_visitor(Visitors vis)
169      : bfs_visitor<Visitors>(vis) {}
170 
171    template <class Edge, class Graph>
172    void edge_relaxed(Edge e, Graph& g) {
173      invoke_visitors(this->m_vis, e, g, on_edge_relaxed());
174    }
175    template <class Edge, class Graph>
176    void edge_not_relaxed(Edge e, Graph& g) {
177      invoke_visitors(this->m_vis, e, g, on_edge_not_relaxed());     
178    }
179    template <class Edge, class Graph>
180    void initialize_edge(Edge e, Graph& g) {
181      invoke_visitors(this->m_vis, e, g, on_initialize_edge());     
182    }
183   
184  private:
185    template <class Edge, class Graph>
186    void tree_edge(Edge e, Edge pe, Graph& g) {}
187    template <class Edge, class Graph>
188    void non_tree_edge(Edge e, Graph& g) {}
189  };
190  template <class Visitors>
191  shooting_star_visitor<Visitors>
192  make_shooting_star_visitor(Visitors vis) {
193    return shooting_star_visitor<Visitors>(vis);
194  }
195  typedef shooting_star_visitor<> default_shooting_star_visitor;
196 
197
198  namespace detail {
199   
200    template <class AStarHeuristic, class UniformCostVisitor,
201              class UpdatableQueue, class PredecessorMap,
202              class CostMap, class DistanceMap, class WeightMap,
203              class EdgeMap,
204              class ColorMap, class EdgeColorMap, class HistoryMap,
205              class BinaryFunction,
206              class BinaryPredicate>
207    struct shooting_star_bfs_visitor
208    {
209     
210      typedef typename property_traits<CostMap>::value_type C;
211      typedef typename property_traits<ColorMap>::value_type ColorValue;
212      typedef color_traits<ColorValue> Color;
213
214      typedef typename property_traits<EdgeColorMap>::value_type EdgeColorValue;
215      typedef color_traits<ColorValue> EdgeColor;
216
217      typedef typename property_traits<DistanceMap>::value_type distance_type;
218     
219      shooting_star_bfs_visitor(AStarHeuristic h, UniformCostVisitor vis,
220                        UpdatableQueue& Q, PredecessorMap& p,
221                        CostMap c, DistanceMap d, WeightMap w, EdgeMap em,
222                        ColorMap col, EdgeColorMap ecol, HistoryMap his,
223                        BinaryFunction combine,
224                        BinaryPredicate compare, C zero)
225        : m_h(h), m_vis(vis), m_Q(Q), m_predecessor(p), m_cost(c),
226          m_distance(d), m_weight(w), m_edge(em), m_color(col),
227          m_ecolor(ecol), m_history(his),
228          m_combine(combine), m_compare(compare), m_zero(zero) {}
229     
230     
231      template <class Vertex, class Graph>
232      void initialize_vertex(Vertex u, Graph& g) {
233        m_vis.initialize_vertex(u, g);
234      }
235      template <class Edge, class Graph>
236      void initialize_edge(Edge e, Graph& g) {
237        m_vis.initialize_edge(e, g);
238      }
239      template <class Vertex, class Graph>
240      void discover_vertex(Vertex u, Graph& g) {
241        m_vis.discover_vertex(u, g);
242      }
243      template <class Edge, class Graph>
244      void discover_edge(Edge e, Graph& g) {
245        m_vis.discover_vertex(e, g);
246      }
247      template <class Vertex, class Graph>
248      void examine_vertex(Vertex u, Graph& g) {
249        m_vis.examine_vertex(u, g);
250      }
251      template <class Vertex, class Graph>
252      void finish_vertex(Vertex u, Graph& g) {
253        m_vis.finish_vertex(u, g);
254      }
255      template <class Edge, class Graph>
256      void examine_edge(Edge e, Graph& g) {
257        if (m_compare(get(m_weight, e), m_zero))
258          throw negative_edge();
259        m_vis.examine_edge(e, g);
260      }
261      template <class Edge, class Graph>
262      void non_tree_edge(Edge, Graph&) {}
263     
264      template <class Edge, class Graph>
265      void finish_edge(Edge e, Graph& g) {
266        m_vis.finish_edge(e, g);
267      }
268     
269     
270      template <class Edge, class Graph>
271      void tree_edge(Edge e, Edge pe, Graph& g, int e_max_id) {
272
273        m_decreased = relax(e, pe, g, m_weight, m_edge, m_predecessor, m_distance,
274                            m_cost, m_history, m_combine, m_compare, e_max_id);
275   
276        if(m_decreased) {
277          m_vis.edge_relaxed(e, g);
278         
279          put(m_cost, e,
280              m_combine(get(m_distance, e),
281                        m_h(e)));
282
283        } else
284          m_vis.edge_not_relaxed(e, g);
285      }
286     
287     
288      template <class Edge, class Graph>
289      void gray_target(Edge e, Edge pe, Graph& g, int e_max_id) {
290       
291        m_decreased = relax(e, pe, g, m_weight, m_edge, m_predecessor, m_distance,
292                            m_cost, m_history, m_combine, m_compare, e_max_id);
293
294        if(m_decreased) {
295          put(m_cost, e,
296              m_combine(get(m_distance, e),
297                        m_h(e)));
298                       
299          m_Q.update(e);
300                 
301          m_vis.edge_relaxed(e, g);
302        } else
303          m_vis.edge_not_relaxed(e, g);
304      }
305     
306           
307      template <class Edge, class Graph>
308      void black_target(Edge e, Edge pe, Graph& g, int e_max_id) {
309
310        m_decreased = relax(e, pe, g, m_weight, m_edge, m_predecessor, m_distance,
311                            m_cost, m_history, m_combine, m_compare, e_max_id);
312
313        if(m_decreased) {
314          m_vis.edge_relaxed(e, g);
315          put(m_cost, e,
316              m_combine(get(m_distance, e),
317                        m_h(e)));
318         
319          m_Q.push(e);
320          put(m_ecolor, e, EdgeColor::gray());
321          m_vis.black_target(e, g);
322        } else
323          m_vis.edge_not_relaxed(e, g);
324      } 
325
326      AStarHeuristic m_h;
327      UniformCostVisitor m_vis;
328      UpdatableQueue& m_Q;
329      PredecessorMap& m_predecessor;
330      CostMap m_cost;
331      EdgeMap m_edge;
332      DistanceMap m_distance;
333      WeightMap m_weight;
334      ColorMap m_color;
335      EdgeColorMap m_ecolor;
336      HistoryMap m_history;
337      BinaryFunction m_combine;
338      BinaryPredicate m_compare;
339      bool m_decreased;
340      C m_zero;
341     
342    };
343   
344  } // namespace detail
345
346  template <typename VertexAndEdgeListGraph, typename AStarHeuristic,
347            typename ShootingStarVisitor, typename PredecessorMap,
348            typename CostMap, typename DistanceMap,
349            typename WeightMap,
350            typename EdgeMap,
351            typename ColorMap, typename EdgeColorMap,
352            typename HistoryMap,
353            typename IndexMap,
354            typename CompareFunction, typename CombineFunction,
355            typename CostInf, typename CostZero>
356  inline void
357  shooting_star_search_no_init
358    (VertexAndEdgeListGraph &g,
359     typename graph_traits<VertexAndEdgeListGraph>::edge_descriptor s,
360     AStarHeuristic h, ShootingStarVisitor vis,
361     PredecessorMap &predecessor, CostMap cost,
362     DistanceMap distance, WeightMap weight, EdgeMap edge_map,
363     ColorMap color, EdgeColorMap edge_color, HistoryMap history,
364     IndexMap index_map, CompareFunction compare, CombineFunction combine,
365     CostInf inf, CostZero zero, int e_max_id)
366  {
367    typedef indirect_cmp<CostMap, CompareFunction> IndirectCmp;
368    IndirectCmp icmp(cost, compare);
369 
370    typedef typename graph_traits<VertexAndEdgeListGraph>::edge_descriptor
371      Edge;
372
373    typedef mutable_queue<Edge, std::vector<Edge>, IndirectCmp, IndexMap>
374      MutableQueue;
375    MutableQueue Q(num_edges(g), icmp, index_map);
376
377    detail::shooting_star_bfs_visitor<AStarHeuristic, ShootingStarVisitor,
378        MutableQueue, PredecessorMap, CostMap, DistanceMap,
379        WeightMap, EdgeMap, ColorMap, EdgeColorMap, HistoryMap, CombineFunction, CompareFunction>
380      bfs_vis(h, vis, Q, predecessor, cost, distance, weight,
381              edge_map, color, edge_color, history, combine, compare, zero);
382 
383    shooting_star_edges_visit(g, s, Q, bfs_vis, color, edge_color, history, e_max_id);
384  }
385 
386  // Non-named parameter interface
387  template <typename VertexAndEdgeListGraph, typename AStarHeuristic,
388            typename ShootingStarVisitor, typename PredecessorMap,
389            typename CostMap, typename DistanceMap,
390            typename WeightMap, typename EdgeMap,
391            typename IndexMap,
392            typename ColorMap, typename EdgeColorMap,
393            typename HistoryMap,
394            typename CompareFunction, typename CombineFunction,
395            typename CostInf, typename CostZero>
396  inline void
397  shooting_star_search
398    (VertexAndEdgeListGraph &g,
399     typename graph_traits<VertexAndEdgeListGraph>::edge_descriptor s,
400     AStarHeuristic h, ShootingStarVisitor vis,
401     PredecessorMap &predecessor, CostMap cost,
402     DistanceMap distance, WeightMap weight,
403     EdgeMap edge_map, IndexMap index_map, ColorMap color, EdgeColorMap edge_color,
404     HistoryMap history, CompareFunction compare, CombineFunction combine,
405     CostInf inf, CostZero zero, int e_max_id)
406  {
407   
408    typedef typename property_traits<ColorMap>::value_type ColorValue;
409    typedef color_traits<ColorValue> Color;
410   
411    typedef typename property_traits<EdgeColorMap>::value_type EdgeColorValue;
412    typedef color_traits<EdgeColorValue> EdgeColor;
413
414    typename graph_traits<VertexAndEdgeListGraph>::vertex_iterator ui, ui_end;
415    typename graph_traits<VertexAndEdgeListGraph>::edge_iterator ei, ei_end;
416
417    for (tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui) {
418      vis.initialize_vertex(*ui, g);
419    }
420
421    for (tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) {
422      put(distance, *ei, inf);
423      put(edge_color, *ei, EdgeColor::white());
424      predecessor[g[*ei].id] = *ei;
425      put(cost, *ei, inf);
426    }
427
428    put(distance, s, zero);
429
430    put(cost, s, h(s));
431
432    shooting_star_search_no_init
433      (g, s, h, vis, predecessor, cost, distance, weight, edge_map,
434       color, edge_color, history, index_map, compare, combine, inf, zero, e_max_id);
435   
436  }
437 
438  namespace detail {
439    template <class VertexAndEdgeListGraph, class AStarHeuristic,
440              class CostMap, class DistanceMap, class WeightMap, class EdgeMap,
441              class IndexMap,
442              class PredecessorMap,
443              class ColorMap, class EdgeColorMap,
444              class HistoryMap, class Params>
445    inline void
446    shooting_star_dispatch2
447      (VertexAndEdgeListGraph& g,
448       typename graph_traits<VertexAndEdgeListGraph>::edge_descriptor s,
449       AStarHeuristic h, CostMap cost, DistanceMap distance,
450       WeightMap weight, EdgeMap edge_map, IndexMap index_map,
451       PredecessorMap& predecessor, ColorMap color,
452       EdgeColorMap edge_color, HistoryMap history, const Params& params,
453       int e_max_id)
454    {
455      dummy_property_map p_map;
456      typedef typename property_traits<CostMap>::value_type C;
457      shooting_star_search
458        (g, s, h,
459         choose_param(get_param(params, graph_visitor),
460                      make_shooting_star_visitor(null_visitor())),
461         predecessor,
462         cost, distance, weight, edge_map, index_map, color, edge_color, history,
463         choose_param(get_param(params, distance_compare_t()),
464                      std::less<C>()),
465         choose_param(get_param(params, distance_combine_t()),
466                      closed_plus<C>()),
467         choose_param(get_param(params, distance_inf_t()),
468                      std::numeric_limits<C>::max BOOST_PREVENT_MACRO_SUBSTITUTION ()),
469         choose_param(get_param(params, distance_zero_t()),
470                      C()),
471         e_max_id
472        );
473    }
474 
475    template <class VertexAndEdgeListGraph, class AStarHeuristic,
476              class CostMap, class DistanceMap, class WeightMap,
477              class EdgeMap, class IndexMap,
478              class PredecessorMap,
479              class ColorMap, class EdgeColorMap,
480              class HistoryMap, class Params>
481    inline void
482    shooting_star_dispatch1
483      (VertexAndEdgeListGraph& g,
484       typename graph_traits<VertexAndEdgeListGraph>::edge_descriptor s,
485       AStarHeuristic h, CostMap cost, DistanceMap distance,
486       WeightMap weight, EdgeMap edge_map, IndexMap index_map, PredecessorMap& predecessor,
487       ColorMap color, EdgeColorMap edge_color, HistoryMap history, const Params& params,
488       int e_max_id)
489    {
490      typedef typename property_traits<WeightMap>::value_type D;
491      typename std::vector<D>::size_type
492        n = is_default_param(distance) ? num_vertices(g) : 1;
493      std::vector<D> distance_map(n);
494      n = is_default_param(cost) ? num_vertices(g) : 1;
495      std::vector<D> cost_map(n);
496
497      std::vector<default_color_type> color_map(num_vertices(g));
498      std::vector<default_color_type> edge_color_map(num_edges(g));
499      default_color_type c = white_color;
500     
501      detail::shooting_star_dispatch2
502        (g, s, h,
503         choose_param(cost, make_iterator_property_map
504                      (cost_map.begin(), index_map,
505                       cost_map[0])),
506         choose_param(distance, make_iterator_property_map
507                      (distance_map.begin(), index_map,
508                       distance_map[0])),
509         weight, edge_map, index_map,
510         predecessor,
511         choose_param(color, make_iterator_property_map
512                      (color_map.begin(), index_map, c)),
513         edge_color,
514         history,
515         params,
516         e_max_id);
517    }
518  } // namespace detail
519 
520  // Named parameter interface
521  template <typename VertexAndEdgeListGraph,
522            typename AStarHeuristic,
523            typename P, typename T, typename R,
524            typename IndexMap,
525            typename DistanceMap,
526            typename CostMap,
527            typename HistoryMap,
528            typename PredecessorMap>
529  void
530  shooting_star_search
531    (VertexAndEdgeListGraph &g,
532     typename graph_traits<VertexAndEdgeListGraph>::edge_descriptor s,
533     AStarHeuristic h, const bgl_named_params<P, T, R>& params,
534     IndexMap edge_index,
535     DistanceMap distance,
536     CostMap cost,
537     HistoryMap history,
538     PredecessorMap &pre_map,
539     int e_max_id)
540  {
541    typedef typename graph_traits<VertexAndEdgeListGraph>::edge_descriptor tEdge;
542
543    detail::shooting_star_dispatch1
544      (g, s, h,
545       cost,
546       distance,
547       choose_const_pmap(get_param(params, edge_weight), g, edge_weight), //weight
548       choose_const_pmap(get_param(params, edge_weight2), g, edge_weight2), //adjacent edges cost
549       edge_index,
550       pre_map, //predecessors
551       get_param(params, vertex_color), //vertex color (deprecated)
552       get_param(params, edge_color), //edge color
553       history,
554       params,
555       e_max_id
556       );   
557  }
558 
559} // namespace boost
560
561#endif // BOOST_GRAPH_SHOOTING_STAR_SEARCH_HPP
Note: See TracBrowser for help on using the browser.