PGROUTING  3.2
Classes | Public Types | Public Member Functions | Private Member Functions | List of all members
Pgr_dag< G > Class Template Reference

#include "pgr_dagShortestPath.hpp"

Collaboration diagram for Pgr_dag< G >:
Collaboration graph
[legend]

Classes

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
 

Public Types

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

Public Member Functions

std::deque< Path > dag (G &graph, const std::vector< int64_t > &start_vertex, const std::vector< int64_t > &end_vertex, bool only_cost)
 
std::deque< Path > dag (G &graph, const std::vector< int64_t > &start_vertex, int64_t end_vertex, bool only_cost)
 
std::deque< Path > dag (G &graph, const std::vector< pgr_combination_t > &combinations, bool only_cost)
 
std::deque< Path > dag (G &graph, int64_t start_vertex, const std::vector< int64_t > &end_vertex, bool only_cost)
 Dijkstra 1 to many. More...
 
Path dag (G &graph, int64_t start_vertex, int64_t end_vertex, bool only_cost=false)
 Dijkstra 1 to 1. More...
 

Private Member Functions

void clear ()
 
bool dag_1_to_1 (G &graph, V source, V target)
 Call to Dijkstra 1 source to 1 target. More...
 
bool dag_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< Path > get_paths (const G &graph, V source, std::vector< V > &targets, bool only_cost) const
 

Private Attributes

members
std::vector< V > predecessors
 
std::vector< double > distances
 
std::deque< V > nodesInDistance
 
std::ostringstream log
 

Detailed Description

template<class G>
class Pgr_dag< G >

Definition at line 49 of file pgr_dagShortestPath.hpp.

Member Typedef Documentation

◆ E

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

Definition at line 52 of file pgr_dagShortestPath.hpp.

◆ V

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

Definition at line 51 of file pgr_dagShortestPath.hpp.

Member Function Documentation

◆ clear()

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

Definition at line 277 of file pgr_dagShortestPath.hpp.

277  {
278  predecessors.clear();
279  distances.clear();
280  nodesInDistance.clear();
281  }

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

Referenced by Pgr_dag< G >::dag().

◆ dag() [1/5]

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

Definition at line 156 of file pgr_dagShortestPath.hpp.

160  {
161  // a call to 1 to many is faster for each of the sources
162  std::deque<Path> paths;
163 
164  for (const auto &start : start_vertex) {
165  auto r_paths = dag(
166  graph,
167  start, end_vertex,
168  only_cost);
169  paths.insert(paths.begin(), r_paths.begin(), r_paths.end());
170  }
171 
172  std::sort(paths.begin(), paths.end(),
173  [](const Path &e1, const Path &e2)->bool {
174  return e1.end_id() < e2.end_id();
175  });
176  std::stable_sort(paths.begin(), paths.end(),
177  [](const Path &e1, const Path &e2)->bool {
178  return e1.start_id() < e2.start_id();
179  });
180  return paths;
181  }

References Pgr_dag< G >::dag().

◆ dag() [2/5]

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

Definition at line 135 of file pgr_dagShortestPath.hpp.

139  {
140  std::deque<Path> paths;
141 
142  for (const auto &start : start_vertex) {
143  paths.push_back(
144  dag(graph, start, end_vertex, only_cost));
145  }
146 
147  std::stable_sort(paths.begin(), paths.end(),
148  [](const Path &e1, const Path &e2)->bool {
149  return e1.start_id() < e2.start_id();
150  });
151  return paths;
152  }

References Pgr_dag< G >::dag().

◆ dag() [3/5]

template<class G >
std::deque<Path> Pgr_dag< G >::dag ( G &  graph,
const std::vector< pgr_combination_t > &  combinations,
bool  only_cost 
)
inline

Definition at line 184 of file pgr_dagShortestPath.hpp.

