PGROUTING  2.6
Pgr_dijkstra< G > Class Template Reference

#include "pgr_dijkstra.hpp"

Collaboration diagram for 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...
 
class  dijkstra_one_goal_visitor
 class for stopping when 1 target is found More...
 
struct  found_goals
 exception for termination 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)
 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)
 

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)
 Call to 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 Pgr_dijkstra< G >

Definition at line 50 of file pgr_dijkstra.hpp.

Member Typedef Documentation

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

Definition at line 93 of file pgr_dijkstra.hpp.

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

Definition at line 92 of file pgr_dijkstra.hpp.

Member Function Documentation

template<class G>
void Pgr_dijkstra< G >::clear ( )
inlineprivate

Definition at line 674 of file pgr_dijkstra.hpp.

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

Referenced by Pgr_dijkstra< G >::dijkstra(), Pgr_dijkstra< G >::drivingDistance(), Pgr_dijkstra< G >::drivingDistance_with_equicost(), and Pgr_dijkstra< G >::execute_drivingDistance().

674  {
675  predecessors.clear();
676  distances.clear();
677  nodesInDistance.clear();
678  }
std::vector< V > predecessors
std::deque< V > nodesInDistance
std::vector< double > distances

Here is the caller graph for this function:

template<class G>
Path 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 159 of file pgr_dijkstra.hpp.

Referenced by Pgr_dijkstra< G >::dijkstra(), Pgr_ksp< G >::doNextCycle(), Pgr_dijkstra< G >::drivingDistance(), Pgr_dijkstraTRSP< G >::getDijkstraSolution(), Pgr_ksp< G >::getFirstSolution(), and pgr_dijkstra().

163  {
164  clear();
165 
166  // adjust predecessors and distances vectors
167  predecessors.resize(graph.num_vertices());
168  distances.resize(graph.num_vertices());
169 
170 
171  if (!graph.has_vertex(start_vertex)
172  || !graph.has_vertex(end_vertex)) {
173  return Path(start_vertex, end_vertex);
174  }
175 
176  // get the graphs source and target
177  auto v_source(graph.get_V(start_vertex));
178  auto v_target(graph.get_V(end_vertex));
179 
180  // perform the algorithm
181  dijkstra_1_to_1(graph, v_source, v_target);
182 
183  // get the results
184  return Path(
185  graph,
186  v_source, v_target,
188  only_cost, true);
189  }
std::vector< V > predecessors
std::vector< double > distances
bool dijkstra_1_to_1(G &graph, V source, V target)
Call to Dijkstra 1 source to 1 target.

Here is the caller graph for this function:

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

Dijkstra 1 to many.

Definition at line 197 of file pgr_dijkstra.hpp.

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

201  {
202  // adjust predecessors and distances vectors
203  clear();
204 
205  predecessors.resize(graph.num_vertices());
206  distances.resize(graph.num_vertices());
207 
208  // get the graphs source and target
209  if (!graph.has_vertex(start_vertex))
210  return std::deque<Path>();
211  auto v_source(graph.get_V(start_vertex));
212 
213  std::set< V > s_v_targets;
214  for (const auto &vertex : end_vertex) {
215  if (graph.has_vertex(vertex)) {
216  s_v_targets.insert(graph.get_V(vertex));
217  }
218  }
219 
220  std::vector< V > v_targets(s_v_targets.begin(), s_v_targets.end());
221  // perform the algorithm
222  dijkstra_1_to_many(graph, v_source, v_targets);
223 
224  std::deque< Path > paths;
225  // get the results // route id are the targets
226  paths = get_paths(graph, v_source, v_targets, only_cost);
227 
228  std::stable_sort(paths.begin(), paths.end(),
229  [](const Path &e1, const Path &e2)->bool {
230  return e1.end_id() < e2.end_id();
231  });
232 
233  return paths;
234  }
std::deque< Path > get_paths(const G &graph, V source, std::vector< V > &targets, bool only_cost) const
std::vector< V > predecessors
int64_t end_id() const
bool dijkstra_1_to_many(G &graph, V source, const std::vector< V > &targets)
Call to Dijkstra 1 source to many targets.
std::vector< double > distances

Here is the call graph for this function:

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

Definition at line 237 of file pgr_dijkstra.hpp.

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

241  {
242  std::deque<Path> paths;
243 
244  for (const auto &start : start_vertex) {
245  paths.push_back(
246  dijkstra(graph, start, end_vertex, only_cost));
247  }
248 
249  std::stable_sort(paths.begin(), paths.end(),
250  [](const Path &e1, const Path &e2)->bool {
251  return e1.start_id() < e2.start_id();
252  });
253  return paths;
254  }
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

