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
contractGraph_driver.cpp
Go to the documentation of this file.
1 /*PGR-GNU*****************************************************************
2 File: contractGraph_driver.cpp
3 
4 Generated with Template by:
5 Copyright (c) 2015 pgRouting developers
6 Mail: project@pgrouting.org
7 
8 Function's developer:
9 Copyright (c) 2016 Rohith Reddy
10 Mail:
11 
12 ------
13 
14 This program is free software; you can redistribute it and/or modify
15 it under the terms of the GNU General Public License as published by
16 the Free Software Foundation; either version 2 of the License, or
17 (at your option) any later version.
18 
19 This program is distributed in the hope that it will be useful,
20 but WITHOUT ANY WARRANTY; without even the implied warranty of
21 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
22 GNU General Public License for more details.
23 
24 You should have received a copy of the GNU General Public License
25 along with this program; if not, write to the Free Software
26 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
27 
28  ********************************************************************PGR-GNU*/
29 
30 
31 #if defined(__MINGW32__) || defined(_MSC_VER)
32 #include <winsock2.h>
33 #include <windows.h>
34 
35 #ifdef unlink
36 #undef unlink
37 #endif
38 
39 #endif
40 
41 
42 // #define DEBUG
43 #include <string.h>
44 #include <sstream>
45 #include <deque>
46 #include <vector>
47 #include "./contractGraph_driver.h"
48 
49 #include "./pgr_contract.hpp"
50 
51 #include "./../../common/src/pgr_types.h"
52 #include "./structs.h"
53 
54 #include "./../../common/src/pgr_alloc.hpp"
55 #include "./../../common/src/debug_macro.h"
56 #include "./../../common/src/identifiers.hpp"
57 
58 
59 /************************************************************
60  edges_sql TEXT,
61  contraction_order BIGINT[],
62  forbidden_vertices BIGINT[] DEFAULT ARRAY[]::BIGINT[],
63  max_cycles integer DEFAULT 1,
64  directed BOOLEAN DEFAULT true
65  ***********************************************************/
66  void
68  pgr_edge_t *data_edges,
69  size_t total_edges,
70  int64_t *forbidden_vertices,
71  size_t size_forbidden_vertices,
72  int64_t *contraction_order,
73  size_t size_contraction_order,
74  int64_t max_cycles,
75  bool directed,
76  pgr_contracted_blob **return_tuples,
77  size_t *return_count,
78  char ** err_msg) {
79  std::ostringstream log;
80  try {
81  std::ostringstream debug;
82  graphType gType = directed? DIRECTED: UNDIRECTED;
83  std::vector< pgr_edge_t > edges(data_edges, data_edges + total_edges);
84  std::vector < pgrouting::contraction::Vertex > vertices(pgrouting::contraction::extract_vertices(edges));
85  Identifiers<int64_t> remaining_vertices;
86  std::vector< pgrouting::contraction::Edge > shortcut_edges;
87 
88  log << "Original Graph: \n" <<
89  std::setprecision(32);
90  for (const auto edge : edges) {
91  log << "id = " << edge.id
92  << "\tsource = " << edge.source
93  << "\ttarget = " << edge.target
94  << "\tcost = " << edge.cost
95  << "\treverse_cost = " << edge.reverse_cost
96  << ")\n";
97  }
98  log << "size_contraction_order " << size_contraction_order << "\n";
99  log << "contraction_order: " <<"{ ";
100  for (size_t i = 0; i < size_contraction_order; ++i) {
101  log << contraction_order[i] << ", ";
102  }
103  log << " }\n";
104 
105  log << "size_forbidden_vertices " << size_forbidden_vertices << "\n";
106  log << "forbidden_vertices" << "{ ";
107  for (size_t i = 0; i < size_forbidden_vertices; ++i) {
108  log << forbidden_vertices[i] << ", ";
109  }
110  log << " }\n";
111  log << "max_cycles " << max_cycles << "\n";
112  log << "directed " << gType << "\n";
113 
114  if (directed) {
115  log << "Working with directed Graph\n";
116  pgrouting::CHDirectedGraph digraph(vertices, gType);
117  digraph.graph_insert_data(data_edges, total_edges);
118  log << "Checking for valid forbidden vertices\n";
119  for (size_t i = 0; i < size_forbidden_vertices; ++i) {
120  if (!digraph.has_vertex(forbidden_vertices[i])) {
121  log << "Invalid forbidden vertex: " << forbidden_vertices[i] << "\n";
122  *err_msg = strdup(log.str().c_str());
123  return;
124  }
125  }
126  Identifiers<int64_t> forbid_vertices(forbidden_vertices,
127  size_forbidden_vertices);
128  log << "Before contraction\n";
129  digraph.print_graph(log);
130  /* Function call to get the contracted graph. */
131  pgr_contractGraph(digraph,
132  forbid_vertices,
133  contraction_order, size_contraction_order,
134  max_cycles, remaining_vertices,
135  shortcut_edges, debug);
136 
137  log << "After contraction\n";
138  digraph.print_graph(log);
139  log << debug.str().c_str() << "\n";
140  (*return_tuples) = pgr_alloc(remaining_vertices.size()+shortcut_edges.size(), (*return_tuples));
141  size_t sequence = 0;
142  int i = 1;
143  log << "Remaining Vertices:" << "\n";
144  for (const auto vertex : remaining_vertices) {
145  log << vertex << "\n";
146  }
147  char *type;
148  for (auto id : remaining_vertices) {
149  type = strdup("v");
150  int64_t *contracted_vertices = NULL;
151  int contracted_vertices_size = 0;
152  digraph.get_contracted_vertices(&contracted_vertices,
153  contracted_vertices_size, id);
154  (*return_tuples)[sequence] = {i, id, type, -1, -1, -1.00,
155  contracted_vertices, contracted_vertices_size};
156  i++;
157  ++sequence;
158  }
159  log << "Added Edges:" << "\n";
160  for (const auto edge : shortcut_edges) {
161  log << edge << "\n";
162  }
163  for (auto edge : shortcut_edges) {
164  type = strdup("e");
165  int64_t *contracted_vertices = NULL;
166  int contracted_vertices_size = 0;
167  digraph.get_ids(&contracted_vertices,
168  contracted_vertices_size, edge.contracted_vertices());
169  (*return_tuples)[sequence] = {i, edge.id, type,
171  contracted_vertices, contracted_vertices_size};
172  i++;
173  ++sequence;
174  }
175 
176  (*return_count) = sequence;
177  log << "Returning from driver\n";
178  } else {
179  log << "Working with Undirected Graph\n";
180 
181  pgrouting::CHUndirectedGraph undigraph(vertices, gType);
182  undigraph.graph_insert_data(data_edges, total_edges);
183  log << "Checking for valid forbidden vertices\n";
184  for (size_t i = 0; i < size_forbidden_vertices; ++i) {
185  if (!undigraph.has_vertex(forbidden_vertices[i])) {
186  log << "Invalid forbidden vertex: " << forbidden_vertices[i] << "\n";
187  *err_msg = strdup(log.str().c_str());
188  return;
189  }
190  }
191  Identifiers<int64_t> forbid_vertices(forbidden_vertices,
192  size_forbidden_vertices);
193  log << "Before contraction\n";
194  undigraph.print_graph(log);
195  /* Function call to get the contracted graph. */
196  pgr_contractGraph(undigraph,
197  forbid_vertices,
198  contraction_order, size_contraction_order,
199  max_cycles, remaining_vertices,
200  shortcut_edges, debug);
201  log << debug.str().c_str() << "\n";
202  log << "After contraction\n";
203  undigraph.print_graph(log);
204  log << "Size of remaining_vertices: " << remaining_vertices.size() << std::endl;
205  (*return_tuples) = pgr_alloc(remaining_vertices.size()+shortcut_edges.size(), (*return_tuples));
206  size_t sequence = 0;
207  int i = 1;
208  log << "Remaining Vertices:" << "\n";
209  for (const auto vertex : remaining_vertices) {
210  log << vertex << "\n";
211  }
212  char *type;
213  for (auto id : remaining_vertices) {
214  type = strdup("v");
215  int64_t *contracted_vertices = NULL;
216  int contracted_vertices_size = 0;
217  undigraph.get_contracted_vertices(&contracted_vertices,
218  contracted_vertices_size, id);
219  (*return_tuples)[sequence] = {i, id, type, -1, -1, -1.00,
220  contracted_vertices, contracted_vertices_size};
221  i++;
222  ++sequence;
223  }
224  log << "Added Edges:" << "\n";
225  for (const auto edge : shortcut_edges) {
226  log << edge << "\n";
227  }
228  for (auto edge : shortcut_edges) {
229  type = strdup("e");
230  int64_t *contracted_vertices = NULL;
231  int contracted_vertices_size = 0;
232  undigraph.get_ids(&contracted_vertices,
233  contracted_vertices_size, edge.contracted_vertices());
234  (*return_tuples)[sequence] = {i, edge.id, type,
236  contracted_vertices, contracted_vertices_size};
237  i++;
238  ++sequence;
239  }
240  (*return_count) = sequence;
241  }
242 #ifndef DEBUG
243  *err_msg = strdup("OK");
244 #else
245  *err_msg = strdup(log.str().c_str());
246 #endif
247  }
248  catch (AssertFailedException &except) {
249  log << except.what() << "\n";
250  *err_msg = strdup(log.str().c_str());
251  } catch (std::exception& except) {
252  log << except.what() << "\n";
253  *err_msg = strdup(log.str().c_str());
254  } catch(...) {
255  log << "Caught unknown exception!\n";
256  *err_msg = strdup(log.str().c_str());
257  }
258  }
259 
260  int is_valid_contraction(int64_t number) {
261  switch (number) {
262  case 1:
263  return 1;
264  break;
265  case 2:
266  return 1;
267  break;
268  default:
269  return -1;
270  break;
271  }
272  }
273 
274 
275 
276 
277 
278 
void get_ids(std::ostringstream &log, Identifiers< int64_t > boost_ids)
get the user ids given the boost graph ids in string format
double cost
Extends std::exception and is the exception that we throw if an assert fails.
Definition: pgr_assert.h:126
void print_graph(std::ostringstream &log)
print the graph with contracted vertices of all vertices and edges
void get_contracted_vertices(std::ostringstream &log, int64_t vid)
get the contracted vertex ids of a given vertex in string format
void pgr_contractGraph(G &graph, Identifiers< int64_t > forbidden_vertices, int64_t *contraction_order, size_t size_contraction_order, int64_t max_cycles, Identifiers< int64_t > &remaining_vertices, std::vector< pgrouting::contraction::Edge > &shortcut_edges, std::ostringstream &debug)
bool has_vertex(int64_t vid) const
True when vid is in the graph.
edge_astar_t * edges
Definition: BDATester.cpp:46
graphType
Definition: pgr_types.h:192
int is_valid_contraction(int64_t number)
size_t size() const
Definition: identifiers.hpp:49
T * pgr_alloc(std::size_t size, T *ptr)
allocates memory
Definition: pgr_alloc.hpp:52
virtual const char * what() const
Definition: pgr_assert.cpp:62
void do_pgr_contractGraph(pgr_edge_t *data_edges, size_t total_edges, int64_t *forbidden_vertices, size_t size_forbidden_vertices, int64_t *contraction_order, size_t size_contraction_order, int64_t max_cycles, bool directed, pgr_contracted_blob **return_tuples, size_t *return_count, char **err_msg)
char * err_msg
Definition: BDATester.cpp:50
void graph_insert_data(const T *edges, int64_t count)
Inserts count edges of type T into the graph.
double reverse_cost
std::vector< Vertex > extract_vertices(const std::vector< pgr_edge_t > &data_edges)
Definition: ch_vertex.cpp:84