187  {
188  std::deque<Path> paths;
189 
190  // group targets per distinct source
191  std::map< int64_t, std::vector<int64_t> > vertex_map;
192  for (const pgr_combination_t &comb : combinations) {
193  std::map< int64_t, std::vector<int64_t> >::iterator it = vertex_map.find(comb.source);
194  if (it != vertex_map.end()) {
195  it->second.push_back(comb.target);
196  } else {
197  std::vector<int64_t > targets{comb.target};
198  vertex_map[comb.source] = targets;
199  }
200  }
201 
202  for (const auto &start_ends : vertex_map) {
203  auto result_paths = dag(
204  graph,
205  start_ends.first,
206  start_ends.second,
207  only_cost);
208  paths.insert(
209  paths.end(),
210  std::make_move_iterator(result_paths.begin()),
211  std::make_move_iterator(result_paths.end()));
212  }
213 
214  return paths;
215  }

References Pgr_dag< G >::dag().

◆ dag() [4/5]

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

Dijkstra 1 to many.

Definition at line 92 of file pgr_dagShortestPath.hpp.

96  {
97  // adjust predecessors and distances vectors
98  clear();
99  size_t n_goals = (std::numeric_limits<size_t>::max)();
100  predecessors.resize(graph.num_vertices());
101  distances.resize(
102  graph.num_vertices(),
103  std::numeric_limits<double>::infinity());
104 
105 
106  // get the graphs source and target
107  if (!graph.has_vertex(start_vertex))
108  return std::deque<Path>();
109  auto v_source(graph.get_V(start_vertex));
110 
111  std::set< V > s_v_targets;
112  for (const auto &vertex : end_vertex) {
113  if (graph.has_vertex(vertex)) {
114  s_v_targets.insert(graph.get_V(vertex));
115  }
116  }
117 
118  std::vector< V > v_targets(s_v_targets.begin(), s_v_targets.end());
119  // perform the algorithm
120  dag_1_to_many(graph, v_source, v_targets, n_goals);
121 
122  std::deque< Path > paths;
123  // get the results // route id are the targets
124  paths = get_paths(graph, v_source, v_targets, only_cost);
125 
126  std::stable_sort(paths.begin(), paths.end(),
127  [](const Path &e1, const Path &e2)->bool {
128  return e1.end_id() < e2.end_id();
129  });
130 
131  return paths;
132  }

References Pgr_dag< G >::clear(), Pgr_dag< G >::dag_1_to_many(), Pgr_dag< G >::distances, Pgr_dag< G >::get_paths(), and Pgr_dag< G >::predecessors.

◆ dag() [5/5]

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

Dijkstra 1 to 1.

Definition at line 56 of file pgr_dagShortestPath.hpp.

60  {
61  clear();
62 
63  // adjust predecessors and distances vectors
64  predecessors.resize(graph.num_vertices());
65  distances.resize(
66  graph.num_vertices(),
67  std::numeric_limits<double>::infinity());
68 
69 
70  if (!graph.has_vertex(start_vertex)
71  || !graph.has_vertex(end_vertex)) {
72  return Path(start_vertex, end_vertex);
73  }
74 
75  // get the graphs source and target
76  auto v_source(graph.get_V(start_vertex));
77  auto v_target(graph.get_V(end_vertex));
78 
79  // perform the algorithm
80  dag_1_to_1(graph, v_source, v_target);
81 
82  // get the results
83  return Path(
84  graph,
85  v_source, v_target,
86  predecessors, distances,
87  only_cost, true);
88  }

References Pgr_dag< G >::clear(), Pgr_dag< G >::dag_1_to_1(), Pgr_dag< G >::distances, and Pgr_dag< G >::predecessors.

Referenced by Pgr_dag< G >::dag(), and pgr_dagShortestPath().

◆ dag_1_to_1()

template<class G >
bool Pgr_dag< G >::dag_1_to_1 ( G &  graph,
V  source,
V  target 
)
inlineprivate

Call to Dijkstra 1 source to 1 target.

Definition at line 221 of file pgr_dagShortestPath.hpp.

224  {
225  /* abort in case of an interruption occurs (e.g. the query is being cancelled) */
226  CHECK_FOR_INTERRUPTS();
227  try {
228  boost::dag_shortest_paths(graph.graph, source,
229  boost::predecessor_map(&predecessors[0])
230  .weight_map(get(&G::G_T_E::cost, graph.graph))
231  .distance_map(&distances[0])
232  .visitor(dijkstra_one_goal_visitor(target)));
233  } catch(found_goals &) {
234  return true;
235  } catch (boost::exception const& ex) {
236  (void)ex;
237  throw;
238  } catch (std::exception &e) {
239  (void)e;
240  throw;
241  } catch (...) {
242  throw;
243  }
244  return true;
245  }

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