Here is the call graph for this function:

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

Definition at line 258 of file pgr_dijkstra.hpp.

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

262  {
263  // a call to 1 to many is faster for each of the sources
264  std::deque<Path> paths;
265  for (const auto &start : start_vertex) {
266  auto r_paths = dijkstra(graph, start, end_vertex, only_cost);
267  paths.insert(paths.begin(), r_paths.begin(), r_paths.end());
268  }
269 
270  std::sort(paths.begin(), paths.end(),
271  [](const Path &e1, const Path &e2)->bool {
272  return e1.end_id() < e2.end_id();
273  });
274  std::stable_sort(paths.begin(), paths.end(),
275  [](const Path &e1, const Path &e2)->bool {
276  return e1.start_id() < e2.start_id();
277  });
278  return paths;
279  }
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

Here is the call graph for this function:

template<class G>
bool 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 285 of file pgr_dijkstra.hpp.

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

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

288  {
289  try {
290  boost::dijkstra_shortest_paths(graph.graph, source,
291  boost::predecessor_map(&predecessors[0])
292  .weight_map(get(&G::G_T_E::cost, graph.graph))
293  .distance_map(&distances[0])
294  .visitor(dijkstra_one_goal_visitor(target)));
295  } catch(found_goals &) {
296  return true;
297  } catch (boost::exception const& ex) {
298  (void)ex;
299  throw;
300  } catch (std::exception &e) {
301  (void)e;
302  throw;
303  } catch (...) {
304  throw;
305  }
306  return true;
307  }
std::vector< V > predecessors
std::vector< double > distances

Here is the caller graph for this function:

template<class G>
bool 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 316 of file pgr_dijkstra.hpp.

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

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

319  {
320  try {
321  boost::dijkstra_shortest_paths(graph.graph, source,
322  boost::predecessor_map(&predecessors[0])
323  .weight_map(get(&G::G_T_E::cost, graph.graph))
324  .distance_map(&distances[0])
325  .visitor(dijkstra_distance_visitor(
326  distance,
328  distances)));
329  } catch(found_goals &) {
330  return true;
331  } catch (boost::exception const& ex) {
332  throw;
333  (void)ex;
334  } catch (std::exception &e) {
335  (void)e;
336  throw;
337  } catch (...) {
338  throw;
339  }
340  return true;
341  }
std::vector< V > predecessors
std::deque< V > nodesInDistance
std::vector< double > distances

Here is the caller graph for this function:

template<class G>
bool 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 348 of file pgr_dijkstra.hpp.

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

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

351  {
352  pgassert(predecessors.size() == graph.num_vertices());
353  pgassert(distances.size() == graph.num_vertices());
354  distances[source] = 0;
355  std::vector<boost::default_color_type> color_map(graph.num_vertices());
356  try {
357  boost::dijkstra_shortest_paths_no_init(graph.graph, source,
358  make_iterator_property_map(
359  predecessors.begin(),
360  graph.vertIndex),
361  make_iterator_property_map(
362  distances.begin(),
363  graph.vertIndex),
364  get(&G::G_T_E::cost, graph.graph),
365  graph.vertIndex,
366  std::less<double>(),
367  boost::closed_plus<double>(),
368  static_cast<double>(0),
369  dijkstra_distance_visitor_no_init(
370  log,
371  source,
372  distance,
373  predecessors,
374  distances,
375  color_map),
376  boost::make_iterator_property_map(
377  color_map.begin(),
378  graph.vertIndex,
379  color_map[0]));
380  } catch(found_goals &) {
381  return true;
382  } catch (boost::exception const& ex) {
383  (void)ex;
384  throw;
385  } catch (std::exception &e) {
386  (void)e;
387  throw;
388  } catch (...) {
389  throw;
390  }
391 
392 #if 0
393  /*
394  * Expensive assertion
395  */
396  for (V v = 0 ; v < predecessors.size(); ++v) {
397  log << "(" << predecessors[v] << "==" << v << "),";
398  if (v != source) {
399  pgassertwm(predecessors[v] == v, log.str().c_str());
400  }
401  }
402 #endif
403  return true;
404  }
#define pgassertwm(expr, msg)
Adds a message to the assertion.
Definition: pgr_assert.h:104
std::vector< V > predecessors
std::ostringstream log
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:81
std::vector< double > distances

Here is the caller graph for this function:

template<class G>
bool Pgr_dijkstra< G >::dijkstra_1_to_many ( G &  graph,
V  source,
const std::vector< V > &  targets 
)
inlineprivate

Call to Dijkstra 1 source to many targets.

Definition at line 649 of file pgr_dijkstra.hpp.

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

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

