PGROUTING  3.1
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 Copyright (c) 2020 The combinations_sql signature is added by Mahmoud SAKR
10 and Esteban ZIMANYI
11 mail: m_attia_sakr@yahoo.com, estebanzimanyi@gmail.com
12 
13 ------
14 
15 This program is free software; you can redistribute it and/or modify
16 it under the terms of the GNU General Public License as published by
17 the Free Software Foundation; either version 2 of the License, or
18 (at your option) any later version.
19 
20 This program is distributed in the hope that it will be useful,
21 but WITHOUT ANY WARRANTY; without even the implied warranty of
22 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
23 GNU General Public License for more details.
24 
25 You should have received a copy of the GNU General Public License
26 along with this program; if not, write to the Free Software
27 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
28 
29  ********************************************************************PGR-GNU*/
30 
31 #ifndef INCLUDE_DIJKSTRA_PGR_DIJKSTRA_HPP_
32 #define INCLUDE_DIJKSTRA_PGR_DIJKSTRA_HPP_
33 #pragma once
34 
35 #include <boost/config.hpp>
36 #include <boost/graph/adjacency_list.hpp>
38 
39 #if Boost_VERSION_MACRO >= 105500
40 #include <boost/graph/dijkstra_shortest_paths.hpp>
41 #else
42 #include "boost/dijkstra_shortest_paths.hpp"
43 #endif
44 
45 #include <deque>
46 #include <set>
47 #include <vector>
48 #include <algorithm>
49 #include <sstream>
50 #include <functional>
51 #include <limits>
52 #include <map>
53 #include <numeric>
54 
59 
60 #if 0
61 #include "./../../common/src/signalhandler.h"
62 #endif
63 
64 namespace pgrouting {
65 
66 template < class G > class Pgr_dijkstra;
67 // user's functions
68 // for development
69 
70 template < class G >
71 std::deque<Path>
73  G &graph,
74  std::vector< int64_t > start_vids,
75  double distance,
76  bool equicost,
77  std::ostringstream &log) {
78  Pgr_dijkstra< G > fn_dijkstra;
79  return fn_dijkstra.drivingDistance(
80  graph,
81  start_vids,
82  distance,
83  equicost,
84  log);
85 }
86 
87 
88 /* 1 to 1*/
89 template < class G >
90 Path
92  G &graph,
93  int64_t source,
94  int64_t target,
95  bool only_cost = false) {
96  Pgr_dijkstra< G > fn_dijkstra;
97  return fn_dijkstra.dijkstra(graph, source, target, only_cost);
98 }
99 
100 
101 
102 
103 //******************************************
104 
105 template < class G >
106 class Pgr_dijkstra {
107  public:
108  typedef typename G::V V;
109  typedef typename G::E E;
110 
112 
115  G &graph,
116  int64_t start_vertex,
117  double distance) {
119  graph,
120  start_vertex,
121  distance)) {
122  auto path = Path(graph,
123  start_vertex,
124  distance,
125  predecessors,
126  distances);
127 
128  std::sort(path.begin(), path.end(),
129  [](const Path_t &l, const Path_t &r)
130  {return l.node < r.node;});
131  std::stable_sort(path.begin(), path.end(),
132  [](const Path_t &l, const Path_t &r)
133  {return l.agg_cost < r.agg_cost;});
134  return path;
135  }
136 
137  /* The result is empty */
138  Path p(start_vertex, start_vertex);
139  p.push_back({start_vertex, -1, 0, 0});
140  return p;
141  }
142 
143  // preparation for many to distance
144  std::deque< Path > drivingDistance(
145  G &graph,
146  const std::vector< int64_t > &start_vertex,
147  double distance,
148  bool equicost,
149  std::ostringstream &the_log) {
150  if (equicost) {
151  auto paths = drivingDistance_with_equicost(
152  graph,
153  start_vertex,
154  distance);
155  the_log << log.str();
156  return paths;
157  } else {
159  graph,
160  start_vertex,
161  distance);
162  }
163  }
164 
165 
166 
167 
168 
169 
171 
173 
174 
177  G &graph,
178  int64_t start_vertex,
179  int64_t end_vertex,
180  bool only_cost = false) {
181  clear();
182 
183  // adjust predecessors and distances vectors
184  predecessors.resize(graph.num_vertices());
185  distances.resize(
186  graph.num_vertices(),
187  std::numeric_limits<double>::infinity());
188 
189 
190  if (!graph.has_vertex(start_vertex)
191  || !graph.has_vertex(end_vertex)) {
192  return Path(start_vertex, end_vertex);
193  }
194 
195  // get the graphs source and target
196  auto v_source(graph.get_V(start_vertex));
197  auto v_target(graph.get_V(end_vertex));
198 
199  // perform the algorithm
200  dijkstra_1_to_1(graph, v_source, v_target);
201 
202  // get the results
203  return Path(
204  graph,
205  v_source, v_target,
207  only_cost, true);
208  }
209 
210 
211 
212 
213 
214 
216  std::deque<Path> dijkstra(
217  G &graph,
218  int64_t start_vertex,
219  const std::vector< int64_t > &end_vertex,
220  bool only_cost,
221  size_t n_goals = (std::numeric_limits<size_t>::max)()) {
222  // adjust predecessors and distances vectors
223  clear();
224 
225  predecessors.resize(graph.num_vertices());
226  distances.resize(
227  graph.num_vertices(),
228  std::numeric_limits<double>::infinity());
229 
230 
231  // get the graphs source and target
232  if (!graph.has_vertex(start_vertex))
233  return std::deque<Path>();
234  auto v_source(graph.get_V(start_vertex));
235 
236  std::set< V > s_v_targets;
237  for (const auto &vertex : end_vertex) {
238  if (graph.has_vertex(vertex)) {
239  s_v_targets.insert(graph.get_V(vertex));
240  }
241  }
242 
243  std::vector< V > v_targets(s_v_targets.begin(), s_v_targets.end());
244  // perform the algorithm
245  dijkstra_1_to_many(graph, v_source, v_targets, n_goals);
246 
247  std::deque< Path > paths;
248  // get the results // route id are the targets
249  paths = get_paths(graph, v_source, v_targets, only_cost);
250 
251  std::stable_sort(paths.begin(), paths.end(),
252  [](const Path &e1, const Path &e2)->bool {
253  return e1.end_id() < e2.end_id();
254  });
255 
256  return paths;
257  }
258 
259  // preparation for many to 1
260  std::deque<Path> dijkstra(
261  G &graph,
262  const std::vector < int64_t > &start_vertex,
263  int64_t end_vertex,
264  bool only_cost) {
265  std::deque<Path> paths;
266 
267  for (const auto &start : start_vertex) {
268  paths.push_back(
269  dijkstra(graph, start, end_vertex, only_cost));
270  }
271 
272  std::stable_sort(paths.begin(), paths.end(),
273  [](const Path &e1, const Path &e2)->bool {
274  return e1.start_id() < e2.start_id();
275  });
276  return paths;
277  }
278 
279 
280  // preparation for many to many
281  std::deque<Path> dijkstra(
282  G &graph,
283  const std::vector< int64_t > &start_vertex,
284  const std::vector< int64_t > &end_vertex,
285  bool only_cost,
286  size_t n_goals = (std::numeric_limits<size_t>::max)()) {
287  // a call to 1 to many is faster for each of the sources
288  std::deque<Path> paths;
289 
290  for (const auto &start : start_vertex) {
291  auto r_paths = dijkstra(
292  graph,
293  start, end_vertex,
294  only_cost, n_goals);
295  paths.insert(paths.begin(), r_paths.begin(), r_paths.end());
296  }
297 
298  std::sort(paths.begin(), paths.end(),
299  [](const Path &e1, const Path &e2)->bool {
300  return e1.end_id() < e2.end_id();
301  });
302  std::stable_sort(paths.begin(), paths.end(),
303  [](const Path &e1, const Path &e2)->bool {
304  return e1.start_id() < e2.start_id();
305  });
306  return paths;
307  }
308 
309  // preparation for parallel arrays
310  std::deque<Path> dijkstra(
311  G &graph,
312  const std::vector< pgr_combination_t > &combinations,
313  bool only_cost,
314  size_t n_goals = (std::numeric_limits<size_t>::max)()) {
315  // a call to 1 to many is faster for each of the sources
316  std::deque<Path> paths;
317 
318  // group targets per distinct source
319  std::map<int64_t , std::vector<int64_t> > vertex_map;
320  for (const pgr_combination_t &comb : combinations) {
321  std::map< int64_t , std::vector<int64_t> >::iterator it = vertex_map.find(comb.source);
322  if (it != vertex_map.end()) {
323  it->second.push_back(comb.target);
324  } else {
325  std::vector<int64_t > targets{comb.target};
326  vertex_map[comb.source] = targets;
327  }
328  }
329 
330  for (const auto &start_ends : vertex_map) {
331  auto r_paths = dijkstra(
332  graph,
333  start_ends.first, start_ends.second,
334  only_cost, n_goals);
335  paths.insert(paths.begin(), r_paths.begin(), r_paths.end());
336  }
337  vertex_map.clear();
338  std::sort(paths.begin(), paths.end(),
339  [](const Path &e1, const Path &e2)->bool {
340  return e1.end_id() < e2.end_id();
341  });
342  std::stable_sort(paths.begin(), paths.end(),
343  [](const Path &e1, const Path &e2)->bool {
344  return e1.start_id() < e2.start_id();
345  });
346 
347  return paths;
348  }
349 
351 
352  private:
355  G &graph,
356  V source,
357  V target) {
358  /* abort in case of an interruption occurs (e.g. the query is being cancelled) */
359  CHECK_FOR_INTERRUPTS();
360  try {
361  boost::dijkstra_shortest_paths(graph.graph, source,
362  boost::predecessor_map(&predecessors[0])
363  .weight_map(get(&G::G_T_E::cost, graph.graph))
364  .distance_map(&distances[0])
365  .visitor(visitors::dijkstra_one_goal_visitor<V>(target)));
366  } catch(found_goals &) {
367  return true;
368  } catch (boost::exception const& ex) {
369  (void)ex;
370  throw;
371  } catch (std::exception &e) {
372  (void)e;
373  throw;
374  } catch (...) {
375  throw;
376  }
377  return true;
378  }
379 
388  G &graph,
389  V source,
390  double distance) {
391  /* abort in case of an interruption occurs (e.g. the query is being cancelled) */
392  CHECK_FOR_INTERRUPTS();
393  try {
394  boost::dijkstra_shortest_paths(graph.graph, source,
395  boost::predecessor_map(&predecessors[0])
396  .weight_map(get(&G::G_T_E::cost, graph.graph))
397  .distance_map(&distances[0])
398  .visitor(dijkstra_distance_visitor(
399  distance,
401  distances)));
402  } catch(found_goals &) {
403  /*No op*/
404  } catch (boost::exception const&) {
405  throw;
406  } catch (std::exception&) {
407  throw;
408  } catch (...) {
409  throw;
410  }
411  return true;
412  }
413 
420  G &graph,
421  V source,
422  double distance) {
423  pgassert(predecessors.size() == graph.num_vertices());
424  pgassert(distances.size() == graph.num_vertices());
425  distances[source] = 0;
426  std::vector<boost::default_color_type> color_map(graph.num_vertices());
427  /* abort in case of an interruption occurs (e.g. the query is being cancelled) */
428  CHECK_FOR_INTERRUPTS();
429  try {
430  boost::dijkstra_shortest_paths_no_init(graph.graph, source,
431  make_iterator_property_map(
432  predecessors.begin(),
433  graph.vertIndex),
434  make_iterator_property_map(
435  distances.begin(),
436  graph.vertIndex),
437  get(&G::G_T_E::cost, graph.graph),
438  graph.vertIndex,
439  std::less<double>(),
440  boost::closed_plus<double>(),
441  static_cast<double>(0),
443  log,
444  source,
445  distance,
446  predecessors,
447  distances,
448  color_map),
449  boost::make_iterator_property_map(
450  color_map.begin(),
451  graph.vertIndex,
452  color_map[0]));
453  } catch(found_goals &) {
454  return true;
455  } catch (boost::exception const& ex) {
456  (void)ex;
457  throw;
458  } catch (std::exception &e) {
459  (void)e;
460  throw;
461  } catch (...) {
462  throw;
463  }
464 
465 #if 0
466  /*
467  * Expensive assertion
468  */
469  for (V v = 0 ; v < predecessors.size(); ++v) {
470  log << "(" << predecessors[v] << "==" << v << "),";
471  if (v != source) {
472  pgassertwm(predecessors[v] == v, log.str().c_str());
473  }
474  }
475 #endif
476  return true;
477  }
478 
479 
493  G &graph,
494  int64_t start_vertex,
495  double distance) {
496  clear();
497 
498  predecessors.resize(graph.num_vertices());
499  distances.resize(
500  graph.num_vertices(),
501  std::numeric_limits<double>::infinity());
502 
503  // get source;
504  if (!graph.has_vertex(start_vertex)) {
505  return false;
506  }
507 
508  return dijkstra_1_to_distance(
509  graph,
510  graph.get_V(start_vertex),
511  distance);
512  }
513 
514 
528  G &graph,
529  V start_vertex,
530  double distance) {
531  pgassert(predecessors.size() == graph.num_vertices());
532  pgassert(distances.size() == graph.num_vertices());
533 
534  std::iota(predecessors.begin(), predecessors.end(), 0);
535 
536 #if 0
537  /*
538  * Expensive assertion
539  */
540  for (V i = 0 ; i < predecessors.size(); ++i) {
541  pgassert(i == predecessors[i]);
542  }
543 #endif
544 
546  graph,
547  start_vertex,
548  distance);
549  }
550 
551  /* preparation for many to distance with equicost
552  *
553  * Idea:
554  * The distances vector does not change
555  * The predecessors vector does not change
556  * The first @b valid execution is done normally:
557  * - The distances will have:
558  * - inf
559  * - values < distance
560  * - values > distance
561  * Subsequent @b valid executions
562  * - will not change the:
563  * - values < distance
564  * Don't know yet what happens to predecessors
565  */
566  std::deque< Path > drivingDistance_with_equicost(
567  G &graph,
568  const std::vector< int64_t > &start_vertex,
569  double distance) {
570  clear();
571  log << "Number of edges:" << boost::num_edges(graph.graph) << "\n";
572 
573  predecessors.resize(graph.num_vertices());
574  distances.resize(
575  graph.num_vertices(),
576  std::numeric_limits<double>::infinity());
577 
578  /*
579  * Vector to store the different predessesors
580  * each is of size = graph.num_vertices()
581  *
582  * TODO(vicky)
583  * - figure out less storage if possible
584  */
585  std::deque< std::vector< V > > pred(start_vertex.size());
586 
587  // perform the algorithm
588  size_t i = 0;
589  for (const auto &vertex : start_vertex) {
590  nodesInDistance.clear();
591  /*
592  * The vertex does not exist
593  * Nothing to do
594  */
595  if (graph.has_vertex(vertex)) {
597  graph,
598  graph.get_V(vertex),
599  distance)) {
600  pred[i] = predecessors;
601  }
602  }
603  ++i;
604  }
605 
606 
607  /*
608  * predecessors of vertices in the set are themselves
609  */
610  for (const auto &vertex : start_vertex) {
611  for (auto &p : pred) {
612  if (!p.empty() && graph.has_vertex(vertex))
613  p[graph.get_V(vertex)] = graph.get_V(vertex);
614  }
615  }
616 
617 
619  graph,
620  start_vertex,
621  pred,
622  distance);
623  }
624 
633  G &graph,
634  const std::vector< int64_t > &start_vertex,
635  std::deque< std::vector< V > > &pred,
636  double distance) {
637  /*
638  * precondition
639  */
640  pgassert(start_vertex.size() == pred.size());
641 
642 
643  /*
644  * Creating all the result "paths"
645  */
646  std::deque<Path> paths;
647  for (const auto vertex : start_vertex) {
648  paths.push_back(Path(vertex, vertex));
649  paths.back().push_back({vertex, -1, 0, 0});
650  }
651 
652  /*
653  * Ciclying the distances:
654  * To which vertex do they belong to?
655  */
656  for (V d = 0; d < distances.size(); ++d) {
657  /*
658  * Sikiping distances greater than the one asked for
659  */
660  if (!(distances[d] <= distance)) continue;
661 
662  for (auto i = start_vertex.size(); i > 0; --i) {
663  /*
664  * The vertex does not exist on the graph
665  */
666  if (pred[i - 1].empty()) break;
667 
668 
669  /*
670  * The predecessor = current then
671  * its unreachable to this vertex
672  */
673  if (pred[i - 1][d] == d) continue;
674 
675  auto cost = distances[d] - distances[pred[i - 1][d]];
676  auto edge_id = graph.get_edge_id(pred[i - 1][d], d, cost);
677  pgassert(edge_id != -1);
678  paths[i - 1].push_back(
679  {graph[d].id,
680  edge_id, cost,
681  distances[d]});
682  break;
683  }
684  }
685 
686  for (auto &path : paths) {
687  path.sort_by_node_agg_cost();
688  }
689  return paths;
690  }
691 
692 
693  // preparation for many to distance No equicost
694  std::deque< Path > drivingDistance_no_equicost(
695  G &graph,
696  const std::vector< int64_t > &start_vertex,
697  double distance) {
698  // perform the algorithm
699  std::deque<Path> paths;
700  for (const auto &vertex : start_vertex) {
701  if (execute_drivingDistance(graph, vertex, distance)) {
702  auto path = Path(
703  graph,
704  vertex,
705  distance,
706  predecessors,
707  distances);
708  path.sort_by_node_agg_cost();
709  paths.push_back(path);
710  } else {
711  Path p(vertex, vertex);
712  p.push_back({vertex, -1, 0, 0});
713  paths.push_back(p);
714  }
715  }
716  return paths;
717  }
718 
719 
722  G &graph,
723  V source,
724  const std::vector< V > &targets,
725  size_t n_goals = (std::numeric_limits<size_t>::max)()) {
726  /* abort in case of an interruption occurs (e.g. the query is being cancelled) */
727  CHECK_FOR_INTERRUPTS();
728  try {
729  boost::dijkstra_shortest_paths(graph.graph, source,
730  boost::predecessor_map(&predecessors[0])
731  .weight_map(get(&G::G_T_E::cost, graph.graph))
732  .distance_map(&distances[0])
733  .distance_inf(std::numeric_limits<double>::infinity())
734  .visitor(dijkstra_many_goal_visitor(targets, n_goals)));
735  } catch(found_goals &) {
736  return true;
737  } catch (boost::exception const& ex) {
738  (void)ex;
739  throw;
740  } catch (std::exception &e) {
741  (void)e;
742  throw;
743  } catch (...) {
744  throw;
745  }
746  return true;
747  }
748 
749 
750  void clear() {
751  predecessors.clear();
752  distances.clear();
753  nodesInDistance.clear();
754  }
755 
756 
757 
758 
759  // used when multiple goals
760  std::deque<Path> get_paths(
761  const G &graph,
762  V source,
763  std::vector< V > &targets,
764  bool only_cost) const {
765  std::deque<Path> paths;
766  for (const auto target : targets) {
767  paths.push_back(Path(
768  graph,
769  source, target,
771  only_cost, true));
772  }
773  return paths;
774  }
775 
776 
777 
779 
780 #if 0
781  struct found_goals{};
782 #endif
783  std::vector< V > predecessors;
784  std::vector< double > distances;
785  std::deque< V > nodesInDistance;
786  std::ostringstream log;
788 
789 
791 
792  class dijkstra_many_goal_visitor : public boost::default_dijkstra_visitor {
794  public:
796  const std::vector< V > &goals,
797  size_t n_goals) :
798  m_goals(goals.begin(), goals.end()),
799  m_n_goals(n_goals) {}
800  template <class B_G>
801  void examine_vertex(V u, B_G &) {
802  auto s_it = m_goals.find(u);
803  if (s_it == m_goals.end()) return;
804 
805  // found one more goal
806  m_goals.erase(s_it);
807 
808  // all goals found
809  if (m_goals.size() == 0) throw found_goals();
810 
811  // number of requested goals found
812  --m_n_goals;
813  if (m_n_goals == 0) throw found_goals();
814  }
815 
816  private:
817  std::set< V > m_goals;
818  size_t m_n_goals;
819  };
820 
821 
823  class dijkstra_distance_visitor : public boost::default_dijkstra_visitor {
824  public:
826  double distance_goal,
827  std::deque< V > &nodesInDistance,
828  std::vector< double > &distances) :
829  m_distance_goal(distance_goal),
830  m_nodes(nodesInDistance),
831  m_dist(distances) {
832  pgassert(m_nodes.empty());
833  pgassert(m_distance_goal > 0);
834  }
835  template <class B_G>
836  void examine_vertex(V u, B_G &) {
837  if (m_dist[u] > m_distance_goal) {
838  throw found_goals();
839  }
840  m_nodes.push_back(u);
841  }
842 
843  private:
845  std::deque< V > &m_nodes;
846  std::vector< double > &m_dist;
847  };
848 
851  : public boost::default_dijkstra_visitor {
852  public:
854  std::ostringstream &p_log,
855  V source,
856  double distance_goal,
857  std::vector< V > &predecessors,
858  std::vector< double > &distances,
859  std::vector<boost::default_color_type> &color_map) :
860  log(p_log),
861  first(source),
862  m_distance_goal(distance_goal),
863  m_num_examined(0),
864  m_predecessors(predecessors),
865  m_dist(distances),
866  m_color(color_map) {
867  pgassert(m_num_examined == 0);
868  pgassert(m_distance_goal > 0);
869  }
870 
871  template <class B_G>
872  void examine_vertex(V u, B_G &) {
873  if ( 0 == m_num_examined++) first = u;
874  if (m_dist[u] > m_distance_goal) {
875  throw found_goals();
876  }
877  if (u != first && m_predecessors[u] == u) {
878  m_color[u] = boost::black_color;
879  }
880  }
881 
882  template <class B_G>
883  void examine_edge(E e, B_G &g) {
884  if (source(e, g) != first
885  && m_predecessors[source(e, g)] == source(e, g)) {
886  m_color[target(e, g)] = boost::black_color;
887  }
888  }
889 
890 
891  template <class B_G>
892  void edge_relaxed(E, B_G &) {
893  }
894 
895 
896 
897  template <class B_G>
898  void edge_not_relaxed(E e, B_G &g) {
899  if (source(e, g) != first
900  && m_predecessors[source(e, g)] == source(e, g)) {
901  m_color[target(e, g)] = boost::black_color;
902  }
903  }
904 
905 
906  template <class B_G>
907  void finish_vertex(V, B_G &) {
908  }
909 
910 
911  template <class B_G>
912  void discover_vertex(V u, B_G &) {
913  if (u != first && m_predecessors[u] == u) {
914  m_color[u] = boost::black_color;
915  }
916  }
917 
918  private:
919  std::ostringstream &log;
920  V first;
923  std::vector< V > &m_predecessors;
924  std::vector< double > &m_dist;
925  std::vector<boost::default_color_type> &m_color;
926  };
927 };
928 
929 } // namespace pgrouting
930 
931 
932 #endif // INCLUDE_DIJKSTRA_PGR_DIJKSTRA_HPP_
std::deque< Path > drivingDistance_no_equicost(G &graph, const std::vector< int64_t > &start_vertex, double distance)
std::deque< Path > drivingDistance(G &graph, const std::vector< int64_t > &start_vertex, double distance, bool equicost, std::ostringstream &the_log)
bool execute_drivingDistance_no_init(G &graph, V start_vertex, double distance)
to use with driving distance
bool dijkstra_1_to_distance(G &graph, V source, double distance)
Call to Dijkstra 1 to distance.
#define pgassertwm(expr, msg)
Adds a message to the assertion.
Definition: pgr_assert.h:117
Path drivingDistance(G &graph, int64_t start_vertex, double distance)
1 to 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)
bool dijkstra_1_to_many(G &graph, V source, const std::vector< V > &targets, size_t n_goals=(std::numeric_limits< size_t >::max)())
Dijkstra 1 source to many targets.
std::vector< V > predecessors
dijkstra_distance_visitor(double distance_goal, std::deque< V > &nodesInDistance, std::vector< double > &distances)
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
boost::graph_traits< BG >::vertex_descriptor V
boost::graph_traits< BG >::edge_descriptor E
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)
std::deque< Path > dijkstra(G &graph, int64_t start_vertex, const std::vector< int64_t > &end_vertex, bool only_cost, size_t n_goals=(std::numeric_limits< size_t >::max)())
Dijkstra 1 to many.
Path pgr_dijkstra(G &graph, int64_t source, int64_t target, bool only_cost=false)
graph::Pgr_base_graph< BG, XY_vertex, Basic_edge > G
class for stopping when a distance/cost has being surpassed
std::deque< Path > dijkstra(G &graph, const std::vector< int64_t > &start_vertex, int64_t end_vertex, bool only_cost)
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:94
int64_t node
Definition: path_t.h:37
std::deque< Path > get_paths(const G &graph, V source, std::vector< V > &targets, bool only_cost) const
int64_t end_id() const
class for stopping when a distance/cost has being surpassed
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)
std::deque< Path > dijkstra(G &graph, const std::vector< pgr_combination_t > &combinations, bool only_cost, size_t n_goals=(std::numeric_limits< size_t >::max)())
Definition: path_t.h:36
std::ostringstream log
Book keeping class for swapping orders between vehicles.
bool dijkstra_1_to_1(G &graph, V source, V target)
Call to Dijkstra 1 source to 1 target.
std::deque< Path > drivingDistance_with_equicost(G &graph, const std::vector< int64_t > &start_vertex, double distance)
std::deque< V > nodesInDistance
std::vector< double > distances
class for stopping when all targets are found
std::deque< Path > dijkstra(G &graph, const std::vector< int64_t > &start_vertex, const std::vector< int64_t > &end_vertex, bool only_cost, size_t n_goals=(std::numeric_limits< size_t >::max)())
int64_t start_id() const
dijkstra_many_goal_visitor(const std::vector< V > &goals, size_t n_goals)
bool execute_drivingDistance(G &graph, int64_t start_vertex, double distance)
to use with driving distance
double agg_cost
Definition: path_t.h:40
bool dijkstra_1_to_distance_no_init(G &graph, V source, double distance)
Call to Dijkstra 1 to distance no init.
exception for visitor termination
Definition: found_goals.hpp:33