Referenced by Pgr_dag< G >::dag().

◆ dag_1_to_many()

template<class G >
bool Pgr_dag< G >::dag_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 248 of file pgr_dagShortestPath.hpp.

252  {
253  /* abort in case of an interruption occurs (e.g. the query is being cancelled) */
254  CHECK_FOR_INTERRUPTS();
255  try {
256  boost::dag_shortest_paths(graph.graph, source,
257  boost::predecessor_map(&predecessors[0])
258  .weight_map(get(&G::G_T_E::cost, graph.graph))
259  .distance_map(&distances[0])
260  .distance_inf(std::numeric_limits<double>::infinity())
261  .visitor(dijkstra_many_goal_visitor(targets, n_goals)));
262  } catch(found_goals &) {
263  return true;
264  } catch (boost::exception const& ex) {
265  (void)ex;
266  throw;
267  } catch (std::exception &e) {
268  (void)e;
269  throw;
270  } catch (...) {
271  throw;
272  }
273  return true;
274  }

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

Referenced by Pgr_dag< G >::dag().

◆ get_paths()

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

Definition at line 287 of file pgr_dagShortestPath.hpp.

291  {
292  std::deque<Path> paths;
293  for (const auto target : targets) {
294  paths.push_back(Path(
295  graph,
296  source, target,
297  predecessors, distances,
298  only_cost, true));
299  }
300  return paths;
301  }

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

Referenced by Pgr_dag< G >::dag().

Member Data Documentation

◆ distances

template<class G >
std::vector< double > Pgr_dag< G >::distances
private

Definition at line 309 of file pgr_dagShortestPath.hpp.

Referenced by Pgr_dag< G >::clear(), Pgr_dag< G >::dag(), Pgr_dag< G >::dag_1_to_1(), Pgr_dag< G >::dag_1_to_many(), and Pgr_dag< G >::get_paths().

◆ log

template<class G >
std::ostringstream Pgr_dag< G >::log
private

Definition at line 311 of file pgr_dagShortestPath.hpp.

◆ nodesInDistance

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

Definition at line 310 of file pgr_dagShortestPath.hpp.

Referenced by Pgr_dag< G >::clear().

◆ predecessors

template<class G >
std::vector< V > Pgr_dag< G >::predecessors
private

Definition at line 308 of file pgr_dagShortestPath.hpp.

Referenced by Pgr_dag< G >::clear(), Pgr_dag< G >::dag(), Pgr_dag< G >::dag_1_to_1(), Pgr_dag< G >::dag_1_to_many(), and Pgr_dag< G >::get_paths().

The documentation for this class was generated from the following file:
Pgr_dag::clear
void clear()
Definition: pgr_dagShortestPath.hpp:277
Path
Definition: basePath_SSEC.hpp:47
Pgr_dag::dag
Path dag(G &graph, int64_t start_vertex, int64_t end_vertex, bool only_cost=false)
Dijkstra 1 to 1.
Definition: pgr_dagShortestPath.hpp:56
Pgr_dag::dag_1_to_many
bool dag_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.
Definition: pgr_dagShortestPath.hpp:248
Pgr_dag::dag_1_to_1
bool dag_1_to_1(G &graph, V source, V target)
Call to Dijkstra 1 source to 1 target.
Definition: pgr_dagShortestPath.hpp:221
Pgr_dag::distances
std::vector< double > distances
Definition: pgr_dagShortestPath.hpp:309
Pgr_dag::get_paths
std::deque< Path > get_paths(const G &graph, V source, std::vector< V > &targets, bool only_cost) const
Definition: pgr_dagShortestPath.hpp:287
pgr_combination_t
Definition: pgr_combination_t.h:43
Pgr_dag::nodesInDistance
std::deque< V > nodesInDistance
Definition: pgr_dagShortestPath.hpp:310
Pgr_dag::predecessors
std::vector< V > predecessors
Definition: pgr_dagShortestPath.hpp:308