PGROUTING  2.5
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
dijkstraVia_driver.cpp File Reference
#include "drivers/dijkstra/dijkstraVia_driver.h"
#include <sstream>
#include <deque>
#include <vector>
#include "dijkstra/pgr_dijkstra.hpp"
#include "cpp_common/pgr_alloc.hpp"
#include "cpp_common/pgr_assert.h"
Include dependency graph for dijkstraVia_driver.cpp:

Go to the source code of this file.

Functions

void do_pgr_dijkstraVia (pgr_edge_t *data_edges, size_t total_edges, int64_t *via_vidsArr, size_t size_via_vidsArr, bool directed, bool strict, bool U_turn_on_edge, Routes_t **return_tuples, size_t *return_count, char **log_msg, char **notice_msg, char **err_msg)
 
static void get_path (int route_id, int path_id, const Path &path, Routes_t **postgres_data, double &route_cost, size_t &sequence)
 
static size_t get_route (Routes_t **ret_path, const std::deque< Path > &paths)
 
template<class G >
void pgr_dijkstraViaVertex (G &graph, const std::vector< int64_t > via_vertices, std::deque< Path > &paths, bool strict, bool U_turn_on_edge, std::ostringstream &log)
 

Function Documentation

void do_pgr_dijkstraVia ( pgr_edge_t data_edges,
size_t  total_edges,
int64_t *  via_vidsArr,
size_t  size_via_vidsArr,
bool  directed,
bool  strict,
bool  U_turn_on_edge,
Routes_t **  return_tuples,
size_t *  return_count,
char **  log_msg,
char **  notice_msg,
char **  err_msg 
)

Definition at line 165 of file dijkstraVia_driver.cpp.

References count_tuples(), DIRECTED, get_route(), pgrouting::graph::Pgr_base_graph< G, Vertex, Edge >::insert_edges(), pgassert, pgr_alloc(), pgr_dijkstraViaVertex(), pgr_free(), pgr_msg(), UNDIRECTED, and AssertFailedException::what().

Referenced by process().

175  {
176  std::ostringstream log;
177  std::ostringstream err;
178  std::ostringstream notice;
179 
180  try {
181  pgassert(total_edges != 0);
182  pgassert(!(*log_msg));
183  pgassert(!(*notice_msg));
184  pgassert(!(*err_msg));
185  pgassert(!(*return_tuples));
186  pgassert(*return_count == 0);
187 
188  graphType gType = directed? DIRECTED: UNDIRECTED;
189 
190  std::deque< Path >paths;
191  log << "\nInserting vertices into a c++ vector structure";
192  std::vector< int64_t > via_vertices(
193  via_vidsArr, via_vidsArr + size_via_vidsArr);
194 
195  if (directed) {
196  log << "\nWorking with directed Graph";
197  pgrouting::DirectedGraph digraph(gType);
198  digraph.insert_edges(data_edges, total_edges);
200  digraph,
201  via_vertices,
202  paths,
203  strict,
204  U_turn_on_edge,
205  log);
206  } else {
207  log << "\nWorking with Undirected Graph";
208  pgrouting::UndirectedGraph undigraph(gType);
209  undigraph.insert_edges(data_edges, total_edges);
211  undigraph,
212  via_vertices,
213  paths,
214  strict,
215  U_turn_on_edge,
216  log);
217  }
218 
219  size_t count(count_tuples(paths));
220 
221  if (count == 0) {
222  (*return_tuples) = NULL;
223  (*return_count) = 0;
224  notice <<
225  "No paths found";
226  *log_msg = pgr_msg(notice.str().c_str());
227  return;
228  }
229 
230  // get the space required to store all the paths
231  (*return_tuples) = pgr_alloc(count, (*return_tuples));
232  log << "\nConverting a set of paths into the tuples";
233  (*return_count) = (get_route(return_tuples, paths));
234  (*return_tuples)[count - 1].edge = -2;
235 
236  *log_msg = log.str().empty()?
237  *log_msg :
238  pgr_msg(log.str().c_str());
239  *notice_msg = notice.str().empty()?
240  *notice_msg :
241  pgr_msg(notice.str().c_str());
242  } catch (AssertFailedException &except) {
243  (*return_tuples) = pgr_free(*return_tuples);
244  (*return_count) = 0;
245  err << except.what();
246  *err_msg = pgr_msg(err.str().c_str());
247  *log_msg = pgr_msg(log.str().c_str());
248  } catch (std::exception &except) {
249  (*return_tuples) = pgr_free(*return_tuples);
250  (*return_count) = 0;
251  err << except.what();
252  *err_msg = pgr_msg(err.str().c_str());
253  *log_msg = pgr_msg(log.str().c_str());
254  } catch(...) {
255  (*return_tuples) = pgr_free(*return_tuples);
256  (*return_count) = 0;
257  err << "Caught unknown exception!";
258  *err_msg = pgr_msg(err.str().c_str());
259  *log_msg = pgr_msg(log.str().c_str());
260  }
261 }
Extends std::exception and is the exception that we throw if an assert fails.
Definition: pgr_assert.h:126
void pgr_dijkstraViaVertex(G &graph, const std::vector< int64_t > via_vertices, std::deque< Path > &paths, bool strict, bool U_turn_on_edge, std::ostringstream &log)
T * pgr_free(T *ptr)
Definition: pgr_alloc.hpp:75
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:81
static size_t get_route(Routes_t **ret_path, const std::deque< Path > &paths)
char * pgr_msg(const std::string &msg)
Definition: pgr_alloc.cpp:29
size_t count_tuples(const std::deque< Path > &paths)
T * pgr_alloc(std::size_t size, T *ptr)
allocates memory
Definition: pgr_alloc.hpp:64
virtual const char * what() const
Definition: pgr_assert.cpp:53
graphType
Definition: graph_enum.h:30

