PGROUTING  2.4
 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 #ifndef SRC_DIJKSTRA_SRC_PGR_DIJKSTRA_HPP_
28 #define SRC_DIJKSTRA_SRC_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 
40 #include "./../../common/src/basePath_SSEC.hpp"
41 #include "./../../common/src/pgr_base_graph.hpp"
42 #if 0
43 #include "./../../common/src/signalhandler.h"
44 #endif
45 
46 
47 template < class G > class Pgr_dijkstra;
48 // user's functions
49 // for development
50 
51 template < class G >
52 std::deque<Path>
54  G &graph,
55  std::vector< int64_t > start_vids,
56  double distance,
57  bool equicost) {
58  Pgr_dijkstra< G > fn_dijkstra;
59  return fn_dijkstra.drivingDistance(graph, start_vids, distance, equicost);
60 }
61 
62 
63 template < class G >
64 Path
66  G &graph,
67  int64_t source,
68  double distance) {
69  Pgr_dijkstra< G > fn_dijkstra;
70  return fn_dijkstra.drivingDistance(graph, source, distance);
71 }
72 
73 
74 /* 1 to 1*/
75 template < class G >
76 Path
78  G &graph,
79  int64_t source,
80  int64_t target,
81  bool only_cost = false) {
82  Pgr_dijkstra< G > fn_dijkstra;
83  return fn_dijkstra.dijkstra(graph, source, target, only_cost);
84 }
85 
86 /* 1 to many*/
87 template < class G >
88 std::deque<Path>
90  G &graph,
91  int64_t source,
92  std::vector< int64_t > targets,
93  bool only_cost = false) {
94  std::sort(targets.begin(), targets.end());
95  targets.erase(
96  std::unique(targets.begin(), targets.end()),
97  targets.end());
98  Pgr_dijkstra< G > fn_dijkstra;
99  return fn_dijkstra.dijkstra(graph, source, targets, only_cost);
100 }
101 
102 /* many to 1*/
103 template < class G >
104 std::deque<Path>
106  G &graph,
107  std::vector< int64_t > sources,
108  int64_t target,
109  bool only_cost = false) {
110  std::sort(sources.begin(), sources.end());
111  sources.erase(
112  std::unique(sources.begin(), sources.end()),
113  sources.end());
114 
115  Pgr_dijkstra< G > fn_dijkstra;
116  return fn_dijkstra.dijkstra(graph, sources, target, only_cost);
117 }
118 
119 /* Many to Many */
120 template < class G >
121 std::deque<Path>
123  G &graph,
124  std::vector< int64_t > sources,
125  std::vector< int64_t > targets,
126  bool only_cost = false) {
127  std::sort(sources.begin(), sources.end());
128  sources.erase(
129  std::unique(sources.begin(), sources.end()),
130  sources.end());
131 
132  std::sort(targets.begin(), targets.end());
133  targets.erase(
134  std::unique(targets.begin(), targets.end()),
135  targets.end());
136 
137  Pgr_dijkstra< G > fn_dijkstra;
138  return fn_dijkstra.dijkstra(graph, sources, targets, only_cost);
139 }
140 
141 
142 
143 //******************************************
144 
145 template < class G >
146 class Pgr_dijkstra {
147  public:
148  typedef typename G::V V;
149 
151 
152  Path
155  G &graph,
156  int64_t start_vertex,
157  double distance);
158 
159 
161  std::deque<Path> drivingDistance(
162  G &graph,
163  std::vector< int64_t > start_vertex,
164  double distance,
165  bool equiCostFlag);
167 
169 
170  Path dijkstra(
172  G &graph,
173  int64_t start_vertex,
174  int64_t end_vertex,
175  bool only_cost = false);
176 
178  std::deque<Path> dijkstra(
179  G &graph,
180  const std::vector < int64_t > &start_vertex,
181  int64_t end_vertex,
182  bool only_cost = false);
183 
185  std::deque<Path> dijkstra(
186  G &graph,
187  const std::vector< int64_t > &start_vertex,
188  const std::vector< int64_t > &end_vertex,
189  bool only_cost = false);
190 
192  std::deque<Path> dijkstra(
193  G &graph,
194  int64_t start_vertex,
195  const std::vector< int64_t > &end_vertex,
196  bool only_cost = false);
198 
199  private:
201  bool dijkstra_1_to_1(
202  G &graph,
203  V source,
204  V target);
205 
208  G &graph,
209  V source,
210  double distance);
211 
213  bool dijkstra_1_to_many(
214  G &graph,
215  V source,
216  const std::vector< V > &targets);
217 
218  void clear() {
219  predecessors.clear();
220  distances.clear();
221  nodesInDistance.clear();
222  }
223 
224 
225 
226 
227  // used when multiple goals
228  std::deque<Path> get_paths(
229  const G &graph,
230  V source,
231  std::vector< V > &targets,
232  bool only_cost) const {
233  std::deque<Path> paths;
234  for (const auto target : targets) {
235  paths.push_back(Path(
236  graph,
237  source, target,
239  only_cost, true));
240  }
241  return paths;
242  }
243 
244 
245 
247 
248  struct found_goals{};
249  std::vector< V > predecessors;
250  std::vector< double > distances;
251  std::deque< V > nodesInDistance;
253 
255 
256  class dijkstra_one_goal_visitor : public boost::default_dijkstra_visitor {
258  public:
259  explicit dijkstra_one_goal_visitor(V goal) : m_goal(goal) {}
260  template <class B_G>
261  void examine_vertex(V &u, B_G &g) {
262 #if 0
263  REG_SIGINT;
265 #endif
266  if (u == m_goal) throw found_goals();
267  num_edges(g);
268  }
269  private:
271  };
272 
274  class dijkstra_many_goal_visitor : public boost::default_dijkstra_visitor {
275  public:
276  explicit dijkstra_many_goal_visitor(std::vector< V > goals)
277  :m_goals(goals.begin(), goals.end()) {}
278  template <class B_G>
279  void examine_vertex(V u, B_G &g) {
280 #if 0
281  REG_SIGINT;
283 #endif
284  auto s_it = m_goals.find(u);
285  if (s_it == m_goals.end()) return;
286  // we found one more goal
287  m_goals.erase(s_it);
288  if (m_goals.size() == 0) throw found_goals();
289  num_edges(g);
290  }
291  private:
292  std::set< V > m_goals;
293  };
294 
295 
297  class dijkstra_distance_visitor : public boost::default_dijkstra_visitor {
298  public:
300  double distance_goal,
301  std::deque< V > &nodesInDistance,
302  std::vector< double > &distances) :
303  m_distance_goal(distance_goal),
304  m_nodes(nodesInDistance),
305  m_dist(distances) {
306  }
307  template <class B_G>
308  void examine_vertex(V u, B_G &g) {
309 #if 0
310  REG_SIGINT;
312 #endif
313  m_nodes.push_back(u);
314  if (m_dist[u] >= m_distance_goal) throw found_goals();
315  num_edges(g);
316  }
317  private:
319  std::deque< V > &m_nodes;
320  std::vector< double > &m_dist;
321  };
322 
323 
325 };
326 
327 
328 /******************** IMPLEMENTTION ******************/
329 
330 
331 
332 // preparation for many to distance
333 template < class G >
334 std::deque< Path >
336  G &graph,
337  std::vector< int64_t > start_vertex,
338  double distance,
339  bool equicost) {
340  clear();
341 
342  predecessors.resize(graph.num_vertices());
343  distances.resize(graph.num_vertices());
344 
345 
346  // perform the algorithm
347  std::deque< Path > paths;
348  for (const auto &vertex : start_vertex) {
349  paths.push_back(
350  drivingDistance(graph, vertex, distance));
351  }
352  if (equicost) {
353  equi_cost(paths);
354  }
355  return paths;
356 }
357 
358 template < class G >
359 Path
361  G &graph,
362  int64_t start_vertex,
363  double distance) {
364  clear();
365 
366  predecessors.resize(graph.num_vertices());
367  distances.resize(graph.num_vertices());
368 
369  // get source;
370  if (!graph.has_vertex(start_vertex)) {
371  /* The node has to be in the path*/
372  Path p(start_vertex, start_vertex);
373  p.push_back({start_vertex, -1, 0, 0});
374  return p;
375  }
376 
377  auto v_source(graph.get_V(start_vertex));;
378  dijkstra_1_to_distance(graph, v_source, distance);
379 
380  auto path = Path(graph, v_source, distance, predecessors, distances);
381 
382  std::sort(path.begin(), path.end(),
383  [](const Path_t &l, const Path_t &r)
384  {return l.node < r.node;});
385  std::stable_sort(path.begin(), path.end(),
386  [](const Path_t &l, const Path_t &r)
387  {return l.agg_cost < r.agg_cost;});
388  return path;
389 }
390 
392 template < class G >
393 Path
395  G &graph,
396  int64_t start_vertex,
397  int64_t end_vertex,
398  bool only_cost) {
399  clear();
400 
401  // adjust predecessors and distances vectors
402  predecessors.resize(graph.num_vertices());
403  distances.resize(graph.num_vertices());
404 
405 
406  if (!graph.has_vertex(start_vertex)
407  || !graph.has_vertex(end_vertex)) {
408  return Path(start_vertex, end_vertex);
409  }
410 
411  // get the graphs source and target
412  auto v_source(graph.get_V(start_vertex));
413  auto v_target(graph.get_V(end_vertex));
414 
415  // perform the algorithm
416  dijkstra_1_to_1(graph, v_source, v_target);
417 
418  // get the results
419  return Path(
420  graph,
421  v_source, v_target,
422  predecessors, distances,
423  only_cost, true);
424 }
425 
427 template < class G >
428 std::deque<Path>
430  G &graph,
431  int64_t start_vertex,
432  const std::vector< int64_t > &end_vertex,
433  bool only_cost) {
434  // adjust predecessors and distances vectors
435  clear();
436 
437  predecessors.resize(graph.num_vertices());
438  distances.resize(graph.num_vertices());
439 
440  // get the graphs source and target
441  if (!graph.has_vertex(start_vertex))
442  return std::deque<Path>();
443  auto v_source(graph.get_V(start_vertex));
444 
445  std::set< V > s_v_targets;
446  for (const auto &vertex : end_vertex) {
447  if (graph.has_vertex(vertex)) {
448  s_v_targets.insert(graph.get_V(vertex));
449  }
450  }
451 
452  std::vector< V > v_targets(s_v_targets.begin(), s_v_targets.end());
453  // perform the algorithm
454  dijkstra_1_to_many(graph, v_source, v_targets);
455 
456  std::deque< Path > paths;
457  // get the results // route id are the targets
458  paths = get_paths(graph, v_source, v_targets, only_cost);
459 
460  std::stable_sort(paths.begin(), paths.end(),
461  [](const Path &e1, const Path &e2)->bool {
462  return e1.end_id() < e2.end_id();
463  });
464 
465  return paths;
466 }
467 
468 // preparation for many to 1
469 template < class G >
470 std::deque<Path>
472  G &graph,
473  const std::vector < int64_t > &start_vertex,
474  int64_t end_vertex,
475  bool only_cost) {
476  std::deque<Path> paths;
477 
478  for (const auto &start : start_vertex) {
479  paths.push_back(
480  dijkstra(graph, start, end_vertex, only_cost));
481  }
482 
483  std::stable_sort(paths.begin(), paths.end(),
484  [](const Path &e1, const Path &e2)->bool {
485  return e1.start_id() < e2.start_id();
486  });
487  return paths;
488 }
489 
490 
491 // preparation for many to many
492 template < class G >
493 std::deque<Path>
495  G &graph,
496  const std::vector< int64_t > &start_vertex,
497  const std::vector< int64_t > &end_vertex,
498  bool only_cost) {
499  // a call to 1 to many is faster for each of the sources
500  std::deque<Path> paths;
501  for (const auto &start : start_vertex) {
502  auto r_paths = dijkstra(graph, start, end_vertex, only_cost);
503  paths.insert(paths.begin(), r_paths.begin(), r_paths.end());
504  }
505 
506  std::sort(paths.begin(), paths.end(),
507  [](const Path &e1, const Path &e2)->bool {
508  return e1.end_id() < e2.end_id();
509  });
510  std::stable_sort(paths.begin(), paths.end(),
511  [](const Path &e1, const Path &e2)->bool {
512  return e1.start_id() < e2.start_id();
513  });
514  return paths;
515 }
516 
517 
519 template < class G >
520 bool
522  G &graph,
523  V source,
524  V target) {
525  bool found = false;
526  try {
527  boost::dijkstra_shortest_paths(graph.graph, source,
528  boost::predecessor_map(&predecessors[0])
529  .weight_map(get(&G::G_T_E::cost, graph.graph))
530  .distance_map(&distances[0])
531  .visitor(dijkstra_one_goal_visitor(target)));
532  }
533  catch(found_goals &) {
534  found = true; // Target vertex found
535  } catch (...) {
536  }
537  return found;
538 }
539 
540 
542 template < class G >
543 bool
544 Pgr_dijkstra< G >::dijkstra_1_to_distance(G &graph, V source, double distance) {
545  bool found = false;
546  try {
547  boost::dijkstra_shortest_paths(graph.graph, source,
548  boost::predecessor_map(&predecessors[0])
549  .weight_map(get(&G::G_T_E::cost, graph.graph))
550  .distance_map(&distances[0])
551  .visitor(dijkstra_distance_visitor(
552  distance,
553  nodesInDistance,
554  distances)));
555  }
556  catch(found_goals &) {
557  found = true;
558  } catch (...) {
559  }
560  return found;
561 }
562 
564 template <class G>
565 bool
567  G &graph,
568  V source,
569  const std::vector< V > &targets) {
570  bool found = false;
571  try {
572  boost::dijkstra_shortest_paths(graph.graph, source,
573  boost::predecessor_map(&predecessors[0])
574  .weight_map(get(&G::G_T_E::cost, graph.graph))
575  .distance_map(&distances[0])
576  .visitor(dijkstra_many_goal_visitor(targets)));
577  }
578  catch(found_goals &) {
579  found = true; // Target vertex found
580  } catch (...) {
581  }
582  return found;
583 }
584 
585 #endif // SRC_DIJKSTRA_SRC_PGR_DIJKSTRA_HPP_
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
#define REG_SIGINT
std::deque< Path > pgr_drivingDistance(G &graph, std::vector< int64_t > start_vids, double distance, bool equicost)
exception for termination
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 source to distance.
int64_t node
Definition: pgr_types.h:97
Path pgr_dijkstra(G &graph, int64_t source, int64_t target, bool only_cost=false)
Path dijkstra(G &graph, int64_t start_vertex, int64_t end_vertex, bool only_cost=false)
one to one
int64_t start_id() const
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.
path_element_t * path
Definition: BDATester.cpp:49
std::deque< V > nodesInDistance
#define THROW_ON_SIGINT
Path drivingDistance(G &graph, int64_t start_vertex, double distance)
1 to distance
std::vector< double > distances
double agg_cost
Definition: pgr_types.h:100
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