PGROUTING  2.4
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
dijkstraVia_driver.cpp
Go to the documentation of this file.
1 /*PGR-GNU*****************************************************************
2 File: dijkstraViaVertex_driver.cpp
3 
4 Generated with Template by:
5 Copyright (c) 2015 pgRouting developers
6 
7 Function's developer:
8 Copyright (c) 2015 Celia Virginia Vergara Castillo
9 
10 ------
11 
12 This program is free software; you can redistribute it and/or modify
13 it under the terms of the GNU General Public License as published by
14 the Free Software Foundation; either version 2 of the License, or
15 (at your option) any later version.
16 
17 This program is distributed in the hope that it will be useful,
18 but WITHOUT ANY WARRANTY; without even the implied warranty of
19 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
20 GNU General Public License for more details.
21 
22 You should have received a copy of the GNU General Public License
23 along with this program; if not, write to the Free Software
24 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
25 
26 ********************************************************************PGR-GNU*/
27 
28 #include "./dijkstraVia_driver.h"
29 
30 #include <sstream>
31 #include <deque>
32 #include <vector>
33 
34 #include "./pgr_dijkstra.hpp"
35 
36 #include "./../../common/src/pgr_alloc.hpp"
37 #include "./../../common/src/pgr_assert.h"
38 #include "./../../common/src/pgr_types.h"
39 
40 
41 template <class G>
42 void
44  G &graph,
45  const std::vector< int64_t > via_vertices,
46  std::deque< Path > &paths,
47  bool strict,
48  bool U_turn_on_edge,
49  std::ostringstream &log) {
50  if (via_vertices.size() == 0) {
51  return;
52  }
53 
54  paths.clear();
55  int64_t prev_vertex = via_vertices[0];
56  Path path;
57 
58  int64_t i = 0;
59  for (const auto &vertex : via_vertices) {
60  if (i == 0) {
61  prev_vertex = vertex; ++i;
62  continue;
63  }
64 
65  // Delete U Turn edges only valid for paths that are not the first path
66  if (!U_turn_on_edge && i > 1) {
67  /*
68  * Can only delete if there was a path,
69  * that is at least one edge size
70  */
71  if (path.size() > 1) {
72  /*
73  * Delete from the graph the last edge if its outgoing also
74  * edge to be removed = second to last edge path[i].edge;
75  */
76  int64_t edge_to_be_removed = path[path.size() - 2].edge;
77  int64_t last_vertex_of_path = prev_vertex;
78 
79  // and the current vertex is not a dead end
80  if (graph.out_degree(last_vertex_of_path) > 1) {
81  log << "\ndeparting from " << last_vertex_of_path
82  << " deleting edge " << edge_to_be_removed << "\n";
83  graph.disconnect_out_going_edge(
84  last_vertex_of_path,
85  edge_to_be_removed);
86  }
87  }
88  }
89 
90  log << "\nfrom " << prev_vertex << " to " << vertex;
91  path = pgr_dijkstra(graph, prev_vertex, vertex);
92 
93  if (!U_turn_on_edge && i > 1) {
94  graph.restore_graph();
95  if (path.empty()) {
96  /*
97  * no path was found with the deleted edge
98  * try with the edge back in the graph
99  */
100  log << "\nEmpty so again from "
101  << prev_vertex << " to " << vertex;
102  path = pgr_dijkstra(graph, prev_vertex, vertex);
103  }
104  }
105 
106  if (strict && path.empty()) {
107  paths.clear();
108  return;
109  }
110  paths.push_back(path);
111 
112  /*
113  * got to the next
114  */
115  prev_vertex = vertex; ++i;
116  }
117 }
118 
119 static
120 void
122  int route_id,
123  int path_id,
124  const Path &path,
125  Routes_t **postgres_data,
126  double &route_cost,
127  size_t &sequence) {
128  int i = 0;
129  for (const auto e : path) {
130  (*postgres_data)[sequence] = {
131  route_id,
132  path_id,
133  i,
134  path.start_id(),
135  path.end_id(),
136  e.node,
137  e.edge,
138  e.cost,
139  e.agg_cost,
140  route_cost};
141  route_cost += path[i].cost;
142  ++i;
143  ++sequence;
144  }
145 }
146 
147 
148 static
149 size_t
151  Routes_t **ret_path,
152  const std::deque< Path > &paths) {
153  size_t sequence = 0;
154  int path_id = 1;
155  int route_id = 1;
156  double route_cost = 0; // routes_agg_cost
157  for (const Path &path : paths) {
158  if (path.size() > 0)
159  get_path(route_id, path_id, path, ret_path, route_cost, sequence);
160  ++path_id;
161  }
162  return sequence;
163 }
164 
165 void
167  pgr_edge_t* data_edges, size_t total_edges,
168  int64_t* via_vidsArr, size_t size_via_vidsArr,
169  bool directed,
170  bool strict,
171  bool U_turn_on_edge,
172  Routes_t** return_tuples, size_t* return_count,
173 
174  char** log_msg,
175  char** notice_msg,
176  char** err_msg) {
177  std::ostringstream log;
178  std::ostringstream err;
179  std::ostringstream notice;
180 
181  try {
182  pgassert(total_edges != 0);
183  pgassert(!(*log_msg));
184  pgassert(!(*notice_msg));
185  pgassert(!(*err_msg));
186  pgassert(!(*return_tuples));
187  pgassert(*return_count == 0);
188 
189  graphType gType = directed? DIRECTED: UNDIRECTED;
190 
191  std::deque< Path >paths;
192  log << "\nInserting vertices into a c++ vector structure";
193  std::vector< int64_t > via_vertices(
194  via_vidsArr, via_vidsArr + size_via_vidsArr);
195 
196  if (directed) {
197  log << "\nWorking with directed Graph";
198  pgrouting::DirectedGraph digraph(gType);
199  digraph.insert_edges(data_edges, total_edges);
201  digraph,
202  via_vertices,
203  paths,
204  strict,
205  U_turn_on_edge,
206  log);
207  } else {
208  log << "\nWorking with Undirected Graph";
209  pgrouting::UndirectedGraph undigraph(gType);
210  undigraph.insert_edges(data_edges, total_edges);
212  undigraph,
213  via_vertices,
214  paths,
215  strict,
216  U_turn_on_edge,
217  log);
218  }
219 
220  size_t count(count_tuples(paths));
221 
222  if (count == 0) {
223  (*return_tuples) = NULL;
224  (*return_count) = 0;
225  notice <<
226  "No paths found";
227  *log_msg = pgr_msg(notice.str().c_str());
228  return;
229  }
230 
231  // get the space required to store all the paths
232  (*return_tuples) = pgr_alloc(count, (*return_tuples));
233  log << "\nConverting a set of paths into the tuples";
234  (*return_count) = (get_route(return_tuples, paths));
235  (*return_tuples)[count - 1].edge = -2;
236 
237  *log_msg = log.str().empty()?
238  *log_msg :
239  pgr_msg(log.str().c_str());
240  *notice_msg = notice.str().empty()?
241  *notice_msg :
242  pgr_msg(notice.str().c_str());
243  } catch (AssertFailedException &except) {
244  (*return_tuples) = pgr_free(*return_tuples);
245  (*return_count) = 0;
246  err << except.what();
247  *err_msg = pgr_msg(err.str().c_str());
248  *log_msg = pgr_msg(log.str().c_str());
249  } catch (std::exception &except) {
250  (*return_tuples) = pgr_free(*return_tuples);
251  (*return_count) = 0;
252  err << except.what();
253  *err_msg = pgr_msg(err.str().c_str());
254  *log_msg = pgr_msg(log.str().c_str());
255  } catch(...) {
256  (*return_tuples) = pgr_free(*return_tuples);
257  (*return_count) = 0;
258  err << "Caught unknown exception!";
259  *err_msg = pgr_msg(err.str().c_str());
260  *log_msg = pgr_msg(log.str().c_str());
261  }
262 }
263 
264 
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)
void insert_edges(const T *edges, int64_t count)
Inserts count edges of type T into the graph.
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)
T * pgr_free(T *ptr)
Definition: pgr_alloc.hpp:73
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:81
std::deque< Path > pgr_dijkstra(G &graph, std::vector< int64_t > sources, std::vector< int64_t > targets, bool only_cost, bool normal)
graphType
Definition: pgr_types.h:222
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
T * pgr_alloc(std::size_t size, T *ptr)
allocates memory
Definition: pgr_alloc.hpp:62
bool empty() const
path_element_t * path
Definition: BDATester.cpp:49
virtual const char * what() const
Definition: pgr_assert.cpp:53
char * err_msg
Definition: BDATester.cpp:50
size_t size() const
static void get_path(int route_id, int path_id, const Path &path, Routes_t **postgres_data, double &route_cost, size_t &sequence)