PGROUTING  3.2
Public Member Functions | Private Types | Private Attributes | Friends | List of all members
Path Class Reference

#include "basePath_SSEC.hpp"

Collaboration diagram for Path:
Collaboration graph
[legend]

Public Member Functions

 Path ()
 
template<typename G >
 Path (const G &graph, const Path &original, bool only_cost)
 
template<typename G , typename V >
 Path (const G &graph, const V v_source, const V v_target, const std::vector< V > &predecessors, const std::vector< double > &distances, bool only_cost, bool normal=true)
 
 Path (const Path &)=default
 
template<typename G , typename V >
 Path (G &graph, int64_t source, double distance, const std::vector< V > &predecessors, const std::vector< double > &distances)
 
template<typename G , typename V >
 Path (G &graph, V v_source, double distance, const std::vector< V > &predecessors, const std::vector< double > &distances)
 
 Path (int64_t s_id, int64_t e_id)
 
void append (const Path &other)
 Path: 2 -> 9 seq node edge cost agg_cost 0 2 4 1 0 1 5 8 1 1 2 6 9 1 2 3 9 -1 0 3 Path: 9 -> 3 seq node edge cost agg_cost 0 9 16 1 0 1 4 3 1 1 2 3 -1 0 2 Path: 2 -> 3 seq node edge cost agg_cost 0 2 4 1 0 1 5 8 1 1 2 6 9 1 2 3 9 16 1 3 4 4 3 1 4 5 3 -1 0 5. More...
 
void appendPath (const Path &o_path)
 
Path_t & back ()
 
const Path_t & back () const
 
pthIt begin ()
 
ConstpthIt begin () const
 
void clear ()
 
template<typename G , typename V >
void complete_path (const G &graph, const V v_source, const V v_target, const std::vector< V > &predecessors, const std::vector< double > &distances, bool normal)
 constructs a path based on results More...
 
size_t countInfinityCost () const
 
bool empty () const
 
void empty_path (unsigned int d_vertex)
 
pthIt end ()
 
ConstpthIt end () const
 
int64_t end_id () const
 
void end_id (int64_t value)
 
void erase (pthIt pos)
 
ConstpthIt find_restriction (const pgrouting::trsp::Rule &rule) const
 get the iterator of the path where the (restriction) rule starts More...
 
Path_t & front ()
 
const Path_t & front () const
 
void generate_postgres_data (General_path_element_t **postgres_data, size_t &sequence) const
 
void get_pg_dd_path (General_path_element_t **ret_path, size_t &sequence) const
 
void get_pg_ksp_path (General_path_element_t **ret_path, size_t &sequence, int routeId) const
 
void get_pg_turn_restricted_path (General_path_element_t **ret_path, size_t &sequence, int routeId) const
 
Path getSubpath (unsigned int j) const
 
bool has_restriction (const pgrouting::trsp::Rule &rule) const
 
Path inf_cost_on_restriction (const pgrouting::trsp::Rule &rule)
 
bool isEqual (const Path &subpath) const
 
Path_t & operator[] (size_t i)
 
const Path_t & operator[] (size_t i) const
 
void push_back (Path_t data)
 
void push_front (int64_t d_vertex, int64_t d_edge, double d_cost, double d_tot_cost)
 
void push_front (Path_t data)
 
void recalculate_agg_cost ()
 
Path & renumber_vertices (int64_t value)
 
void reverse ()
 
Path_t set_data (int64_t d_from, int64_t d_to, int64_t d_vertex, int64_t d_edge, double d_cost, double d_tot_cost)
 
size_t size () const
 
void sort_by_node_agg_cost ()
 Sorts a path by node, aggcost ascending. More...
 
int64_t start_id () const
 
void start_id (int64_t value)
 
double tot_cost () const
 

Private Types

typedef std::deque< Path_t >::const_iterator ConstpthIt
 
typedef std::deque< Path_t >::iterator pthIt
 

Private Attributes

int64_t m_end_id
 
int64_t m_start_id
 
double m_tot_cost
 
std::deque< Path_t > path
 

Friends

size_t collapse_paths (General_path_element_t **ret_path, const std::deque< Path > &paths)
 
size_t count_tuples (const std::deque< Path > &paths)
 counts the tuples to be returned More...
 
void equi_cost (std::deque< Path > &paths)
 discards common vertices with greater agg_cost More...
 
std::ostream & operator<< (std::ostream &log, const Path &p)
 

