pgRouting  2.2
pgRouting extends the PostGIS / PostgreSQL geospatial database to provide geospatial routing functionality.
 All Classes Functions Variables Pages
dijkstraVia_driver.cpp
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 #ifdef __MINGW32__
30 #include <winsock2.h>
31 #include <windows.h>
32 #endif
33 
34 
35 #include <sstream>
36 #include <deque>
37 #include <vector>
38 #include "./pgr_dijkstra.hpp"
39 #include "./dijkstraVia_driver.h"
40 #include "./../../common/src/memory_func.hpp"
41 
42 // #define DEBUG
43 
44 extern "C" {
45 #include "./../../common/src/pgr_types.h"
46 }
47 
48 
49 template <class G>
50 void
51 pgr_dijkstraViaVertex(
52  G &graph,
53  const std::vector< int64_t > via_vertices,
54  std::deque< Path > &paths,
55  bool strict,
56  bool U_turn_on_edge,
57  std::ostringstream &log) {
58 
59  if (via_vertices.size() == 0) {
60  return;
61  }
62 
63  paths.clear();
64  int64_t prev_vertex = via_vertices[0];
65  Path path;
66 
67  //for (size_t i = 0; i < via_vertices.size() - 1; ++i) {
68  int64_t i = 0;
69  for (const auto &vertex : via_vertices) {
70  if (i == 0) {
71  prev_vertex = vertex; ++i;
72  continue;
73  }
74 
75  // Delete uTurn edges only valid for paths that are not the first path
76  if (!U_turn_on_edge && i > 1) {
77 
78  // we can only delete if there is was a path, that is at least one edge size
79  if (path.size() > 1) {
80  // Delete from the graph the last edge if its outgoing also
81  // edge to be removed = second to last edge path[i].edge;
82  int64_t edge_to_be_removed = path[path.size() - 2].edge;
83  int64_t last_vertex_of_path = prev_vertex;
84  // path.path[path.path.size() - 1].vertex;
85 
86  // and the current vertex is not a dead end
87  if (graph.out_degree(last_vertex_of_path) > 1) {
88  log << "departing from " << last_vertex_of_path
89  << " deleting edge " << edge_to_be_removed << "\n";
90  graph.disconnect_out_going_edge(last_vertex_of_path, edge_to_be_removed);
91  }
92  }
93  }
94 
95  path.clear();
96 
97  log << "from " << prev_vertex << " to " << vertex << "\n";
98  pgr_dijkstra(graph, path, prev_vertex, vertex);
99 
100  if (!U_turn_on_edge && i > 1) {
101  graph.restore_graph();
102  if (path.empty()) {
103  /*
104  * no path was found with the deleted edge
105  * try with the edge back in the graph
106  */
107  log << "WAS empty so again from " << prev_vertex << " to " << vertex << "\n";
108  pgr_dijkstra(graph, path, prev_vertex, vertex);
109  }
110  }
111 
112  if (strict && path.empty()) {
113  paths.clear();
114  return;
115  }
116  paths.push_back(path);
117 
118  /*
119  * got to the next
120  */
121  prev_vertex = vertex; ++i;
122  }
123 }
124 
125 static
126 void
127 get_path(
128  int route_id,
129  int path_id,
130  const Path &path,
131  Routes_t **postgres_data,
132  double &route_cost,
133  size_t &sequence) {
134  int i = 0;
135  //for (size_t i = 0; i < path.size(); i++) {
136  for (const auto e : path) {
137  (*postgres_data)[sequence] = {
138  route_id,
139  path_id,
140  i,
141  path.start_id(),
142  path.end_id(),
143  e.node,
144  e.edge,
145  e.cost,
146  e.agg_cost,
147  route_cost};
148  route_cost += path[i].cost;
149  ++i;
150  ++sequence;
151  }
152 }
153 
154 
155 static
156 size_t
157 get_route(
158  Routes_t **ret_path,
159  const std::deque< Path > &paths) {
160  size_t sequence = 0; //arrys index
161  int path_id = 1; // id's in posgresql start with 1
162  int route_id = 1;
163  double route_cost = 0; // routes_agg_cost
164  for (const Path &path : paths) {
165  if (path.size() > 0)
166  get_path(route_id, path_id, path, ret_path, route_cost, sequence);
167  ++path_id;
168  }
169  return sequence;
170 }
171 
172 // CREATE OR REPLACE FUNCTION pgr_dijkstraViaVertices(sql text, vertices anyarray, directed boolean default true,
173 void
174 do_pgr_dijkstraViaVertex(
175  pgr_edge_t *data_edges, size_t total_tuples,
176  int64_t *via_vidsArr, size_t size_via_vidsArr,
177  bool directed,
178  bool strict,
179  bool U_turn_on_edge,
180  Routes_t **return_tuples, size_t *return_count,
181  char ** err_msg){
182  std::ostringstream log;
183  try {
184 
185  if (total_tuples == 1) {
186  log << "Requiered: more than one tuple\n";
187  (*return_tuples) = NULL;
188  (*return_count) = 0;
189  *err_msg = strdup(log.str().c_str());
190  return;
191  }
192 
193  graphType gType = directed? DIRECTED: UNDIRECTED;
194  const auto initial_size = total_tuples;
195 
196  std::deque< Path >paths;
197  log << "Inserting vertices into a c++ vector structure\n";
198  std::vector< int64_t > via_vertices(via_vidsArr, via_vidsArr + size_via_vidsArr);
199 
200  if (directed) {
201  log << "Working with directed Graph\n";
202  Pgr_base_graph< DirectedGraph > digraph(gType, initial_size);
203  digraph.graph_insert_data(data_edges, total_tuples);
204  pgr_dijkstraViaVertex(digraph, via_vertices, paths, strict, U_turn_on_edge, log);
205  } else {
206  log << "Working with Undirected Graph\n";
207  Pgr_base_graph< UndirectedGraph > undigraph(gType, initial_size);
208  undigraph.graph_insert_data(data_edges, total_tuples);
209  pgr_dijkstraViaVertex(undigraph, via_vertices, paths, strict, U_turn_on_edge, log);
210  }
211 
212  size_t count(count_tuples(paths));
213 
214  if (count == 0) {
215  (*return_tuples) = NULL;
216  (*return_count) = 0;
217  log <<
218  "No paths found between Starting and any of the Ending vertices\n";
219  *err_msg = strdup(log.str().c_str());
220  return;
221  }
222 
223  // get the space required to store all the paths
224  (*return_tuples) = get_memory(count, (*return_tuples));
225  log << "Converting a set of paths into the tuples\n";
226  (*return_count) = (get_route(return_tuples, paths));
227  (*return_tuples)[count - 1].edge = -2;
228 
229 #ifndef DEBUG
230  *err_msg = strdup("OK");
231 #else
232  *err_msg = strdup(log.str().c_str());
233 #endif
234  } catch ( ... ) {
235  log << "Caught unknown expection!\n";
236  *err_msg = strdup(log.str().c_str());
237  }
238 }
239 
240 
241 
242 
243 
Definition: alpha.h:33