PGROUTING  2.4
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
basePath_SSEC.hpp
Go to the documentation of this file.
1 /*PGR-GNU*****************************************************************
2 
3 File: basePath_SSEC.hpp
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 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
22 
23 ********************************************************************PGR-GNU*/
24 
25 #ifndef SRC_COMMON_SRC_BASEPATH_SSEC_HPP_
26 #define SRC_COMMON_SRC_BASEPATH_SSEC_HPP_
27 #pragma once
28 
29 
30 #include <boost/config.hpp>
31 #include <boost/graph/adjacency_list.hpp>
32 
33 
34 #include <deque>
35 #include <vector>
36 #include <iostream>
37 #include <algorithm>
38 #include "./pgr_types.h"
39 #include "./pgr_base_graph.hpp"
40 
41 
42 class Path {
43  typedef std::deque< Path_t >::iterator pthIt;
44  typedef std::deque< Path_t >::const_iterator ConstpthIt;
45 
46  private:
47  std::deque< Path_t > path;
48  int64_t m_start_id;
49  int64_t m_end_id;
50  double m_tot_cost;
51 
52  public:
53  Path(): m_tot_cost(0) {}
54  Path(int64_t s_id, int64_t e_id)
55  : m_start_id(s_id), m_end_id(e_id), m_tot_cost(0)
56  {}
57  Path(const Path&) = default;
58  int64_t start_id() const {return m_start_id;}
59  void start_id(int64_t value) {m_start_id = value;}
60  int64_t end_id() const {return m_end_id;}
61  void end_id(int64_t value) {m_end_id = value;}
62  double tot_cost() const {return m_tot_cost;}
63 
64  size_t size() const {return path.size();}
65  bool empty() const {return path.empty();}
66 
67  void push_front(Path_t data);
68  void push_back(Path_t data);
69  const Path_t& operator[](size_t i) const {return path[i];}
70  Path_t& operator[](size_t i) {return path[i];}
71 
72  pthIt begin() {return path.begin();}
73  pthIt end() {return path.end();}
74  ConstpthIt begin() const {return path.begin();}
75  ConstpthIt end() const {return path.end();}
76 
77 
78  void erase(pthIt pos) {path.erase(pos);}
79  const Path_t& back() const {return path.back();}
80  Path_t& back() {return path.back();}
81  const Path_t& front() const {return path.front();}
82  Path_t& front() {return path.front();}
83 
84 
86  int64_t d_from,
87  int64_t d_to,
88  int64_t d_vertex,
89  int64_t d_edge,
90  double d_cost,
91  double d_tot_cost);
92 
93  void push_front(
94  int64_t d_vertex,
95  int64_t d_edge,
96  double d_cost,
97  double d_tot_cost);
98  void clear();
99 
100  friend std::ostream& operator<<(std::ostream &log, const Path &p);
101 
102 
103  void reverse();
104 
105  Path getSubpath(unsigned int j) const;
106 
107 
108  bool isEqual(const Path &subpath) const;
109  void appendPath(const Path &o_path);
110  void append(const Path &other);
111  void empty_path(unsigned int d_vertex);
112 
113  void get_pg_dd_path(
114  General_path_element_t **ret_path,
115  size_t &sequence) const;
116 
117  void get_pg_ksp_path(
118  General_path_element_t **ret_path,
119  size_t &sequence, int routeId) const;
120 
122  General_path_element_t **postgres_data,
123  size_t &sequence) const;
124 
125  friend size_t collapse_paths(
126  General_path_element_t **ret_path,
127  const std::deque< Path > &paths) {
128  size_t sequence = 0;
129  for (const Path &path : paths) {
130  if (path.path.size() > 0)
131  path.generate_postgres_data(ret_path, sequence);
132  }
133  return sequence;
134  }
135 
136 
137 
138  /*
139  * sort the paths by size from greater to smaller
140  * and sort each path by node
141  * all the nodes on p2 are going to be compared
142  * with the nodes of p1
143  *
144  * When both paths reach the node and p1.agg_cost > p2.agg_cost
145  * erase the node of p1
146  * (can't erase from p2 because we loose the iterators
147  * so in a future cycle it will be deleted)
148  *
149  * sort the paths by start_id,
150  */
151 
152  friend void equi_cost(std::deque< Path > &paths) {
153  /* sort paths by size: largest first */
154  std::sort(paths.begin(), paths.end(),
155  [](const Path &e1, const Path &e2)->bool {
156  return e2.size() < e1.size();
157  });
158 
159  /* sort each path by node: smaller id first */
160  for (auto &p : paths) {
161  if (p.size() < 2) continue;
162  std::sort(p.begin(), p.end(),
163  [](const Path_t &e1, const Path_t &e2)->bool {
164  return e1.node < e2.node;
165  });
166  }
167 
168  for (auto &p1 : paths) {
169  for (const auto &p2 : paths) {
170  if (p1.start_id() == p2.start_id()) continue;
171  for (const auto &stop : p2.path) {
172  /* find the node of p2 in p1 */
173  auto pos = lower_bound(p1.begin(), p1.end(), stop,
174  [](const Path_t &l, const Path_t &r)->bool {
175  return l.node < r.node;
176  });
177 
178  if (pos != p1.end()
179  && (stop.node == pos->node)
180  && (stop.agg_cost < pos->agg_cost)) {
181  /* both share the same node &
182  * the second path has the smallest
183  * So erasing from the first path */
184  p1.erase(pos);
185  }
186  }
187  }
188  }
189 
190  /* sort paths by start_id */
191  std::sort(paths.begin(), paths.end(),
192  [](const Path &e1, const Path &e2)->bool {
193  return e1.start_id() < e2.start_id();
194  });
195 
196  /* sort each path by agg_cost, node */
197  for (auto &path : paths) {
198  /* least influential data first */
199  std::sort(path.begin(), path.end(),
200  [](const Path_t &l, const Path_t &r)
201  { return l.node < r.node;});
202  /* preserve the order of what we did before */
203  std::stable_sort(path.begin(), path.end(),
204  [](const Path_t &l, const Path_t &r)
205  { return l.agg_cost < r.agg_cost;});
206  }
207  }
208 
209  friend size_t count_tuples(const std::deque< Path > &paths) {
210  size_t count(0);
211  for (const Path &e : paths) {
212  count += e.path.size();
213  }
214  return count;
215  }
216 
217 
218  template <typename G , typename V> Path(
219  G &graph,
220  V v_source,
221  double distance,
222  const std::vector<V> &predecessors,
223  const std::vector<double> &distances) :
224  m_start_id(graph.graph[v_source].id),
225  m_end_id(graph.graph[v_source].id) {
226  for (V i = 0; i < distances.size(); ++i) {
227  if (distances[i] <= distance) {
228  auto cost = distances[i] - distances[predecessors[i]];
229  auto edge_id = graph.get_edge_id(predecessors[i], i, cost);
230  push_back(
231  {graph[i].id,
232  edge_id, cost,
233  distances[i]});
234  }
235  }
236  }
237 
238 
239 
240  template <typename G , typename V> Path(
241  const G &graph,
242  const V v_source,
243  const V v_target,
244  const std::vector<V> &predecessors,
245  const std::vector<double> &distances,
246  bool only_cost,
247  bool normal = true) :
248  m_start_id(graph.graph[v_source].id),
249  m_end_id(graph.graph[v_target].id) {
250  if (!only_cost) {
251  complete_path(graph,
252  v_source,
253  v_target,
254  predecessors,
255  distances,
256  normal);
257  return;
258  }
259  /*
260  * only_cost
261  */
262  if (v_target != predecessors[v_target]) {
263  push_front(
264  {graph.graph[v_target].id,
265  -1,
266  distances[v_target],
267  distances[v_target]});
268  }
269  return;
270  }
271 
276  template <typename G , typename V> void complete_path(
277  const G &graph,
278  const V v_source,
279  const V v_target,
280  const std::vector<V> &predecessors,
281  const std::vector<double> &distances,
282  bool normal) {
283  // no path was found
284  if (v_target == predecessors[v_target]) {
285  return;
286  }
287 
288  /*
289  * set the target
290  */
291  auto target = v_target;
292 
293  /*
294  * the last stop is the target
295  */
296  push_front(
297  {graph.graph[target].id, -1,
298  0, distances[target]});
299 
300  /*
301  * get the path
302  */
303  while (target != v_source) {
304  /*
305  * done when the predecesor of the target is the target
306  */
307  if (target == predecessors[target]) break;
308 
309  /*
310  * Inserting values in the path
311  */
312  auto cost = distances[target] - distances[predecessors[target]];
313  auto vertex_id = graph.graph[predecessors[target]].id;
314  auto edge_id = normal?
315  graph.get_edge_id(predecessors[target], target, cost)
316  : graph.get_edge_id(target, predecessors[target], cost);
317 
318  push_front({
319  vertex_id,
320  edge_id,
321  cost,
322  distances[target] - cost});
323  target = predecessors[target];
324  }
325 
326  return;
327  }
328 };
329 
330 
331 #endif // SRC_COMMON_SRC_BASEPATH_SSEC_HPP_
int64_t m_end_id
void push_front(Path_t data)
std::deque< Path_t >::const_iterator ConstpthIt
Path_t & front()
int64_t m_start_id
Path(int64_t s_id, int64_t e_id)
void end_id(int64_t value)
friend size_t count_tuples(const std::deque< Path > &paths)
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)
void get_pg_dd_path(General_path_element_t **ret_path, size_t &sequence) const
Path_t & operator[](size_t i)
ConstpthIt end() const
void push_back(Path_t data)
void generate_postgres_data(General_path_element_t **postgres_data, size_t &sequence) const
const Path_t & back() const
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)
int64_t end_id() const
double tot_cost() const
void start_id(int64_t value)
int64_t node
Definition: pgr_types.h:97
pthIt end()
void empty_path(unsigned int d_vertex)
const Path_t & operator[](size_t i) const
void reverse()
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)
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...
int64_t start_id() const
const Path_t & front() const
pthIt begin()
bool empty() const
Path getSubpath(unsigned int j) const
size_t size() const
void clear()
ConstpthIt begin() const
void erase(pthIt pos)
std::deque< Path_t > path
Path_t & back()
double agg_cost
Definition: pgr_types.h:100
double m_tot_cost
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
void appendPath(const Path &o_path)
std::deque< Path_t >::iterator pthIt
Path(G &graph, V v_source, double distance, const std::vector< V > &predecessors, const std::vector< double > &distances)
bool isEqual(const Path &subpath) const