pgRouting  2.2
pgRouting extends the PostGIS / PostgreSQL geospatial database to provide geospatial routing functionality.
 All Classes Functions Variables Pages
shooting_star_search.hpp
1 /*PGR-GNU*****************************************************************
2 
3 Copyright (c) 2015 pgRouting developers
4 Mail: project@pgrouting.org
5 
6 ------
7 
8 This program is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 2 of the License, or
11 (at your option) any later version.
12 
13 This program is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
17 
18 You should have received a copy of the GNU General Public License
19 along with this program; if not, write to the Free Software
20 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
21 
22 ********************************************************************PGR-GNU*/
23 //
24 //=======================================================================
25 // Copyright (c) 2004 Kristopher Beevers
26 // 2007 Anton A. Patrushev, Orkney Inc.
27 //
28 // Distributed under the Boost Software License, Version 1.0. (See
29 // accompanying file LICENSE_1_0.txt or copy at
30 // http://www.boost.org/LICENSE_1_0.txt)
31 //=======================================================================
32 //
33 
34 #ifndef BOOST_GRAPH_SHOOTING_STAR_SEARCH_HPP
35 #define BOOST_GRAPH_SHOOTING_STAR_SEARCH_HPP
36 
37 #define MAX_RULE_LENGTH 5
38 
39 #include <functional>
40 #include <boost/limits.hpp>
41 #include <boost/graph/named_function_params.hpp>
42 #include <boost/pending/mutable_queue.hpp>
43 #include <boost/pending/relaxed_heap.hpp>
44 #include <shooting_star_relax.hpp>
45 #include <boost/pending/indirect_cmp.hpp>
46 #include <boost/graph/exception.hpp>
47 #include <boost/graph/breadth_first_search.hpp>
48 
49 #include <queue>
50 #include "edge_visitors.hpp"
51 
52 template <class Edge>
54 {
55  bool operator()(const Edge& LHS, const Edge& RHS)
56  {
57  return (LHS.rank < RHS.rank);
58  }
59 
60 };
61 
62 template <class Edge, class Container, class Cmp>
63 class edge_queue : public std::priority_queue<Edge, Container, Cmp>
64 {
65 protected:
66  using std::priority_queue< Edge, Container, Cmp >::c;
67  using std::priority_queue< Edge, Container, Cmp >::comp;
68 
69 public:
70  void sort()
71  {
72  sort_heap(c.begin(), c.end(), comp);
73  }
74 };
75 
76 namespace boost
77 {
78 
79  template <class Heuristic, class Graph>
81  {
82  void constraints()
83  {
84  function_requires< CopyConstructibleConcept<Heuristic> >();
85  h(u);
86  }
87  Heuristic h;
88  typename graph_traits<Graph>::vertex_descriptor u;
89  };
90 
91 
92 
93  template <class Graph, class CostType>
94  class astar_heuristic : public std::unary_function<
95  typename graph_traits<Graph>::vertex_descriptor, CostType>
96  {
97  public:
98  typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
99  astar_heuristic() {}
100  CostType operator()(Vertex u) { return static_cast<CostType>(0); }
101  };
102 
103 
104  template <class Visitor, class Graph>
106  void constraints()
107  {
108  function_requires< CopyConstructibleConcept<Visitor> >();
109  vis.initialize_vertex(u, g);
110  vis.discover_vertex(u, g);
111  vis.examine_vertex(u, g);
112  vis.examine_edge(e, g, e_max_id);
113  vis.black_target(e, pe, s, g, e_max_id);
114  vis.gray_target(e, pe, s, g, e_max_id);
115  vis.finish_vertex(u, g);
116 
117  vis.tree_edge(e, pe, s, g, e_max_id);
118 
119  vis.initialize_edge(e, g);
120  vis.discover_edge(e, g);
121  vis.finish_edge(e, g);
122 
123  }
124  Visitor vis;
125  Graph g;
126  typename graph_traits<Graph>::vertex_descriptor u;
127  typename graph_traits<Graph>::edge_descriptor e, pe, s;
128  int e_max_id;
129  };
130 
131 
132  // Main visitor function.
133  // It decides what to do with an edge of certain color
134 
135  template <class IncidenceGraph, class Buffer, class BFSVisitor,
136  class ColorMap, class EdgeColorMap/*, class HistoryMap*/>
137  void shooting_star_edges_visit (const IncidenceGraph& g,
138  typename graph_traits<IncidenceGraph>::edge_descriptor s,
139  Buffer& Q, BFSVisitor vis, ColorMap color, EdgeColorMap edge_color,
140  int e_max_id)
141  {
142  function_requires< IncidenceGraphConcept<IncidenceGraph> >();
143  typedef graph_traits<IncidenceGraph> GTraits;
144  typedef typename GTraits::vertex_descriptor Vertex;
145  typedef typename GTraits::edge_descriptor Edge;
146  function_requires< ShootingStarVisitorConcept<BFSVisitor, IncidenceGraph> >();
147  function_requires< ReadWritePropertyMapConcept<EdgeColorMap, Edge> >();
148 
149  typedef typename property_traits<ColorMap>::value_type ColorValue;
150  typedef color_traits<ColorValue> Color;
151 
152  typedef typename property_traits<EdgeColorMap>::value_type EdgeColorValue;
153  typedef color_traits<EdgeColorValue> EdgeColor;
154 
155  typename GTraits::out_edge_iterator ei, ei_end;
156 
157  // Paint source edge gray
158  put(edge_color, s, EdgeColor::gray());
159  vis.discover_edge(s, g);
160 
161  // Enqueue the source edge
162  Q.push(s);
163 
164  // While the queue is not empty
165  while (! Q.empty())
166  {
167  // Get an edge from the top
168  Edge e = Q.top(); Q.pop();
169 
170  // Examine the edge
171  vis.examine_edge(e, g, e_max_id);
172 
173  // For all adjacent edges for the current one
174  for (tie(ei, ei_end) = out_edges(target(e, g), g); ei != ei_end; ++ei)
175  {
176  // Get a color
177  EdgeColorValue e_color = get(edge_color, *ei);
178 
179  // Discover the edge and paint it grey
180  // and enqueue it if it was white
181  if (e_color == EdgeColor::white())
182  {
183  vis.tree_edge(*ei, e, s, g, e_max_id);
184  put(edge_color, *ei, EdgeColor::gray());
185  vis.discover_edge(*ei, g);
186  Q.push(*ei);
187  }
188  // or execute appropriate function
189  // if it was grey or black
190  else
191  {
192  vis.non_tree_edge(*ei, g);
193  if (e_color == EdgeColor::gray())
194  {
195  vis.gray_target(*ei, e, s, g, e_max_id);
196  }
197  else
198  {
199  vis.black_target(*ei, e, s, g, e_max_id);
200  }
201  }
202 
203  } // end for
204 
205  // Finally paint the parent edge black
206  put(edge_color, e, EdgeColor::black());
207  vis.finish_edge(e, g);
208 
209  } // end while
210  }
211 
212 
213  template <class Visitors = null_visitor>
214  class shooting_star_visitor : public bfs_visitor<Visitors>
215  {
216  public:
218  shooting_star_visitor(Visitors vis)
219  : bfs_visitor<Visitors>(vis) {}
220 
221  template <class Edge, class Graph>
222  void edge_relaxed(Edge e, Graph& g)
223  {
224  invoke_visitors(this->m_vis, e, g, on_edge_relaxed());
225  }
226  template <class Edge, class Graph>
227  void edge_not_relaxed(Edge e, Graph& g)
228  {
229  invoke_visitors(this->m_vis, e, g, on_edge_not_relaxed());
230  }
231  template <class Edge, class Graph>
232  void initialize_edge(Edge e, Graph& g)
233  {
234  invoke_visitors(this->m_vis, e, g, on_initialize_edge());
235  }
236 
237  private:
238  template <class Edge, class Graph>
239  void tree_edge(Edge e, Edge pe, Edge s, Graph& g) {}
240  template <class Edge, class Graph>
241  void non_tree_edge(Edge e, Graph& g) {}
242  };
243 
244  template <class Visitors>
246  make_shooting_star_visitor(Visitors vis)
247  {
249  }
250 
251  typedef shooting_star_visitor<> default_shooting_star_visitor;
252 
253 
254  namespace detail {
255 
256  // Shooting* visitor
257  // based on BFS visitor concept from BGL
258  template <class AStarHeuristic, class UniformCostVisitor,
259  class UpdatableQueue, class PredecessorMap,
260  class CostMap,
261  class DistanceMap, class WeightMap,
262  class EdgeMap,
263  class ColorMap, class EdgeColorMap,
264  class BinaryFunction,
265  class BinaryPredicate>
267  {
268 
269  typedef typename property_traits<CostMap>::value_type C;
270  typedef typename property_traits<ColorMap>::value_type ColorValue;
271  typedef color_traits<ColorValue> Color;
272 
273  typedef typename property_traits<EdgeColorMap>::value_type EdgeColorValue;
274  typedef color_traits<ColorValue> EdgeColor;
275 
276  typedef typename property_traits<DistanceMap>::value_type distance_type;
277 
278  shooting_star_bfs_visitor(AStarHeuristic h, UniformCostVisitor vis,
279  UpdatableQueue& Q, PredecessorMap& p,
280  CostMap c, DistanceMap d, WeightMap w, EdgeMap em,
281  ColorMap col, EdgeColorMap ecol, //HistoryMap his,
282  BinaryFunction combine,
283  BinaryPredicate compare, C zero)
284  : m_h(h), m_vis(vis), m_Q(Q), m_predecessor(p), m_cost(c),
285  m_distance(d), m_weight(w), m_edge(em), m_color(col),
286  m_ecolor(ecol), //m_history(his),
287  m_combine(combine), m_compare(compare), m_zero(zero) {}
288 
290  : m_h(v.m_h), m_vis(v.m_vis), m_Q(v.m_Q), m_predecessor(v.m_predecessor), m_cost(v.m_cost),
291  m_distance(v.m_distance), m_weight(v.m_weight), m_edge(v.m_edge), m_color(v.m_color),
292  m_ecolor(v.m_ecolor), //m_history(his),
293  m_combine(v.m_combine), m_compare(v.m_compare), m_zero(v.m_zero) {}
294 
296 
297  template <class Vertex, class Graph>
298  void initialize_vertex(Vertex u, Graph& g)
299  {
300  m_vis.initialize_vertex(u, g);
301  }
302  template <class Edge, class Graph>
303  void initialize_edge(Edge e, Graph& g)
304  {
305  m_vis.initialize_edge(e, g);
306  }
307  template <class Vertex, class Graph>
308  void discover_vertex(Vertex u, Graph& g)
309  {
310  m_vis.discover_vertex(u, g);
311  }
312  template <class Edge, class Graph>
313  void discover_edge(Edge e, Graph& g)
314  {
315  m_vis.discover_vertex(e, g);
316  }
317  template <class Vertex, class Graph>
318  void examine_vertex(Vertex u, Graph& g)
319  {
320  m_vis.examine_vertex(u, g);
321  }
322  template <class Vertex, class Graph>
323  void finish_vertex(Vertex u, Graph& g)
324  {
325  m_vis.finish_vertex(u, g);
326  }
327  template <class Edge, class Graph>
328  void examine_edge(Edge e, Graph& g, int e_max_id)
329  {
330  if (m_compare(get(m_weight, e), m_zero))
331  throw negative_edge();
332  m_vis.examine_edge(e, g, e_max_id);
333  }
334  template <class Edge, class Graph>
335  void non_tree_edge(Edge, Graph&) {}
336 
337  template <class Edge, class Graph>
338  void finish_edge(Edge e, Graph& g)
339  {
340  m_vis.finish_edge(e, g);
341  }
342 
343 
344  template <class Edge, class Graph>
345  void tree_edge(Edge e, Edge pe, Edge s, Graph& g, int e_max_id)
346  {
347  m_decreased = relax(e, pe, s, g, m_weight, m_edge, m_predecessor, m_distance,
348  m_cost, m_combine, m_compare, e_max_id);
349 
350  if(m_decreased)
351  {
352  m_vis.edge_relaxed(e, g);
353 
354  put(m_cost, e,
355  m_combine(get(m_distance, e),
356  m_h(e)));
357 
358  }
359  else
360  m_vis.edge_not_relaxed(e, g);
361  }
362 
363 
364  template <class Edge, class Graph>
365  void gray_target(Edge e, Edge pe, Edge s, Graph& g, int e_max_id)
366  {
367  m_decreased = relax(e, pe, s, g, m_weight, m_edge, m_predecessor, m_distance,
368  m_cost, m_combine, m_compare, e_max_id);
369 
370  if(m_decreased)
371  {
372  put(m_cost, e,
373  m_combine(get(m_distance, e),
374  m_h(e)));
375 
376  m_Q.update(e);
377 
378  m_vis.edge_relaxed(e, g);
379  }
380  else
381  m_vis.edge_not_relaxed(e, g);
382  }
383 
384 
385  template <class Edge, class Graph>
386  void black_target(Edge e, Edge pe, Edge s, Graph& g, int e_max_id)
387  {
388 
389  m_decreased = relax(e, pe, s, g, m_weight, m_edge, m_predecessor, m_distance,
390  m_cost, m_combine, m_compare, e_max_id);
391 
392  if(m_decreased)
393  {
394  m_vis.edge_relaxed(e, g);
395  put(m_cost, e, m_combine(get(m_distance, e), m_h(e)));
396 
397  m_Q.push(e);
398  put(m_ecolor, e, EdgeColor::gray());
399  m_vis.black_target(e, g);
400  }
401  else
402  m_vis.edge_not_relaxed(e, g);
403  }
404 
405  AStarHeuristic m_h;
406  UniformCostVisitor m_vis;
407  UpdatableQueue& m_Q;
408  PredecessorMap& m_predecessor;
409  CostMap m_cost;
410  EdgeMap m_edge;
411  DistanceMap m_distance;
412  WeightMap m_weight;
413  ColorMap m_color;
414  EdgeColorMap m_ecolor;
415  BinaryFunction m_combine;
416  BinaryPredicate m_compare;
417  bool m_decreased;
418  C m_zero;
419  };
420 
421  } // namespace detail
422 
423  template <typename VertexAndEdgeListGraph, typename AStarHeuristic,
424  typename ShootingStarVisitor, typename PredecessorMap,
425  typename CostMap,
426  typename DistanceMap,
427  typename WeightMap,
428  typename EdgeMap,
429  typename ColorMap, typename EdgeColorMap,
430  typename IndexMap,
431  typename CompareFunction, typename CombineFunction,
432  typename CostInf, typename CostZero>
433  inline void
434  shooting_star_search_no_init
435  (VertexAndEdgeListGraph &g,
436  typename graph_traits<VertexAndEdgeListGraph>::edge_descriptor s,
437  AStarHeuristic h, ShootingStarVisitor vis,
438  PredecessorMap &predecessor, CostMap cost,
439  DistanceMap distance, WeightMap weight, EdgeMap edge_map,
440  ColorMap color, EdgeColorMap edge_color,
441  IndexMap index_map, CompareFunction compare, CombineFunction combine,
442  CostInf inf, CostZero zero, int e_max_id)
443  {
444  typedef indirect_cmp<CostMap, CompareFunction> IndirectCmp;
445  IndirectCmp icmp(cost, compare);
446 
447  typedef typename graph_traits<VertexAndEdgeListGraph>::edge_descriptor
448  Edge;
449 
450  // Queue to store the list of edges to examine.
451  // I really hate this queue for what it does with the memory sometimes.
452  //
453  //And by the way...
454  //
455  //This place is for rent :)
456  //
457  typedef mutable_queue<Edge, std::vector<Edge>, IndirectCmp, IndexMap>
458  MutableQueue;
459  MutableQueue Q(num_edges(g), icmp, index_map);
460 
461  detail::shooting_star_bfs_visitor<AStarHeuristic, ShootingStarVisitor,
462  MutableQueue, PredecessorMap, CostMap, DistanceMap,
463  WeightMap, EdgeMap, ColorMap, EdgeColorMap, /*HistoryMap,*/ CombineFunction, CompareFunction>
464  bfs_vis(h, vis, Q, predecessor, cost, distance, weight,
465  edge_map, color, edge_color, combine, compare, zero);
466 
467  shooting_star_edges_visit(g, s, Q, bfs_vis, color, edge_color, e_max_id);
468  }
469 
470  // Non-named parameter interface
471  template <typename VertexAndEdgeListGraph, typename AStarHeuristic,
472  typename ShootingStarVisitor, typename PredecessorMap,
473  typename CostMap, typename DistanceMap,
474  typename WeightMap, typename EdgeMap,
475  typename IndexMap,
476  typename ColorMap, typename EdgeColorMap,
477  //typename HistoryMap,
478  typename CompareFunction, typename CombineFunction,
479  typename CostInf, typename CostZero>
480  inline void
481  shooting_star_search
482  (VertexAndEdgeListGraph &g,
483  typename graph_traits<VertexAndEdgeListGraph>::edge_descriptor s,
484  AStarHeuristic h, ShootingStarVisitor vis,
485  PredecessorMap &predecessor, CostMap cost,
486  DistanceMap distance, WeightMap weight,
487  EdgeMap edge_map, IndexMap index_map, ColorMap color, EdgeColorMap edge_color,
488  CompareFunction compare, CombineFunction combine,
489  CostInf inf, CostZero zero, int e_max_id)
490  {
491 
492  typedef typename property_traits<ColorMap>::value_type ColorValue;
493  typedef color_traits<ColorValue> Color;
494 
495  typedef typename property_traits<EdgeColorMap>::value_type EdgeColorValue;
496  typedef color_traits<EdgeColorValue> EdgeColor;
497 
498  typename graph_traits<VertexAndEdgeListGraph>::vertex_iterator ui, ui_end;
499  typename graph_traits<VertexAndEdgeListGraph>::edge_iterator ei, ei_end;
500 
501  for (tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui)
502  {
503  vis.initialize_vertex(*ui, g);
504  }
505 
506  for (tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
507  {
508  put(distance, *ei, inf);
509  put(edge_color, *ei, EdgeColor::white());
510  predecessor[g[*ei].id] = *ei;
511  put(cost, *ei, inf);
512  }
513 
514  put(distance, s, zero);
515 
516  put(cost, s, h(s));
517 
518  shooting_star_search_no_init
519  (g, s, h, vis, predecessor, cost, distance, weight, edge_map,
520  color, edge_color, index_map, compare, combine, inf, zero, e_max_id);
521 
522  }
523 
524  namespace detail
525  {
526  template <class VertexAndEdgeListGraph, class AStarHeuristic,
527  class CostMap, class DistanceMap, class WeightMap, class EdgeMap,
528  class IndexMap,
529  class PredecessorMap,
530  class ColorMap, class EdgeColorMap,
531  class Params>
532  inline void
533  shooting_star_dispatch2
534  (VertexAndEdgeListGraph& g,
535  typename graph_traits<VertexAndEdgeListGraph>::edge_descriptor s,
536  AStarHeuristic h, CostMap cost, DistanceMap distance,
537  WeightMap weight, EdgeMap edge_map, IndexMap index_map,
538  PredecessorMap& predecessor, ColorMap color,
539  EdgeColorMap edge_color, const Params& params,
540  int e_max_id)
541  {
542  dummy_property_map p_map;
543  typedef typename property_traits<CostMap>::value_type C;
544  shooting_star_search
545  (g, s, h,
546  choose_param(get_param(params, graph_visitor),
547  make_shooting_star_visitor(null_visitor())),
548  predecessor,
549  cost, distance, weight, edge_map, index_map, color, edge_color, //history,
550  choose_param(get_param(params, distance_compare_t()),
551  std::less<C>()),
552  choose_param(get_param(params, distance_combine_t()),
553  closed_plus<C>()),
554  choose_param(get_param(params, distance_inf_t()),
555  std::numeric_limits<C>::max BOOST_PREVENT_MACRO_SUBSTITUTION ()),
556  choose_param(get_param(params, distance_zero_t()),
557  C()),
558  e_max_id
559  );
560  }
561 
562  template <class VertexAndEdgeListGraph, class AStarHeuristic,
563  class CostMap, class DistanceMap, class WeightMap,
564  class EdgeMap, class IndexMap,
565  class PredecessorMap,
566  class ColorMap, class EdgeColorMap,
567  class Params>
568  inline void
569  shooting_star_dispatch1
570  (VertexAndEdgeListGraph& g,
571  typename graph_traits<VertexAndEdgeListGraph>::edge_descriptor s,
572  AStarHeuristic h, CostMap cost, DistanceMap distance,
573  WeightMap weight, EdgeMap edge_map, IndexMap index_map, PredecessorMap& predecessor,
574  ColorMap color, EdgeColorMap edge_color, const Params& params,
575  int e_max_id)
576  {
577  typedef typename property_traits<WeightMap>::value_type D;
578  typename std::vector<D>::size_type
579  n = is_default_param(distance) ? num_vertices(g) : 1;
580  std::vector<D> distance_map(n);
581  n = is_default_param(cost) ? num_vertices(g) : 1;
582  std::vector<D> cost_map(n);
583 
584  std::vector<default_color_type> color_map(num_vertices(g));
585  default_color_type c = white_color;
586 
587  detail::shooting_star_dispatch2
588  (g, s, h,
589  choose_param(cost, make_iterator_property_map
590  (cost_map.begin(), index_map,
591  cost_map[0])),
592  choose_param(distance, make_iterator_property_map
593  (distance_map.begin(), index_map,
594  distance_map[0])),
595  weight, edge_map, index_map,
596  predecessor,
597  choose_param(color, make_iterator_property_map
598  (color_map.begin(), index_map, c)),
599  edge_color,
600  params,
601  e_max_id);
602  }
603  } // namespace detail
604 
605  // Named parameter interface
606  template <typename VertexAndEdgeListGraph,
607  typename AStarHeuristic,
608  typename P, typename T, typename R,
609  typename IndexMap,
610  typename DistanceMap,
611  typename CostMap,
612  typename PredecessorMap>
613  void
614  shooting_star_search
615  (VertexAndEdgeListGraph &g,
616  typename graph_traits<VertexAndEdgeListGraph>::edge_descriptor s,
617  AStarHeuristic h, const bgl_named_params<P, T, R>& params,
618  IndexMap edge_index,
619  DistanceMap distance,
620  CostMap cost,
621  PredecessorMap &pre_map,
622  int e_max_id)
623  {
624  typedef typename graph_traits<VertexAndEdgeListGraph>::edge_descriptor tEdge;
625 
626  detail::shooting_star_dispatch1
627  (g, s, h,
628  cost,
629  distance,
630  choose_const_pmap(get_param(params, edge_weight), g, edge_weight), //weight
631  choose_const_pmap(get_param(params, edge_weight2), g, edge_weight2), //adjacent edges cost
632  edge_index,
633  pre_map, //predecessors
634  get_param(params, vertex_color), //vertex color (deprecated)
635  get_param(params, edge_color), //edge color
636  params,
637  e_max_id
638  );
639  }
640 
641 } // namespace boost
642 
643 #endif // BOOST_GRAPH_SHOOTING_STAR_SEARCH_HPP