PGROUTING  2.5
 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 
29 
30 #include <sstream>
31 #include <deque>
32 #include <vector>
33 
35 
36 #include "cpp_common/pgr_alloc.hpp"
37 #include "cpp_common/pgr_assert.h"
38 
39 
40 template <class G>
41 void
43  G &graph,
44  const std::vector< int64_t > via_vertices,
45  std::deque< Path > &paths,
46  bool strict,
47  bool U_turn_on_edge,
48  std::ostringstream &log) {
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 }
117 
118 static
119 void
121  int route_id,
122  int path_id,
123  const Path &path,
124  Routes_t **postgres_data,
125  double &route_cost,
126  size_t &sequence) {
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 }
145 
146 
147 static
148 size_t
150  Routes_t **ret_path,
151  const std::deque< Path > &paths) {
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 }
163 
164 void
166  pgr_edge_t* data_edges, size_t total_edges,
167  int64_t* via_vidsArr, size_t size_via_vidsArr,
168  bool directed,
169  bool strict,
170  bool U_turn_on_edge,
171  Routes_t** return_tuples, size_t* return_count,
172 
173  char** log_msg,
174  char** notice_msg,
175  char** err_msg) {
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 }
262 
263 
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.
std::deque< Path > pgr_dijkstra(G &graph, std::vector< int64_t > sources, std::vector< int64_t > targets, bool only_cost, bool normal)
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: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
bool empty() const
Assertions Handling.
virtual const char * what() const
Definition: pgr_assert.cpp:53
graphType
Definition: graph_enum.h:30
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)