pgRouting
pgRouting extends the PostGIS / PostgreSQL geospatial database to provide geospatial routing functionality.
 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 
29 #if defined(__MINGW32__) || defined(_MSC_VER)
30 #include <winsock2.h>
31 #include <windows.h>
32 #endif
33 
34 #include <sstream>
35 #include <deque>
36 #include <vector>
37 #include "./pgr_dijkstra.hpp"
38 #include "./dijkstraVia_driver.h"
39 #include "./../../common/src/pgr_alloc.hpp"
40 
41 
42 #include "./../../common/src/pgr_types.h"
43 
44 
45 template <class G>
46 void
48  G &graph,
49  const std::vector< int64_t > via_vertices,
50  std::deque< Path > &paths,
51  bool strict,
52  bool U_turn_on_edge,
53  std::ostringstream &log) {
54  if (via_vertices.size() == 0) {
55  return;
56  }
57 
58  paths.clear();
59  int64_t prev_vertex = via_vertices[0];
60  Path path;
61 
62  int64_t i = 0;
63  for (const auto &vertex : via_vertices) {
64  if (i == 0) {
65  prev_vertex = vertex; ++i;
66  continue;
67  }
68 
69  // Delete uTurn edges only valid for paths that are not the first path
70  if (!U_turn_on_edge && i > 1) {
71  // we can only delete if there is was a path, that is at least one edge size
72  if (path.size() > 1) {
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  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 << "departing from " << last_vertex_of_path
81  << " deleting edge " << edge_to_be_removed << "\n";
82  graph.disconnect_out_going_edge(last_vertex_of_path, edge_to_be_removed);
83  }
84  }
85  }
86 
87  path.clear();
88 
89  log << "from " << prev_vertex << " to " << vertex << "\n";
90  pgr_dijkstra(graph, path, 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 << "WAS empty so again from " << prev_vertex << " to " << vertex << "\n";
100  pgr_dijkstra(graph, path, prev_vertex, vertex);
101  }
102  }
103 
104  if (strict && path.empty()) {
105  paths.clear();
106  return;
107  }
108  paths.push_back(path);
109 
110  /*
111  * got to the next
112  */
113  prev_vertex = vertex; ++i;
114  }
115 }
116 
117 static
118 void
120  int route_id,
121  int path_id,
122  const Path &path,
123  Routes_t **postgres_data,
124  double &route_cost,
125  size_t &sequence) {
126  int i = 0;
127  for (const auto e : path) {
128  (*postgres_data)[sequence] = {
129  route_id,
130  path_id,
131  i,
132  path.start_id(),
133  path.end_id(),
134  e.node,
135  e.edge,
136  e.cost,
137  e.agg_cost,
138  route_cost};
139  route_cost += path[i].cost;
140  ++i;
141  ++sequence;
142  }
143 }
144 
145 
146 static
147 size_t
149  Routes_t **ret_path,
150  const std::deque< Path > &paths) {
151  size_t sequence = 0;
152  int path_id = 1;
153  int route_id = 1;
154  double route_cost = 0; // routes_agg_cost
155  for (const Path &path : paths) {
156  if (path.size() > 0)
157  get_path(route_id, path_id, path, ret_path, route_cost, sequence);
158  ++path_id;
159  }
160  return sequence;
161 }
162 
163 // CREATE OR REPLACE FUNCTION pgr_dijkstraViaVertices(sql text, vertices anyarray, directed boolean default true,
164 void
166  pgr_edge_t *data_edges, size_t total_tuples,
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  char ** err_msg) {
173  std::ostringstream log;
174  try {
175  if (total_tuples == 1) {
176  log << "Required: more than one tuple\n";
177  (*return_tuples) = NULL;
178  (*return_count) = 0;
179  *err_msg = strdup(log.str().c_str());
180  return;
181  }
182 
183  graphType gType = directed? DIRECTED: UNDIRECTED;
184 
185  std::deque< Path >paths;
186  log << "Inserting vertices into a c++ vector structure\n";
187  std::vector< int64_t > via_vertices(via_vidsArr, via_vidsArr + size_via_vidsArr);
188 
189  if (directed) {
190  log << "Working with directed Graph\n";
191  pgrouting::DirectedGraph digraph(gType);
192  digraph.graph_insert_data(data_edges, total_tuples);
193  pgr_dijkstraViaVertex(digraph, via_vertices, paths, strict, U_turn_on_edge, log);
194  } else {
195  log << "Working with Undirected Graph\n";
196  pgrouting::UndirectedGraph undigraph(gType);
197  undigraph.graph_insert_data(data_edges, total_tuples);
198  pgr_dijkstraViaVertex(undigraph, via_vertices, paths, strict, U_turn_on_edge, log);
199  }
200 
201  size_t count(count_tuples(paths));
202 
203  if (count == 0) {
204  (*return_tuples) = NULL;
205  (*return_count) = 0;
206  log <<
207  "No paths found\n";
208  *err_msg = strdup(log.str().c_str());
209  return;
210  }
211 
212  // get the space required to store all the paths
213  (*return_tuples) = pgr_alloc(count, (*return_tuples));
214  log << "Converting a set of paths into the tuples\n";
215  (*return_count) = (get_route(return_tuples, paths));
216  (*return_tuples)[count - 1].edge = -2;
217 
218 #ifndef DEBUG
219  *err_msg = strdup("OK");
220 #else
221  *err_msg = strdup(log.str().c_str());
222 #endif
223  } catch ( ... ) {
224  log << "Caught unknown exception!\n";
225  *err_msg = strdup(log.str().c_str());
226  }
227 }
228 
229 
230 
231 
232 
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 pgr_dijkstra(G &graph, Path &path, int64_t source, int64_t target, bool only_cost=false)
graphType
Definition: pgr_types.h:192
static size_t get_route(Routes_t **ret_path, const std::deque< Path > &paths)
void do_pgr_dijkstraViaVertex(pgr_edge_t *data_edges, size_t total_tuples, 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 **err_msg)
T * pgr_alloc(std::size_t size, T *ptr)
allocates memory
Definition: pgr_alloc.hpp:52
bool empty() const
path_element_t * path
Definition: BDATester.cpp:49
char * err_msg
Definition: BDATester.cpp:50
size_t size() const
void clear()
static void get_path(int route_id, int path_id, const Path &path, Routes_t **postgres_data, double &route_cost, size_t &sequence)
void graph_insert_data(const T *edges, int64_t count)
Inserts count edges of type T into the graph.