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