PGROUTING  3.1
pgrouting::Pgr_dijkstra< G > Class Template Reference

#include "pgr_dijkstra.hpp"

Collaboration diagram for pgrouting::Pgr_dijkstra< G >:

Classes

class  dijkstra_distance_visitor
 class for stopping when a distance/cost has being surpassed More...
 
class  dijkstra_distance_visitor_no_init
 class for stopping when a distance/cost has being surpassed More...
 
class  dijkstra_many_goal_visitor
 class for stopping when all targets are found More...
 

Public Types

typedef G::E E
 
typedef G::V V
 

Public Member Functions

drivingDistance
Path drivingDistance (G &graph, int64_t start_vertex, double distance)
 1 to distance More...
 
std::deque< PathdrivingDistance (G &graph, const std::vector< int64_t > &start_vertex, double distance, bool equicost, std::ostringstream &the_log)
 
Dijkstra
Path dijkstra (G &graph, int64_t start_vertex, int64_t end_vertex, bool only_cost=false)
 Dijkstra 1 to 1. More...
 
std::deque< Pathdijkstra (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. More...
 
std::deque< Pathdijkstra (G &graph, const std::vector< int64_t > &start_vertex, int64_t end_vertex, bool only_cost)
 
std::deque< Pathdijkstra (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)())
 
std::deque< Pathdijkstra (G &graph, const std::vector< pgr_combination_t > &combinations, bool only_cost, size_t n_goals=(std::numeric_limits< size_t >::max)())
 

Private Member Functions

void clear ()
 
bool dijkstra_1_to_1 (G &graph, V source, V target)
 Call to Dijkstra 1 source to 1 target. More...
 
bool dijkstra_1_to_distance (G &graph, V source, double distance)
 Call to Dijkstra 1 to distance. More...
 
bool dijkstra_1_to_distance_no_init (G &graph, V source, double distance)
 Call to Dijkstra 1 to distance no init. More...
 
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. More...
 
std::deque< PathdrivingDistance_no_equicost (G &graph, const std::vector< int64_t > &start_vertex, double distance)
 
std::deque< PathdrivingDistance_with_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 More...
 
bool execute_drivingDistance_no_init (G &graph, V start_vertex, double distance)
 to use with driving distance More...
 
std::deque< Pathget_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 More...
 
std::deque< Pathget_paths (const G &graph, V source, std::vector< V > &targets, bool only_cost) const
 

Private Attributes

members
std::vector< Vpredecessors
 
std::vector< double > distances
 
std::deque< VnodesInDistance
 
std::ostringstream log
 

Detailed Description

template<class G>
class pgrouting::Pgr_dijkstra< G >

Definition at line 66 of file pgr_dijkstra.hpp.

Member Typedef Documentation

◆ E

template<class G>
typedef G::E pgrouting::Pgr_dijkstra< G >::E

Definition at line 109 of file pgr_dijkstra.hpp.

◆ V

template<class G>
typedef G::V pgrouting::Pgr_dijkstra< G >::V

Definition at line 108 of file pgr_dijkstra.hpp.

Member Function Documentation

◆ clear()

◆ dijkstra() [1/5]

template<class G>
Path pgrouting::Pgr_dijkstra< G >::dijkstra ( G &  graph,
int64_t  start_vertex,
int64_t  end_vertex,
bool  only_cost = false 
)
inline

Dijkstra 1 to 1.

Definition at line 176 of file pgr_dijkstra.hpp.

References pgrouting::Pgr_dijkstra< G >::clear(), pgrouting::Pgr_dijkstra< G >::dijkstra_1_to_1(), pgrouting::Pgr_dijkstra< G >::distances, and pgrouting::Pgr_dijkstra< G >::predecessors.

Referenced by pgrouting::Pgr_dijkstra< G >::dijkstra(), pgrouting::yen::Pgr_ksp< G >::doNextCycle(), pgrouting::yen::Pgr_ksp< G >::getFirstSolution(), pgr_dijkstra(), pgrouting::pgr_dijkstra(), and detail::pgr_dijkstra().

180  {
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  }
std::vector< V > predecessors
bool dijkstra_1_to_1(G &graph, V source, V target)
Call to Dijkstra 1 source to 1 target.
std::vector< double > distances

◆ dijkstra() [2/5]

