PGROUTING  2.6
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 
34 
35 Path& Path::renumber_vertices(int64_t value) {
36  for (auto &r : path) {
37  r.node += value;
38  }
39  m_start_id += value;
40  m_end_id += value;
41  return *this;
42 }
43 
45  path.push_front(data);
46  m_tot_cost += data.cost;
47 }
48 
49 void Path::push_back(Path_t data) {
50  path.push_back(data);
51  m_tot_cost += data.cost;
52 }
53 
54 void Path::reverse() {
55  std::swap(m_start_id, m_end_id);
56  if (path.size() <= 1) return;
57  std::deque< Path_t > newpath;
58  for (size_t i = 0; i < path.size(); ++i) {
59  newpath.push_front({
60  path[i].node,
61  (i == 0? -1 : path[i - 1].edge),
62  (i == 0? 0 : path[i - 1].cost),
63  0
64  });
65  }
66  for (size_t i = 0; i < newpath.size(); ++i) {
67  newpath[i].agg_cost = (i == 0)?
68  0 :
69  newpath[i - 1].agg_cost + newpath[i - 1].cost;
70  }
71  path = newpath;
72 }
73 
75  m_tot_cost = 0;
76  for (auto &p : path) {
77  p.agg_cost = m_tot_cost;
78  m_tot_cost += p.cost;
79  }
80 }
81 
82 
83 
84 void Path::clear() {
85  path.clear();
86  m_tot_cost = 0;
87  m_start_id = 0;
88  m_end_id = 0;
89 }
90 
91 std::ostream& operator<<(std::ostream &log, const Path &path) {
92  log << "Path: " << path.start_id() << " -> " << path.end_id() << "\n"
93  << "seq\tnode\tedge\tcost\tagg_cost\n";
94  int64_t i = 0;
95  for (const auto &e : path) {
96  log << i << "\t"
97  << e.node << "\t"
98  << e.edge << "\t"
99  << e.cost << "\t"
100  << e.agg_cost << "\n";
101  ++i;
102  }
103  return log;
104 }
105 
106 
107 
108 Path Path::getSubpath(unsigned int j) const {
109  Path result(start_id(), end_id());
110  if (j == 0) return result;
111  for (auto i = path.begin(); i != path.begin() + j; ++i) {
112  result.push_back((*i));
113  }
114  pgassert(result.tot_cost() != 0);
115  pgassert(this->tot_cost() != 0);
116  return result;
117 }
118 
119 
120 bool Path::isEqual(const Path &subpath) const {
121  if (subpath.empty()) return true;
122  if (subpath.size() >= path.size()) return false;
123  std::deque< Path_t >::const_iterator i, j;
124  for (i = path.begin(), j = subpath.begin();
125  j != subpath.end();
126  ++i, ++j)
127  if ((*i).node != (*j).node) return false;
128  return true;
129 }
130 
131 void Path::appendPath(const Path &o_path) {
132  path.insert(path.end(), o_path.path.begin(), o_path.path.end());
133  m_tot_cost += o_path.m_tot_cost;
134 }
135 
136 
160 void Path::append(const Path &other) {
161  pgassert(m_end_id == other.m_start_id);
162  if (other.m_start_id == other.m_end_id) {
163  pgassert(other.path.empty());
164  return;
165  }
166  if (m_start_id == m_end_id) {
167  pgassert(path.empty());
168  *this = other;
169  return;
170  }
171 #if 0
172  pgassert(path.back().cost == 0);
173 #endif
174  pgassert(path.back().edge == -1);
175  m_end_id = other.m_end_id;
176 
177  auto last = path.back();
178  auto agg_cost = last.agg_cost;
179 
180  path.pop_back();
181 
182  for (auto item : other.path) {
183  item.agg_cost += agg_cost;
184  push_back(item);
185  }
186 }
187 
188 
190  General_path_element_t **postgres_data,
191  size_t &sequence) const {
192  int i = 1;
193  double total_cost = 0;
194  for (const auto e : path) {
195  (*postgres_data)[sequence] =
196  {i, start_id(), end_id(), e.node, e.edge, e.cost, e.agg_cost};
197  total_cost += e.cost;
198  ++i;
199  ++sequence;
200  }
201 }
202 
203 /* used by driving distance */
205  General_path_element_t **ret_path,
206  size_t &sequence) const {
207  for (unsigned int i = 0; i < path.size(); i++) {
208  (*ret_path)[sequence].seq = i;
209  (*ret_path)[sequence].start_id = start_id();
210  (*ret_path)[sequence].end_id = start_id();
211  (*ret_path)[sequence].node = path[i].node;
212  (*ret_path)[sequence].edge = path[i].edge;
213  (*ret_path)[sequence].cost = path[i].cost;
214  (*ret_path)[sequence].agg_cost = path[i].agg_cost;
215  sequence++;
216  }
217 }
218 
219 /* used by ksp */
221  General_path_element_t **ret_path,
222  size_t &sequence, int routeId) const {
223  for (unsigned int i = 0; i < path.size(); i++) {
224  (*ret_path)[sequence].seq = i + 1;
225  (*ret_path)[sequence].start_id = routeId;
226  (*ret_path)[sequence].end_id = end_id();
227  (*ret_path)[sequence].node = path[i].node;
228  (*ret_path)[sequence].edge = path[i].edge;
229  (*ret_path)[sequence].cost = path[i].cost;
230  (*ret_path)[sequence].agg_cost = (i == 0)?
231  0 :
232  (*ret_path)[sequence-1].agg_cost + path[i-1].cost;
233  sequence++;
234  }
235 }
236 
237 
243 void
245  std::sort(path.begin(), path.end(),
246  [](const Path_t &l, const Path_t &r)
247  {return l.node < r.node;});
248  std::stable_sort(path.begin(), path.end(),
249  [](const Path_t &l, const Path_t &r)
250  {return l.agg_cost < r.agg_cost;});
251 }
252 
253 /*
254  * FRIENDS
255  */
256 
257 
258 size_t
260  General_path_element_t **ret_path,
261  const std::deque< Path > &paths) {
262  size_t sequence = 0;
263  for (const Path &path : paths) {
264  if (path.path.size() > 0)
265  path.generate_postgres_data(ret_path, sequence);
266  }
267  return sequence;
268 }
269 
270 /*
271  * sort the paths by size from greater to smaller
272  * and sort each path by node
273  * all the nodes on p2 are going to be compared
274  * with the nodes of p1
275  *
276  * When both paths reach the node and p1.agg_cost > p2.agg_cost
277  * erase the node of p1
278  * (can't erase from p2 because we loose the iterators
279  * so in a future cycle it will be deleted)
280  *
281  * sort the paths by start_id,
282  */
283 
284 void
285 equi_cost(std::deque< Path > &paths) {
286  /* sort paths by size: largest first */
287  std::sort(paths.begin(), paths.end(),
288  [](const Path &e1, const Path &e2)->bool {
289  return e2.size() < e1.size();
290  });
291 
292  /* sort each path by node: smaller id first */
293  for (auto &p : paths) {
294  if (p.size() < 2) continue;
295  std::sort(p.begin(), p.end(),
296  [](const Path_t &e1, const Path_t &e2)->bool {
297  return e1.node < e2.node;
298  });
299  }
300 
301  for (auto &p1 : paths) {
302  for (const auto &p2 : paths) {
303  if (p1.start_id() == p2.start_id()) continue;
304  for (const auto &stop : p2.path) {
305  /* find the node of p2 in p1 */
306  auto pos = lower_bound(p1.begin(), p1.end(), stop,
307  [](const Path_t &l, const Path_t &r)->bool {
308  return l.node < r.node;
309  });
310 
311  if (pos != p1.end()
312  && (stop.node == pos->node)
313  && (stop.agg_cost < pos->agg_cost)) {
314  /* both share the same node &
315  * the second path has the smallest
316  * So erasing from the first path */
317  p1.erase(pos);
318  }
319  }
320  }
321  }
322  /* sort paths by start_id */
323  std::sort(paths.begin(), paths.end(),
324  [](const Path &e1, const Path &e2)->bool {
325  return e1.start_id() < e2.start_id();
326  });
327 
328  /* sort each path by agg_cost, node */
329  for (auto &path : paths) {
330  path.sort_by_node_agg_cost();
331  }
332 }
333 
334 
335 size_t
336 count_tuples(const std::deque< Path > &paths) {
337  size_t count(0);
338  for (const Path &e : paths) {
339  count += e.path.size();
340  }
341  return count;
342 }
int64_t m_end_id
void push_front(Path_t data)
int64_t m_start_id
void recalculate_agg_cost()
friend size_t count_tuples(const std::deque< Path > &paths)
counts the tuples to be returned
friend std::ostream & operator<<(std::ostream &log, const Path &p)
void get_pg_ksp_path(General_path_element_t **ret_path, size_t &sequence, int routeId) const
friend size_t collapse_paths(General_path_element_t **ret_path, const std::deque< Path > &paths)
friend void equi_cost(std::deque< Path > &paths)
discards common vertices with greater agg_cost
void sort_by_node_agg_cost()
Sorts a path by node, aggcost ascending.
void get_pg_dd_path(General_path_element_t **ret_path, size_t &sequence) const
double cost
Definition: path_t.h:39
Path & renumber_vertices(int64_t value)
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
#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
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