Here is the call graph for this function:

Here is the caller graph for this function:

static void get_path ( int  route_id,
int  path_id,
const Path path,
Routes_t **  postgres_data,
double &  route_cost,
size_t &  sequence 
)
static

Definition at line 120 of file dijkstraVia_driver.cpp.

Referenced by get_route().

126  {
127  int i = 0;
128  for (const auto e : path) {
129  (*postgres_data)[sequence] = {
130  route_id,
131  path_id,
132  i,
133  path.start_id(),
134  path.end_id(),
135  e.node,
136  e.edge,
137  e.cost,
138  e.agg_cost,
139  route_cost};
140  route_cost += path[i].cost;
141  ++i;
142  ++sequence;
143  }
144 }

Here is the caller graph for this function:

static size_t get_route ( Routes_t **  ret_path,
const std::deque< Path > &  paths 
)
static

Definition at line 149 of file dijkstraVia_driver.cpp.

References get_path().

Referenced by do_pgr_dijkstraVia().

151  {
152  size_t sequence = 0;
153  int path_id = 1;
154  int route_id = 1;
155  double route_cost = 0; // routes_agg_cost
156  for (const Path &path : paths) {
157  if (path.size() > 0)
158  get_path(route_id, path_id, path, ret_path, route_cost, sequence);
159  ++path_id;
160  }
161  return sequence;
162 }
static void get_path(int route_id, int path_id, const Path &path, Routes_t **postgres_data, double &route_cost, size_t &sequence)

Here is the call graph for this function:

Here is the caller graph for this function:

template<class G >
void pgr_dijkstraViaVertex ( G &  graph,
const std::vector< int64_t >  via_vertices,
std::deque< Path > &  paths,
bool  strict,
bool  U_turn_on_edge,
std::ostringstream &  log 
)

Definition at line 42 of file dijkstraVia_driver.cpp.

References Path::empty(), pgr_dijkstra(), and Path::size().

Referenced by do_pgr_dijkstraVia().

48  {
49  if (via_vertices.size() == 0) {
50  return;
51  }
52 
53  paths.clear();
54  int64_t prev_vertex = via_vertices[0];
55  Path path;
56 
57  int64_t i = 0;
58  for (const auto &vertex : via_vertices) {
59  if (i == 0) {
60  prev_vertex = vertex; ++i;
61  continue;
62  }
63 
64  // Delete U Turn edges only valid for paths that are not the first path
65  if (!U_turn_on_edge && i > 1) {
66  /*
67  * Can only delete if there was a path,
68  * that is at least one edge size
69  */
70  if (path.size() > 1) {
71  /*
72  * Delete from the graph the last edge if its outgoing also
73  * edge to be removed = second to last edge path[i].edge;
74  */
75  int64_t edge_to_be_removed = path[path.size() - 2].edge;
76  int64_t last_vertex_of_path = prev_vertex;
77 
78  // and the current vertex is not a dead end
79  if (graph.out_degree(last_vertex_of_path) > 1) {
80  log << "\ndeparting from " << last_vertex_of_path
81  << " deleting edge " << edge_to_be_removed << "\n";
82  graph.disconnect_out_going_edge(
83  last_vertex_of_path,
84  edge_to_be_removed);
85  }
86  }
87  }
88 
89  log << "\nfrom " << prev_vertex << " to " << vertex;
90  path = pgr_dijkstra(graph, prev_vertex, vertex);
91 
92  if (!U_turn_on_edge && i > 1) {
93  graph.restore_graph();
94  if (path.empty()) {
95  /*
96  * no path was found with the deleted edge
97  * try with the edge back in the graph
98  */
99  log << "\nEmpty so again from "
100  << prev_vertex << " to " << vertex;
101  path = pgr_dijkstra(graph, prev_vertex, vertex);
102  }
103  }
104 
105  if (strict && path.empty()) {
106  paths.clear();
107  return;
108  }
109  paths.push_back(path);
110 
111  /*
112  * got to the next
113  */
114  prev_vertex = vertex; ++i;
115  }
116 }
std::deque< Path > pgr_dijkstra(G &graph, std::vector< int64_t > sources, std::vector< int64_t > targets, bool only_cost, bool normal)
bool empty() const
size_t size() const

Here is the call graph for this function:

Here is the caller graph for this function: