PGROUTING  2.6
pgr_dijkstra.hpp
Go to the documentation of this file.
1 /*PGR-GNU*****************************************************************
2 
3 Copyright (c) 2015 pgRouting developers
4 Mail: project@pgrouting.org
5 
6 Copyright (c) 2015 Celia Virginia Vergara Castillo
7 vicky_vergara@hotmail.com
8 
9 ------
10 
11 This program is free software; you can redistribute it and/or modify
12 it under the terms of the GNU General Public License as published by
13 the Free Software Foundation; either version 2 of the License, or
14 (at your option) any later version.
15 
16 This program is distributed in the hope that it will be useful,
17 but WITHOUT ANY WARRANTY; without even the implied warranty of
18 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19 GNU General Public License for more details.
20 
21 You should have received a copy of the GNU General Public License
22 along with this program; if not, write to the Free Software
23 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
24 
25 ********************************************************************PGR-GNU*/
26 
27 #ifndef INCLUDE_DIJKSTRA_PGR_DIJKSTRA_HPP_
28 #define INCLUDE_DIJKSTRA_PGR_DIJKSTRA_HPP_
29 #pragma once
30 
31 #include <boost/config.hpp>
32 #include <boost/graph/adjacency_list.hpp>
33 #include <boost/graph/dijkstra_shortest_paths.hpp>
34 
35 #include <deque>
36 #include <set>
37 #include <vector>
38 #include <algorithm>
39 #include <sstream>
40 #include <functional>
41 #include <limits>
42 
45 #if 0
46 #include "./../../common/src/signalhandler.h"
47 #endif
48 
49 
50 template < class G > class Pgr_dijkstra;
51 // user's functions
52 // for development
53 
54 template < class G >
55 std::deque<Path>
57  G &graph,
58  std::vector< int64_t > start_vids,
59  double distance,
60  bool equicost,
61  std::ostringstream &log) {
62  Pgr_dijkstra< G > fn_dijkstra;
63  return fn_dijkstra.drivingDistance(
64  graph,
65  start_vids,
66  distance,
67  equicost,
68  log);
69 }
70 
71 
72 /* 1 to 1*/
73 template < class G >
74 Path
76  G &graph,
77  int64_t source,
78  int64_t target,
79  bool only_cost = false) {
80  Pgr_dijkstra< G > fn_dijkstra;
81  return fn_dijkstra.dijkstra(graph, source, target, only_cost);
82 }
83 
84 
85 
86 
87 //******************************************
88 
89 template < class G >
90 class Pgr_dijkstra {
91  public:
92  typedef typename G::V V;
93  typedef typename G::E E;
94 
96 
99  G &graph,
100  int64_t start_vertex,
101  double distance) {
103  graph,
104  start_vertex,
105  distance)) {
106  auto path = Path(graph,
107  start_vertex,
108  distance,
109  predecessors,
110  distances);
111 
112  std::sort(path.begin(), path.end(),
113  [](const Path_t &l, const Path_t &r)
114  {return l.node < r.node;});
115  std::stable_sort(path.begin(), path.end(),
116  [](const Path_t &l, const Path_t &r)
117  {return l.agg_cost < r.agg_cost;});
118  return path;
119  }
120 
121  /* The result is empty */
122  Path p(start_vertex, start_vertex);
123  p.push_back({start_vertex, -1, 0, 0});
124  return p;
125  }
126 
127  // preparation for many to distance
128  std::deque< Path > drivingDistance(
129  G &graph,
130  const std::vector< int64_t > start_vertex,
131  double distance,
132  bool equicost,
133  std::ostringstream &the_log) {
134  if (equicost) {
135  auto paths = drivingDistance_with_equicost(
136  graph,
137  start_vertex,
138  distance);
139  the_log << log.str();
140  return paths;
141  } else {
143  graph,
144  start_vertex,
145  distance);
146  }
147  }
148 
149 
150 
151 
152 
153 
155 
157 
158  Path dijkstra(
160  G &graph,
161  int64_t start_vertex,
162  int64_t end_vertex,
163  bool only_cost = false) {
164  clear();
165 
166  // adjust predecessors and distances vectors
167  predecessors.resize(graph.num_vertices());
168  distances.resize(graph.num_vertices());
169 
170 
171  if (!graph.has_vertex(start_vertex)
172  || !graph.has_vertex(end_vertex)) {
173  return Path(start_vertex, end_vertex);
174  }
175 
176  // get the graphs source and target
177  auto v_source(graph.get_V(start_vertex));
178  auto v_target(graph.get_V(end_vertex));
179 
180  // perform the algorithm
181  dijkstra_1_to_1(graph, v_source, v_target);
182 
183  // get the results
184  return Path(
185  graph,
186  v_source, v_target,
188  only_cost, true);
189  }
190 
191 
192 
193 
194 
195 
197  std::deque<Path> dijkstra(
198  G &graph,
199  int64_t start_vertex,
200  const std::vector< int64_t > &end_vertex,
201  bool only_cost) {
202  // adjust predecessors and distances vectors
203  clear();
204 
205  predecessors.resize(graph.num_vertices());
206  distances.resize(graph.num_vertices());
207 
208  // get the graphs source and target
209  if (!graph.has_vertex(start_vertex))
210  return std::deque<Path>();
211  auto v_source(graph.get_V(start_vertex));
212 
213  std::set< V > s_v_targets;
214  for (const auto &vertex : end_vertex) {
215  if (graph.has_vertex(vertex)) {
216  s_v_targets.insert(graph.get_V(vertex));
217  }
218  }
219 
220  std::vector< V > v_targets(s_v_targets.begin(), s_v_targets.end());
221  // perform the algorithm
222  dijkstra_1_to_many(graph, v_source, v_targets);
223 
224  std::deque< Path > paths;
225  // get the results // route id are the targets
226  paths = get_paths(graph, v_source, v_targets, only_cost);
227 
228  std::stable_sort(paths.begin(), paths.end(),
229  [](const Path &e1, const Path &e2)->bool {
230  return e1.end_id() < e2.end_id();
231  });
232 
233  return paths;
234  }
235 
236  // preparation for many to 1
237  std::deque<Path> dijkstra(
238  G &graph,
239  const std::vector < int64_t > &start_vertex,
240  int64_t end_vertex,
241  bool only_cost) {
242  std::deque<Path> paths;
243 
244  for (const auto &start : start_vertex) {
245  paths.push_back(
246  dijkstra(graph, start, end_vertex, only_cost));
247  }
248 
249  std::stable_sort(paths.begin(), paths.end(),
250  [](const Path &e1, const Path &e2)->bool {
251  return e1.start_id() < e2.start_id();
252  });
253  return paths;
254  }
255 
256 
257  // preparation for many to many
258  std::deque<Path> dijkstra(
259  G &graph,
260  const std::vector< int64_t > &start_vertex,
261  const std::vector< int64_t > &end_vertex,
262  bool only_cost) {
263  // a call to 1 to many is faster for each of the sources
264  std::deque<Path> paths;
265  for (const auto &start : start_vertex) {
266  auto r_paths = dijkstra(graph, start, end_vertex, only_cost);
267  paths.insert(paths.begin(), r_paths.begin(), r_paths.end());
268  }
269 
270  std::sort(paths.begin(), paths.end(),
271  [](const Path &e1, const Path &e2)->bool {
272  return e1.end_id() < e2.end_id();
273  });
274  std::stable_sort(paths.begin(), paths.end(),
275  [](const Path &e1, const Path &e2)->bool {
276  return e1.start_id() < e2.start_id();
277  });
278  return paths;
279  }
280 
282 
283  private:
286  G &graph,
287  V source,
288  V target) {
289  try {
290  boost::dijkstra_shortest_paths(graph.graph, source,
291  boost::predecessor_map(&predecessors[0])
292  .weight_map(get(&G::G_T_E::cost, graph.graph))
293  .distance_map(&distances[0])
294  .visitor(dijkstra_one_goal_visitor(target)));
295  } catch(found_goals &) {
296  return true;
297  } catch (boost::exception const& ex) {
298  (void)ex;
299  throw;
300  } catch (std::exception &e) {
301  (void)e;
302  throw;
303  } catch (...) {
304  throw;
305  }
306  return true;
307  }
308 
317  G &graph,
318  V source,
319  double distance) {
320  try {
321  boost::dijkstra_shortest_paths(graph.graph, source,
322  boost::predecessor_map(&predecessors[0])
323  .weight_map(get(&G::G_T_E::cost, graph.graph))
324  .distance_map(&distances[0])
325  .visitor(dijkstra_distance_visitor(
326  distance,
328  distances)));
329  } catch(found_goals &) {
330  return true;
331  } catch (boost::exception const& ex) {
332  throw;
333  (void)ex;
334  } catch (std::exception &e) {
335  (void)e;
336  throw;
337  } catch (...) {
338  throw;
339  }
340  return true;
341  }
342 
349  G &graph,
350  V source,
351  double distance) {
352  pgassert(predecessors.size() == graph.num_vertices());
353  pgassert(distances.size() == graph.num_vertices());
354  distances[source] = 0;
355  std::vector<boost::default_color_type> color_map(graph.num_vertices());
356  try {
357  boost::dijkstra_shortest_paths_no_init(graph.graph, source,
358  make_iterator_property_map(
359  predecessors.begin(),
360  graph.vertIndex),
361  make_iterator_property_map(
362  distances.begin(),
363  graph.vertIndex),
364  get(&G::G_T_E::cost, graph.graph),
365  graph.vertIndex,
366  std::less<double>(),
367  boost::closed_plus<double>(),
368  static_cast<double>(0),
370  log,
371  source,
372  distance,
373  predecessors,
374  distances,
375  color_map),
376  boost::make_iterator_property_map(
377  color_map.begin(),
378  graph.vertIndex,
379  color_map[0]));
380  } catch(found_goals &) {
381  return true;
382  } catch (boost::exception const& ex) {
383  (void)ex;
384  throw;
385  } catch (std::exception &e) {
386  (void)e;
387  throw;
388  } catch (...) {
389  throw;
390  }
391 
392 #if 0
393  /*
394  * Expensive assertion
395  */
396  for (V v = 0 ; v < predecessors.size(); ++v) {
397  log << "(" << predecessors[v] << "==" << v << "),";
398  if (v != source) {
399  pgassertwm(predecessors[v] == v, log.str().c_str());
400  }
401  }
402 #endif
403  return true;
404  }
405 
406 
420  G &graph,
421  int64_t start_vertex,
422  double distance) {
423  clear();
424 
425  predecessors.resize(graph.num_vertices());
426  distances.resize(graph.num_vertices());
427 
428  // get source;
429  if (!graph.has_vertex(start_vertex)) {
430  return false;
431  }
432 
433  return dijkstra_1_to_distance(
434  graph,
435  graph.get_V(start_vertex),
436  distance);
437  }
438 
439 
453  G &graph,
454  V start_vertex,
455  double distance) {
456  pgassert(predecessors.size() == graph.num_vertices());
457  pgassert(distances.size() == graph.num_vertices());
458 
459  std::iota(predecessors.begin(), predecessors.end(), 0);
460 
461 #if 0
462  /*
463  * Expensive assertion
464  */
465  for (V i = 0 ; i < predecessors.size(); ++i) {
466  pgassert(i == predecessors[i]);
467  }
468 #endif
469 
471  graph,
472  start_vertex,
473  distance);
474  }
475 
476  /* preparation for many to distance with equicost
477  *
478  * Idea:
479  * The distances vector does not change
480  * The predecessors vector does not change
481  * The first @b valid execution is done normally:
482  * - The distances will have:
483  * - inf
484  * - values < distance
485  * - values > distance
486  * Subsequent @b valid executions
487  * - will not change the:
488  * - values < distance
489  * Don't know yet what happens to predecessors
490  */
491  std::deque< Path > drivingDistance_with_equicost(
492  G &graph,
493  const std::vector< int64_t > start_vertex,
494  double distance) {
495  clear();
496  log << "Number of edges:" << boost::num_edges(graph.graph) << "\n";
497 
498  predecessors.resize(graph.num_vertices());
499  distances.resize(
500  graph.num_vertices(),
501  std::numeric_limits<double>::max());
502 
503  /*
504  * Vector to store the different predessesors
505  * each is of size = graph.num_vertices()
506  *
507  * TODO(vicky)
508  * - figure out less storage if possible
509  */
510  std::deque< std::vector< V > > pred(start_vertex.size());
511 
512  // perform the algorithm
513  size_t i = 0;
514  for (const auto &vertex : start_vertex) {
515  nodesInDistance.clear();
516  /*
517  * The vertex does not exist
518  * Nothing to do
519  */
520  if (graph.has_vertex(vertex)) {
522  graph,
523  graph.get_V(vertex),
524  distance)) {
525  pred[i] = predecessors;
526  }
527  }
528  ++i;
529  }
530 
531 
532  /*
533  * predecessors of vertices in the set are themselves
534  */
535  for (const auto &vertex : start_vertex) {
536  for (auto &p : pred) {
537  if (!p.empty() & graph.has_vertex(vertex))
538  p[graph.get_V(vertex)] = graph.get_V(vertex);
539  }
540  }
541 
542 
544  graph,
545  start_vertex,
546  pred,
547  distance);
548  }
549 
558  G &graph,
559  const std::vector< int64_t > &start_vertex,
560  std::deque< std::vector< V > > &pred,
561  double distance) {
562  /*
563  * precondition
564  */
565  pgassert(start_vertex.size() == pred.size());
566 
567 
568  /*
569  * Creating all the result "paths"
570  */
571  std::deque<Path> paths;
572  for (const auto vertex : start_vertex) {
573  paths.push_back(Path(vertex, vertex));
574  paths.back().push_back({vertex, -1, 0, 0});
575  }
576 
577  /*
578  * Ciclying the distances:
579  * To which vertex do they belong to?
580  */
581  for (V d = 0; d < distances.size(); ++d) {
582  /*
583  * Sikiping distances greater than the one asked for
584  */
585  if (!(distances[d] <= distance)) continue;
586 
587  for (auto i = start_vertex.size(); i > 0; --i) {
588  /*
589  * The vertex does not exist on the graph
590  */
591  if (pred[i - 1].empty()) {pgassert(false); continue;}
592 
593 
594  /*
595  * The predecessor = current then
596  * its unreachable to this vertex
597  */
598  if (pred[i - 1][d] == d) continue;
599 
600  auto cost = distances[d] - distances[pred[i - 1][d]];
601  auto edge_id = graph.get_edge_id(pred[i - 1][d], d, cost);
602  pgassert(edge_id != -1);
603  paths[i - 1].push_back(
604  {graph[d].id,
605  edge_id, cost,
606  distances[d]});
607  break;
608  }
609  }
610 
611  for (auto &path : paths) {
612  path.sort_by_node_agg_cost();
613  }
614  return paths;
615  }
616 
617 
618  // preparation for many to distance No equicost
619  std::deque< Path > drivingDistance_no_equicost(
620  G &graph,
621  const std::vector< int64_t > start_vertex,
622  double distance) {
623  std::deque< std::vector< V > > pred;
624  std::deque< std::vector< double > > dist;
625 
626  // perform the algorithm
627  std::deque<Path> paths;
628  for (const auto &vertex : start_vertex) {
629  if (execute_drivingDistance(graph, vertex, distance)) {
630  auto path = Path(
631  graph,
632  vertex,
633  distance,
634  predecessors,
635  distances);
636  path.sort_by_node_agg_cost();
637  paths.push_back(path);
638  } else {
639  Path p(vertex, vertex);
640  p.push_back({vertex, -1, 0, 0});
641  paths.push_back(p);
642  }
643  }
644  return paths;
645  }
646 
647 
650  G &graph,
651  V source,
652  const std::vector< V > &targets) {
653  try {
654  boost::dijkstra_shortest_paths(graph.graph, source,
655  boost::predecessor_map(&predecessors[0])
656  .weight_map(get(&G::G_T_E::cost, graph.graph))
657  .distance_map(&distances[0])
658  .visitor(dijkstra_many_goal_visitor(targets)));
659  } catch(found_goals &) {
660  return true;
661  } catch (boost::exception const& ex) {
662  (void)ex;
663  throw;
664  } catch (std::exception &e) {
665  (void)e;
666  throw;
667  } catch (...) {
668  throw;
669  }
670  return true;
671  }
672 
673 
674  void clear() {
675  predecessors.clear();
676  distances.clear();
677  nodesInDistance.clear();
678  }
679 
680 
681 
682 
683  // used when multiple goals
684  std::deque<Path> get_paths(
685  const G &graph,
686  V source,
687  std::vector< V > &targets,
688  bool only_cost) const {
689  std::deque<Path> paths;
690  for (const auto target : targets) {
691  paths.push_back(Path(
692  graph,
693  source, target,
695  only_cost, true));
696  }
697  return paths;
698  }
699 
700 
701 
703 
704  struct found_goals{};
705  std::vector< V > predecessors;
706  std::vector< double > distances;
707  std::deque< V > nodesInDistance;
708  std::ostringstream log;
710 
712 
713  class dijkstra_one_goal_visitor : public boost::default_dijkstra_visitor {
715  public:
716  explicit dijkstra_one_goal_visitor(V goal) : m_goal(goal) {}
717  template <class B_G>
718  void examine_vertex(V &u, B_G &) {
719  if (u == m_goal) throw found_goals();
720  }
721  private:
723  };
724 
726  class dijkstra_many_goal_visitor : public boost::default_dijkstra_visitor {
727  public:
728  explicit dijkstra_many_goal_visitor(std::vector< V > goals)
729  :m_goals(goals.begin(), goals.end()) {}
730  template <class B_G>
731  void examine_vertex(V u, B_G &) {
732  auto s_it = m_goals.find(u);
733  if (s_it == m_goals.end()) return;
734  // we found one more goal
735  m_goals.erase(s_it);
736  if (m_goals.size() == 0) throw found_goals();
737  }
738  private:
739  std::set< V > m_goals;
740  };
741 
742 
744  class dijkstra_distance_visitor : public boost::default_dijkstra_visitor {
745  public:
747  double distance_goal,
748  std::deque< V > &nodesInDistance,
749  std::vector< double > &distances) :
750  m_distance_goal(distance_goal),
751  m_nodes(nodesInDistance),
752  m_dist(distances) {
753  pgassert(m_nodes.empty());
754  pgassert(m_distance_goal > 0);
755  }
756  template <class B_G>
757  void examine_vertex(V u, B_G &) {
758  if (m_dist[u] > m_distance_goal) {
759  throw found_goals();
760  }
761  m_nodes.push_back(u);
762  }
763 
764  private:
766  std::deque< V > &m_nodes;
767  std::vector< double > &m_dist;
768  };
769 
772  : public boost::default_dijkstra_visitor {
773  public:
775  std::ostringstream &p_log,
776  V source,
777  double distance_goal,
778  std::vector< V > &predecessors,
779  std::vector< double > &distances,
780  std::vector<boost::default_color_type> &color_map) :
781  log(p_log),
782  first(source),
783  m_distance_goal(distance_goal),
784  m_num_examined(0),
785  m_predecessors(predecessors),
786  m_dist(distances),
787  m_color(color_map) {
788  pgassert(m_num_examined == 0);
789  pgassert(m_distance_goal > 0);
790  }
791 
792  template <class B_G>
793  void examine_vertex(V u, B_G &) {
794  if ( 0 == m_num_examined++) first = u;
795  if (m_dist[u] > m_distance_goal) {
796  throw found_goals();
797  }
798  if (u != first && m_predecessors[u] == u) {
799  m_color[u] = boost::black_color;
800  }
801  }
802 
803  template <class B_G>
804  void examine_edge(E e, B_G &g) {
805  if (source(e, g) != first
806  && m_predecessors[source(e, g)] == source(e, g)) {
807  m_color[target(e, g)] = boost::black_color;
808  }
809  }
810 
811 
812  template <class B_G>
813  void edge_relaxed(E, B_G &) {
814  }
815 
816 
817 
818  template <class B_G>
819  void edge_not_relaxed(E e, B_G &g) {
820  if (source(e, g) != first
821  && m_predecessors[source(e, g)] == source(e, g)) {
822  m_color[target(e, g)] = boost::black_color;
823  }
824  }
825 
826 
827  template <class B_G>
828  void finish_vertex(V, B_G &) {
829  }
830 
831 
832  template <class B_G>
833  void discover_vertex(V u, B_G &) {
834  if (u != first && m_predecessors[u] == u) {
835  m_color[u] = boost::black_color;
836  }
837  }
838 
839  private:
840  std::ostringstream &log;
841  V first;
844  std::vector< V > &m_predecessors;
845  std::vector< double > &m_dist;
846  std::vector<boost::default_color_type> &m_color;
847  };
848 
849 
851 };
852 
853 
854 
855 #endif // INCLUDE_DIJKSTRA_PGR_DIJKSTRA_HPP_
class for stopping when a distance/cost has being surpassed
std::deque< Path > drivingDistance(G &graph, const std::vector< int64_t > start_vertex, double distance, bool equicost, std::ostringstream &the_log)
std::deque< Path > drivingDistance_no_equicost(G &graph, const std::vector< int64_t > start_vertex, double distance)
bool execute_drivingDistance(G &graph, int64_t start_vertex, double distance)
to use with driving distance
dijkstra_distance_visitor_no_init(std::ostringstream &p_log, V source, double distance_goal, std::vector< V > &predecessors, std::vector< double > &distances, std::vector< boost::default_color_type > &color_map)
#define pgassertwm(expr, msg)
Adds a message to the assertion.
Definition: pgr_assert.h:104
dijkstra_distance_visitor(double distance_goal, std::deque< V > &nodesInDistance, std::vector< double > &distances)
std::deque< Path > get_paths(const G &graph, V source, std::vector< V > &targets, bool only_cost) const
std::vector< V > predecessors
exception for termination
std::ostringstream log
std::deque< Path > drivingDistance_with_equicost(G &graph, const std::vector< int64_t > start_vertex, double distance)
std::vector< boost::default_color_type > & m_color
static size_t pred(size_t i, size_t n)
Definition: pgr_tsp.cpp:64
void push_back(Path_t data)
class for stopping when a distance/cost has being surpassed
int64_t end_id() const
bool dijkstra_1_to_distance(G &graph, V source, double distance)
Call to Dijkstra 1 to distance.
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:81
int64_t node
Definition: path_t.h:37
Path pgr_dijkstra(G &graph, int64_t source, int64_t target, bool only_cost=false)
bool dijkstra_1_to_distance_no_init(G &graph, V source, double distance)
Call to Dijkstra 1 to distance no init.
Path dijkstra(G &graph, int64_t start_vertex, int64_t end_vertex, bool only_cost=false)
Dijkstra 1 to 1.
std::deque< Path > pgr_drivingDistance(G &graph, std::vector< int64_t > start_vids, double distance, bool equicost, std::ostringstream &log)
Definition: path_t.h:36
int64_t start_id() const
bool execute_drivingDistance_no_init(G &graph, V start_vertex, double distance)
to use with driving distance
dijkstra_many_goal_visitor(std::vector< V > goals)
class for stopping when all targets are found
bool dijkstra_1_to_many(G &graph, V source, const std::vector< V > &targets)
Call to Dijkstra 1 source to many targets.
std::deque< V > nodesInDistance
std::deque< Path > get_drivingDistance_with_equicost_paths(G &graph, const std::vector< int64_t > &start_vertex, std::deque< std::vector< V > > &pred, double distance)
gets results in form of a container of paths
std::deque< Path > dijkstra(G &graph, const std::vector< int64_t > &start_vertex, const std::vector< int64_t > &end_vertex, bool only_cost)
Path drivingDistance(G &graph, int64_t start_vertex, double distance)
1 to distance
std::vector< double > distances
std::deque< Path > dijkstra(G &graph, const std::vector< int64_t > &start_vertex, int64_t end_vertex, bool only_cost)
double agg_cost
Definition: path_t.h:40
std::deque< Path > dijkstra(G &graph, int64_t start_vertex, const std::vector< int64_t > &end_vertex, bool only_cost)
Dijkstra 1 to many.
bool dijkstra_1_to_1(G &graph, V source, V target)
Call to Dijkstra 1 source to 1 target.
class for stopping when 1 target is found