template<class G>
std::deque<Path> pgrouting::Pgr_dijkstra< G >::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)() 
)
inline

Dijkstra 1 to many.

Definition at line 216 of file pgr_dijkstra.hpp.

References pgrouting::Pgr_dijkstra< G >::clear(), pgrouting::Pgr_dijkstra< G >::dijkstra_1_to_many(), pgrouting::Pgr_dijkstra< G >::distances, Path::end_id(), pgrouting::Pgr_dijkstra< G >::get_paths(), and pgrouting::Pgr_dijkstra< G >::predecessors.

221  {
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  }
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
std::deque< Path > get_paths(const G &graph, V source, std::vector< V > &targets, bool only_cost) const
int64_t end_id() const
std::vector< double > distances

◆ dijkstra() [3/5]

template<class G>
std::deque<Path> pgrouting::Pgr_dijkstra< G >::dijkstra ( G &  graph,
const std::vector< int64_t > &  start_vertex,
int64_t  end_vertex,
bool  only_cost 
)
inline

Definition at line 260 of file pgr_dijkstra.hpp.

References pgrouting::Pgr_dijkstra< G >::dijkstra(), and Path::start_id().

264  {
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  }
Path dijkstra(G &graph, int64_t start_vertex, int64_t end_vertex, bool only_cost=false)
Dijkstra 1 to 1.
int64_t start_id() const

◆ dijkstra() [4/5]

template<class G>
std::deque<Path> pgrouting::Pgr_dijkstra< G >::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)() 
)
inline

Definition at line 281 of file pgr_dijkstra.hpp.

References pgrouting::Pgr_dijkstra< G >::dijkstra(), Path::end_id(), and Path::start_id().

286  {
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  }
int64_t end_id() const
Path dijkstra(G &graph, int64_t start_vertex, int64_t end_vertex, bool only_cost=false)
Dijkstra 1 to 1.
int64_t start_id() const

◆ dijkstra() [5/5]

template<class G>
std::deque<Path> pgrouting::Pgr_dijkstra< G >::dijkstra ( G &  graph,
const std::vector< pgr_combination_t > &  combinations,
bool  only_cost,
size_t  n_goals = (std::numeric_limits<size_t>::max)() 
)
inline

Definition at line 310 of file pgr_dijkstra.hpp.

References pgrouting::Pgr_dijkstra< G >::dijkstra(), Path::end_id(), and Path::start_id().

314  {
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  }
int64_t end_id() const
Path dijkstra(G &graph, int64_t start_vertex, int64_t end_vertex, bool only_cost=false)
Dijkstra 1 to 1.
int64_t start_id() const

◆ dijkstra_1_to_1()

template<class G>
bool pgrouting::Pgr_dijkstra< G >::dijkstra_1_to_1 ( G &  graph,
V  source,
V  target 
)
inlineprivate

Call to Dijkstra 1 source to 1 target.

Definition at line 354 of file pgr_dijkstra.hpp.

References pgrouting::Pgr_dijkstra< G >::distances, and pgrouting::Pgr_dijkstra< G >::predecessors.

Referenced by pgrouting::Pgr_dijkstra< G >::dijkstra().

357  {
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  }
std::vector< V > predecessors
std::vector< double > distances

◆ dijkstra_1_to_distance()

template<class G>
bool pgrouting::Pgr_dijkstra< G >::dijkstra_1_to_distance ( G &  graph,
V  source,
double  distance 
)
inlineprivate

Call to Dijkstra 1 to distance.

Used on: 1 to distance many to distance On the first call of many to distance with equi_cost

Definition at line 387 of file pgr_dijkstra.hpp.

References pgrouting::Pgr_dijkstra< G >::distances, pgrouting::Pgr_dijkstra< G >::nodesInDistance, and pgrouting::Pgr_dijkstra< G >::predecessors.

Referenced by pgrouting::Pgr_dijkstra< G >::execute_drivingDistance().

390  {
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  }
std::vector< V > predecessors
std::deque< V > nodesInDistance
std::vector< double > distances

◆ dijkstra_1_to_distance_no_init()

template<class G>
bool pgrouting::Pgr_dijkstra< G >::dijkstra_1_to_distance_no_init ( G &  graph,
V  source,
double  distance 
)
inlineprivate

Call to Dijkstra 1 to distance no init.