Detailed Description

Definition at line 47 of file basePath_SSEC.hpp.

Member Typedef Documentation

◆ ConstpthIt

typedef std::deque< Path_t >::const_iterator Path::ConstpthIt
private

Definition at line 49 of file basePath_SSEC.hpp.

◆ pthIt

typedef std::deque< Path_t >::iterator Path::pthIt
private

Definition at line 48 of file basePath_SSEC.hpp.

Constructor & Destructor Documentation

◆ Path() [1/7]

Path::Path ( )
inline

Definition at line 58 of file basePath_SSEC.hpp.

58  : m_start_id(0), m_end_id(0), m_tot_cost(0)
59  {}

◆ Path() [2/7]

Path::Path ( int64_t  s_id,
int64_t  e_id 
)
inline

Definition at line 60 of file basePath_SSEC.hpp.

61  : m_start_id(s_id), m_end_id(e_id), m_tot_cost(0)
62  {}

◆ Path() [3/7]

Path::Path ( const Path &  )
default

◆ Path() [4/7]

template<typename G , typename V >
Path::Path ( G &  graph,
int64_t  source,
double  distance,
const std::vector< V > &  predecessors,
const std::vector< double > &  distances 
)
inline

Definition at line 162 of file basePath_SSEC.hpp.

167  :
168  m_start_id(source),
169  m_end_id(source) {
170  for (V i = 0; i < distances.size(); ++i) {
171  if (distances[i] <= distance) {
172  auto cost = distances[i] - distances[predecessors[i]];
173  auto edge_id = graph.get_edge_id(predecessors[i], i, cost);
174  push_back(
175  {graph[i].id,
176  edge_id, cost,
177  distances[i]});
178  }
179  }
180  }

References push_back().

◆ Path() [5/7]

template<typename G >
Path::Path ( const G &  graph,
const Path &  original,
bool  only_cost 
)
inline

Definition at line 183 of file basePath_SSEC.hpp.

186  :
187  m_start_id(original.m_start_id),
188  m_end_id(original.m_end_id),
189  m_tot_cost(0) {
190  if (original.path.empty()) return;
191 
192  typename G::EO_i ei, ei_end;
193 
194 // auto last_node = m_start_id;
195  for (const auto &p : original.path) {
196  boost::tie(ei, ei_end) = out_edges(
197  graph.get_V(p.node),
198  graph.graph);
199 
200  if (p.edge == -1) {
201  path.push_back({m_end_id, -1, 0, 0});
202  } else {
203  for ( ; ei != ei_end; ++ei) {
204  if (graph[*ei].id == p.edge) {
205  auto cost = graph[*ei].cost;
206  push_back({p.node, p.edge, cost, 0});
207  }
208  }
209  }
210 // last_node = p.node;
211  }
212  recalculate_agg_cost();
213 
214  if (only_cost) {
215  path.clear();
216  path.push_back(
217  {m_end_id,
218  -1,
219  m_tot_cost,
220  m_tot_cost});
221  }
222  }

References m_end_id, m_tot_cost, path, push_back(), and recalculate_agg_cost().

◆ Path() [6/7]

template<typename G , typename V >
Path::Path ( G &  graph,
V  v_source,
double  distance,
const std::vector< V > &  predecessors,
const std::vector< double > &  distances 
)
inline

Definition at line 224 of file basePath_SSEC.hpp.

229  :
230  m_start_id(graph.graph[v_source].id),
231  m_end_id(graph.graph[v_source].id) {
232  for (V i = 0; i < distances.size(); ++i) {
233  if (distances[i] <= distance) {
234  auto cost = distances[i] - distances[predecessors[i]];
235  auto edge_id = graph.get_edge_id(predecessors[i], i, cost);
236  push_back(
237  {graph[i].id,
238  edge_id, cost,
239  distances[i]});
240  }
241  }
242  }

References push_back().

◆ Path() [7/7]

template<typename G , typename V >
Path::Path ( const G &  graph,
const V  v_source,
const V  v_target,
const std::vector< V > &  predecessors,
const std::vector< double > &  distances,
bool  only_cost,
bool  normal = true 
)
inline

Definition at line 246 of file basePath_SSEC.hpp.

