PGROUTING  2.4
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
pgr_contract.hpp
Go to the documentation of this file.
1 /*PGR-GNU*****************************************************************
2 File: pgr_contract.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_CONTRACT_HPP_
31 #define SRC_CONTRACTION_SRC_PGR_CONTRACT_HPP_
32 #pragma once
33 
34 #include <deque>
35 #include <vector>
36 #include "../../common/src/pgr_assert.h"
37 
41 
42 namespace pgrouting {
43 namespace contraction {
44 
45 
46 template < class G >
47 class Pgr_contract {
48  typedef typename G::V V;
49 
50 
51  void perform_deadEnd(G &graph,
52  Identifiers<V> forbidden_vertices,
53  std::ostringstream& debug) {
54  Pgr_deadend<G> deadendContractor;
55  debug << "Setting forbidden_vertices";
56  deadendContractor.setForbiddenVertices(forbidden_vertices);
57 
58  deadendContractor.calculateVertices(graph);
59  try {
60  deadendContractor.doContraction(graph);
61  }
62  catch ( ... ) {
63  debug << "Caught unknown exception!\n";
64  }
65  }
66 
67 
68  void perform_linear(G &graph,
69  Identifiers<V>& forbidden_vertices,
70  std::ostringstream& debug) {
71  std::ostringstream linear_debug;
72  Pgr_linear<G> linearContractor;
73  linearContractor.setForbiddenVertices(forbidden_vertices);
74  linearContractor.calculateVertices(graph);
75  try {
76  linearContractor.doContraction(graph);
77  }
78  catch ( ... ) {
79  linear_debug << "Caught unknown exception!\n";
80  }
81  debug << linear_debug.str().c_str() << "\n";
82  }
83 
84 
85  public:
87  G &graph,
88  Identifiers<V> forbidden_vertices,
89  std::vector<int64_t> contraction_order,
90  int64_t max_cycles,
91  Identifiers<int64_t> &remaining_vertices,
92  std::vector<pgrouting::CH_edge> &shortcut_edges,
93  std::ostringstream& debug) {
94  std::deque<int64_t> contract_order;
95  // push -1 to indicate the start of the queue
96  contract_order.push_back(-1);
97  contract_order.insert(
98  contract_order.end(),
99  contraction_order.begin(), contraction_order.end());
100  for (int64_t i = 0; i < max_cycles; ++i) {
101  int64_t front = contract_order.front();
102  debug << "Starting cycle " << i+1 << "\n";
103  contract_order.pop_front();
104  contract_order.push_back(front);
105  front = contract_order.front();
106  while (front != -1) {
107  switch (front) {
108  case -1:
109  debug << "Finished cycle " << i+1 << std::endl;
110  break;
111  default:
112  debug << "contraction "<< front
113  << " asked" << std::endl;
114  if (front == 1) {
115 #ifndef NDEBUG
116  debug << "Graph before dead end contraction"
117  << std::endl;
118  graph.print_graph(debug);
119  debug << "Performing dead end contraction"
120  << std::endl;
121 #endif
122  perform_deadEnd(graph, forbidden_vertices, debug);
123 #ifndef NDEBUG
124  debug << "Graph after dead end contraction"
125  << std::endl;
126  graph.print_graph(debug);
127 #endif
128  } else if (front == 2) {
129 #ifndef NDEBUG
130  debug << "Graph before linear contraction"
131  << std::endl;
132  graph.print_graph(debug);
133  debug << "Performing linear contraction"
134  << std::endl;
135 #endif
136  perform_linear(graph, forbidden_vertices, debug);
137 #ifndef NDEBUG
138  debug << "Graph after linear contraction"
139  << std::endl;
140  graph.print_graph(debug);
141 #endif
142  }
143  contract_order.pop_front();
144  contract_order.push_back(front);
145  front = contract_order.front();
146  }
147  }
148  }
149  remaining_vertices = graph.get_changed_vertices();
150  debug << "Printing shortcuts\n";
151  for (auto shortcut : graph.shortcuts) {
152  debug << shortcut;
153  shortcut_edges.push_back(shortcut);
154  }
155  }
156 
157 #if 0
158  bool is_valid_contraction_number(int number) {
159  switch (number) {
160  case -2:
161  return false;
162  break;
163  case -1:
164  return false;
165  break;
166  case 0:
167  return true;
168  break;
169  case 1:
170  return true;
171  break;
172  default:
173  return false;
174  break;
175  }
176  }
177 #endif
178 };
179 
180 } // namespace contraction
181 } // namespace pgrouting
182 
183 #endif // SRC_CONTRACTION_SRC_PGR_CONTRACT_HPP_
void perform_deadEnd(G &graph, Identifiers< V > forbidden_vertices, std::ostringstream &debug)
void setForbiddenVertices(Identifiers< V > forbidden_vertices)
void setForbiddenVertices(Identifiers< V > forbidden_vertices)
Pgr_contract(G &graph, Identifiers< V > forbidden_vertices, std::vector< int64_t > contraction_order, int64_t max_cycles, Identifiers< int64_t > &remaining_vertices, std::vector< pgrouting::CH_edge > &shortcut_edges, std::ostringstream &debug)
void perform_linear(G &graph, Identifiers< V > &forbidden_vertices, std::ostringstream &debug)