PGROUTING  2.4
 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 #include "./contractGraph_driver.h"
31 
32 #include <string.h>
33 #include <sstream>
34 #include <deque>
35 #include <vector>
36 
38 #include "./pgr_contract.hpp"
39 
40 #include "./../../common/src/pgr_alloc.hpp"
41 #include "./../../common/src/pgr_types.h"
42 
43 static
44 bool
45 is_valid_contraction(int64_t number) {
46  switch (number) {
47  case 1:
48  case 2:
49  return true;
50  break;
51  default:
52  return false;
53  break;
54  }
55 }
56 
57 
58 template <typename G>
59 static void process_contraction(
60  G &graph,
61  const std::vector< pgr_edge_t > &edges,
62  const std::vector< int64_t > forbidden_vertices,
63  const std::vector< int64_t > contraction_order,
64  int64_t max_cycles,
65  Identifiers<int64_t> &remaining_vertices,
66  std::vector< pgrouting::CH_edge > &shortcut_edges,
67  std::ostringstream &log,
68  std::ostringstream &err) {
69  graph.insert_edges(edges);
70  /*
71  * this check does not ignore vertices ids that do not belong to the graph
72  */
73  log << "Checking for valid forbidden vertices\n";
74  for (const auto vertex : forbidden_vertices) {
75  if (!graph.has_vertex(vertex)) {
76  err << "Invalid forbidden vertex: " << vertex << "\n";
77  return;
78  }
79  }
80 
81  Identifiers<typename G::V> forbid_vertices;
82  for (const auto &vertex : forbidden_vertices) {
83  if (graph.has_vertex(vertex)) {
84  forbid_vertices.insert(graph.get_V(vertex));
85  }
86  }
87 
88 #ifndef NDEBUG
89  log << "Before contraction\n";
90  graph.print_graph(log);
91 #endif
92 
93  /*
94  * Function call to get the contracted graph.
95  */
97  forbid_vertices,
98  contraction_order,
99  max_cycles, remaining_vertices,
100  shortcut_edges, log);
101 
102 #ifndef NDEBUG
103  log << "After contraction\n";
104  log << graph;
105  log << "Remaining Vertices:" << "\n";
106  for (const auto vertex : remaining_vertices) {
107  log << vertex << "\n";
108  }
109  log << "Added Edges:" << "\n";
110  for (const auto edge : shortcut_edges) {
111  log << edge << "\n";
112  }
113 #endif
114 }
115 
116 template <typename G>
117 static
119  G &graph,
120  const Identifiers<int64_t> remaining_vertices,
121  const std::vector< pgrouting::CH_edge > shortcut_edges,
122  pgr_contracted_blob **return_tuples) {
123  (*return_tuples) = pgr_alloc(
124  remaining_vertices.size() + shortcut_edges.size(),
125  (*return_tuples));
126 
127  size_t sequence = 0;
128 
129  for (auto id : remaining_vertices) {
130  int64_t* contracted_vertices = NULL;
131  auto ids = graph.get_contracted_vertices(id);
132  contracted_vertices = pgr_alloc(
133  ids.size(), contracted_vertices);
134  int count = 0;
135  for (const auto id : ids) {
136  contracted_vertices[count++] = id;
137  }
138  (*return_tuples)[sequence] = {id, const_cast<char*>("v"), -1, -1, -1.00,
139  contracted_vertices, count};
140 
141  ++sequence;
142  }
143 
144  for (auto edge : shortcut_edges) {
145  int64_t* contracted_vertices = NULL;
146  auto ids = graph.get_ids(edge.contracted_vertices());
147 
148  contracted_vertices = pgr_alloc(
149  ids.size(), contracted_vertices);
150  int count = 0;
151  for (const auto id : ids) {
152  contracted_vertices[count++] = id;
153  }
154  (*return_tuples)[sequence] = {edge.id, const_cast<char*>("e"),
156  contracted_vertices, count};
157 
158  ++sequence;
159  }
160 }
161 
162 
163 
164 
165 /************************************************************
166  edges_sql TEXT,
167  contraction_order BIGINT[],
168  forbidden_vertices BIGINT[] DEFAULT ARRAY[]::BIGINT[],
169  max_cycles integer DEFAULT 1,
170  directed BOOLEAN DEFAULT true
171  ***********************************************************/
172 void
174  pgr_edge_t *data_edges,
175  size_t total_edges,
176  int64_t *forbidden_vertices,
177  size_t size_forbidden_vertices,
178  int64_t *contraction_order,
179  size_t size_contraction_order,
180  int64_t max_cycles,
181  bool directed,
182  pgr_contracted_blob **return_tuples,
183  size_t *return_count,
184  char **log_msg,
185  char **notice_msg,
186  char **err_msg) {
187  std::ostringstream log;
188  std::ostringstream notice;
189  std::ostringstream err;
190  try {
191  pgassert(total_edges != 0);
192  pgassert(size_contraction_order != 0);
193  pgassert(max_cycles != 0);
194  pgassert(!(*log_msg));
195  pgassert(!(*notice_msg));
196  pgassert(!(*err_msg));
197  pgassert(!(*return_tuples));
198  pgassert(*return_count == 0);
199 
200  std::ostringstream debug;
201  /*
202  * Converting to C++ structures
203  */
204  std::vector<pgr_edge_t> edges(data_edges, data_edges + total_edges);
205  std::vector<int64_t> forbid(
206  forbidden_vertices,
207  forbidden_vertices + size_forbidden_vertices);
208  std::vector<int64_t> ordering(
209  contraction_order,
210  contraction_order + size_contraction_order);
211 
212  for (const auto o : ordering) {
213  if (!is_valid_contraction(o)) {
214  *err_msg = pgr_msg("Invalid Contraction Type found");
215  log << "Contraction type " << o << " not valid";
216  *log_msg = pgr_msg(log.str().c_str());
217  return;
218  }
219  }
220 
221 
222  /*
223  * Extracting vertices of the graph
224  */
225  Identifiers<int64_t> remaining_vertices;
226  std::vector< pgrouting::CH_edge > shortcut_edges;
227 
228 #ifndef NDEBUG
229  log << "Original Graph: \n" <<
230  std::setprecision(32);
231  for (const auto edge : edges) {
232  log << "id = " << edge.id
233  << "\tsource = " << edge.source
234  << "\ttarget = " << edge.target
235  << "\tcost = " << edge.cost
236  << "\treverse_cost = " << edge.reverse_cost
237  << ")\n";
238  }
239  log << "size_contraction_order " << ordering.size() << "\n";
240  log << "contraction_order: " <<"{ ";
241  for (const auto o : ordering) {
242  log << o << ", ";
243  }
244  log << " }\n";
245 
246  log << "size_forbidden_vertices " << forbid.size() << "\n";
247  log << "forbidden_vertices" << "{ ";
248  for (const auto vertex : forbid) {
249  log << vertex << ", ";
250  }
251  log << " }\n";
252  log << "max_cycles " << max_cycles << "\n";
253  log << "directed " << directed << "\n";
254 #endif
255 
256  graphType gType = directed? DIRECTED: UNDIRECTED;
257  if (directed) {
258  log << "Working with directed Graph\n";
259  pgrouting::CHDirectedGraph digraph(gType);
260 
261  process_contraction(digraph, edges, forbid, ordering,
262  max_cycles,
263  remaining_vertices, shortcut_edges,
264  log, err);
265 
267  digraph,
268  remaining_vertices,
269  shortcut_edges,
270  return_tuples);
271  } else {
272  log << "Working with Undirected Graph\n";
273 
274  pgrouting::CHUndirectedGraph undigraph(gType);
275  process_contraction(undigraph, edges, forbid, ordering,
276  max_cycles,
277  remaining_vertices, shortcut_edges,
278  log, err);
279 
281  undigraph,
282  remaining_vertices,
283  shortcut_edges,
284  return_tuples);
285  }
286 
287  (*return_count) = remaining_vertices.size()+shortcut_edges.size();
288 
289 
290  *log_msg = log.str().empty()?
291  *log_msg :
292  pgr_msg(log.str().c_str());
293  *notice_msg = notice.str().empty()?
294  *notice_msg :
295  pgr_msg(notice.str().c_str());
296  } catch (AssertFailedException &except) {
297  (*return_tuples) = pgr_free(*return_tuples);
298  (*return_count) = 0;
299  err << except.what();
300  *err_msg = pgr_msg(err.str().c_str());
301  *log_msg = pgr_msg(log.str().c_str());
302  } catch (std::exception &except) {
303  (*return_tuples) = pgr_free(*return_tuples);
304  (*return_count) = 0;
305  err << except.what();
306  *err_msg = pgr_msg(err.str().c_str());
307  *log_msg = pgr_msg(log.str().c_str());
308  } catch(...) {
309  (*return_tuples) = pgr_free(*return_tuples);
310  (*return_count) = 0;
311  err << "Caught unknown exception!";
312  *err_msg = pgr_msg(err.str().c_str());
313  *log_msg = pgr_msg(log.str().c_str());
314  }
315 }
static void process_contraction(G &graph, const std::vector< pgr_edge_t > &edges, const std::vector< int64_t > forbidden_vertices, const std::vector< int64_t > contraction_order, int64_t max_cycles, Identifiers< int64_t > &remaining_vertices, std::vector< pgrouting::CH_edge > &shortcut_edges, std::ostringstream &log, std::ostringstream &err)
Extends std::exception and is the exception that we throw if an assert fails.
Definition: pgr_assert.h:126
double cost
T * pgr_free(T *ptr)
Definition: pgr_alloc.hpp:73
static void get_postgres_result(G &graph, const Identifiers< int64_t > remaining_vertices, const std::vector< pgrouting::CH_edge > shortcut_edges, pgr_contracted_blob **return_tuples)
void insert(const Identifiers< T > &other)
Inserts a set of identifiers of type Identifiers<T> to this set.
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:81
double reverse_cost
edge_astar_t * edges
Definition: BDATester.cpp:46
graphType
Definition: pgr_types.h:222
size_t size() const
Definition: identifiers.hpp:56
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
virtual const char * what() const
Definition: pgr_assert.cpp:53
static bool is_valid_contraction(int64_t number)
char * err_msg
Definition: BDATester.cpp:50
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 **log_msg, char **notice_msg, char **err_msg)