652  {
653  try {
654  boost::dijkstra_shortest_paths(graph.graph, source,
655  boost::predecessor_map(&predecessors[0])
656  .weight_map(get(&G::G_T_E::cost, graph.graph))
657  .distance_map(&distances[0])
658  .visitor(dijkstra_many_goal_visitor(targets)));
659  } catch(found_goals &) {
660  return true;
661  } catch (boost::exception const& ex) {
662  (void)ex;
663  throw;
664  } catch (std::exception &e) {
665  (void)e;
666  throw;
667  } catch (...) {
668  throw;
669  }
670  return true;
671  }
std::vector< V > predecessors
std::vector< double > distances

Here is the caller graph for this function:

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

1 to distance

Definition at line 98 of file pgr_dijkstra.hpp.

Referenced by pgr_drivingDistance().

101  {
103  graph,
104  start_vertex,
105  distance)) {
106  auto path = Path(graph,
107  start_vertex,
108  distance,
109  predecessors,
110  distances);
111 
112  std::sort(path.begin(), path.end(),
113  [](const Path_t &l, const Path_t &r)
114  {return l.node < r.node;});
115  std::stable_sort(path.begin(), path.end(),
116  [](const Path_t &l, const Path_t &r)
117  {return l.agg_cost < r.agg_cost;});
118  return path;
119  }
120 
121  /* The result is empty */
122  Path p(start_vertex, start_vertex);
123  p.push_back({start_vertex, -1, 0, 0});
124  return p;
125  }
bool execute_drivingDistance(G &graph, int64_t start_vertex, double distance)
to use with driving distance
std::vector< V > predecessors
int64_t node
Definition: path_t.h:37
Definition: path_t.h:36
std::vector< double > distances
double agg_cost
Definition: path_t.h:40

Here is the caller graph for this function:

template<class G>
std::deque< Path > 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 128 of file pgr_dijkstra.hpp.

References Pgr_dijkstra< G >::clear(), Pgr_dijkstra< G >::dijkstra(), Pgr_dijkstra< G >::dijkstra_1_to_1(), Pgr_dijkstra< G >::distances, Pgr_dijkstra< G >::drivingDistance_no_equicost(), Pgr_dijkstra< G >::drivingDistance_with_equicost(), Pgr_dijkstra< G >::log, and Pgr_dijkstra< G >::predecessors.

133  {
134  if (equicost) {
135  auto paths = drivingDistance_with_equicost(
136  graph,
137  start_vertex,
138  distance);
139  the_log << log.str();
140  return paths;
141  } else {
143  graph,
144  start_vertex,
145  distance);
146  }
147  }
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)

Here is the call graph for this function:

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

Definition at line 619 of file pgr_dijkstra.hpp.

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

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

622  {
623  std::deque< std::vector< V > > pred;
624  std::deque< std::vector< double > > dist;
625 
626  // perform the algorithm
627  std::deque<Path> paths;
628  for (const auto &vertex : start_vertex) {
629  if (execute_drivingDistance(graph, vertex, distance)) {
630  auto path = Path(
631  graph,
632  vertex,
633  distance,
634  predecessors,
635  distances);
636  path.sort_by_node_agg_cost();
637  paths.push_back(path);
638  } else {
639  Path p(vertex, vertex);
640  p.push_back({vertex, -1, 0, 0});
641  paths.push_back(p);
642  }
643  }
644  return paths;
645  }
bool execute_drivingDistance(G &graph, int64_t start_vertex, double distance)
to use with driving distance
std::vector< V > predecessors
static size_t pred(size_t i, size_t n)
Definition: pgr_tsp.cpp:64
std::vector< double > distances

Here is the call graph for this function:

Here is the caller graph for this function:

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

Definition at line 491 of file pgr_dijkstra.hpp.

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

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