Used on: On the subsequent calls of many to distance with equi_cost

Definition at line 419 of file pgr_dijkstra.hpp.

References pgrouting::Pgr_dijkstra< G >::distances, pgrouting::Pgr_dijkstra< G >::log, pgassert, pgassertwm, and pgrouting::Pgr_dijkstra< G >::predecessors.

Referenced by pgrouting::Pgr_dijkstra< G >::execute_drivingDistance_no_init().

422  {
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),
442  dijkstra_distance_visitor_no_init(
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  }
#define pgassertwm(expr, msg)
Adds a message to the assertion.
Definition: pgr_assert.h:117
std::vector< V > predecessors
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:94
std::ostringstream log
std::vector< double > distances

◆ dijkstra_1_to_many()

template<class G>
bool pgrouting::Pgr_dijkstra< G >::dijkstra_1_to_many ( G &  graph,
V  source,
const std::vector< V > &  targets,
size_t  n_goals = (std::numeric_limits<size_t>::max)() 
)
inlineprivate

Dijkstra 1 source to many targets.

Definition at line 721 of file pgr_dijkstra.hpp.

References pgrouting::Pgr_dijkstra< G >::distances, and pgrouting::Pgr_dijkstra< G >::predecessors.

Referenced by pgrouting::Pgr_dijkstra< G >::dijkstra().

725  {
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  }
std::vector< V > predecessors
std::vector< double > distances

◆ drivingDistance() [1/2]

template<class G>
Path pgrouting::Pgr_dijkstra< G >::drivingDistance ( G &  graph,
int64_t  start_vertex,
double  distance 
)
inline

1 to distance

Definition at line 114 of file pgr_dijkstra.hpp.

Referenced by pgrouting::pgr_drivingDistance().

117  {
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  }
std::vector< V > predecessors
int64_t node
Definition: path_t.h:37
Definition: path_t.h:36
std::vector< double > distances
bool execute_drivingDistance(G &graph, int64_t start_vertex, double distance)
to use with driving distance
double agg_cost
Definition: path_t.h:40

◆ drivingDistance() [2/2]

template<class G>
std::deque< Path > pgrouting::Pgr_dijkstra< G >::drivingDistance ( G &  graph,
const std::vector< int64_t > &  start_vertex,
double  distance,
bool  equicost,
std::ostringstream &  the_log 
)
inline

Definition at line 144 of file pgr_dijkstra.hpp.

References pgrouting::Pgr_dijkstra< G >::drivingDistance_no_equicost(), pgrouting::Pgr_dijkstra< G >::drivingDistance_with_equicost(), and pgrouting::Pgr_dijkstra< G >::log.

149  {
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  }
std::deque< Path > drivingDistance_no_equicost(G &graph, const std::vector< int64_t > &start_vertex, double distance)
std::ostringstream log
std::deque< Path > drivingDistance_with_equicost(G &graph, const std::vector< int64_t > &start_vertex, double distance)

◆ drivingDistance_no_equicost()

template<class G>
std::deque< Path > pgrouting::Pgr_dijkstra< G >::drivingDistance_no_equicost ( G &  graph,
const std::vector< int64_t > &  start_vertex,
double  distance 
)
inlineprivate

Definition at line 694 of file pgr_dijkstra.hpp.

References pgrouting::Pgr_dijkstra< G >::distances, pgrouting::Pgr_dijkstra< G >::execute_drivingDistance(), pgrouting::Pgr_dijkstra< G >::predecessors, and Path::push_back().

Referenced by pgrouting::Pgr_dijkstra< G >::drivingDistance().

697  {
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  }
std::vector< V > predecessors
std::vector< double > distances
bool execute_drivingDistance(G &graph, int64_t start_vertex, double distance)
to use with driving distance

◆ drivingDistance_with_equicost()

template<class G>
std::deque< Path > pgrouting::Pgr_dijkstra< G >::drivingDistance_with_equicost ( G &  graph,
const std::vector< int64_t > &  start_vertex,
double  distance 
)
inlineprivate

Definition at line 566 of file pgr_dijkstra.hpp.