253  :
254  m_start_id(graph.graph[v_source].id),
255  m_end_id(graph.graph[v_target].id) {
256  if (!only_cost) {
257  complete_path(graph,
258  v_source,
259  v_target,
260  predecessors,
261  distances,
262  normal);
263  return;
264  }
265  /*
266  * only_cost
267  */
268  if (v_target != predecessors[v_target]) {
269  push_front(
270  {graph.graph[v_target].id,
271  -1,
272  distances[v_target],
273  distances[v_target]});
274  }
275  return;
276  }

References complete_path(), and push_front().

Member Function Documentation

◆ append()

void Path::append ( const Path &  other)

Path: 2 -> 9 seq node edge cost agg_cost 0 2 4 1 0 1 5 8 1 1 2 6 9 1 2 3 9 -1 0 3 Path: 9 -> 3 seq node edge cost agg_cost 0 9 16 1 0 1 4 3 1 1 2 3 -1 0 2 Path: 2 -> 3 seq node edge cost agg_cost 0 2 4 1 0 1 5 8 1 1 2 6 9 1 2 3 9 16 1 3 4 4 3 1 4 5 3 -1 0 5.

Definition at line 192 of file basePath_SSEC.cpp.

192  {
193  pgassert(m_end_id == other.m_start_id);
194  if (other.m_start_id == other.m_end_id) {
195  pgassert(other.path.empty());
196  return;
197  }
198  if (m_start_id == m_end_id) {
199  pgassert(path.empty());
200  *this = other;
201  return;
202  }
203 #if 0
204  pgassert(path.back().cost == 0);
205 #endif
206  pgassert(path.back().edge == -1);
207  m_end_id = other.m_end_id;
208 
209  auto last = path.back();
210  auto agg_cost = last.agg_cost;
211 
212  path.pop_back();
213 
214  for (auto item : other.path) {
215  item.agg_cost += agg_cost;
216  push_back(item);
217  }
218 }

References m_end_id, m_start_id, path, pgassert, and push_back().

Referenced by pgrouting::bidirectional::Pgr_bidirectional< G >::bidirectional().

◆ appendPath()

void Path::appendPath ( const Path &  o_path)

Definition at line 164 of file basePath_SSEC.cpp.

164  {
165  path.insert(path.end(), o_path.path.begin(), o_path.path.end());
166  recalculate_agg_cost();
167 }

References path, and recalculate_agg_cost().

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

◆ back() [1/2]

Path_t& Path::back ( )
inline

Definition at line 89 of file basePath_SSEC.hpp.

89 {return path.back();}

References path.

◆ back() [2/2]

const Path_t& Path::back ( ) const
inline

Definition at line 88 of file basePath_SSEC.hpp.

88 {return path.back();}

References path.

◆ begin() [1/2]

pthIt Path::begin ( )
inline

Definition at line 81 of file basePath_SSEC.hpp.

81 {return path.begin();}

References path.

Referenced by pgrouting::functions::Pgr_binaryBreadthFirstSearch< G >::getPath(), pgrouting::functions::Pgr_edwardMoore< G >::getPath(), and isEqual().

◆ begin() [2/2]

ConstpthIt Path::begin ( ) const
inline

Definition at line 83 of file basePath_SSEC.hpp.

83 {return path.begin();}

References path.

◆ clear()

void Path::clear ( )

Definition at line 87 of file basePath_SSEC.cpp.

87  {
88  path.clear();
89  m_tot_cost = 0;
90  m_start_id = 0;
91  m_end_id = 0;
92 }

References m_end_id, m_start_id, m_tot_cost, and path.

Referenced by pgrouting::trsp::Pgr_trspHandler::clear().

◆ complete_path()

template<typename G , typename V >
void Path::complete_path ( const G &  graph,
const V  v_source,
const V  v_target,
const std::vector< V > &  predecessors,
const std::vector< double > &  distances,
bool  normal 
)
inline

constructs a path based on results

Normal = false for reversed search path like in pgr_bdDijkstra

Definition at line 282 of file basePath_SSEC.hpp.

288  {
289  // no path was found
290  if (v_target == predecessors[v_target]) {
291  return;
292  }
293 
294  /*
295  * set the target
296  */
297  auto target = v_target;
298 
299  /*
300  * the last stop is the target
301  */
302  push_front(
303  {graph.graph[target].id, -1,
304  0, distances[target]});
305 
306  /*
307  * get the path
308  */
309  while (target != v_source) {
310  /*
311  * done when the predecesor of the target is the target
312  */
313  if (target == predecessors[target]) break;
314 
315  /*
316  * Inserting values in the path
317  */
318  auto cost = distances[target] - distances[predecessors[target]];
319  auto vertex_id = graph.graph[predecessors[target]].id;
320  auto edge_id = normal?
321  graph.get_edge_id(predecessors[target], target, cost)
322  : graph.get_edge_id(target, predecessors[target], cost);
323 
324  push_front({
325  vertex_id,
326  edge_id,
327  cost,
328  distances[target] - cost});
329  target = predecessors[target];
330  }
331 
332  return;
333  }

