pgRouting
pgRouting extends the PostGIS / PostgreSQL geospatial database to provide geospatial routing functionality.
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
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 #pragma once
28 
29 #if defined(__MINGW32__) || defined(_MSC_VER)
30 #include <winsock2.h>
31 #include <windows.h>
32 #ifdef unlink
33 #undef unlink
34 #endif
35 #endif
36 
37 
38 #include <deque>
39 #include <vector>
40 
41 #include <boost/config.hpp>
42 
43 
44 #include <boost/graph/adjacency_list.hpp>
45 #include <boost/graph/dijkstra_shortest_paths.hpp>
46 
47 #include "./../../common/src/basePath_SSEC.hpp"
48 #include "./../../common/src/pgr_base_graph.hpp"
49 #if 0
50 #include "./../../common/src/signalhandler.h"
51 #endif
52 
53 
54 template < class G > class Pgr_dijkstra;
55 // user's functions
56 // for development
57 
58 template < class G >
60  G &graph,
61  std::deque< Path > &paths,
62  std::vector< int64_t > start_vids,
63  double distance,
64  bool equicost) {
65  Pgr_dijkstra< G > fn_dijkstra;
66  fn_dijkstra.drivingDistance(graph, paths, start_vids, distance, equicost);
67 }
68 
69 
70 template < class G >
71 void
73  G &graph,
74  Path &path,
75  int64_t source,
76  double distance) {
77  Pgr_dijkstra< G > fn_dijkstra;
78  fn_dijkstra.drivingDistance(graph, path, source, distance);
79 }
80 
81 
82 template < class G >
83 void
85  G &graph,
86  Path &path,
87  int64_t source,
88  int64_t target,
89  bool only_cost = false) {
90  Pgr_dijkstra< G > fn_dijkstra;
91  fn_dijkstra.dijkstra(graph, path, source, target, only_cost);
92 }
93 
94 template < class G >
95 void
97  G &graph,
98  std::deque<Path> &paths,
99  int64_t source,
100  const std::vector< int64_t > &targets,
101  bool only_cost = false) {
102  Pgr_dijkstra< G > fn_dijkstra;
103  fn_dijkstra.dijkstra(graph, paths, source, targets, only_cost);
104 }
105 
106 template < class G >
107 void
108 pgr_dijkstra(G &graph,
109  std::deque<Path> &paths,
110  const std::vector< int64_t > &sources,
111  int64_t target,
112  bool only_cost = false) {
113  Pgr_dijkstra< G > fn_dijkstra;
114  fn_dijkstra.dijkstra(graph, paths, sources, target, only_cost);
115 }
116 
117 template < class G >
118 void
120  G &graph, std::deque<Path> &paths,
121  const std::vector< int64_t > &sources,
122  const std::vector< int64_t > &targets,
123  bool only_cost = false) {
124  Pgr_dijkstra< G > fn_dijkstra;
125  fn_dijkstra.dijkstra(graph, paths, sources, targets, only_cost);
126 }
127 
128 
129 
130 //******************************************
131 
132 template < class G >
133 class Pgr_dijkstra {
134  public:
135  typedef typename G::V V;
136 
138 
139  void drivingDistance(
141  G &graph,
142  Path &path,
143  int64_t start_vertex,
144  double distance);
145 
146 
148  void drivingDistance(
149  G &graph, std::deque< Path > &paths,
150  std::vector< int64_t > start_vertex,
151  double distance,
152  bool equiCostFlag);
154 
156 
157  void dijkstra(
159  G &graph,
160  Path &path,
161  int64_t start_vertex,
162  int64_t end_vertex,
163  bool only_cost = false);
164 
166  void dijkstra(
167  G &graph,
168  std::deque< Path > &paths,
169  const std::vector < int64_t > &start_vertex,
170  int64_t end_vertex,
171  bool only_cost = false);
172 
174  void dijkstra(
175  G &graph,
176  std::deque< Path > &paths,
177  const std::vector< int64_t > &start_vertex,
178  const std::vector< int64_t > &end_vertex,
179  bool only_cost = false);
180 
182  void dijkstra(
183  G &graph,
184  std::deque< Path > &paths,
185  int64_t start_vertex,
186  const std::vector< int64_t > &end_vertex,
187  bool only_cost = false);
189 
190  private:
192  bool dijkstra_1_to_1(
193  G &graph,
194  V source,
195  V target);
196 
199  G &graph,
200  V source,
201  double distance);
202 
204  bool dijkstra_1_to_many(
205  G &graph,
206  V source,
207  const std::vector< V > &targets);
208 
209  void get_nodesInDistance(
210  G &graph,
211  Path &path,
212  V source,
213  double distance);
214 
215  void clear() {
216  predecessors.clear();
217  distances.clear();
218  nodesInDistance.clear();
219  }
220 
221 
222  void get_path(
223  const G &graph,
224  V source,
225  V target,
226  Path &path) const;
227  void get_cost(
228  const G &graph,
229  V source,
230  V target,
231  Path &path) const;
232 
233 
234  // used when multiple goals
235  void get_path(
236  const G &graph,
237  std::deque< Path > &paths,
238  V source,
239  std::vector< V > &targets) const;
240 
241  void get_cost(
242  const G &graph,
243  std::deque< Path > &paths,
244  V source,
245  std::vector< V > &targets) const;
246 
247 
249 
250  struct found_goals{};
251  std::vector< V > predecessors;
252  std::vector< double > distances;
253  std::deque< V > nodesInDistance;
255 
257 
258  class dijkstra_one_goal_visitor : public boost::default_dijkstra_visitor {
260  public:
261  explicit dijkstra_one_goal_visitor(V goal) : m_goal(goal) {}
262  template <class B_G>
263  void examine_vertex(V &u, B_G &g) {
264 #if 0
265  REG_SIGINT;
267 #endif
268  if (u == m_goal) throw found_goals();
269  num_edges(g);
270  }
271  private:
273  };
274 
276  class dijkstra_many_goal_visitor : public boost::default_dijkstra_visitor {
277  public:
278  explicit dijkstra_many_goal_visitor(std::vector< V > goals)
279  :m_goals(goals.begin(), goals.end()) {}
280  template <class B_G>
281  void examine_vertex(V u, B_G &g) {
282 #if 0
283  REG_SIGINT;
285 #endif
286  auto s_it = m_goals.find(u);
287  if (s_it == m_goals.end()) return;
288  // we found one more goal
289  m_goals.erase(s_it);
290  if (m_goals.size() == 0) throw found_goals();
291  num_edges(g);
292  }
293  private:
294  std::set< V > m_goals;
295  };
296 
297 
299  class dijkstra_distance_visitor : public boost::default_dijkstra_visitor {
300  public:
302  double distance_goal,
303  std::deque< V > &nodesInDistance,
304  std::vector< double > &distances) :
305  m_distance_goal(distance_goal),
306  m_nodes(nodesInDistance),
307  m_dist(distances) {
308  }
309  template <class B_G>
310  void examine_vertex(V u, B_G &g) {
311 #if 0
312  REG_SIGINT;
314 #endif
315  m_nodes.push_back(u);
316  if (m_dist[u] >= m_distance_goal) throw found_goals();
317  num_edges(g);
318  }
319  private:
321  std::deque< V > &m_nodes;
322  std::vector< double > &m_dist;
323  };
324 
325 
327 };
328 
329 
330 /******************** IMPLEMENTTION ******************/
331 
332 
333 template < class G >
334 void
336  G &graph,
337  Path &path,
338  V source,
339  double distance) {
340  path.clear();
341  double cost;
342  int64_t edge_id;
343  Path r_path(graph[source].id, graph[source].id);
344  for (V i = 0; i < distances.size(); ++i) {
345  if (distances[i] <= distance) {
346  cost = distances[i] - distances[predecessors[i]];
347  edge_id = graph.get_edge_id(predecessors[i], i, cost);
348  r_path.push_back(
349  {graph[i].id,
350  edge_id, cost,
351  distances[i]});
352  }
353  }
354  path = r_path;
355 }
356 
357 
358 template < class G >
359 void
361  const G &graph,
362  std::deque< Path > &paths,
363  V source,
364  std::vector< V > &targets) const {
365  Path path;
366  typename std::vector< V >::iterator s_it;
367  for (s_it = targets.begin(); s_it != targets.end(); ++s_it) {
368  path.clear();
369  get_path(graph, source, *s_it, path);
370  paths.push_back(path);
371  }
372 }
373 
374 template < class G >
375 void
377  const G &graph,
378  V source,
379  V target,
380  Path &r_path) const {
381  // backup of the target
382  V target_back = target;
383  uint64_t from(graph.graph[source].id);
384  uint64_t to(graph.graph[target].id);
385 
386  // no path was found
387  if (target == predecessors[target]) {
388  r_path.clear();
389  return;
390  }
391 
392  // find out how large is the path
393  int64_t result_size = 1;
394  while (target != source) {
395  if (target == predecessors[target]) break;
396  result_size++;
397  target = predecessors[target];
398  }
399 
400  // recover the target
401  target = target_back;
402 
403  // variables that are going to be stored
404  int64_t vertex_id;
405  int64_t edge_id;
406  double cost;
407 
408  // working from the last to the beginning
409 
410  // initialize the sequence
411  auto seq = result_size;
412  // the last stop is the target
413  Path path(from, to);
414  path.push_front(
415  {graph.graph[target].id, -1,
416  0, distances[target]});
417 
418  while (target != source) {
419  // we are done when the predecesor of the target is the target
420  if (target == predecessors[target]) break;
421  // values to be inserted in the path
422  --seq;
423  cost = distances[target] - distances[predecessors[target]];
424  vertex_id = graph.graph[predecessors[target]].id;
425  edge_id = graph.get_edge_id(predecessors[target], target, cost);
426 
427  path.push_front({vertex_id, edge_id,
428  cost, (distances[target] - cost)});
429  target = predecessors[target];
430  }
431  r_path = path;
432  return;
433 }
434 
435 template < class G >
436 void
438  const G &graph,
439  std::deque< Path > &paths,
440  V source,
441  std::vector< V > &targets) const {
442  Path path;
443  for (auto s_it = targets.begin(); s_it != targets.end(); ++s_it) {
444  path.clear();
445  get_cost(graph, source, *s_it, path);
446  paths.push_back(path);
447  }
448 }
449 
450 
451 template < class G >
452 void
454  const G &graph,
455  V source,
456  V target,
457  Path &r_path) const {
458  // backup of the target
459  int64_t from(graph.graph[source].id);
460  int64_t to(graph.graph[target].id);
461 
462  // no path was found
463  if (target == predecessors[target]) {
464  r_path.clear();
465  } else {
466  Path path(from, to);
467  path.push_front(
468  {to, -1, distances[target], distances[target]});
469  r_path = path;
470  }
471 }
472 
473 template < class G >
474 // preparation for many to distance
475 void
476 Pgr_dijkstra< G >::drivingDistance(G &graph, std::deque< Path > &paths,
477  std::vector< int64_t > start_vertex,
478  double distance,
479  bool equicost) {
480  clear();
481 
482  predecessors.resize(graph.num_vertices());
483  distances.resize(graph.num_vertices());
484 
485 
486  // perform the algorithm
487  for (const auto &vertex : start_vertex) {
488  Path path;
489  drivingDistance(graph, path, vertex, distance);
490  paths.push_back(path);
491  }
492  if (equicost) {
493  equi_cost(paths);
494  }
495 }
496 
497 template < class G >
498 void
500  G &graph,
501  Path &path,
502  int64_t start_vertex,
503  double distance) {
504 
505 
506  clear();
507 
508  predecessors.resize(graph.num_vertices());
509  distances.resize(graph.num_vertices());
510 
511  // get source;
512  if (!graph.has_vertex(start_vertex)) {
513  /* The node has to be in the path*/
514  Path p(start_vertex, start_vertex);
515  p.push_back({start_vertex, -1, 0, 0});
516  path = p;
517  return;
518  }
519 
520  auto v_source(graph.get_V(start_vertex));;
521  dijkstra_1_to_distance(graph, v_source, distance);
522  get_nodesInDistance(graph, path, v_source, distance);
523  std::sort(path.begin(), path.end(),
524  [](const Path_t &l, const Path_t &r)
525  {return l.node < r.node;});
526  std::stable_sort(path.begin(), path.end(),
527  [](const Path_t &l, const Path_t &r)
528  {return l.agg_cost < r.agg_cost;});
529  return;
530 }
531 
533 template < class G >
534 void
536  G &graph,
537  Path &path,
538  int64_t start_vertex,
539  int64_t end_vertex,
540  bool only_cost) {
541  clear();
542 
543  // adjust predecessors and distances vectors
544  predecessors.resize(graph.num_vertices());
545  distances.resize(graph.num_vertices());
546 
547 
548  if (!graph.has_vertex(start_vertex)
549  || !graph.has_vertex(end_vertex)) {
550  path.clear();
551  return;
552  }
553 
554  // get the graphs source and target
555  auto v_source(graph.get_V(start_vertex));
556  auto v_target(graph.get_V(end_vertex));
557 
558  // perform the algorithm
559  dijkstra_1_to_1(graph, v_source, v_target);
560 
561  // get the results
562  if (only_cost) {
563  get_cost(graph, v_source, v_target, path);
564  } else {
565  get_path(graph, v_source, v_target, path);
566  }
567  return;
568 }
569 
571 template < class G >
572 void
574  G &graph,
575  std::deque< Path > &paths,
576  int64_t start_vertex,
577  const std::vector< int64_t > &end_vertex,
578  bool only_cost) {
579  // adjust predecessors and distances vectors
580  clear();
581 
582  predecessors.resize(graph.num_vertices());
583  distances.resize(graph.num_vertices());
584 
585  // get the graphs source and target
586  if (!graph.has_vertex(start_vertex)) return;
587  auto v_source(graph.get_V(start_vertex));
588 
589  std::set< V > s_v_targets;
590  for (const auto &vertex : end_vertex) {
591  if (graph.has_vertex(vertex)) {
592  s_v_targets.insert(graph.get_V(vertex));
593  }
594  }
595 
596  std::vector< V > v_targets(s_v_targets.begin(), s_v_targets.end());
597  // perform the algorithm
598  dijkstra_1_to_many(graph, v_source, v_targets);
599 
600  // get the results // route id are the targets
601  if (only_cost) {
602  get_cost(graph, paths, v_source, v_targets);
603  } else {
604  get_path(graph, paths, v_source, v_targets);
605  }
606 
607  std::stable_sort(paths.begin(), paths.end(),
608  [](const Path &e1, const Path &e2)->bool {
609  return e1.end_id() < e2.end_id();
610  });
611 
612  return;
613 }
614 
615 // preparation for many to 1
616 template < class G >
617 void
619  G &graph, std::deque< Path > &paths,
620  const std::vector < int64_t > &start_vertex,
621  int64_t end_vertex,
622  bool only_cost) {
623  // perform the algorithm // a call for each of the sources
624  for (const auto &start : start_vertex) {
625  Path path;
626  // each call cleans the local structures
627  dijkstra(graph, path, start, end_vertex, only_cost);
628  paths.push_back(path);
629  }
630 
631  std::stable_sort(paths.begin(), paths.end(),
632  [](const Path &e1, const Path &e2)->bool {
633  return e1.start_id() < e2.start_id();
634  });
635  return;
636 }
637 
638 
639 // preparation for many to many
640 template < class G >
641 void
643  G &graph, std::deque< Path > &paths,
644  const std::vector< int64_t > &start_vertex,
645  const std::vector< int64_t > &end_vertex,
646  bool only_cost) {
647  // a call to 1 to many is faster for each of the sources
648  for (const auto &start : start_vertex) {
649  dijkstra(graph, paths, start, end_vertex, only_cost);
650  }
651 
652  std::sort(paths.begin(), paths.end(),
653  [](const Path &e1, const Path &e2)->bool {
654  return e1.end_id() < e2.end_id();
655  });
656  std::stable_sort(paths.begin(), paths.end(),
657  [](const Path &e1, const Path &e2)->bool {
658  return e1.start_id() < e2.start_id();
659  });
660  return;
661 }
662 
663 
665 template < class G >
666 bool
668  G &graph,
669  V source,
670  V target) {
671  bool found = false;
672  try {
673  boost::dijkstra_shortest_paths(graph.graph, source,
674  boost::predecessor_map(&predecessors[0])
675  .weight_map(get(&pgrouting::Basic_edge::cost, graph.graph))
676  .distance_map(&distances[0])
677  .visitor(dijkstra_one_goal_visitor(target)));
678  }
679  catch(found_goals &) {
680  found = true; // Target vertex found
681  }
682  return found;
683 }
684 
685 
687 template < class G >
688 bool
689 Pgr_dijkstra< G >::dijkstra_1_to_distance(G &graph, V source, double distance) {
690  bool found = false;
691  try {
692  boost::dijkstra_shortest_paths(graph.graph, source,
693  boost::predecessor_map(&predecessors[0])
694  .weight_map(get(&pgrouting::Basic_edge::cost, graph.graph))
695  .distance_map(&distances[0])
696  .visitor(dijkstra_distance_visitor(
697  distance,
698  nodesInDistance,
699  distances)));
700  }
701  catch(found_goals &) {
702  found = true;
703  }
704  return found;
705 }
706 
708 template <class G>
709 bool
711  G &graph,
712  V source,
713  const std::vector< V > &targets) {
714  bool found = false;
715  try {
716  boost::dijkstra_shortest_paths(graph.graph, source,
717  boost::predecessor_map(&predecessors[0])
718  .weight_map(get(&pgrouting::Basic_edge::cost, graph.graph))
719  .distance_map(&distances[0])
720  .visitor(dijkstra_many_goal_visitor(targets)));
721  }
722  catch(found_goals &) {
723  found = true; // Target vertex found
724  }
725  return found;
726 }
727 
void push_front(Path_t data)
void get_path(const G &graph, V source, V target, Path &path) const
dijkstra_distance_visitor(double distance_goal, std::deque< V > &nodesInDistance, std::vector< double > &distances)
std::vector< V > predecessors
#define REG_SIGINT
void drivingDistance(G &graph, Path &path, int64_t start_vertex, double distance)
1 to distance
exception for termination
void push_back(Path_t data)
class for stopping when a distance/cost has being surpassed
int64_t end_id() const
void pgr_dijkstra(G &graph, Path &path, int64_t source, int64_t target, bool only_cost=false)
void get_nodesInDistance(G &graph, Path &path, V source, double distance)
bool dijkstra_1_to_distance(G &graph, V source, double distance)
Call to Dijkstra 1 source to distance.
int64_t node
Definition: pgr_types.h:83
pthIt end()
int64_t start_id() const
dijkstra_many_goal_visitor(std::vector< V > goals)
pthIt begin()
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.
path_element_t * path
Definition: BDATester.cpp:49
std::deque< V > nodesInDistance
#define THROW_ON_SIGINT
void pgr_drivingDistance(G &graph, std::deque< Path > &paths, std::vector< int64_t > start_vids, double distance, bool equicost)
void dijkstra(G &graph, Path &path, int64_t start_vertex, int64_t end_vertex, bool only_cost=false)
one to one
void clear()
static void get_path(int route_id, int path_id, const Path &path, Routes_t **postgres_data, double &route_cost, size_t &sequence)
void get_cost(const G &graph, V source, V target, Path &path) const
std::vector< double > distances
double agg_cost
Definition: pgr_types.h:86
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