PGROUTING  3.2
pgr_turnRestrictedPath.hpp
Go to the documentation of this file.
1 /*PGR-GNU*****************************************************************
2 File: pgr_dijkstraTR.hpp
3 
4 Generated with Template by:
5 Copyright (c) 2015 pgRouting developers
7 
8 Function's developer:
9 Copyright (c) 2017 Vidhan Jain
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 #ifndef INCLUDE_YEN_PGR_TURNRESTRICTEDPATH_HPP_
30 #define INCLUDE_YEN_PGR_TURNRESTRICTEDPATH_HPP_
31 #pragma once
32 
33 #include "yen/pgr_ksp.hpp"
34 
35 #include <sstream>
36 #include <deque>
37 #include <vector>
38 #include <set>
39 #include <limits>
40 
41 #include "cpp_common/pgr_assert.h"
43 #include "cpp_common/compPaths.h"
45 #include "cpp_common/rule.h"
46 #include "c_types/line_graph_rt.h"
47 
48 namespace pgrouting {
49 namespace yen {
50 
51 template < typename G >
52 class Pgr_turnRestrictedPath : public Pgr_ksp< G > {
53  typedef std::set<Path, compPathsLess> pSet;
54 
55  public:
56  Pgr_turnRestrictedPath() = default;
57  struct found_goals{};
58  class Myvisitor : public Pgr_ksp<G>::Visitor {
59  public:
61  pSet &solutions,
62  std::vector<trsp::Rule> &restrictions,
63  bool stop_on_first):
64  m_stop_on_first(stop_on_first),
65  m_solutions(solutions),
66  m_restrictions(restrictions) {
67  }
68 
69  void on_insert_first_solution(const Path path) const {
70  if (path.empty()) return;
71  if (has_restriction(path)) return;
72 
73  m_solutions.insert(path);
74 
75  if (m_stop_on_first) throw found_goals();
76  }
77 
78  void on_insert_to_heap(const Path path) const {
79  if (path.empty()) return;
80  if (has_restriction(path)) return;
81 
82  m_solutions.insert(path);
83 
84  if (m_stop_on_first) {
85  throw found_goals();
86  }
87  }
88 
89  private:
90  bool has_restriction(const Path &path) const {
91  for (const auto &r : m_restrictions) {
92  if (path.has_restriction(r)) {
93  return true;
94  }
95  }
96 
97  return false;
98  }
99 
102  std::vector<trsp::Rule> &m_restrictions;
103  };
104 
105 
106  std::deque<Path> turnRestrictedPath(
107  G& graph,
108  const std::vector<pgrouting::trsp::Rule> &restrictions,
109  int64_t source,
110  int64_t target,
111  size_t k,
112  bool heap_paths,
113  bool stop_on_first,
114  bool strict) {
115  pgassert(m_restrictions.empty());
116  pgassert(this->m_Heap.empty());
117  pgassert(this->m_ResultSet.empty());
118 
119  m_stop_on_first = stop_on_first;
120  m_strict = strict;
121  m_restrictions = restrictions;
122  m_heap_paths = heap_paths;
123 
124  return Yen(graph, source, target, k);
125  }
126 
127 
135  std::deque<Path> Yen(G &graph,
136  int64_t start_vertex,
137  int64_t end_vertex,
138  size_t K) {
139  /*
140  * No path: already in destination
141  */
142  if (start_vertex == end_vertex) {
143  return std::deque<Path>();
144  }
145 
146  /*
147  * no path: disconnected vertices
148  */
149  if (!graph.has_vertex(start_vertex)
150  || !graph.has_vertex(end_vertex)) {
151  return std::deque<Path>();
152  }
153 
154  /*
155  * clean up containers
156  */
157  clear();
158 
159  this->v_source = graph.get_V(start_vertex);
160  this->v_target = graph.get_V(end_vertex);
161  this->m_start = start_vertex;
162  this->m_end = end_vertex;
163  this->m_K = K;
165  delete this->m_vis;
166  this->m_vis = new Myvisitor(
167  m_solutions,
170 
171 
172 
173  try {
175  } catch(found_goals &) {
176  pgassert(!m_solutions.empty());
177  std::deque<Path> solutions(m_solutions.begin(), m_solutions.end());
178  return solutions;
179  } catch (boost::exception const& ex) {
180  (void)ex;
181  throw;
182  } catch (std::exception &e) {
183  (void)e;
184  throw;
185  } catch (...) {
186  throw;
187  }
188 
189 
190  if (!m_solutions.empty()) {
191  std::deque<Path> solutions(m_solutions.begin(), m_solutions.end());
192  return solutions;
193  }
194 
195  auto solutions = Pgr_ksp<G>::get_results();
196 
197  return get_results(solutions);
198  }
199 
200  private:
201  std::deque<Path> get_results(
202  std::deque<Path> &paths) {
203  if (paths.empty()) return paths;
204  if (m_strict) return std::deque<Path>();
205 
206  paths = inf_cost_on_restriction(paths);
207 
208  std::stable_sort(paths.begin(), paths.end(),
209  [](const Path &left, const Path &right) -> bool {
210  return (left.countInfinityCost() < right.countInfinityCost());
211  });
212 
213  auto count = paths.begin()->countInfinityCost();
214 
215 
216  if (m_heap_paths) return paths;
217 
218  paths.erase(
219  std::remove_if(
220  paths.begin(), paths.end(),
221  [&count](const Path &p){
222  return count != p.countInfinityCost();
223  }),
224  paths.end());
225 
226  return paths;
227  }
228 
229 
234  void clear() {
236  m_solutions.clear();
237  }
238 
239 
240 
245  std::deque<Path> inf_cost_on_restriction(std::deque<Path> &paths) {
246  if (paths.empty()) return paths;
247  for (auto &p : paths) {
248  for (const auto &r : m_restrictions) {
249  p = p.inf_cost_on_restriction(r);
250  }
251  }
252  return paths;
253  }
254 
255 
256  private:
257  std::vector<pgrouting::trsp::Rule> m_restrictions;
258  bool m_strict;
262 };
263 
264 } // namespace yen
265 } // namespace pgrouting
266 
267 
268 
269 #endif // INCLUDE_YEN_PGR_TURNRESTRICTEDPATH_HPP_
pgr_ksp.hpp
pgrouting::yen::Pgr_ksp::m_vis
Visitor * m_vis
Definition: pgr_ksp.hpp:234
pgrouting::yen::Pgr_turnRestrictedPath::clear
void clear()
containers cleanup
Definition: pgr_turnRestrictedPath.hpp:234
Path
Definition: basePath_SSEC.hpp:47
pgrouting::yen::Pgr_turnRestrictedPath::Myvisitor::Myvisitor
Myvisitor(pSet &solutions, std::vector< trsp::Rule > &restrictions, bool stop_on_first)
Definition: pgr_turnRestrictedPath.hpp:60
pgrouting::yen::Pgr_turnRestrictedPath::Myvisitor::m_solutions
pSet & m_solutions
Definition: pgr_turnRestrictedPath.hpp:101
pgr_messages.h
pgrouting::yen::Pgr_ksp::clear
void clear()
Definition: pgr_ksp.hpp:104
pgrouting::yen::Pgr_ksp::m_start
int64_t m_start
source id
Definition: pgr_ksp.hpp:224
pgrouting::yen::Pgr_ksp::get_results
std::deque< Path > get_results()
Definition: pgr_ksp.hpp:200
pgrouting::yen::Pgr_turnRestrictedPath::pSet
std::set< Path, compPathsLess > pSet
Definition: pgr_turnRestrictedPath.hpp:53
pgrouting::yen::Pgr_turnRestrictedPath::Myvisitor::m_restrictions
std::vector< trsp::Rule > & m_restrictions
Definition: pgr_turnRestrictedPath.hpp:102
Path::empty
bool empty() const
Definition: basePath_SSEC.hpp:72
pgrouting::yen::Pgr_turnRestrictedPath::Myvisitor
Definition: pgr_turnRestrictedPath.hpp:58
pgrouting::yen::Pgr_ksp::m_ResultSet
pSet m_ResultSet
ordered set of shortest paths
Definition: pgr_ksp.hpp:231
pgrouting::yen::Pgr_turnRestrictedPath
Definition: pgr_turnRestrictedPath.hpp:52
pgassert
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:94
pgrouting::yen::Pgr_turnRestrictedPath::Pgr_turnRestrictedPath
Pgr_turnRestrictedPath()=default
pgrouting::yen::Pgr_turnRestrictedPath::m_strict
bool m_strict
Definition: pgr_turnRestrictedPath.hpp:258
pgrouting::yen::Pgr_turnRestrictedPath::get_results
std::deque< Path > get_results(std::deque< Path > &paths)
Definition: pgr_turnRestrictedPath.hpp:201
pgrouting::yen::Pgr_turnRestrictedPath::m_solutions
pSet m_solutions
Definition: pgr_turnRestrictedPath.hpp:259
compPaths.h
pgrouting::yen::Pgr_turnRestrictedPath::m_heap_paths
bool m_heap_paths
Definition: pgr_turnRestrictedPath.hpp:261
Path::has_restriction
bool has_restriction(const pgrouting::trsp::Rule &rule) const
Definition: basePath_SSEC.cpp:100
pgrouting::yen::Pgr_ksp::pSet
std::set< Path, compPathsLess > pSet
Definition: pgr_ksp.hpp:49
pgrouting::yen::Pgr_turnRestrictedPath::found_goals
Definition: pgr_turnRestrictedPath.hpp:57
pgrouting::yen::Pgr_ksp::v_target
V v_target
target descriptor
Definition: pgr_ksp.hpp:223
pgrouting::yen::Pgr_ksp
Definition: pgr_ksp.hpp:47
rule.h
pgrouting::yen::Pgr_ksp::executeYen
void executeYen(G &graph)
the actual algorithm
Definition: pgr_ksp.hpp:126
pgr_assert.h
An assert functionality that uses C++ throw().
pgrouting::yen::Pgr_turnRestrictedPath::Myvisitor::on_insert_first_solution
void on_insert_first_solution(const Path path) const
Definition: pgr_turnRestrictedPath.hpp:69
pgrouting::yen::Pgr_ksp::m_K
size_t m_K
Definition: pgr_ksp.hpp:226
line_graph_rt.h
pgrouting::yen::Pgr_ksp::m_end
int64_t m_end
target id
Definition: pgr_ksp.hpp:225
pgrouting::yen::Pgr_turnRestrictedPath::m_stop_on_first
bool m_stop_on_first
Definition: pgr_turnRestrictedPath.hpp:260
pgrouting::yen::Pgr_turnRestrictedPath::turnRestrictedPath
std::deque< Path > turnRestrictedPath(G &graph, const std::vector< pgrouting::trsp::Rule > &restrictions, int64_t source, int64_t target, size_t k, bool heap_paths, bool stop_on_first, bool strict)
Definition: pgr_turnRestrictedPath.hpp:106
pgrouting::yen::Pgr_ksp::Visitor
Definition: pgr_ksp.hpp:111
pgrouting::yen::Pgr_turnRestrictedPath::Myvisitor::m_stop_on_first
bool m_stop_on_first
Definition: pgr_turnRestrictedPath.hpp:100
pgrouting::alphashape::G
graph::Pgr_base_graph< BG, XY_vertex, Basic_edge > G
Definition: pgr_alphaShape.h:56
pgrouting::yen::Pgr_turnRestrictedPath::Myvisitor::on_insert_to_heap
void on_insert_to_heap(const Path path) const
Definition: pgr_turnRestrictedPath.hpp:78
pgrouting::yen::Pgr_ksp::v_source
V v_source
source descriptor
Definition: pgr_ksp.hpp:222
pgrouting::yen::Pgr_turnRestrictedPath::m_restrictions
std::vector< pgrouting::trsp::Rule > m_restrictions
Definition: pgr_turnRestrictedPath.hpp:257
pgrouting::yen::Pgr_turnRestrictedPath::Myvisitor::has_restriction
bool has_restriction(const Path &path) const
Definition: pgr_turnRestrictedPath.hpp:90
pgrouting
Book keeping class for swapping orders between vehicles.
Definition: pgr_alphaShape.cpp:56
pgrouting::yen::Pgr_turnRestrictedPath::Yen
std::deque< Path > Yen(G &graph, int64_t start_vertex, int64_t end_vertex, size_t K)
Definition: pgr_turnRestrictedPath.hpp:135
pgrouting::yen::Pgr_ksp::m_Heap
pSet m_Heap
the heap
Definition: pgr_ksp.hpp:232
pgrouting::yen::Pgr_turnRestrictedPath::inf_cost_on_restriction
std::deque< Path > inf_cost_on_restriction(std::deque< Path > &paths)
sets an inf value on agg_cost on the vertex/edge where the restriction begins
Definition: pgr_turnRestrictedPath.hpp:245
basePath_SSEC.hpp