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_linearContraction.hpp
Go to the documentation of this file.
1 /*PGR-GNU*****************************************************************
2 File: pgr_contractionGraph.c
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 #pragma once
30 #ifdef __MINGW32__
31 #include <winsock2.h>
32 #include <windows.h>
33 #ifdef open
34 #undef open
35 #endif
36 #endif
37 #include <functional>
38 #include <queue>
39 #include <vector>
40 #include "../../common/src/identifiers.hpp"
41 namespace pgrouting {
42 template < class G >
44  public:
45  typedef typename G::V V;
46  typedef typename G::E E;
47  typedef typename G::V_i V_i;
48  typedef typename G::E_i E_i;
49  typedef typename G::EO_i EO_i;
50  typedef typename G::EI_i EI_i;
51  typedef typename G::degree_size_type degree_size_type;
53  void setForbiddenVertices(G &graph,
54  Identifiers<int64_t> forbidden_vertices,
55  std::ostringstream& debug);
56  void setForbiddenVertices(G &graph, int64_t *forbidden_vertices,
57  size_t size_forbidden_vertices,
58  std::ostringstream& debug);
59  void calculateVertices(G &graph,
60  std::ostringstream& debug);
61  void doContraction(G &graph,
62  std::ostringstream& debug);
63 
64  private:
67  int64_t last_edge_id;
68  bool is_linear(G &graph, V v,
69  std::ostringstream& debug);
70  void add_if_linear(G &graph, V v,
71  std::ostringstream& debug);
72  void add_edge_pair(V vertex, int64_t &incoming_eid,
73  int64_t &outgoing_eid,
74  std::ostringstream& debug);
75  void add_shortcut(G &graph, V vertex,
76  E incoming_edge,
77  E outgoing_edge,
78  std::ostringstream& debug);
79  void add_shortcut(G &graph,
81  std::ostringstream& debug);
82  int64_t& get_next_id() {
83  return --last_edge_id;
84  }
85 };
86 
87  template < class G >
89  Identifiers<int64_t> forbidden_vertices,
90  std::ostringstream& debug) {
91  debug << "Setting forbidden vertices\n";
92  for (auto forbiddenVertex : forbidden_vertices) {
93  forbiddenVertices += graph.get_V(forbiddenVertex);
94  }
95  }
96 
97  template < class G >
99  int64_t *forbidden_vertices,
100  size_t size_forbidden_vertices,
101  std::ostringstream& debug) {
102  debug << "Setting forbidden vertices\n";
103  for (int64_t i = 0; i < size_forbidden_vertices; ++i) {
104  forbiddenVertices += graph.get_V(forbidden_vertices[i]);
105  }
106  }
107 
108  template < class G >
110  std::ostringstream& debug) {
111  degree_size_type in_degree, out_degree;
112  in_degree = graph.in_degree(v);
113  out_degree = graph.out_degree(v);
114  Identifiers<V> adjacent_vertices = graph.find_adjacent_vertices(v);
115  if (adjacent_vertices.size() == 2) {
116  if (in_degree > 0 && out_degree > 0) {
117  debug << graph.graph[v].id << " is linear " << std::endl;
118  return true;
119  }
120  }
121  debug << graph.graph[v].id << " is not linear " << std::endl;
122  return false;
123  }
124 
125  template < class G >
127  std::ostringstream& debug) {
128  debug << "Calculating vertices\n";
129  V_i vi;
130  for (vi = vertices(graph.graph).first; vi != vertices(graph.graph).second; ++vi) {
131  debug << "Checking vertex " << graph.graph[(*vi)].id << '\n';
132  if (is_linear(graph, *vi, debug)) {
133  // debug << "Adding " << graph.graph[(*vi)].id << " to linear" << '\n';
134  linearVertices += (*vi);
135  }
136  }
137  linearVertices -= forbiddenVertices;
138  }
139 
140 
141 
142  template < class G >
144  std::ostringstream& debug) {
145  std::ostringstream contraction_debug;
146  contraction_debug << "Performing contraction\n";
147  std::priority_queue<V, std::vector<V>, std::greater<V> > linearPriority;
148  for (V linearVertex : linearVertices) {
149  linearPriority.push(linearVertex);
150  }
151  contraction_debug << "Linear vertices" << std::endl;
152  for (auto v : linearVertices) {
153  contraction_debug << graph[v].id << ", ";
154  }
155  contraction_debug << std::endl;
156  while (!linearPriority.empty()) {
157  V current_vertex = linearPriority.top();
158  linearPriority.pop();
159  if (!is_linear(graph, current_vertex, debug)) {
160  linearVertices -= current_vertex;
161  continue;
162  }
163  Identifiers<V> adjacent_vertices = graph.find_adjacent_vertices(current_vertex);
164  pgassert(adjacent_vertices.size() == 2);
165  V vertex_1 = adjacent_vertices[0];
166  V vertex_2 = adjacent_vertices[1];
167  contraction_debug << "Adjacent vertices\n";
168  contraction_debug << graph[vertex_1].id << ", " << graph[vertex_2].id << std::endl;
169 
170  if (graph.m_gType == DIRECTED) {
171  if (graph.out_degree_to_vertex(vertex_1, current_vertex) > 0
172  && graph.in_degree_from_vertex(vertex_2, current_vertex) > 0) {
173  E e1 = graph.get_min_cost_edge(vertex_1,
174  current_vertex);
175  E e2 = graph.get_min_cost_edge(current_vertex,
176  vertex_2);
177  add_shortcut(graph, current_vertex, e1, e2, contraction_debug);
178  }
179 
180  if (graph.out_degree_to_vertex(vertex_2, current_vertex) > 0
181  && graph.in_degree_from_vertex(vertex_1, current_vertex) > 0) {
182  E e1 = graph.get_min_cost_edge(vertex_2,
183  current_vertex);
184  E e2 = graph.get_min_cost_edge(current_vertex,
185  vertex_1);
186  add_shortcut(graph, current_vertex, e1, e2, contraction_debug);
187  }
188  } else if (graph.m_gType == UNDIRECTED) {
189  if (graph.out_degree_to_vertex(vertex_1, current_vertex) > 0
190  && graph.in_degree_from_vertex(vertex_2, current_vertex) > 0) {
191  contraction_debug << "UNDIRECTED graph before contraction\n";
192  graph.print_graph(contraction_debug);
193  E e1 = graph.get_min_cost_edge(vertex_1,
194  current_vertex);
195  E e2 = graph.get_min_cost_edge(current_vertex,
196  vertex_2);
197  add_shortcut(graph, current_vertex, e1, e2, contraction_debug);
198  }
199  }
200 
201  graph.disconnect_vertex(contraction_debug, current_vertex);
202  linearVertices -= current_vertex;
203  if (is_linear(graph, vertex_1, debug)
204  && !forbiddenVertices.has(vertex_1)) {
205  linearPriority.push(vertex_1);
206  linearVertices += vertex_1;
207  }
208  if (is_linear(graph, vertex_2, debug)
209  && !forbiddenVertices.has(vertex_2)) {
210  linearPriority.push(vertex_2);
211  linearVertices += vertex_2;
212  }
213  }
214  debug << contraction_debug.str().c_str() << "\n";
215  }
216 
217 
218 
219  template < class G >
221  E incoming_edge,
222  E outgoing_edge,
223  std::ostringstream& debug) {
224  if (graph.m_gType == UNDIRECTED) {
225  Identifiers<V> adjacent_vertices = graph.find_adjacent_vertices(vertex);
226  V vertex_1 = adjacent_vertices[0];
227  V vertex_2 = adjacent_vertices[1];
228  E shortcut_E;
229  contraction::Edge shortcut(get_next_id(), graph[vertex_1].id,
230  graph[vertex_2].id,
231  graph[incoming_edge].cost + graph[outgoing_edge].cost);
232  shortcut.add_contracted_vertex(graph[vertex], vertex);
233  shortcut.add_contracted_edge_vertices(graph[incoming_edge]);
234  shortcut.add_contracted_edge_vertices(graph[outgoing_edge]);
235  debug << "Adding shortcut\n";
236  debug << shortcut;
237  graph.graph_add_shortcut(shortcut, debug);
238  debug << "Added shortcut\n";
239  } else if (graph.m_gType == DIRECTED) {
240  contraction::Edge shortcut(get_next_id(), graph[incoming_edge].source,
241  graph[outgoing_edge].target,
242  graph[incoming_edge].cost + graph[outgoing_edge].cost);
243  shortcut.add_contracted_vertex(graph[vertex], vertex);
244  shortcut.add_contracted_edge_vertices(graph[incoming_edge]);
245  shortcut.add_contracted_edge_vertices(graph[outgoing_edge]);
246  debug << "Adding shortcut\n";
247  debug << shortcut;
248  graph.graph_add_shortcut(shortcut, debug);
249  debug << "Added shortcut\n";
250  }
251  }
252  template < class G >
255  std::ostringstream& debug) {
256  graph.graph_add_shortcut(shortcut, debug);
257  }
258 
259 } // namespace pgrouting
void add_if_linear(G &graph, V v, std::ostringstream &debug)
void calculateVertices(G &graph, std::ostringstream &debug)
void add_edge_pair(V vertex, int64_t &incoming_eid, int64_t &outgoing_eid, std::ostringstream &debug)
void add_contracted_edge_vertices(Edge &e)
Definition: ch_edge.cpp:104
bool is_linear(G &graph, V v, std::ostringstream &debug)
void doContraction(G &graph, std::ostringstream &debug)
void add_shortcut(G &graph, V vertex, E incoming_edge, E outgoing_edge, std::ostringstream &debug)
void add_contracted_vertex(Vertex &v, int64_t vid)
Definition: ch_edge.cpp:95
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:81
size_t size() const
Definition: identifiers.hpp:49
void setForbiddenVertices(G &graph, Identifiers< int64_t > forbidden_vertices, std::ostringstream &debug)