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
pgr_contract.hpp
Go to the documentation of this file.
1 /*PGR-GNU*****************************************************************
2 File: pgr_contract.hpp
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 #pragma once
31 #include <stack>
32 #include <iostream>
33 #include <sstream>
34 #include <deque>
35 #include <queue>
36 #include <string>
37 #include <utility>
38 #include <functional>
39 #include <vector>
40 #include <map>
41 
45 #include "../../common/src/pgr_assert.h"
46 
47 
48 template < class G > class Pgr_contract;
49 
50 template < class G >
51 void perform_deadEnd(G &graph,
52  Identifiers<int64_t> forbidden_vertices,
53  std::ostringstream& debug) {
54  pgrouting::Pgr_deadEndContraction<G> deadendContractor;
55  debug << "Setting forbidden_vertices";
56  deadendContractor.setForbiddenVertices(graph, forbidden_vertices
57  , debug);
58 
59  deadendContractor.calculateVertices(graph, debug);
60  try {
61  deadendContractor.doContraction(graph, debug);
62  }
63  catch ( ... ) {
64  debug << "Caught unknown exception!\n";
65  }
66 }
67 
68 #if 1
69 
70 template < class G >
71 void perform_linear(G &graph,
72  Identifiers<int64_t>& forbidden_vertices,
73  std::ostringstream& debug) {
74  std::ostringstream linear_debug;
75  pgrouting::Pgr_linearContraction<G> linearContractor;
76  linearContractor.setForbiddenVertices(graph, forbidden_vertices
77  , linear_debug);
78  linearContractor.calculateVertices(graph, linear_debug);
79  try {
80  linearContractor.doContraction(graph, linear_debug);
81  }
82  catch ( ... ) {
83  linear_debug << "Caught unknown exception!\n";
84  }
85  debug << linear_debug.str().c_str() << "\n";
86 }
87 #endif
88 
89 
90 template < class G >
92  G &graph, Identifiers<int64_t> forbidden_vertices,
93  int64_t *contraction_order,
94  size_t size_contraction_order,
95  int64_t max_cycles,
96  Identifiers<int64_t> &remaining_vertices,
97  std::vector<pgrouting::contraction::Edge> &shortcut_edges,
98  std::ostringstream& debug) {
99  std::deque<int64_t> contract_order;
100  // push -1 to indicate the start of the queue
101  contract_order.push_back(-1);
102  for (size_t i = 0; i < size_contraction_order; ++i) {
103  contract_order.push_back(contraction_order[i]);
104  }
105  for (int64_t i = 0; i < max_cycles; ++i) {
106  int64_t front = contract_order.front();
107  debug << "Starting cycle " << i+1 << "\n";
108  contract_order.pop_front();
109  contract_order.push_back(front);
110  front = contract_order.front();
111  while (front != -1) {
112  switch (front) {
113  case -1:
114  debug << "Finished cycle " << i+1 << std::endl;
115  break;
116  default:
117  debug << "contraction "<< front << " asked" << std::endl;
118  if (front == 1) {
119  debug << "Graph before dead end contraction" << std::endl;
120  graph.print_graph(debug);
121  debug << "Performing dead end contraction" << std::endl;
122  perform_deadEnd(graph, forbidden_vertices, debug);
123  debug << "Graph after dead end contraction" << std::endl;
124  graph.print_graph(debug);
125  } else if (front == 2) {
126  debug << "Graph before linear contraction" << std::endl;
127  graph.print_graph(debug);
128  debug << "Performing linear contraction" << std::endl;
129  perform_linear(graph, forbidden_vertices, debug);
130  debug << "Graph after linear contraction" << std::endl;
131  graph.print_graph(debug);
132  }
133  contract_order.pop_front();
134  contract_order.push_back(front);
135  front = contract_order.front();
136  }
137  }
138  }
139  graph.get_changed_vertices(remaining_vertices);
140  debug << "Printing shortcuts\n";
141  for (auto shortcut : graph.shortcuts) {
142  debug << shortcut;
143  shortcut_edges.push_back(shortcut);
144  }
145 }
146 
147 bool is_valid_contraction_number(int number) {
148  switch (number) {
149  case -2:
150  return false;
151  break;
152  case -1:
153  return false;
154  break;
155  case 0:
156  return true;
157  break;
158  case 1:
159  return true;
160  break;
161  default:
162  return false;
163  break;
164  }
165 }
166 
167 template < class G >
168 class Pgr_contract {
169  public:
181  // @{
182  typedef typename G::V V;
183  typedef typename G::E E;
184  typedef typename G::V_i V_i;
185  typedef typename G::E_i E_i;
186  typedef typename G::EO_i EO_i;
187  #if 0
188  typedef typename G::degree_to_V_i degree_to_V_i;
189  #endif
190  typedef typename G::EI_i EI_i;
191  // @}
192  // ! @name Framework related functions
193  // @{
199  void disconnectVertex(G &graph, int64_t vertex_id);
205  void setForbiddenVertices(int64_t *forbidden_vertices,
206  size_t size_forbidden_vertices);
207 
212  void getAllVertices(G &graph);
213 
218 
225  Identifiers<int64_t> getAdjacentVertices(G &graph, int64_t vertex_id);
230  void print_identifiers(std::ostringstream& stream, Identifiers<int64_t> identifiers);
231 
235  void print_forbidden_vertices(std::ostringstream& stream);
236 
240  void print_all_vertices(std::ostringstream& stream);
241 
245  void print_non_contracted_vertices(std::ostringstream& stream);
246 
247  // @}
248  // ! @name Dead end contraction related functions
249  // @{
250 
255  bool is_dead_end(G &graph, int64_t vertex_id) const;
256 
261  void getDeadEndSet(G &graph);
262 
266  void print_dead_end_vertices(std::ostringstream& stream);
267 
268  // @}
269 
270  // bool is_connected(G &graph, V v) const;
271  #if 0
272  void contract_to_level(
273  G &graph,
274  int64_t level);
275  #endif
276 
277  #if 0
278  void dead_end_contraction(G &graph);
279  void remove_2_degree_vertices(G &graph);
280 
281 
282  void calculateDegrees(G &graph);
283 
284  void degreeMap(G &graph, std::ostringstream& dmap);
285 
286  void getGraphName(std::ostringstream& name, Contraction_type ctype);
287 
288  int64_t getGraph_string(G &graph, std::ostringstream& estring);
289 
290  void getRemovedE_string(G &graph, std::ostringstream& estring);
291 
292  void getRemovedV_string(std::ostringstream& vstring);
293 
294  void getPseudoE_string(std::ostringstream& pstring);
295 
296  typedef typename std::map<V, std::deque<Edge> > removed_V;
297  typedef typename std::map<V, std::deque<Edge> >::iterator removed_V_i;
298  typedef typename std::map<int64_t, std::pair<int64_t, int64_t> > psuedo_E;
299  typedef typename std::map<int64_t, std::pair<int64_t, int64_t> >::iterator psuedo_E_i;
300  typedef std::map< int, std::priority_queue<int64_t, std::vector<int64_t>, std::greater<int64_t> > > degree_to_V;
301  // typedef std::map< int, std::vector<int64_t> > degree_to_V;
302  typedef typename std::vector<V>::iterator Q_i;
303  #endif
304 
305  private:
306  int64_t last_edge_id;
307  // ! Used for storing the ids of all vertices of the graph
309  // ! Used for storing the ids of dead end vertices of the graph
311  // ! Used for storing the ids of vertices of the graph which are not contracted
313  // ! Used for storing the ids of vertices forbidden from contraction
315  #if 0
316  removed_V removedVertices;
317  psuedo_E pseudoEdges;
318  degree_to_V degree_to_V_map;
319  #endif
320  // set of dead_end_vertices;
321  // Identifiers<V> dead_end_vertices;
322 };
323 
324 
325 /******************** IMPLEMENTATION ******************/
326 template < class G >
327 void Pgr_contract< G >::disconnectVertex(G &graph, int64_t vertex_id) {
328  pgassert(graph.is_connected(vertex_id));
329  pgassert(is_dead_end(vertex_id));
330  graph.disconnect_vertex(vertex_id);
331  pgassert(!graph.is_connected(vertex_id));
332 }
333 
334 template < class G >
335 void Pgr_contract< G >::setForbiddenVertices(int64_t *forbidden_vertices,
336  size_t size_forbidden_vertices ) {
337  for (int64_t i = 0; i < size_forbidden_vertices; ++i) {
338  forbidden += forbidden_vertices[i];
339  }
340 }
341 
342 template <class G>
344  // Identifiers<int64_t> dead_end_vertices;
345  V_i vi;
346  for (vi = vertices(graph.graph).first; vi != vertices(graph.graph).second; ++vi) {
347  // debug << "Checking vertex " << graph.graph[(*vi)].id << '\n';
348  all += graph.graph[(*vi)].id;
349  }
350 }
351 
352 template <class G>
354  non_contracted = all - dead_end;
355 }
356 
357 template < class G >
359  EO_i out, out_end;
360  EI_i in, in_end;
361  V v;
362  Identifiers<int64_t> adjacent_vertices_set;
363  if (!graph.has_vertex(vertex_id)) {
364  return adjacent_vertices_set;
365  }
366  v = graph.get_V(vertex_id);
367  for (boost::tie(out, out_end) = out_edges(v, graph.graph);
368  out != out_end; ++out) {
369  adjacent_vertices_set += graph.graph[target(*out, graph.graph)].id;
370  }
371  for (boost::tie(in, in_end) = in_edges(v, graph.graph);
372  in != in_end; ++in) {
373  adjacent_vertices_set += graph.graph[source(*in, graph.graph)].id;
374  }
375  return adjacent_vertices_set;
376 }
377 
378 template <class G>
379 void Pgr_contract< G >::print_identifiers(std::ostringstream& stream, Identifiers<int64_t> identifiers) {
380  stream << identifiers << '\n';
381 }
382 
383 template <class G>
384 void Pgr_contract< G >::print_forbidden_vertices(std::ostringstream& stream) {
385  stream << forbidden << '\n';
386 }
387 
388 template <class G>
389 void Pgr_contract< G >::print_all_vertices(std::ostringstream& stream) {
390  stream << all << '\n';
391 }
392 
393 
394 template <class G>
395 void Pgr_contract< G >::print_non_contracted_vertices(std::ostringstream& stream) {
396  stream << non_contracted << '\n';
397 }
398 
399 template < class G >
400 bool Pgr_contract< G >::is_dead_end(G &graph, int64_t vertex_id) const {
401  // debug << "in_degree: " << graph.in_degree(vertex_id) << '\n';
402  // debug << "out_degree: " << graph.out_degree(vertex_id) << '\n';
403  V v;
404  if (!graph.has_vertex(vertex_id)) {
405  return false;
406  }
407  v = graph.get_V(vertex_id);
408  if (graph.out_degree(v) == 1 && graph.in_degree(v) == 0) return true;
409  if (graph.out_degree(v) == 0 && graph.in_degree(v) == 1) return true;
410  if (graph.out_degree(v) == 1 && graph.in_degree(v) == 1) {
411  int64_t incoming_edge_id, outgoing_edge_id;
412  EO_i out, out_end;
413  EI_i in, in_end;
414  for (boost::tie(out, out_end) = out_edges(v, graph.graph);
415  out != out_end; ++out) {
416  outgoing_edge_id = graph.graph[*out].id;
417  }
418  for (boost::tie(in, in_end) = in_edges(v, graph.graph);
419  in != in_end; ++in) {
420  incoming_edge_id = graph.graph[*in].id;
421  }
422  if (incoming_edge_id == outgoing_edge_id)
423  return true;
424  return false;
425  }
426  return false;
427 }
428 
429 template <class G>
431  V_i vi;
432  for (vi = vertices(graph.graph).first; vi != vertices(graph.graph).second; ++vi) {
433  // debug << "Checking vertex " << graph.graph[(*vi)].id << '\n';
434  if (is_dead_end(graph, graph.graph[(*vi)].id)) {
435  // debug << "Adding " << graph.graph[(*vi)].id << "to dead end" << '\n';
436  dead_end += graph.graph[(*vi)].id;
437  }
438  }
439 }
440 
441 template <class G>
442 void Pgr_contract< G >::print_dead_end_vertices(std::ostringstream& stream) {
443  stream << dead_end << '\n';
444 }
void print_identifiers(std::ostringstream &stream, Identifiers< int64_t > identifiers)
Writes the string form of identifier class to the stream
void calculateVertices(G &graph, std::ostringstream &debug)
void calculateVertices(G &graph, std::ostringstream &debug)
void getDeadEndSet(G &graph)
Stores ids of dead end vertices of the graph in a set Stores them in the set dead_end_vertices ...
Identifiers< int64_t > forbidden
void print_dead_end_vertices(std::ostringstream &stream)
Writes the string form of dead end vertices to the stream
void doContraction(G &graph, std::ostringstream &debug)
Identifiers< int64_t > non_contracted
bool is_dead_end(G &graph, int64_t vertex_id) const
Checks whether a vertex is a dead end vertex.
void setForbiddenVertices(int64_t *forbidden_vertices, size_t size_forbidden_vertices)
Stores the ids of those vertices forbidden from contraction in a set Stores them in the set forbidden...
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)
Identifiers< int64_t > getAdjacentVertices(G &graph, int64_t vertex_id)
Returns a set of ids of all those vertices adjacent to vertex with id vertex_id Calls the disconnect_...
void getNonContractedVertices()
Stores the set of ids of those vertices which are not contracted Stores them in the set non_contracte...
Identifiers< int64_t > dead_end
void print_forbidden_vertices(std::ostringstream &stream)
Writes the string form of forbidden vertices to the stream
bool is_valid_contraction_number(int number)
void getAllVertices(G &graph)
Stores ids of all the vertices of the graph in a set Stores them in the set all_vertices ...
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:81
int64_t last_edge_id
void doContraction(G &graph, std::ostringstream &debug)
void print_non_contracted_vertices(std::ostringstream &stream)
Writes the string form of non contracted vertices to the stream
void perform_deadEnd(G &graph, Identifiers< int64_t > forbidden_vertices, std::ostringstream &debug)
void setForbiddenVertices(G &graph, Identifiers< int64_t > forbidden_vertices, std::ostringstream &debug)
void perform_linear(G &graph, Identifiers< int64_t > &forbidden_vertices, std::ostringstream &debug)
void print_all_vertices(std::ostringstream &stream)
Writes the string form of all vertices to the stream
void setForbiddenVertices(G &graph, Identifiers< int64_t > forbidden_vertices, std::ostringstream &debug)
void disconnectVertex(G &graph, int64_t vertex_id)
Disconnects all incoming and outgoing edges from the vertex Calls the disconnect_vertex function of t...
Identifiers< int64_t > all