pgRouting  2.2
pgRouting extends the PostGIS / PostgreSQL geospatial database to provide geospatial routing functionality.
 All Classes Functions Variables Pages
pgr_dijkstra.hpp
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 #ifdef __MINGW32__
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/baseGraph.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 >
59 void pgr_drivingDistance(
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
72 pgr_drivingDistance(
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
84 pgr_dijkstra(
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
96 pgr_dijkstra(
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
119 pgr_dijkstra(
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;
266  THROW_ON_SIGINT;
267 #endif
268  if (u == m_goal) throw found_goals();
269  num_edges(g);
270  }
271  private:
272  V m_goal;
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;
284  THROW_ON_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:
301  explicit dijkstra_distance_visitor(
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;
313  THROW_ON_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:
320  double m_distance_goal;
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  // findout 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  V v_source;
513  if (!graph.get_gVertex(start_vertex, v_source)) {
514  /* The node has to be in the path*/
515  Path p(start_vertex, start_vertex);
516  p.push_back({start_vertex, -1, 0, 0});
517  path = p;
518  return;
519  }
520 
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  // get the graphs source and target
548  V v_source;
549  V v_target;
550 
551  if (!graph.get_gVertex(start_vertex, v_source)
552  || !graph.get_gVertex(end_vertex, v_target)) {
553  path.clear();
554  return;
555  }
556 
557  // perform the algorithm
558  dijkstra_1_to_1(graph, v_source, v_target);
559 
560  // get the results
561  if (only_cost) {
562  get_cost(graph, v_source, v_target, path);
563  } else {
564  get_path(graph, v_source, v_target, path);
565  }
566  return;
567 }
568 
570 template < class G >
571 void
573  G &graph,
574  std::deque< Path > &paths,
575  int64_t start_vertex,
576  const std::vector< int64_t > &end_vertex,
577  bool only_cost) {
578  // adjust predecessors and distances vectors
579  clear();
580 
581  predecessors.resize(graph.num_vertices());
582  distances.resize(graph.num_vertices());
583 
584  // get the graphs source and target
585  V v_source;
586  if (!graph.get_gVertex(start_vertex, v_source)) {
587  // paths.clear();
588  return;
589  }
590 
591  std::set< V > s_v_targets;
592  for (const auto &vertex : end_vertex) {
593  V v_target;
594  if (graph.get_gVertex(vertex, v_target)) {
595  s_v_targets.insert(v_target);
596  }
597  }
598 
599  std::vector< V > v_targets(s_v_targets.begin(), s_v_targets.end());
600  // perform the algorithm
601  dijkstra_1_to_many(graph, v_source, v_targets);
602 
603  // get the results // route id are the targets
604  if (only_cost) {
605  get_cost(graph, paths, v_source, v_targets);
606  } else {
607  get_path(graph, paths, v_source, v_targets);
608  }
609 
610  std::stable_sort(paths.begin(), paths.end(),
611  [](const Path &e1, const Path &e2)->bool {
612  return e1.end_id() < e2.end_id();
613  });
614 
615  return;
616 }
617 
618 // preparation for many to 1
619 template < class G >
620 void
622  G &graph, std::deque< Path > &paths,
623  const std::vector < int64_t > &start_vertex,
624  int64_t end_vertex,
625  bool only_cost) {
626  // perform the algorithm // a call for each of the sources
627  for (const auto &start : start_vertex) {
628  Path path;
629  // each call cleans the local structures
630  dijkstra(graph, path, start, end_vertex, only_cost);
631  paths.push_back(path);
632  }
633 
634  std::stable_sort(paths.begin(), paths.end(),
635  [](const Path &e1, const Path &e2)->bool {
636  return e1.start_id() < e2.start_id();
637  });
638  return;
639 }
640 
641 
642 // preparation for many to many
643 template < class G >
644 void
646  G &graph, std::deque< Path > &paths,
647  const std::vector< int64_t > &start_vertex,
648  const std::vector< int64_t > &end_vertex,
649  bool only_cost) {
650  // a call to 1 to many is faster for each of the sources
651  for (const auto &start : start_vertex) {
652  dijkstra(graph, paths, start, end_vertex, only_cost);
653  }
654 
655  std::sort(paths.begin(), paths.end(),
656  [](const Path &e1, const Path &e2)->bool {
657  return e1.end_id() < e2.end_id();
658  });
659  std::stable_sort(paths.begin(), paths.end(),
660  [](const Path &e1, const Path &e2)->bool {
661  return e1.start_id() < e2.start_id();
662  });
663  return;
664 }
665 
666 
668 template < class G >
669 bool
671  G &graph,
672  V source,
673  V target) {
674  bool found = false;
675  try {
676  boost::dijkstra_shortest_paths(graph.graph, source,
677  boost::predecessor_map(&predecessors[0])
678  .weight_map(get(&boost_edge_t::cost, graph.graph))
679  .distance_map(&distances[0])
680  .visitor(dijkstra_one_goal_visitor(target)));
681  }
682  catch(found_goals &fg) {
683  found = true; // Target vertex found
684  }
685  return found;
686 }
687 
688 
690 template < class G >
691 bool
692 Pgr_dijkstra< G >::dijkstra_1_to_distance(G &graph, V source, double distance) {
693  bool found = false;
694  try {
695  boost::dijkstra_shortest_paths(graph.graph, source,
696  boost::predecessor_map(&predecessors[0])
697  .weight_map(get(&boost_edge_t::cost, graph.graph))
698  .distance_map(&distances[0])
699  .visitor(dijkstra_distance_visitor(
700  distance,
701  nodesInDistance,
702  distances)));
703  }
704  catch(found_goals &fg) {
705  found = true;
706  }
707  return found;
708 }
709 
711 template <class G>
712 bool
714  G &graph,
715  V source,
716  const std::vector< V > &targets) {
717  bool found = false;
718  try {
719  boost::dijkstra_shortest_paths(graph.graph, source,
720  boost::predecessor_map(&predecessors[0])
721  .weight_map(get(&boost_edge_t::cost, graph.graph))
722  .distance_map(&distances[0])
723  .visitor(dijkstra_many_goal_visitor(targets)));
724  }
725  catch(found_goals &fg) {
726  found = true; // Target vertex found
727  }
728  return found;
729 }
730 
Definition: alpha.h:33
void drivingDistance(G &graph, Path &path, int64_t start_vertex, double distance)
1 to distance
exception for termination
class for stopping when a distance/cost has being surpassed
bool dijkstra_1_to_distance(G &graph, V source, double distance)
Call to Dijkstra 1 source to distance.
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.
void dijkstra(G &graph, Path &path, int64_t start_vertex, int64_t end_vertex, bool only_cost=false)
one to one
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