PGROUTING  2.5
pgr_linearContraction.hpp
Go to the documentation of this file.
1 /*PGR-GNU*****************************************************************
2 File: pgr_linear.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 
30 #ifndef SRC_CONTRACTION_SRC_PGR_LINEARCONTRACTION_HPP_
31 #define SRC_CONTRACTION_SRC_PGR_LINEARCONTRACTION_HPP_
32 #pragma once
33 
34 
35 #include <queue>
36 #include <functional>
37 #include <vector>
38 
40 
41 
42 namespace pgrouting {
43 namespace contraction {
44 
45 template < class G >
46 class Pgr_linear {
47  private:
48  typedef typename G::V V;
49  typedef typename G::E E;
50  typedef typename G::V_i V_i;
51  typedef typename G::E_i E_i;
52  typedef typename G::EO_i EO_i;
53  typedef typename G::EI_i EI_i;
54  typedef typename G::degree_size_type degree_size_type;
55 
56 
57  public:
60  Identifiers<V> forbidden_vertices);
61  void calculateVertices(G &graph);
62  void doContraction(G &graph);
63 
64  private:
65  int64_t get_next_id() {
66  return --last_edge_id;
67  }
68 
69  bool is_linear(G &graph, V v);
70  void add_if_linear(G &graph, V v);
71  void add_edge_pair(V vertex, int64_t &incoming_eid,
72  int64_t &outgoing_eid);
73  void add_shortcut(G &graph, V vertex,
74  E incoming_edge,
75  E outgoing_edge);
76  void add_shortcut(G &graph,
77  pgrouting::CH_edge &shortcut);
78 
79  private:
82 
83  int64_t last_edge_id;
84  std::ostringstream debug;
85 };
86 
87 /*************** IMPLEMENTTION **************/
88 
89 template < class G >
90 void
92  Identifiers<V> forbidden_vertices) {
93  debug << "Setting forbidden vertices\n";
94  forbiddenVertices = forbidden_vertices;
95 }
96 
97 
98 template < class G >
99 bool Pgr_linear<G>::is_linear(G &graph, V v) {
100  degree_size_type in_degree, out_degree;
101  in_degree = graph.in_degree(v);
102  out_degree = graph.out_degree(v);
103  Identifiers<V> adjacent_vertices = graph.find_adjacent_vertices(v);
104  if (adjacent_vertices.size() == 2) {
105  if (in_degree > 0 && out_degree > 0) {
106  debug << graph.graph[v].id << " is linear " << std::endl;
107  return true;
108  }
109  }
110  debug << graph.graph[v].id << " is not linear " << std::endl;
111  return false;
112 }
113 
114 template < class G >
116  debug << "Calculating vertices\n";
117  V_i vi;
118  for (vi = vertices(graph.graph).first;
119  vi != vertices(graph.graph).second;
120  ++vi) {
121  debug << "Checking vertex " << graph.graph[(*vi)].id << '\n';
122  if (is_linear(graph, *vi)) {
123  linearVertices += (*vi);
124  }
125  }
127 }
128 
129 
130 
131 template < class G >
133  std::ostringstream contraction_debug;
134  contraction_debug << "Performing contraction\n";
135  std::priority_queue<V, std::vector<V>, std::greater<V> > linearPriority;
136  for (const auto linearVertex : linearVertices) {
137  linearPriority.push(linearVertex);
138  }
139  contraction_debug << "Linear vertices" << std::endl;
140  for (const auto v : linearVertices) {
141  contraction_debug << graph[v].id << ", ";
142  }
143  contraction_debug << std::endl;
144  while (!linearPriority.empty()) {
145  V current_vertex = linearPriority.top();
146  linearPriority.pop();
147  if (!is_linear(graph, current_vertex)) {
148  linearVertices -= current_vertex;
149  continue;
150  }
151  Identifiers<V> adjacent_vertices =
152  graph.find_adjacent_vertices(current_vertex);
153  pgassert(adjacent_vertices.size() == 2);
154 
155  V vertex_1 = adjacent_vertices.front();
156  adjacent_vertices.pop_front();
157  V vertex_2 = adjacent_vertices.front();
158  adjacent_vertices.pop_front();
159 
160  contraction_debug << "Adjacent vertices\n";
161  contraction_debug << graph[vertex_1].id
162  << ", " << graph[vertex_2].id
163  << std::endl;
164 
165  if (graph.m_gType == DIRECTED) {
166  if (graph.out_degree_to_vertex(vertex_1, current_vertex) > 0 &&
167  graph.in_degree_from_vertex(vertex_2, current_vertex) > 0) {
168  E e1 = graph.get_min_cost_edge(vertex_1,
169  current_vertex);
170  E e2 = graph.get_min_cost_edge(current_vertex,
171  vertex_2);
172  add_shortcut(graph, current_vertex, e1, e2);
173  }
174 
175  if (graph.out_degree_to_vertex(vertex_2, current_vertex) > 0 &&
176  graph.in_degree_from_vertex(vertex_1, current_vertex) > 0) {
177  E e1 = graph.get_min_cost_edge(vertex_2,
178  current_vertex);
179  E e2 = graph.get_min_cost_edge(current_vertex,
180  vertex_1);
181  add_shortcut(graph, current_vertex, e1, e2);
182  }
183  } else if (graph.m_gType == UNDIRECTED) {
184  if (graph.out_degree_to_vertex(vertex_1, current_vertex) > 0 &&
185  graph.in_degree_from_vertex(vertex_2, current_vertex) > 0) {
186  contraction_debug << "UNDIRECTED graph before contraction\n";
187  graph.print_graph(contraction_debug);
188  E e1 = graph.get_min_cost_edge(vertex_1,
189  current_vertex);
190  E e2 = graph.get_min_cost_edge(current_vertex,
191  vertex_2);
192  add_shortcut(graph, current_vertex, e1, e2);
193  }
194  }
195 
196  graph.disconnect_vertex(current_vertex);
197  linearVertices -= current_vertex;
198  if (is_linear(graph, vertex_1)
199  && !forbiddenVertices.has(vertex_1)) {
200  linearPriority.push(vertex_1);
201  linearVertices += vertex_1;
202  }
203  if (is_linear(graph, vertex_2)
204  && !forbiddenVertices.has(vertex_2)) {
205  linearPriority.push(vertex_2);
206  linearVertices += vertex_2;
207  }
208  }
209  debug << contraction_debug.str().c_str() << "\n";
210 }
211 
212 
225 template < class G >
226 void
228  G &graph, V vertex,
229  E incoming_edge,
230  E outgoing_edge) {
231  pgassert(incoming_edge != outgoing_edge);
232 
233  auto a = graph.adjacent(vertex, incoming_edge);
234  auto c = graph.adjacent(vertex, outgoing_edge);
235  pgassert(a != vertex);
236  pgassert(a != c);
237  pgassert(vertex != c);
238 
239  if (graph.is_undirected()) {
240  Identifiers<V> adjacent_vertices = graph.find_adjacent_vertices(vertex);
241 
242  V vertex_1 = adjacent_vertices.front();
243  adjacent_vertices.pop_front();
244  V vertex_2 = adjacent_vertices.front();
245  adjacent_vertices.pop_front();
246 
247  E shortcut_E;
248  CH_edge shortcut(get_next_id(), graph[vertex_1].id,
249  graph[vertex_2].id,
250  graph[incoming_edge].cost + graph[outgoing_edge].cost);
251  shortcut.add_contracted_vertex(graph[vertex], vertex);
252  shortcut.add_contracted_edge_vertices(graph[incoming_edge]);
253  shortcut.add_contracted_edge_vertices(graph[outgoing_edge]);
254  debug << "Adding shortcut\n";
255  debug << shortcut;
256  graph.add_shortcut(shortcut);
257  debug << "Added shortcut\n";
258  } else {
259  CH_edge shortcut(
260  get_next_id(),
261  graph[a].id,
262  graph[c].id,
263  graph[incoming_edge].cost + graph[outgoing_edge].cost);
264  shortcut.add_contracted_vertex(graph[vertex], vertex);
265  shortcut.add_contracted_edge_vertices(graph[incoming_edge]);
266  shortcut.add_contracted_edge_vertices(graph[outgoing_edge]);
267  debug << "Adding shortcut\n";
268  debug << shortcut;
269  graph.add_shortcut(shortcut);
270  debug << "Added shortcut\n";
271  }
272 }
273 template < class G >
275  pgrouting::CH_edge &shortcut) {
276  graph.add_shortcut(shortcut);
277 }
278 
279 } // namespace contraction
280 } // namespace pgrouting
281 
282 #endif // SRC_CONTRACTION_SRC_PGR_LINEARCONTRACTION_HPP_
bool has(const T other) const
true ids() has element
Definition: identifiers.hpp:97
void add_shortcut(G &graph, V vertex, E incoming_edge, E outgoing_edge)
add edges(shortuct) to the graph during contraction
void pop_front()
Definition: identifiers.hpp:82
void setForbiddenVertices(Identifiers< V > forbidden_vertices)
void add_contracted_edge_vertices(CH_edge &e)
Definition: ch_edge.cpp:61
void add_contracted_vertex(CH_vertex &v, int64_t vid)
Definition: ch_edge.cpp:54
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:81
void add_edge_pair(V vertex, int64_t &incoming_eid, int64_t &outgoing_eid)
size_t size() const
Definition: identifiers.hpp:77
Book keeping class for swapping orders between vehicles.
Definition: basic_edge.cpp:28
T front() const
Definition: identifiers.hpp:79
void add_if_linear(G &graph, V v)