PGROUTING  2.5
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
basePath_SSEC.cpp
Go to the documentation of this file.
1 /*PGR-GNU*****************************************************************
2 File: basePath_SSEC.cpp
3 
4 Copyright (c) 2015 Celia Virginia Vergara Castillo
5 vicky_vergara@hotmail.com
6 
7 ------
8 
9 This program is free software; you can redistribute it and/or modify
10 it under the terms of the GNU General Public License as published by
11 the Free Software Foundation; either version 2 of the License, or
12 (at your option) any later version.
13 
14 This program is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 GNU General Public License for more details.
18 
19 You should have received a copy of the GNU General Public License
20 along with this program; if not, write to the Free Software
21 
22 ********************************************************************PGR-GNU*/
23 
25 
26 #include <deque>
27 #include <iostream>
28 #include <algorithm>
29 #include <utility>
30 
32 #include "cpp_common/pgr_assert.h"
33 
35  path.push_front(data);
36  m_tot_cost += data.cost;
37 }
38 
39 void Path::push_back(Path_t data) {
40  path.push_back(data);
41  m_tot_cost += data.cost;
42 }
43 
44 void Path::reverse() {
45  std::swap(m_start_id, m_end_id);
46  if (path.size() <= 1) return;
47  std::deque< Path_t > newpath;
48  for (size_t i = 0; i < path.size(); ++i) {
49  newpath.push_front({
50  path[i].node,
51  (i == 0? -1 : path[i - 1].edge),
52  (i == 0? 0 : path[i - 1].cost),
53  0
54  });
55  }
56  for (size_t i = 0; i < newpath.size(); ++i) {
57  newpath[i].agg_cost = (i == 0)?
58  0 :
59  newpath[i - 1].agg_cost + newpath[i - 1].cost;
60  }
61  path = newpath;
62 }
63 
64 
65 void Path::clear() {
66  path.clear();
67  m_tot_cost = 0;
68  m_start_id = 0;
69  m_end_id = 0;
70 }
71 
72 std::ostream& operator<<(std::ostream &log, const Path &path) {
73  log << "Path: " << path.start_id() << " -> " << path.end_id() << "\n"
74  << "seq\tnode\tedge\tcost\tagg_cost\n";
75  int64_t i = 0;
76  for (const auto &e : path) {
77  log << i << "\t"
78  << e.node << "\t"
79  << e.edge << "\t"
80  << e.cost << "\t"
81  << e.agg_cost << "\n";
82  ++i;
83  }
84  return log;
85 }
86 
87 
88 
89 Path Path::getSubpath(unsigned int j) const {
90  Path result(start_id(), end_id());
91  if (j == 0) return result;
92  for (auto i = path.begin(); i != path.begin() + j; ++i) {
93  result.push_back((*i));
94  }
95  pgassert(result.tot_cost() != 0);
96  pgassert(this->tot_cost() != 0);
97  return result;
98 }
99 
100 
101 bool Path::isEqual(const Path &subpath) const {
102  if (subpath.empty()) return true;
103  if (subpath.size() >= path.size()) return false;
104  std::deque< Path_t >::const_iterator i, j;
105  for (i = path.begin(), j = subpath.begin();
106  j != subpath.end();
107  ++i, ++j)
108  if ((*i).node != (*j).node) return false;
109  return true;
110 }
111 
112 void Path::appendPath(const Path &o_path) {
113  path.insert(path.end(), o_path.path.begin(), o_path.path.end());
114  m_tot_cost += o_path.m_tot_cost;
115 }
116 
117 
141 void Path::append(const Path &other) {
142  pgassert(m_end_id == other.m_start_id);
143  if (other.m_start_id == other.m_end_id) {
144  pgassert(other.path.empty());
145  return;
146  }
147  if (m_start_id == m_end_id) {
148  pgassert(path.empty());
149  *this = other;
150  return;
151  }
152 #if 0
153  pgassert(path.back().cost == 0);
154 #endif
155  pgassert(path.back().edge == -1);
156  m_end_id = other.m_end_id;
157 
158  auto last = path.back();
159  auto agg_cost = last.agg_cost;
160 
161  path.pop_back();
162 
163  for (auto item : other.path) {
164  item.agg_cost += agg_cost;
165  push_back(item);
166  }
167 }
168 
169 
171  General_path_element_t **postgres_data,
172  size_t &sequence) const {
173  int i = 1;
174  for (const auto e : path) {
175  (*postgres_data)[sequence] =
176  {i, start_id(), end_id(), e.node, e.edge, e.cost, e.agg_cost};
177  ++i;
178  ++sequence;
179  }
180 }
181 
182 /* used by driving distance */
184  General_path_element_t **ret_path,
185  size_t &sequence) const {
186  for (unsigned int i = 0; i < path.size(); i++) {
187  (*ret_path)[sequence].seq = i;
188  (*ret_path)[sequence].start_id = start_id();
189  (*ret_path)[sequence].end_id = start_id();
190  (*ret_path)[sequence].node = path[i].node;
191  (*ret_path)[sequence].edge = path[i].edge;
192  (*ret_path)[sequence].cost = path[i].cost;
193  (*ret_path)[sequence].agg_cost = path[i].agg_cost;
194  sequence++;
195  }
196 }
197 
198 /* used by ksp */
200  General_path_element_t **ret_path,
201  size_t &sequence, int routeId) const {
202  for (unsigned int i = 0; i < path.size(); i++) {
203  (*ret_path)[sequence].seq = i + 1;
204  (*ret_path)[sequence].start_id = routeId;
205  (*ret_path)[sequence].end_id = end_id();
206  (*ret_path)[sequence].node = path[i].node;
207  (*ret_path)[sequence].edge = path[i].edge;
208  (*ret_path)[sequence].cost = path[i].cost;
209  (*ret_path)[sequence].agg_cost = (i == 0)?
210  0 :
211  (*ret_path)[sequence-1].agg_cost + path[i-1].cost;
212  sequence++;
213  }
214 }
215 
216 
222 void
224  std::sort(path.begin(), path.end(),
225  [](const Path_t &l, const Path_t &r)
226  {return l.node < r.node;});
227  std::stable_sort(path.begin(), path.end(),
228  [](const Path_t &l, const Path_t &r)
229  {return l.agg_cost < r.agg_cost;});
230 }
231 
232 /*
233  * FRIENDS
234  */
235 
236 
237 size_t
239  General_path_element_t **ret_path,
240  const std::deque< Path > &paths) {
241  size_t sequence = 0;
242  for (const Path &path : paths) {
243  if (path.path.size() > 0)
244  path.generate_postgres_data(ret_path, sequence);
245  }
246  return sequence;
247 }
248 
249 /*
250  * sort the paths by size from greater to smaller
251  * and sort each path by node
252  * all the nodes on p2 are going to be compared
253  * with the nodes of p1
254  *
255  * When both paths reach the node and p1.agg_cost > p2.agg_cost
256  * erase the node of p1
257  * (can't erase from p2 because we loose the iterators
258  * so in a future cycle it will be deleted)
259  *
260  * sort the paths by start_id,
261  */
262 
263 void
264 equi_cost(std::deque< Path > &paths) {
265  /* sort paths by size: largest first */
266  std::sort(paths.begin(), paths.end(),
267  [](const Path &e1, const Path &e2)->bool {
268  return e2.size() < e1.size();
269  });
270 
271  /* sort each path by node: smaller id first */
272  for (auto &p : paths) {
273  if (p.size() < 2) continue;
274  std::sort(p.begin(), p.end(),
275  [](const Path_t &e1, const Path_t &e2)->bool {
276  return e1.node < e2.node;
277  });
278  }
279 
280  for (auto &p1 : paths) {
281  for (const auto &p2 : paths) {
282  if (p1.start_id() == p2.start_id()) continue;
283  for (const auto &stop : p2.path) {
284  /* find the node of p2 in p1 */
285  auto pos = lower_bound(p1.begin(), p1.end(), stop,
286  [](const Path_t &l, const Path_t &r)->bool {
287  return l.node < r.node;
288  });
289 
290  if (pos != p1.end()
291  && (stop.node == pos->node)
292  && (stop.agg_cost < pos->agg_cost)) {
293  /* both share the same node &
294  * the second path has the smallest
295  * So erasing from the first path */
296  p1.erase(pos);
297  }
298  }
299  }
300  }
301  /* sort paths by start_id */
302  std::sort(paths.begin(), paths.end(),
303  [](const Path &e1, const Path &e2)->bool {
304  return e1.start_id() < e2.start_id();
305  });
306 
307  /* sort each path by agg_cost, node */
308  for (auto &path : paths) {
309  path.sort_by_node_agg_cost();
310  }
311 }
312 
313 
314 size_t
315 count_tuples(const std::deque< Path > &paths) {
316  size_t count(0);
317  for (const Path &e : paths) {
318  count += e.path.size();
319  }
320  return count;
321 }
int64_t m_end_id
void push_front(Path_t data)
int64_t m_start_id
void get_pg_ksp_path(General_path_element_t **ret_path, size_t &sequence, int routeId) const
void sort_by_node_agg_cost()
Sorts a path by node, aggcost ascending.
size_t collapse_paths(General_path_element_t **ret_path, const std::deque< Path > &paths)
void get_pg_dd_path(General_path_element_t **ret_path, size_t &sequence) const
void equi_cost(std::deque< Path > &paths)
double cost
Definition: path_t.h:39
void push_back(Path_t data)
void generate_postgres_data(General_path_element_t **postgres_data, size_t &sequence) const
int64_t end_id() const
double tot_cost() const
std::ostream & operator<<(std::ostream &log, const Path &path)
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:81
int64_t node
Definition: path_t.h:37
pthIt end()
void reverse()
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 no...
Definition: path_t.h:36
int64_t start_id() const
size_t count_tuples(const std::deque< Path > &paths)
pthIt begin()
bool empty() const
Assertions Handling.
Path getSubpath(unsigned int j) const
size_t size() const
void clear()
std::deque< Path_t > path
double agg_cost
Definition: path_t.h:40
double m_tot_cost
void appendPath(const Path &o_path)
bool isEqual(const Path &subpath) const