PGROUTING  3.2
pgrouting::yen::Pgr_turnRestrictedPath< G > Class Template Reference

#include "pgr_turnRestrictedPath.hpp"

Inheritance diagram for pgrouting::yen::Pgr_turnRestrictedPath< G >:
Collaboration diagram for pgrouting::yen::Pgr_turnRestrictedPath< G >:

Classes

struct  found_goals
 
class  Myvisitor
 

Public Member Functions

 Pgr_turnRestrictedPath ()=default
 
std::string get_error () const
 get_error More...
 
std::string get_log () const
 get_log More...
 
std::string get_notice () const
 get_notice More...
 
bool has_error () const
 get_error More...
 
std::deque< PathturnRestrictedPath (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)
 
std::deque< PathYen (G &graph, int64_t start_vertex, int64_t end_vertex, size_t K)
 
std::deque< PathYen (G &graph, int64_t start_vertex, int64_t end_vertex, size_t K, bool heap_paths)
 

Public Attributes

std::ostringstream error
 Stores the error information. More...
 
std::ostringstream log
 Stores the hint information. More...
 
std::ostringstream notice
 Stores the notice information. More...
 

Protected Member Functions

void executeYen (G &graph)
 the actual algorithm More...
 
Auxiliary function for yen's algorithm
Path getFirstSolution (G &graph)
 Performs the first Dijkstra of the algorithm. More...
 
void doNextCycle (G &graph)
 Performs the next cycle of the algorithm. More...
 
void removeVertices (G &graph, const Path &subpath)
 stores in subPath the first i elements of path More...
 
std::deque< Pathget_results ()
 
Auxiliary function for yen's algorithm
Path getFirstSolution (G &graph)
 Performs the first Dijkstra of the algorithm. More...
 
void doNextCycle (G &graph)
 Performs the next cycle of the algorithm. More...
 
void removeVertices (G &graph, const Path &subpath)
 stores in subPath the first i elements of path More...
 
std::deque< Pathget_results ()
 

Protected Attributes

members
V v_source
 source descriptor More...
 
V v_target
 target descriptor More...
 
int64_t m_start
 source id More...
 
int64_t m_end
 target id More...
 
size_t m_K
 
Path curr_result_path
 storage for the current result More...
 
pSet m_ResultSet
 ordered set of shortest paths More...
 
pSet m_Heap
 the heap More...
 
Visitorm_vis
 

Private Types

typedef std::set< Path, compPathsLesspSet
 
typedef G::V V
 

Private Member Functions

void clear ()
 containers cleanup More...
 
std::deque< Pathget_results (std::deque< Path > &paths)
 
std::deque< Pathinf_cost_on_restriction (std::deque< Path > &paths)
 sets an inf value on agg_cost on the vertex/edge where the restriction begins More...
 

Private Attributes

bool m_heap_paths
 
std::vector< pgrouting::trsp::Rulem_restrictions
 
pSet m_solutions
 
bool m_stop_on_first
 
bool m_strict
 

Detailed Description

template<typename G>
class pgrouting::yen::Pgr_turnRestrictedPath< G >

Definition at line 52 of file pgr_turnRestrictedPath.hpp.

Member Typedef Documentation

◆ pSet

template<typename G >
typedef std::set<Path, compPathsLess> pgrouting::yen::Pgr_turnRestrictedPath< G >::pSet
private

Definition at line 53 of file pgr_turnRestrictedPath.hpp.

◆ V

template<class G >
typedef G::V pgrouting::yen::Pgr_ksp< G >::V
privateinherited

Definition at line 48 of file pgr_ksp.hpp.

Constructor & Destructor Documentation

◆ Pgr_turnRestrictedPath()

template<typename G >
pgrouting::yen::Pgr_turnRestrictedPath< G >::Pgr_turnRestrictedPath ( )
default

Member Function Documentation

◆ clear()

template<typename G >
void pgrouting::yen::Pgr_turnRestrictedPath< G >::clear ( )
inlineprivate

containers cleanup

empties containers

Definition at line 234 of file pgr_turnRestrictedPath.hpp.

234  {
236  m_solutions.clear();
237  }

References pgrouting::yen::Pgr_ksp< G >::clear(), and pgrouting::yen::Pgr_turnRestrictedPath< G >::m_solutions.

Referenced by pgrouting::yen::Pgr_turnRestrictedPath< G >::Yen().

◆ doNextCycle()

template<class G >
void pgrouting::yen::Pgr_ksp< G >::doNextCycle ( G &  graph)
inlineprotectedinherited

Performs the next cycle of the algorithm.

Definition at line 163 of file pgr_ksp.hpp.

163  {
164  for (unsigned int i = 0; i < curr_result_path.size(); ++i) {
165  int64_t spurNodeId = curr_result_path[i].node;
166 
167  auto rootPath = curr_result_path.getSubpath(i);
168 
169  for (const auto &path : m_ResultSet) {
170  if (path.isEqual(rootPath)) {
171  if (path.size() > i + 1) {
172  graph.disconnect_edge(path[i].node, // from
173  path[i + 1].node); // to
174  }
175  }
176  }
177 
178  removeVertices(graph, rootPath);
179 
180  Pgr_dijkstra< G > fn_dijkstra;
181  auto spurPath = fn_dijkstra.dijkstra(graph, spurNodeId, m_end);
182 
183  if (spurPath.size() > 0) {
184  rootPath.appendPath(spurPath);
185  m_Heap.insert(rootPath);
186  m_vis->on_insert_to_heap(rootPath);
187  }
188 
189  graph.restore_graph();
190  }
191  }

References Path::appendPath(), pgrouting::yen::Pgr_ksp< G >::curr_result_path, pgrouting::Pgr_dijkstra< G >::dijkstra(), Path::getSubpath(), pgrouting::yen::Pgr_ksp< G >::m_end, pgrouting::yen::Pgr_ksp< G >::m_Heap, pgrouting::yen::Pgr_ksp< G >::m_ResultSet, pgrouting::yen::Pgr_ksp< G >::m_vis, pgrouting::yen::Pgr_ksp< G >::Visitor::on_insert_to_heap(), pgrouting::yen::Pgr_ksp< G >::removeVertices(), and Path::size().

Referenced by pgrouting::yen::Pgr_ksp< G >::executeYen().

◆ executeYen()

◆ get_error()

std::string pgrouting::Pgr_messages::get_error ( ) const
inherited

get_error

Returns
the current contents of the log and clears the log

Definition at line 53 of file pgr_messages.cpp.

53  {
54  auto str = error.str();
55  return str;
56 }

References pgrouting::Pgr_messages::error.

Referenced by do_pgr_many_withPointsDD(), do_pgr_pickDeliver(), do_pgr_pickDeliverEuclidean(), do_pgr_withPoints(), do_pgr_withPointsKsp(), and pgrouting::vrp::Pgr_pickDeliver::Pgr_pickDeliver().

◆ get_log()

std::string pgrouting::Pgr_messages::get_log ( ) const
inherited

◆ get_notice()

std::string pgrouting::Pgr_messages::get_notice ( ) const
inherited

get_notice

Returns
the current contents of the log and clears the log

Definition at line 42 of file pgr_messages.cpp.

42  {
43  auto str = notice.str();
44  return str;
45 }

References pgrouting::Pgr_messages::notice.

◆ get_results() [1/2]

template<class G >
std::deque<Path> pgrouting::yen::Pgr_ksp< G >::get_results ( )
inlineprotectedinherited

Definition at line 200 of file pgr_ksp.hpp.

200  {
201  if (this->m_ResultSet.empty()) {
202  return std::deque<Path>();
203  }
204 
205  std::deque<Path> paths(m_ResultSet.begin(), m_ResultSet.end());
206 
207  if (m_heap_paths && !m_Heap.empty()) {
208  paths.insert(paths.end(), m_Heap.begin(), m_Heap.end());
209  }
210  pgassert(!paths.empty());
211 
212  std::sort(paths.begin(), paths.end(), compPathsLess());
213 
214  return paths;
215  }

References pgrouting::yen::Pgr_ksp< G >::m_Heap, pgrouting::yen::Pgr_ksp< G >::m_heap_paths, pgrouting::yen::Pgr_ksp< G >::m_ResultSet, and pgassert.

Referenced by pgrouting::yen::Pgr_ksp< G >::Yen(), and pgrouting::yen::Pgr_turnRestrictedPath< G >::Yen().

◆ get_results() [2/2]

template<typename G >
std::deque<Path> pgrouting::yen::Pgr_turnRestrictedPath< G >::get_results ( std::deque< Path > &  paths)
inlineprivate

Definition at line 201 of file pgr_turnRestrictedPath.hpp.

202  {
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  }

References pgrouting::yen::Pgr_turnRestrictedPath< G >::inf_cost_on_restriction(), pgrouting::yen::Pgr_turnRestrictedPath< G >::m_heap_paths, and pgrouting::yen::Pgr_turnRestrictedPath< G >::m_strict.

◆ getFirstSolution()

template<class G >
Path pgrouting::yen::Pgr_ksp< G >::getFirstSolution ( G &  graph)
inlineprotectedinherited

Performs the first Dijkstra of the algorithm.

Definition at line 148 of file pgr_ksp.hpp.

148  {
149  Path path;
150 
151  Pgr_dijkstra< G > fn_dijkstra;
152  path = fn_dijkstra.dijkstra(graph, m_start, m_end);
153  path.recalculate_agg_cost();
154 
155  if (path.empty()) return path;
156  m_ResultSet.insert(path);
157  return path;
158  }

References pgrouting::Pgr_dijkstra< G >::dijkstra(), Path::empty(), pgrouting::yen::Pgr_ksp< G >::m_end, pgrouting::yen::Pgr_ksp< G >::m_ResultSet, pgrouting::yen::Pgr_ksp< G >::m_start, and Path::recalculate_agg_cost().

Referenced by pgrouting::yen::Pgr_ksp< G >::executeYen().

◆ has_error()

bool pgrouting::Pgr_messages::has_error ( ) const
inherited

get_error

Returns
the current contents of the log and clears the log

Definition at line 48 of file pgr_messages.cpp.

48  {
49  return !error.str().empty();
50 }

References pgrouting::Pgr_messages::error.

Referenced by do_pgr_many_withPointsDD(), do_pgr_withPoints(), and do_pgr_withPointsKsp().

◆ inf_cost_on_restriction()

template<typename G >
std::deque<Path> pgrouting::yen::Pgr_turnRestrictedPath< G >::inf_cost_on_restriction ( std::deque< Path > &  paths)
inlineprivate

sets an inf value on agg_cost on the vertex/edge where the restriction begins

Parameters
[in]pathsthat is being analized

Definition at line 245 of file pgr_turnRestrictedPath.hpp.

245  {
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  }

References pgrouting::yen::Pgr_turnRestrictedPath< G >::m_restrictions.

Referenced by pgrouting::yen::Pgr_turnRestrictedPath< G >::get_results().

◆ removeVertices()

template<class G >
void pgrouting::yen::Pgr_ksp< G >::removeVertices ( G &  graph,
const Path subpath 
)
inlineprotectedinherited

stores in subPath the first i elements of path

Definition at line 195 of file pgr_ksp.hpp.

195  {
196  for (const auto &e : subpath)
197  graph.disconnect_vertex(e.node);
198  }

Referenced by pgrouting::yen::Pgr_ksp< G >::doNextCycle().

◆ turnRestrictedPath()

template<typename G >
std::deque<Path> pgrouting::yen::Pgr_turnRestrictedPath< G >::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 
)
inline

◆ Yen() [1/2]

template<typename G >
std::deque<Path> pgrouting::yen::Pgr_turnRestrictedPath< G >::Yen ( G &  graph,
int64_t  start_vertex,
int64_t  end_vertex,
size_t  K 
)
inline
Parameters
[in]graph
[in]start_vertexoriginal id of vertex
[in]end_vertexoriginal id of vertex
[in]Kwhen k=0 stop at first path without turn restriction when k > 0 do K cycles and return best path without turn restriction

Definition at line 135 of file pgr_turnRestrictedPath.hpp.

138  {
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  }

References pgrouting::yen::Pgr_turnRestrictedPath< G >::clear(), pgrouting::yen::Pgr_ksp< G >::executeYen(), pgrouting::yen::Pgr_ksp< G >::get_results(), pgrouting::yen::Pgr_ksp< G >::m_end, pgrouting::yen::Pgr_ksp< G >::m_K, pgrouting::yen::Pgr_turnRestrictedPath< G >::m_restrictions, pgrouting::yen::Pgr_turnRestrictedPath< G >::m_solutions, pgrouting::yen::Pgr_ksp< G >::m_start, pgrouting::yen::Pgr_turnRestrictedPath< G >::m_stop_on_first, pgrouting::yen::Pgr_ksp< G >::m_vis, pgassert, pgrouting::yen::Pgr_ksp< G >::v_source, and pgrouting::yen::Pgr_ksp< G >::v_target.

Referenced by pgrouting::yen::Pgr_turnRestrictedPath< G >::turnRestrictedPath().

◆ Yen() [2/2]

template<class G >
std::deque<Path> pgrouting::yen::Pgr_ksp< G >::Yen ( G &  graph,
int64_t  start_vertex,
int64_t  end_vertex,
size_t  K,
bool  heap_paths 
)
inlineinherited

Definition at line 61 of file pgr_ksp.hpp.

66  {
67  /*
68  * No path: already in destination
69  */
70  if ((start_vertex == end_vertex) || (K == 0)) {
71  return std::deque<Path>();
72  }
73 
74  /*
75  * no path: disconnected vertices
76  */
77  if (!graph.has_vertex(start_vertex)
78  || !graph.has_vertex(end_vertex)) {
79  return std::deque<Path>();
80  }
81 
82  /*
83  * clean up containers
84  */
85  clear();
86 
87 
88  v_source = graph.get_V(start_vertex);
89  v_target = graph.get_V(end_vertex);
90  m_start = start_vertex;
91  m_end = end_vertex;
92  m_K = K;
93  m_heap_paths = heap_paths;
94 
95 
96  executeYen(graph);
97 
98  auto paths = get_results();
99  if (!m_heap_paths && paths.size() > m_K) paths.resize(m_K);
100 
101  return paths;
102  }

References pgrouting::yen::Pgr_ksp< G >::clear(), pgrouting::yen::Pgr_ksp< G >::executeYen(), pgrouting::yen::Pgr_ksp< G >::get_results(), pgrouting::yen::Pgr_ksp< G >::m_end, pgrouting::yen::Pgr_ksp< G >::m_heap_paths, pgrouting::yen::Pgr_ksp< G >::m_K, pgrouting::yen::Pgr_ksp< G >::m_start, pgrouting::yen::Pgr_ksp< G >::v_source, and pgrouting::yen::Pgr_ksp< G >::v_target.

Referenced by do_pgr_ksp(), and do_pgr_withPointsKsp().

Member Data Documentation

◆ curr_result_path

template<class G >
Path pgrouting::yen::Pgr_ksp< G >::curr_result_path
protectedinherited

storage for the current result

Definition at line 229 of file pgr_ksp.hpp.

Referenced by pgrouting::yen::Pgr_ksp< G >::doNextCycle(), and pgrouting::yen::Pgr_ksp< G >::executeYen().

◆ error

◆ log

◆ m_end

◆ m_Heap

◆ m_heap_paths

◆ m_K

template<class G >
size_t pgrouting::yen::Pgr_ksp< G >::m_K
protectedinherited

◆ m_restrictions

◆ m_ResultSet

◆ m_solutions

◆ m_start

template<class G >
int64_t pgrouting::yen::Pgr_ksp< G >::m_start
protectedinherited

◆ m_stop_on_first

◆ m_strict

◆ m_vis

◆ notice

std::ostringstream pgrouting::Pgr_messages::notice
mutableinherited

Stores the notice information.

Definition at line 83 of file pgr_messages.h.

Referenced by pgrouting::Pgr_messages::clear(), and pgrouting::Pgr_messages::get_notice().

◆ v_source

template<class G >
V pgrouting::yen::Pgr_ksp< G >::v_source
protectedinherited

source descriptor

Definition at line 222 of file pgr_ksp.hpp.

Referenced by pgrouting::yen::Pgr_ksp< G >::Yen(), and pgrouting::yen::Pgr_turnRestrictedPath< G >::Yen().

◆ v_target

template<class G >
V pgrouting::yen::Pgr_ksp< G >::v_target
protectedinherited

target descriptor

Definition at line 223 of file pgr_ksp.hpp.

Referenced by pgrouting::yen::Pgr_ksp< G >::Yen(), and pgrouting::yen::Pgr_turnRestrictedPath< G >::Yen().


The documentation for this class was generated from the following file:
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_ksp::Visitor::on_insert_to_heap
virtual void on_insert_to_heap(const Path) const
Definition: pgr_ksp.hpp:119
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
Path::empty
bool empty() const
Definition: basePath_SSEC.hpp:72
Path::getSubpath
Path getSubpath(unsigned int j) const
Definition: basePath_SSEC.cpp:141
pgrouting::yen::Pgr_ksp::m_ResultSet
pSet m_ResultSet
ordered set of shortest paths
Definition: pgr_ksp.hpp:231
pgrouting::Pgr_messages::error
std::ostringstream error
Stores the error information.
Definition: pgr_messages.h:85
pgrouting::Pgr_messages::log
std::ostringstream log
Stores the hint information.
Definition: pgr_messages.h:81
pgassert
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:94
pgrouting::yen::Pgr_turnRestrictedPath::m_strict
bool m_strict
Definition: pgr_turnRestrictedPath.hpp:258
pgrouting::yen::Pgr_ksp::getFirstSolution
Path getFirstSolution(G &graph)
Performs the first Dijkstra of the algorithm.
Definition: pgr_ksp.hpp:148
pgrouting::yen::Pgr_turnRestrictedPath::m_solutions
pSet m_solutions
Definition: pgr_turnRestrictedPath.hpp:259
pgrouting::yen::Pgr_turnRestrictedPath::m_heap_paths
bool m_heap_paths
Definition: pgr_turnRestrictedPath.hpp:261
pgrouting::yen::Pgr_ksp::m_heap_paths
bool m_heap_paths
Definition: pgr_ksp.hpp:227
pgrouting::yen::Pgr_ksp::v_target
V v_target
target descriptor
Definition: pgr_ksp.hpp:223
pgrouting::yen::Pgr_ksp::executeYen
void executeYen(G &graph)
the actual algorithm
Definition: pgr_ksp.hpp:126
pgrouting::yen::Pgr_ksp::m_K
size_t m_K
Definition: pgr_ksp.hpp:226
pgrouting::yen::Pgr_ksp::curr_result_path
Path curr_result_path
storage for the current result
Definition: pgr_ksp.hpp:229
pgrouting::yen::Pgr_ksp::removeVertices
void removeVertices(G &graph, const Path &subpath)
stores in subPath the first i elements of path
Definition: pgr_ksp.hpp:195
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
Path::size
size_t size() const
Definition: basePath_SSEC.hpp:71
pgrouting::Pgr_messages::notice
std::ostringstream notice
Stores the notice information.
Definition: pgr_messages.h:83
pgrouting::yen::Pgr_ksp::Visitor::on_insert_first_solution
virtual void on_insert_first_solution(const Path) const
Definition: pgr_ksp.hpp:115
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_ksp::doNextCycle
void doNextCycle(G &graph)
Performs the next cycle of the algorithm.
Definition: pgr_ksp.hpp:163
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
Path::recalculate_agg_cost
void recalculate_agg_cost()
Definition: basePath_SSEC.cpp:77