PGROUTING  2.4
 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_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 
39 #include "../../common/src/identifiers.hpp"
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  }
126  linearVertices -= forbiddenVertices;
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  V vertex_1 = adjacent_vertices[0];
155  V vertex_2 = adjacent_vertices[1];
156  contraction_debug << "Adjacent vertices\n";
157  contraction_debug << graph[vertex_1].id
158  << ", " << graph[vertex_2].id
159  << std::endl;
160 
161  if (graph.m_gType == DIRECTED) {
162  if (graph.out_degree_to_vertex(vertex_1, current_vertex) > 0 &&
163  graph.in_degree_from_vertex(vertex_2, current_vertex) > 0) {
164  E e1 = graph.get_min_cost_edge(vertex_1,
165  current_vertex);
166  E e2 = graph.get_min_cost_edge(current_vertex,
167  vertex_2);
168  add_shortcut(graph, current_vertex, e1, e2);
169  }
170 
171  if (graph.out_degree_to_vertex(vertex_2, current_vertex) > 0 &&
172  graph.in_degree_from_vertex(vertex_1, current_vertex) > 0) {
173  E e1 = graph.get_min_cost_edge(vertex_2,
174  current_vertex);
175  E e2 = graph.get_min_cost_edge(current_vertex,
176  vertex_1);
177  add_shortcut(graph, current_vertex, e1, e2);
178  }
179  } else if (graph.m_gType == UNDIRECTED) {
180  if (graph.out_degree_to_vertex(vertex_1, current_vertex) > 0 &&
181  graph.in_degree_from_vertex(vertex_2, current_vertex) > 0) {
182  contraction_debug << "UNDIRECTED graph before contraction\n";
183  graph.print_graph(contraction_debug);
184  E e1 = graph.get_min_cost_edge(vertex_1,
185  current_vertex);
186  E e2 = graph.get_min_cost_edge(current_vertex,
187  vertex_2);
188  add_shortcut(graph, current_vertex, e1, e2);
189  }
190  }
191 
192  graph.disconnect_vertex(current_vertex);
193  linearVertices -= current_vertex;
194  if (is_linear(graph, vertex_1)
195  && !forbiddenVertices.has(vertex_1)) {
196  linearPriority.push(vertex_1);
197  linearVertices += vertex_1;
198  }
199  if (is_linear(graph, vertex_2)
200  && !forbiddenVertices.has(vertex_2)) {
201  linearPriority.push(vertex_2);
202  linearVertices += vertex_2;
203  }
204  }
205  debug << contraction_debug.str().c_str() << "\n";
206 }
207 
208 
221 template < class G >
222 void
224  G &graph, V vertex,
225  E incoming_edge,
226  E outgoing_edge) {
227  pgassert(incoming_edge != outgoing_edge);
228 
229  auto a = graph.adjacent(vertex, incoming_edge);
230  auto c = graph.adjacent(vertex, outgoing_edge);
231  pgassert(a != vertex);
232  pgassert(a != c);
233  pgassert(vertex != c);
234 
235  if (graph.is_undirected()) {
236  Identifiers<V> adjacent_vertices = graph.find_adjacent_vertices(vertex);
237  V vertex_1 = adjacent_vertices[0];
238  V vertex_2 = adjacent_vertices[1];
239  E shortcut_E;
240  CH_edge shortcut(get_next_id(), graph[vertex_1].id,
241  graph[vertex_2].id,
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.add_shortcut(shortcut);
249  debug << "Added shortcut\n";
250  } else {
251  CH_edge shortcut(
252  get_next_id(),
253  graph[a].id,
254  graph[c].id,
255  graph[incoming_edge].cost + graph[outgoing_edge].cost);
256  shortcut.add_contracted_vertex(graph[vertex], vertex);
257  shortcut.add_contracted_edge_vertices(graph[incoming_edge]);
258  shortcut.add_contracted_edge_vertices(graph[outgoing_edge]);
259  debug << "Adding shortcut\n";
260  debug << shortcut;
261  graph.add_shortcut(shortcut);
262  debug << "Added shortcut\n";
263  }
264 }
265 template < class G >
267  pgrouting::CH_edge &shortcut) {
268  graph.add_shortcut(shortcut);
269 }
270 
271 } // namespace contraction
272 } // namespace pgrouting
273 
274 #endif // SRC_CONTRACTION_SRC_PGR_LINEARCONTRACTION_HPP_
void add_shortcut(G &graph, V vertex, E incoming_edge, E outgoing_edge)
add edges(shortuct) to the graph during contraction
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:56
void add_if_linear(G &graph, V v)