References push_front().

Referenced by Path().

◆ countInfinityCost()

size_t Path::countInfinityCost ( ) const

Definition at line 133 of file basePath_SSEC.cpp.

133  {
134  return static_cast<size_t>(std::count_if(path.begin(), path.end(),
135  [](Path_t const&p) -> size_t {
136  return std::isinf(p.agg_cost);
137  }));
138 }

References path.

◆ empty()

bool Path::empty ( ) const
inline

Definition at line 72 of file basePath_SSEC.hpp.

72 {return path.empty();}

References path.

Referenced by pgrouting::Pg_points_graph::adjust_pids(), pgrouting::Pg_points_graph::eliminate_details(), pgrouting::Pg_points_graph::eliminate_details_dd(), pgrouting::yen::Pgr_ksp< G >::getFirstSolution(), isEqual(), pgrouting::yen::Pgr_turnRestrictedPath< G >::Myvisitor::on_insert_first_solution(), pgrouting::yen::Pgr_turnRestrictedPath< G >::Myvisitor::on_insert_to_heap(), and pgRouting::pgr_dijkstraVia().

◆ empty_path()

void Path::empty_path ( unsigned int  d_vertex)

◆ end() [1/2]

pthIt Path::end ( )
inline

Definition at line 82 of file basePath_SSEC.hpp.

82 {return path.end();}

References path.

Referenced by pgrouting::functions::Pgr_binaryBreadthFirstSearch< G >::getPath(), pgrouting::functions::Pgr_edwardMoore< G >::getPath(), and isEqual().

◆ end() [2/2]

ConstpthIt Path::end ( ) const
inline

Definition at line 84 of file basePath_SSEC.hpp.

84 {return path.end();}

References path.

◆ end_id() [1/2]

int64_t Path::end_id ( ) const
inline

Definition at line 67 of file basePath_SSEC.hpp.

67 {return m_end_id;}

References m_end_id.

Referenced by pgrouting::Pg_points_graph::adjust_pids(), do_pgr_withPoints(), pgrouting::Pg_points_graph::eliminate_details(), pgrouting::Pg_points_graph::eliminate_details_dd(), generate_postgres_data(), get_pg_ksp_path(), get_pg_turn_restricted_path(), getSubpath(), operator<<(), and pgrouting::trsp::Pgr_trspHandler::process_trsp().

◆ end_id() [2/2]

void Path::end_id ( int64_t  value)
inline

Definition at line 68 of file basePath_SSEC.hpp.

68 {m_end_id = value;}

References m_end_id.

◆ erase()

void Path::erase ( pthIt  pos)
inline

Definition at line 87 of file basePath_SSEC.hpp.

87 {path.erase(pos);}

References path.

◆ find_restriction()

Path::ConstpthIt Path::find_restriction ( const pgrouting::trsp::Rule &  rule) const

get the iterator of the path where the (restriction) rule starts

Parameters
[in]ruleA subpath of edges for turn restrictions
Returns
the iterator of the path

Definition at line 94 of file basePath_SSEC.cpp.

95  {
96  return std::search(path.begin(), path.end(), rule.begin(), rule.end(),
97  [](Path_t p, int64_t e) {return p.edge == e;});
98 }

References pgrouting::trsp::Rule::begin(), pgrouting::trsp::Rule::end(), and path.

Referenced by has_restriction().

◆ front() [1/2]

Path_t& Path::front ( )
inline

Definition at line 91 of file basePath_SSEC.hpp.

91 {return path.front();}

References path.

◆ front() [2/2]

const Path_t& Path::front ( ) const
inline

Definition at line 90 of file basePath_SSEC.hpp.

90 {return path.front();}

References path.

◆ generate_postgres_data()

void Path::generate_postgres_data ( General_path_element_t **  postgres_data,
size_t &  sequence 
) const

Definition at line 221 of file basePath_SSEC.cpp.

223  {
224  int i = 1;
225  for (const auto e : path) {
226  auto agg_cost = std::fabs(
227  e.agg_cost - (std::numeric_limits<double>::max)()) < 1?
228  std::numeric_limits<double>::infinity() : e.agg_cost;
229  auto cost = std::fabs(e.cost - (std::numeric_limits<double>::max)()) < 1?
230  std::numeric_limits<double>::infinity() : e.cost;
231 
232  (*postgres_data)[sequence] = {i, start_id(), end_id(), e.node, e.edge, cost, agg_cost};
233  ++i;
234  ++sequence;
235  }
236 }

References end_id(), path, and start_id().

◆ get_pg_dd_path()

void Path::get_pg_dd_path ( General_path_element_t **  ret_path,
size_t &  sequence 
) const

Definition at line 239 of file basePath_SSEC.cpp.

241  {
242  for (unsigned int i = 0; i < path.size(); i++) {
243  (*ret_path)[sequence].seq = static_cast<int>(i);
244  (*ret_path)[sequence].start_id = start_id();
245  (*ret_path)[sequence].end_id = start_id();
246  (*ret_path)[sequence].node = path[i].node;
247  (*ret_path)[sequence].edge = path[i].edge;
248  (*ret_path)[sequence].cost = path[i].cost;
249  (*ret_path)[sequence].agg_cost = path[i].agg_cost;
250  sequence++;
251  }
252 }

References path, and start_id().

◆ get_pg_ksp_path()

void Path::get_pg_ksp_path ( General_path_element_t **  ret_path,
size_t &  sequence,
int  routeId 
) const

Definition at line 255 of file basePath_SSEC.cpp.

257  {
258  for (unsigned int i = 0; i < path.size(); i++) {
259  (*ret_path)[sequence].seq = static_cast<int>(i + 1);
260  (*ret_path)[sequence].start_id = routeId;
261  (*ret_path)[sequence].end_id = end_id();
262  (*ret_path)[sequence].node = path[i].node;
263  (*ret_path)[sequence].edge = path[i].edge;
264  (*ret_path)[sequence].cost = path[i].cost;
265  (*ret_path)[sequence].agg_cost = (i == 0)?
266  0 :
267  (*ret_path)[sequence-1].agg_cost + path[i-1].cost;
268  sequence++;
269  }
270 }

References end_id(), and path.

◆ get_pg_turn_restricted_path()

void Path::get_pg_turn_restricted_path ( General_path_element_t **  ret_path,
size_t &  sequence,
int  routeId 
) const

Definition at line 273 of file basePath_SSEC.cpp.

275  {
276  for (unsigned int i = 0; i < path.size(); i++) {
277  (*ret_path)[sequence].seq = static_cast<int>(i + 1);
278  (*ret_path)[sequence].start_id = routeId;
279  (*ret_path)[sequence].end_id = end_id();
280  (*ret_path)[sequence].node = path[i].node;
281  (*ret_path)[sequence].edge = path[i].edge;
282  (*ret_path)[sequence].cost = path[i].cost;
283  (*ret_path)[sequence].agg_cost = path[i].agg_cost;
284  sequence++;
285  }
286 }

References end_id(), and path.

◆ getSubpath()

Path Path::getSubpath ( unsigned int  j) const

Definition at line 141 of file basePath_SSEC.cpp.

141  {
142  Path result(start_id(), end_id());
143  if (j == 0) return result;
144  for (auto i = path.begin(); i != path.begin() + j; ++i) {
145  result.push_back((*i));
146  }
147  pgassert(result.tot_cost() != 0);
148  pgassert(this->tot_cost() != 0);
149  return result;
150 }

References end_id(), path, pgassert, push_back(), start_id(), and tot_cost().

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

◆ has_restriction()

bool Path::has_restriction ( const pgrouting::trsp::Rule &  rule) const

Definition at line 100 of file basePath_SSEC.cpp.

101  {
102  return find_restriction(rule) != path.end();
103 }

References find_restriction(), and path.

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

◆ inf_cost_on_restriction()

Path Path::inf_cost_on_restriction ( const pgrouting::trsp::Rule &  rule)

Definition at line 105 of file basePath_SSEC.cpp.

106  {
107  auto position = std::search(
108  path.begin(), path.end(), rule.begin(), rule.end(),
109  [](Path_t p, int64_t e) { return p.edge == e;});
110  if (position != path.end()) {
111  position->agg_cost = std::numeric_limits<double>::infinity();
112  }
113  return *this;
114 }

References pgrouting::trsp::Rule::begin(), pgrouting::trsp::Rule::end(), and path.

◆ isEqual()

bool Path::isEqual ( const Path &  subpath) const

Definition at line 153 of file basePath_SSEC.cpp.

153  {
154  if (subpath.empty()) return true;
155  if (subpath.size() >= path.size()) return false;
156  std::deque< Path_t >::const_iterator i, j;
157  for (i = path.begin(), j = subpath.begin();
158  j != subpath.end();
159  ++i, ++j)
160  if ((*i).node != (*j).node) return false;
161  return true;
162 }

References begin(), empty(), end(), path, and size().

◆ operator[]() [1/2]

Path_t& Path::operator[] ( size_t  i)
inline

Definition at line 78 of file basePath_SSEC.hpp.

78 {return path[i];}

References path.

◆ operator[]() [2/2]

const Path_t& Path::operator[] ( size_t  i) const
inline

Definition at line 77 of file basePath_SSEC.hpp.

77 {return path[i];}

References path.

◆ push_back()

void Path::push_back ( Path_t  data)

Definition at line 52 of file basePath_SSEC.cpp.

52  {
53  path.push_back(data);
54  m_tot_cost += data.cost;
55 }

References Path_t::cost, m_tot_cost, and path.

Referenced by append(), pgrouting::trsp::Pgr_trspHandler::construct_path(), pgrouting::Pgr_dijkstra< G >::drivingDistance_no_equicost(), pgrouting::Pg_points_graph::eliminate_details(), pgrouting::Pg_points_graph::eliminate_details_dd(), pgrouting::functions::Pgr_binaryBreadthFirstSearch< G >::getPath(), pgrouting::functions::Pgr_edwardMoore< G >::getPath(), getSubpath(), Path(), and pgrouting::trsp::Pgr_trspHandler::process_trsp().

◆ push_front() [1/2]

void Path::push_front ( int64_t  d_vertex,
int64_t  d_edge,
double  d_cost,
double  d_tot_cost 
)

◆ push_front() [2/2]

void Path::push_front ( Path_t  data)

Definition at line 47 of file basePath_SSEC.cpp.

47  {
48  path.push_front(data);
49  m_tot_cost += data.cost;
50 }

References Path_t::cost, m_tot_cost, and path.

Referenced by complete_path(), and Path().

◆ recalculate_agg_cost()

void Path::recalculate_agg_cost ( )

Definition at line 77 of file basePath_SSEC.cpp.

77  {
78  m_tot_cost = 0;
79  for (auto &p : path) {
80  p.agg_cost = m_tot_cost;
81  m_tot_cost += p.cost;
82  }
83 }

References m_tot_cost, and path.

Referenced by appendPath(), pgrouting::yen::Pgr_ksp< G >::executeYen(), pgrouting::yen::Pgr_ksp< G >::getFirstSolution(), Path(), and detail::post_process().

◆ renumber_vertices()

Path & Path::renumber_vertices ( int64_t  value)

Definition at line 38 of file basePath_SSEC.cpp.

38  {
39  for (auto &r : path) {
40  r.node += value;
41  }
42  m_start_id += value;
43  m_end_id += value;
44  return *this;
45 }

References m_end_id, m_start_id, and path.

Referenced by pgrouting::trsp::Pgr_trspHandler::process_trsp().

◆ reverse()

void Path::reverse ( )

Definition at line 57 of file basePath_SSEC.cpp.

57  {
58  std::swap(m_start_id, m_end_id);
59  if (path.size() <= 1) return;
60  std::deque< Path_t > newpath;
61  for (size_t i = 0; i < path.size(); ++i) {
62  newpath.push_front({
63  path[i].node,
64  (i == 0? -1 : path[i - 1].edge),
65  (i == 0? 0 : path[i - 1].cost),
66  0
67  });
68  }
69  for (size_t i = 0; i < newpath.size(); ++i) {
70  newpath[i].agg_cost = (i == 0)?
71  0 :
72  newpath[i - 1].agg_cost + newpath[i - 1].cost;
73  }
74  path = newpath;
75 }

References m_end_id, m_start_id, and path.

Referenced by pgrouting::bidirectional::Pgr_bidirectional< G >::bidirectional(), pgr_astar(), and pgr_dijkstra().

◆ set_data()

Path_t Path::set_data ( int64_t  d_from,
int64_t  d_to,
int64_t  d_vertex,
int64_t  d_edge,
double  d_cost,
double  d_tot_cost 
)

◆ size()

size_t Path::size ( ) const
inline

Definition at line 71 of file basePath_SSEC.hpp.

71 {return path.size();}

References path.

Referenced by pgrouting::yen::Pgr_ksp< G >::doNextCycle(), pgrouting::Pg_points_graph::eliminate_details(), isEqual(), pgrouting::compPathsLess::operator()(), and pgRouting::pgr_dijkstraVia().

◆ sort_by_node_agg_cost()

void Path::sort_by_node_agg_cost ( )

Sorts a path by node, aggcost ascending.

nodes ASC agg_cost ASC

Definition at line 295 of file basePath_SSEC.cpp.

295  {
296  std::sort(path.begin(), path.end(),
297  [](const Path_t &l, const Path_t &r)
298  {return l.node < r.node;});
299  std::stable_sort(path.begin(), path.end(),
300  [](const Path_t &l, const Path_t &r)
301  {return l.agg_cost < r.agg_cost;});
302 }

References path.

◆ start_id() [1/2]

int64_t Path::start_id ( ) const
inline

Definition at line 65 of file basePath_SSEC.hpp.

65 {return m_start_id;}

References m_start_id.

Referenced by pgrouting::Pg_points_graph::adjust_pids(), pgrouting::trsp::Pgr_trspHandler::construct_path(), pgrouting::Pg_points_graph::eliminate_details(), pgrouting::Pg_points_graph::eliminate_details_dd(), generate_postgres_data(), get_pg_dd_path(), getSubpath(), operator<<(), and pgrouting::trsp::Pgr_trspHandler::process_trsp().

◆ start_id() [2/2]

void Path::start_id ( int64_t  value)
inline

Definition at line 66 of file basePath_SSEC.hpp.

66 {m_start_id = value;}

References m_start_id.

◆ tot_cost()

double Path::tot_cost ( ) const
inline

Definition at line 69 of file basePath_SSEC.hpp.

69 {return m_tot_cost;}

References m_tot_cost.

Referenced by getSubpath(), and pgrouting::compPathsLess::operator()().

Friends And Related Function Documentation

◆ collapse_paths

size_t collapse_paths ( General_path_element_t **  ret_path,
const std::deque< Path > &  paths 
)
friend

Definition at line 310 of file basePath_SSEC.cpp.

312  {
313  size_t sequence = 0;
314  for (const Path &path : paths) {
315  if (path.path.size() > 0)
316  path.generate_postgres_data(ret_path, sequence);
317  }
318  return sequence;
319 }

◆ count_tuples

size_t count_tuples ( const std::deque< Path > &  paths)
friend

counts the tuples to be returned

Definition at line 387 of file basePath_SSEC.cpp.

387  {
388  size_t count(0);
389  for (const Path &e : paths) {
390  count += e.path.size();
391  }
392  return count;
393 }

◆ equi_cost

void equi_cost ( std::deque< Path > &  paths)
friend

discards common vertices with greater agg_cost

Definition at line 336 of file basePath_SSEC.cpp.

336  {
337  /* sort paths by size: largest first */
338  std::sort(paths.begin(), paths.end(),
339  [](const Path &e1, const Path &e2)->bool {
340  return e2.size() < e1.size();
341  });
342 
343  /* sort each path by node: smaller id first */
344  for (auto &p : paths) {
345  if (p.size() < 2) continue;
346  std::sort(p.begin(), p.end(),
347  [](const Path_t &e1, const Path_t &e2)->bool {
348  return e1.node < e2.node;
349  });
350  }
351 
352  for (auto &p1 : paths) {
353  for (const auto &p2 : paths) {
354  if (p1.start_id() == p2.start_id()) continue;
355  for (const auto &stop : p2.path) {
356  /* find the node of p2 in p1 */
357  auto pos = lower_bound(p1.begin(), p1.end(), stop,
358  [](const Path_t &l, const Path_t &r)->bool {
359  return l.node < r.node;
360  });
361 
362  if (pos != p1.end()
363  && (stop.node == pos->node)
364  && (stop.agg_cost < pos->agg_cost)) {
365  /* both share the same node &
366  * the second path has the smallest
367  * So erasing from the first path */
368  p1.erase(pos);
369  }
370  }
371  }
372  }
373  /* sort paths by start_id */
374  std::sort(paths.begin(), paths.end(),
375  [](const Path &e1, const Path &e2)->bool {
376  return e1.start_id() < e2.start_id();
377  });
378 
379  /* sort each path by agg_cost, node */
380  for (auto &path : paths) {
381  path.sort_by_node_agg_cost();
382  }
383 }

◆ operator<<

std::ostream& operator<< ( std::ostream &  log,
const Path &  p 
)
friend

Definition at line 118 of file basePath_SSEC.cpp.

118  {
119  log << "Path: " << path.start_id() << " -> " << path.end_id() << "\n"
120  << "seq\tnode\tedge\tcost\tagg_cost\n";
121  int64_t i = 0;
122  for (const auto &e : path) {
123  log << i << "\t"
124  << e.node << "\t"
125  << e.edge << "\t"
126  << e.cost << "\t"
127  << e.agg_cost << "\n";
128  ++i;
129  }
130  return log;
131 }

Member Data Documentation

◆ m_end_id

int64_t Path::m_end_id
private

Definition at line 54 of file basePath_SSEC.hpp.

Referenced by append(), clear(), end_id(), Path(), renumber_vertices(), and reverse().

◆ m_start_id

int64_t Path::m_start_id
private

Definition at line 53 of file basePath_SSEC.hpp.

Referenced by append(), clear(), renumber_vertices(), reverse(), and start_id().

◆ m_tot_cost

double Path::m_tot_cost
private

Definition at line 55 of file basePath_SSEC.hpp.

Referenced by clear(), Path(), push_back(), push_front(), recalculate_agg_cost(), and tot_cost().

◆ path

std::deque< Path_t > Path::path
private

Definition at line 52 of file basePath_SSEC.hpp.

Referenced by append(), appendPath(), back(), begin(), clear(), countInfinityCost(), empty(), end(), erase(), find_restriction(), front(), generate_postgres_data(), get_pg_dd_path(), get_pg_ksp_path(), get_pg_turn_restricted_path(), getSubpath(), has_restriction(), inf_cost_on_restriction(), isEqual(), operator[](), Path(), push_back(), push_front(), recalculate_agg_cost(), renumber_vertices(), reverse(), size(), and sort_by_node_agg_cost().

The documentation for this class was generated from the following files:
Path::end_id
int64_t end_id() const
Definition: basePath_SSEC.hpp:67
Path
Definition: basePath_SSEC.hpp:47
Path::path
std::deque< Path_t > path
Definition: basePath_SSEC.hpp:52
Path::start_id
int64_t start_id() const
Definition: basePath_SSEC.hpp:65
Path::push_back
void push_back(Path_t data)
Definition: basePath_SSEC.cpp:52
Path_t
Definition: path_t.h:36
Path::end
pthIt end()
Definition: basePath_SSEC.hpp:82
Path::empty
bool empty() const
Definition: basePath_SSEC.hpp:72
Path::push_front
void push_front(Path_t data)
Definition: basePath_SSEC.cpp:47
pgassert
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:94
Path::m_end_id
int64_t m_end_id
Definition: basePath_SSEC.hpp:54
Path::complete_path
void complete_path(const G &graph, const V v_source, const V v_target, const std::vector< V > &predecessors, const std::vector< double > &distances, bool normal)
constructs a path based on results
Definition: basePath_SSEC.hpp:282
Path::size
size_t size() const
Definition: basePath_SSEC.hpp:71
Path::m_tot_cost
double m_tot_cost
Definition: basePath_SSEC.hpp:55
Path::m_start_id
int64_t m_start_id
Definition: basePath_SSEC.hpp:53
pgrouting::trsp::Rule::begin
constiterator begin() const
Definition: rule.h:52
pgrouting::trsp::Rule::end
constiterator end() const
Definition: rule.h:53
pgrouting::alphashape::V
boost::graph_traits< BG >::vertex_descriptor V
Definition: pgr_alphaShape.h:58
Path::begin
pthIt begin()
Definition: basePath_SSEC.hpp:81
Path::recalculate_agg_cost
void recalculate_agg_cost()
Definition: basePath_SSEC.cpp:77
Path_t::cost
double cost
Definition: path_t.h:39
Path::tot_cost
double tot_cost() const
Definition: basePath_SSEC.hpp:69
Path::find_restriction
ConstpthIt find_restriction(const pgrouting::trsp::Rule &rule) const
get the iterator of the path where the (restriction) rule starts
Definition: basePath_SSEC.cpp:94