References pgrouting::Pgr_dijkstra< G >::clear(), pgrouting::Pgr_dijkstra< G >::distances, pgrouting::Pgr_dijkstra< G >::execute_drivingDistance_no_init(), pgrouting::Pgr_dijkstra< G >::get_drivingDistance_with_equicost_paths(), pgrouting::Pgr_dijkstra< G >::log, pgrouting::Pgr_dijkstra< G >::nodesInDistance, pred(), and pgrouting::Pgr_dijkstra< G >::predecessors.

Referenced by pgrouting::Pgr_dijkstra< G >::drivingDistance().

569  {
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  }
bool execute_drivingDistance_no_init(G &graph, V start_vertex, double distance)
to use with driving distance
std::vector< V > predecessors
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
static size_t pred(size_t i, size_t n)
Definition: pgr_tsp.cpp:64
std::ostringstream log
std::deque< V > nodesInDistance
std::vector< double > distances

◆ execute_drivingDistance()

template<class G>
bool pgrouting::Pgr_dijkstra< G >::execute_drivingDistance ( G &  graph,
int64_t  start_vertex,
double  distance 
)
inlineprivate

to use with driving distance

Prepares the execution for a driving distance:

Parameters
graph
start_vertex
distanceResults are kept on predecessor & distances
Returns
bool True when results are found

Definition at line 492 of file pgr_dijkstra.hpp.

References pgrouting::Pgr_dijkstra< G >::clear(), pgrouting::Pgr_dijkstra< G >::dijkstra_1_to_distance(), pgrouting::Pgr_dijkstra< G >::distances, and pgrouting::Pgr_dijkstra< G >::predecessors.

Referenced by pgrouting::Pgr_dijkstra< G >::drivingDistance_no_equicost().

495  {
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  }
bool dijkstra_1_to_distance(G &graph, V source, double distance)
Call to Dijkstra 1 to distance.
std::vector< V > predecessors
std::vector< double > distances

◆ execute_drivingDistance_no_init()

template<class G>
bool pgrouting::Pgr_dijkstra< G >::execute_drivingDistance_no_init ( G &  graph,
V  start_vertex,
double  distance 
)
inlineprivate

to use with driving distance

Prepares the execution for a driving distance:

Parameters
graph
start_vertex
distanceResults are kept on predecessor & distances
Returns
bool True when results are found

Definition at line 527 of file pgr_dijkstra.hpp.

References pgrouting::Pgr_dijkstra< G >::dijkstra_1_to_distance_no_init(), pgrouting::Pgr_dijkstra< G >::distances, pgassert, and pgrouting::Pgr_dijkstra< G >::predecessors.

Referenced by pgrouting::Pgr_dijkstra< G >::drivingDistance_with_equicost().

530  {
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  }
std::vector< V > predecessors
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:94
std::vector< double > distances
bool dijkstra_1_to_distance_no_init(G &graph, V source, double distance)
Call to Dijkstra 1 to distance no init.

◆ get_drivingDistance_with_equicost_paths()

template<class G>
std::deque< Path > pgrouting::Pgr_dijkstra< G >::get_drivingDistance_with_equicost_paths ( G &  graph,
const std::vector< int64_t > &  start_vertex,
std::deque< std::vector< V > > &  pred,
double  distance 
)
inlineprivate

gets results in form of a container of paths

Parameters
[in]graphThe graph that is being worked
[in]start_vertexAn array of vertices id
[in]predan array of predecessors
[in]distancethe max distance

Definition at line 632 of file pgr_dijkstra.hpp.

References pgrouting::Pgr_dijkstra< G >::distances, pgassert, and pred().

Referenced by pgrouting::Pgr_dijkstra< G >::drivingDistance_with_equicost().

636  {
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  }
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:94
std::vector< double > distances

◆ get_paths()

template<class G>
std::deque<Path> pgrouting::Pgr_dijkstra< G >::get_paths ( const G &  graph,
V  source,
std::vector< V > &  targets,
bool  only_cost 
) const
inlineprivate

Definition at line 760 of file pgr_dijkstra.hpp.

References pgrouting::Pgr_dijkstra< G >::distances, and pgrouting::Pgr_dijkstra< G >::predecessors.

Referenced by pgrouting::Pgr_dijkstra< G >::dijkstra().

764  {
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  }
std::vector< V > predecessors
std::vector< double > distances

Member Data Documentation

◆ distances

◆ log

◆ nodesInDistance

◆ predecessors


The documentation for this class was generated from the following file: