PGROUTING  2.4
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
pgr_deadEndContraction.hpp
Go to the documentation of this file.
1 /*PGR-GNU*****************************************************************
2 File: pgr_deadend.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 #ifndef SRC_CONTRACTION_SRC_PGR_DEADENDCONTRACTION_HPP_
31 #define SRC_CONTRACTION_SRC_PGR_DEADENDCONTRACTION_HPP_
32 #pragma once
33 
34 
35 #include <queue>
36 #include <functional>
37 #include <vector>
38 #include "../../common/src/identifiers.hpp"
39 
40 namespace pgrouting {
41 namespace contraction {
42 
43 template < class G >
44 class Pgr_deadend {
45  private:
46  typedef typename G::V V;
47  typedef typename G::E E;
48 
49  public:
51  Identifiers<V> forbidden_vertices);
52 
53  void calculateVertices(G &graph);
55  bool is_dead_end(G &graph, V v);
56  void add_if_dead_end(G &graph, V v);
57  void doContraction(G &graph);
58 
59  private:
62  std::ostringstream debug;
63 };
64 
65 /******* IMPLEMENTATION ************/
66 template < class G >
67 void
69  Identifiers<V> forbidden_vertices) {
70 #ifndef NDEBUG
71  debug << "Setting forbidden vertices\n";
72 #endif
73  forbiddenVertices = forbidden_vertices;
74 }
75 
76 
77 template < class G >
79  debug << "Calculating vertices\n";
80 
81  for (auto vi = vertices(graph.graph).first;
82  vi != vertices(graph.graph).second;
83  ++vi) {
84 #ifndef NDEBUG
85  debug << "Checking vertex " << graph[(*vi)].id << '\n';
86 #endif
87  if (is_dead_end(graph, *vi)) {
88 #ifndef NDEBUG
89  debug << "Adding " << graph[(*vi)].id << " to dead end" << '\n';
90 #endif
91  deadendVertices += (*vi);
92  }
93  }
94  deadendVertices -= forbiddenVertices;
95 }
96 
97 template < class G >
98 bool Pgr_deadend<G>::is_dead_end(G &graph, V v) {
99 #ifndef NDEBUG
100  debug << "Is dead end: " << graph.graph[v].id << "?\n";
101 #endif
102 
103  if (forbiddenVertices.has(v)) {
109  return false;
110  }
111 
112  if (graph.is_undirected()) {
137  Identifiers<V> adjacent_vertices = graph.find_adjacent_vertices(v);
138  if (adjacent_vertices.size() == 1) {
139  return true;
140  }
141  return false;
142  }
143 
144  pgassert(graph.is_directed());
145  /*
146  * directed graph
147  *
148  * is dead end when:
149  * (2) one incoming edge, no outgoing edge (dead end)
150  * (3) one outgoing edge, one incoming edge
151  * and both are from/to the same vertex
152  * (4) many incoming edges
153  * and no outgoing edges
154  * (5) many outgoing edges TODO but all go to same vertex
155  * and no incoming edges
156  *
157  * NOT dead end when:
158  * (3) one outgoing edge, one incoming edge
159  * and both from/to different vertex
160  *
161  * note: when contracting case 4 & 5, the vertex has to be
162  * part of all the adjacent vertices
163  */
164 
165  if (graph.in_degree(v) == 0 && graph.out_degree(v) == 1) {
190  return true;
191  }
192 
193  if (graph.in_degree(v) == 1 && graph.out_degree(v) == 0) {
216  return true;
217  }
218 
219  if (graph.out_degree(v) == 1 && graph.in_degree(v) == 1) {
244  auto out_e = *(out_edges(v, graph.graph).first);
245  auto in_e = *(in_edges(v, graph.graph).first);
246 
247  auto out_v = graph.is_source(v, out_e) ?
248  graph.target(out_e) : graph.source(out_e);
249  auto in_v = graph.is_source(v, in_e) ?
250  graph.target(in_e) : graph.source(in_e);
251 
252  if (out_v == in_v) {
253  return true;
254  }
255  return false;
256  }
257 
258  if (graph.in_degree(v) > 0 && graph.out_degree(v) == 0) {
284  return true;
285  }
286 
287  if (graph.in_degree(v) > 0 && graph.out_degree(v) > 0) {
316  auto adjacent_vertices = graph.find_adjacent_vertices(v);
317  if (adjacent_vertices.size() == 1) {
318  return true;
319  }
320  }
321  debug << "Is Not Dead End\n";
322  return false;
323 }
324 
325 template < class G >
326 void
328  if (is_dead_end(graph, v)) {
329  deadendVertices += v;
330  }
331 }
332 
333 template < class G >
334 void
336 #ifndef NDEBUG
337  debug << "Performing contraction\n";
338 #endif
339  std::priority_queue<V, std::vector<V>, std::greater<V> > deadendPriority;
340 
341  for (V deadendVertex : deadendVertices) {
342  deadendPriority.push(deadendVertex);
343  }
344 
345  while (!deadendPriority.empty()) {
346  V current_vertex = deadendPriority.top();
347  deadendPriority.pop();
348 
349  if (!is_dead_end(graph, current_vertex)) {
350  continue;
351  }
352 
353  Identifiers<V> adjacent_vertices =
354  graph.find_adjacent_vertices(current_vertex);
355 
356  for (auto adjacent_vertex : adjacent_vertices) {
357 #ifndef NDEBUG
358  debug << "Contracting current vertex "
359  << graph[current_vertex].id << std::endl;
360 #endif
361  graph[adjacent_vertex].add_contracted_vertex(
362  graph[current_vertex], current_vertex);
363 
364 #ifndef NDEBUG
365  debug << "Adding contracted vertices of the edge\n";
366 #endif
367  auto o_edges = out_edges(current_vertex, graph.graph);
368  for (auto out = o_edges.first;
369  out != o_edges.second;
370  ++out) {
371  debug << graph.graph[*out];
372  graph.add_contracted_edge_vertices(
373  adjacent_vertex, graph[*out]);
374  }
375  auto i_edges = in_edges(current_vertex, graph.graph);
376  for (auto in = i_edges.first;
377  in != i_edges.second; ++in) {
378 #ifndef NDEBUG
379  debug << graph.graph[*in];
380 #endif
381  graph.add_contracted_edge_vertices(adjacent_vertex, graph[*in]);
382  }
383 #ifndef NDEBUG
384  debug << "Current Vertex:\n";
385  debug << graph[current_vertex];
386  debug << "Adjacent Vertex:\n";
387  debug << graph[adjacent_vertex];
388 #endif
389  graph.disconnect_vertex(current_vertex);
390  deadendVertices -= current_vertex;
391 #ifndef NDEBUG
392  debug << "Adjacent vertex dead_end?: "
393  << is_dead_end(graph, adjacent_vertex)
394  << std::endl;
395 #endif
396  if (is_dead_end(graph, adjacent_vertex)
397  && !forbiddenVertices.has(adjacent_vertex)) {
398  deadendVertices += adjacent_vertex;
399  deadendPriority.push(adjacent_vertex);
400  }
401  }
402  }
403 }
404 
405 } // namespace contraction
406 } // namespace pgrouting
407 
408 #endif // SRC_CONTRACTION_SRC_PGR_DEADENDCONTRACTION_HPP_
void setForbiddenVertices(Identifiers< V > forbidden_vertices)
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:81
size_t size() const
Definition: identifiers.hpp:56
bool is_dead_end(G &graph, V v)
true when v is a dead end