494  {
495  clear();
496  log << "Number of edges:" << boost::num_edges(graph.graph) << "\n";
497 
498  predecessors.resize(graph.num_vertices());
499  distances.resize(
500  graph.num_vertices(),
501  std::numeric_limits<double>::max());
502 
503  /*
504  * Vector to store the different predessesors
505  * each is of size = graph.num_vertices()
506  *
507  * TODO(vicky)
508  * - figure out less storage if possible
509  */
510  std::deque< std::vector< V > > pred(start_vertex.size());
511 
512  // perform the algorithm
513  size_t i = 0;
514  for (const auto &vertex : start_vertex) {
515  nodesInDistance.clear();
516  /*
517  * The vertex does not exist
518  * Nothing to do
519  */
520  if (graph.has_vertex(vertex)) {
522  graph,
523  graph.get_V(vertex),
524  distance)) {
525  pred[i] = predecessors;
526  }
527  }
528  ++i;
529  }
530 
531 
532  /*
533  * predecessors of vertices in the set are themselves
534  */
535  for (const auto &vertex : start_vertex) {
536  for (auto &p : pred) {
537  if (!p.empty() & graph.has_vertex(vertex))
538  p[graph.get_V(vertex)] = graph.get_V(vertex);
539  }
540  }
541 
542 
544  graph,
545  start_vertex,
546  pred,
547  distance);
548  }
std::vector< V > predecessors
std::ostringstream log
static size_t pred(size_t i, size_t n)
Definition: pgr_tsp.cpp:64
bool execute_drivingDistance_no_init(G &graph, V start_vertex, double distance)
to use with driving distance
std::deque< V > nodesInDistance
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
std::vector< double > distances

Here is the call graph for this function:

Here is the caller graph for this function:

template<class G>
bool 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 419 of file pgr_dijkstra.hpp.

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

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

422  {
423  clear();
424 
425  predecessors.resize(graph.num_vertices());
426  distances.resize(graph.num_vertices());
427 
428  // get source;
429  if (!graph.has_vertex(start_vertex)) {
430  return false;
431  }
432 
433  return dijkstra_1_to_distance(
434  graph,
435  graph.get_V(start_vertex),
436  distance);
437  }
std::vector< V > predecessors
bool dijkstra_1_to_distance(G &graph, V source, double distance)
Call to Dijkstra 1 to distance.
std::vector< double > distances

Here is the call graph for this function:

Here is the caller graph for this function:

template<class G>
bool 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 452 of file pgr_dijkstra.hpp.

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

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

455  {
456  pgassert(predecessors.size() == graph.num_vertices());
457  pgassert(distances.size() == graph.num_vertices());
458 
459  std::iota(predecessors.begin(), predecessors.end(), 0);
460 
461 #if 0
462  /*
463  * Expensive assertion
464  */
465  for (V i = 0 ; i < predecessors.size(); ++i) {
466  pgassert(i == predecessors[i]);
467  }
468 #endif
469 
471  graph,
472  start_vertex,
473  distance);
474  }
std::vector< V > predecessors
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:81
bool dijkstra_1_to_distance_no_init(G &graph, V source, double distance)
Call to Dijkstra 1 to distance no init.
std::vector< double > distances

Here is the call graph for this function:

Here is the caller graph for this function:

template<class G>
std::deque< Path > 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 557 of file pgr_dijkstra.hpp.

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

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

561  {
562  /*
563  * precondition
564  */
565  pgassert(start_vertex.size() == pred.size());
566 
567 
568  /*
569  * Creating all the result "paths"
570  */
571  std::deque<Path> paths;
572  for (const auto vertex : start_vertex) {
573  paths.push_back(Path(vertex, vertex));
574  paths.back().push_back({vertex, -1, 0, 0});
575  }
576 
577  /*
578  * Ciclying the distances:
579  * To which vertex do they belong to?
580  */
581  for (V d = 0; d < distances.size(); ++d) {
582  /*
583  * Sikiping distances greater than the one asked for
584  */
585  if (!(distances[d] <= distance)) continue;
586 
587  for (auto i = start_vertex.size(); i > 0; --i) {
588  /*
589  * The vertex does not exist on the graph
590  */
591  if (pred[i - 1].empty()) {pgassert(false); continue;}
592 
593 
594  /*
595  * The predecessor = current then
596  * its unreachable to this vertex
597  */
598  if (pred[i - 1][d] == d) continue;
599 
600  auto cost = distances[d] - distances[pred[i - 1][d]];
601  auto edge_id = graph.get_edge_id(pred[i - 1][d], d, cost);
602  pgassert(edge_id != -1);
603  paths[i - 1].push_back(
604  {graph[d].id,
605  edge_id, cost,
606  distances[d]});
607  break;
608  }
609  }
610 
611  for (auto &path : paths) {
612  path.sort_by_node_agg_cost();
613  }
614  return paths;
615  }
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:81
std::vector< double > distances

Here is the call graph for this function:

Here is the caller graph for this function:

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

Definition at line 684 of file pgr_dijkstra.hpp.

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

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

688  {
689  std::deque<Path> paths;
690  for (const auto target : targets) {
691  paths.push_back(Path(
692  graph,
693  source, target,
695  only_cost, true));
696  }
697  return paths;
698  }
std::vector< V > predecessors
std::vector< double > distances

Here is the caller graph for this function:

Member Data Documentation

template<class G>
std::deque< V > Pgr_dijkstra< G >::nodesInDistance
private

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