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_deadEndContraction.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 
38 #include <queue>
39 #include <functional>
40 #include <vector>
41 #include "../../common/src/identifiers.hpp"
42 namespace pgrouting {
43 template < class G >
45  public:
46  typedef typename G::V V;
47  typedef typename G::E E;
48  typedef typename G::V_i V_i;
49  typedef typename G::E_i E_i;
50  typedef typename G::EO_i EO_i;
51  typedef typename G::EI_i EI_i;
52  void setForbiddenVertices(G &graph,
53  Identifiers<int64_t> forbidden_vertices,
54  std::ostringstream& debug);
55  void setForbiddenVertices(G &graph, int64_t *forbidden_vertices,
56  size_t size_forbidden_vertices,
57  std::ostringstream& debug);
58  void calculateVertices(G &graph,
59  std::ostringstream& debug);
60  bool is_dead_end(G &graph, V v,
61  std::ostringstream& debug);
62  void add_if_dead_end(G &graph, V v,
63  std::ostringstream& debug);
64  void doContraction(G &graph,
65  std::ostringstream& debug);
66 
67  private:
70 };
71 
72  template < class G >
74  Identifiers<int64_t> forbidden_vertices,
75  std::ostringstream& debug) {
76  debug << "Setting forbidden vertices\n";
77  for (auto forbiddenVertex : forbidden_vertices) {
78  forbiddenVertices += graph.get_V(forbiddenVertex);
79  }
80  }
81 
82  template < class G >
84  int64_t *forbidden_vertices,
85  size_t size_forbidden_vertices,
86  std::ostringstream& debug) {
87  debug << "Setting forbidden vertices\n";
88  for (int64_t i = 0; i < size_forbidden_vertices; ++i) {
89  forbiddenVertices += graph.get_V(forbidden_vertices[i]);
90  }
91  }
92 
93  template < class G >
95  std::ostringstream& debug) {
96  debug << "Calculating vertices\n";
97  V_i vi;
98  for (vi = vertices(graph.graph).first; vi != vertices(graph.graph).second; ++vi) {
99  debug << "Checking vertex " << graph.graph[(*vi)].id << '\n';
100  if (is_dead_end(graph, *vi, debug)) {
101  debug << "Adding " << graph.graph[(*vi)].id << " to dead end" << '\n';
102  deadendVertices += (*vi);
103  }
104  }
105  deadendVertices -= forbiddenVertices;
106  }
107 
108  template < class G >
110  std::ostringstream& debug) {
111  debug << "Is dead end: " << graph.graph[v].id << "?\n";
112  // debug << "in_degree: " << graph.in_degree(vertex_id) << '\n';
113  // debug << "out_degree: " << graph.out_degree(vertex_id) << '\n';
114  // if(graph.out_degree(v) == 1 && graph.in_degree(v) == 0) return true;
115  // if(graph.out_degree(v) == 0 && graph.in_degree(v) == 1) return true;
116  if (graph.m_gType == UNDIRECTED) {
117  /* the condition in case of undirected graph
118  is all incoming edges come from a single vertex
119  */
120  debug << "undirected\nAdjacent Vertices\n";
121  Identifiers<V> adjacent_vertices = graph.find_adjacent_vertices(v);
122  debug << adjacent_vertices;
123  // only one adjacent vertex
124  if (adjacent_vertices.size() == 1)
125  return true;
126  else
127  return false;
128  } else {
129  if (graph.out_degree(v) == 1 && graph.in_degree(v) == 1) {
130  int64_t incoming_edge_id = -1;
131  int64_t outgoing_edge_id = -2;
132  EO_i out, out_end;
133  EI_i in, in_end;
134  for (boost::tie(out, out_end) = out_edges(v, graph.graph);
135  out != out_end; ++out) {
136  outgoing_edge_id = graph.graph[*out].id;
137  }
138  for (boost::tie(in, in_end) = in_edges(v, graph.graph);
139  in != in_end; ++in) {
140  incoming_edge_id = graph.graph[*in].id;
141  }
142  if (incoming_edge_id == outgoing_edge_id) {
143  debug << "Yes\n";
144  return true;
145  }
146  debug << "No\n";
147  return false;
148  }
149  // additional cases
150  if (graph.out_degree(v) == 0 && graph.in_degree(v) > 0) {
151  return true;
152  }
153  /* dead start
154  if (graph.in_degree(v) == 0 && graph.out_degree(v) > 0) {
155  return true;
156  }
157  */
158  debug << "No\n";
159  return false;
160  }
161  return false;
162  }
163 
164  template < class G >
166  std::ostringstream& debug) {
167  debug << "Adding if dead end\n";
168  if (is_dead_end(graph, v, debug)) {
169  deadendVertices += v;
170  } else {
171  debug << "Not dead end\n";
172  }
173  }
174 
175  template < class G >
177  std::ostringstream& debug) {
178  debug << "Performing contraction\n";
179  std::priority_queue<V, std::vector<V>, std::greater<V> > deadendPriority;
180  for (V deadendVertex : deadendVertices) {
181  deadendPriority.push(deadendVertex);
182  }
183  // debug << "Dead end vertices" << std::endl;
184  // debug << deadendVertices;
185  while (!deadendPriority.empty()) {
186  V current_vertex = deadendPriority.top();
187  deadendPriority.pop();
188  if (!is_dead_end(graph, current_vertex, debug)) {
189  continue;
190  }
191  Identifiers<V> adjacent_vertices = graph.find_adjacent_vertices(current_vertex);
192  for (auto adjacent_vertex : adjacent_vertices) {
193  // debug << "Current Vertex: "<< graph[current_vertex].id << std::endl;
194  // debug << "Adjacent Vertex: "<< graph[adjacent_vertex].id << std::endl;
195  debug << "Contracting current vertex "<< graph[current_vertex].id << std::endl;
196  graph[adjacent_vertex].add_contracted_vertex(graph[current_vertex], current_vertex);
197  // Adding contracted vertices of the edge
198  EO_i out, out_end;
199  EI_i in, in_end;
200  debug << "Adding contracted vertices of the edge\n";
201  for (boost::tie(out, out_end) = out_edges(current_vertex, graph.graph);
202  out != out_end; ++out) {
203  debug << graph.graph[*out];
204  graph.add_contracted_edge_vertices(adjacent_vertex, graph.graph[*out]);
205  }
206  for (boost::tie(in, in_end) = in_edges(current_vertex, graph.graph);
207  in != in_end; ++in) {
208  debug << graph.graph[*in];
209  graph.add_contracted_edge_vertices(adjacent_vertex, graph.graph[*in]);
210  }
211  debug << "Current Vertex:\n";
212  debug << graph[current_vertex];
213  // debug << graph.graph[current_vertex].print_vertex(debug, graph.graph);
214  debug << "Adjacent Vertex:\n";
215  // debug << graph.graph[adjacent_vertex].print_vertex(debug, graph.graph);
216  debug << graph[adjacent_vertex];
217  graph.disconnect_vertex(debug, current_vertex);
218  deadendVertices -= current_vertex;
219  debug << "Adjacent vertex dead_end?: " << is_dead_end(graph, adjacent_vertex, debug) << std::endl;
220  if (is_dead_end(graph, adjacent_vertex, debug)
221  && !forbiddenVertices.has(adjacent_vertex)) {
222  deadendVertices += adjacent_vertex;
223  deadendPriority.push(adjacent_vertex);
224  }
225  }
226  }
227  }
228 
229 } // namespace pgrouting
void calculateVertices(G &graph, std::ostringstream &debug)
bool is_dead_end(G &graph, V v, std::ostringstream &debug)
void doContraction(G &graph, std::ostringstream &debug)
void add_if_dead_end(G &graph, V v, std::ostringstream &debug)
void setForbiddenVertices(G &graph, Identifiers< int64_t > forbidden_vertices, std::ostringstream &debug)