pgRouting
pgRouting extends the PostGIS / PostgreSQL geospatial database to provide geospatial routing functionality.
 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 #pragma once
26 #if defined(__MINGW32__) || defined(_MSC_VER)
27 #include <winsock2.h>
28 #include <windows.h>
29 #ifdef open
30 #undef open
31 #endif
32 #endif
33 
34 
35 #include <deque>
36 #include <iostream>
37 #include <algorithm>
38 #include "./pgr_types.h"
39 
40 class Path {
41  typedef std::deque< Path_t >::iterator pthIt;
42  typedef std::deque< Path_t >::const_iterator ConstpthIt;
43 
44  private:
45  std::deque< Path_t > path;
46  int64_t m_start_id;
47  int64_t m_end_id;
48  double m_tot_cost;
49 
50  public:
51  Path(): m_tot_cost(0) {}
52  Path(int64_t s_id, int64_t e_id)
53  : m_start_id(s_id), m_end_id(e_id), m_tot_cost(0)
54  {}
55  int64_t start_id() const {return m_start_id;}
56  void start_id(int64_t value) {m_start_id = value;}
57  int64_t end_id() const {return m_end_id;}
58  void end_id(int64_t value) {m_end_id = value;}
59  double tot_cost() const {return m_tot_cost;}
60 
61  size_t size() const {return path.size();}
62  bool empty() const {return path.empty();}
63 
64  void push_front(Path_t data);
65  void push_back(Path_t data);
66  const Path_t& operator[](size_t i) const {return path[i];}
67  Path_t& operator[](size_t i) {return path[i];}
68 
69  pthIt begin() {return path.begin();}
70  pthIt end() {return path.end();}
71  ConstpthIt begin() const {return path.begin();}
72  ConstpthIt end() const {return path.end();}
73 
74 
75  void erase(pthIt pos) {path.erase(pos);}
76  const Path_t& back() const {return path.back();}
77  Path_t& back() {return path.back();}
78  const Path_t& front() const {return path.front();}
79  Path_t& front() {return path.front();}
80 
81 
83  int64_t d_from,
84  int64_t d_to,
85  int64_t d_vertex,
86  int64_t d_edge,
87  double d_cost,
88  double d_tot_cost);
89 
90  void push_front(
91  int64_t d_vertex,
92  int64_t d_edge,
93  double d_cost,
94  double d_tot_cost);
95  void clear();
96 
97  friend std::ostream& operator<<(std::ostream &log, const Path &p);
98 
99 
100  void reverse();
101 
102  Path getSubpath(unsigned int j) const;
103 
104 
105  bool isEqual(const Path &subpath) const;
106  void appendPath(const Path &o_path);
107  void empty_path(unsigned int d_vertex);
108 
109  void get_pg_dd_path(
110  General_path_element_t **ret_path,
111  size_t &sequence) const;
112 
113  void get_pg_ksp_path(
114  General_path_element_t **ret_path,
115  size_t &sequence, int routeId) const;
116 
118  General_path_element_t **postgres_data,
119  size_t &sequence) const;
120 
121  friend size_t collapse_paths(
122  General_path_element_t **ret_path,
123  const std::deque< Path > &paths) {
124  size_t sequence = 0;
125  for (const Path &path : paths) {
126  if (path.path.size() > 0)
127  path.generate_postgres_data(ret_path, sequence);
128  }
129  return sequence;
130  }
131 
132 
133 
134  /*
135  * sort the paths by size from greater to smaller
136  * and sort each path by node
137  * all the nodes on p2 are going to be compared
138  * with the nodes of p1
139  *
140  * When both paths reach the node and p1.agg_cost > p2.agg_cost
141  * erase the node of p1
142  * (can't erase from p2 because we loose the iterators
143  * so in a future cycle it will be deleted)
144  *
145  * sort the paths by start_id,
146  */
147 
148  friend void equi_cost(std::deque< Path > &paths) {
149  /* sort paths by size: largest first */
150  std::sort(paths.begin(), paths.end(),
151  [](const Path &e1, const Path &e2)->bool {
152  return e2.size() < e1.size();
153  });
154 
155  /* sort each path by node: smaller id first */
156  for (auto &p : paths) {
157  if (p.size() < 2) continue;
158  std::sort(p.begin(), p.end(),
159  [](const Path_t &e1, const Path_t &e2)->bool {
160  return e1.node < e2.node;
161  });
162  }
163 
164  for (auto &p1 : paths) {
165  for (const auto &p2 : paths) {
166  if (p1.start_id() == p2.start_id()) continue;
167  for (const auto &stop : p2.path) {
168  /* find the node of p2 in p1 */
169  auto pos = lower_bound(p1.begin(), p1.end(), stop,
170  [](const Path_t &l, const Path_t &r)->bool {
171  return l.node < r.node;
172  });
173 
174  if (pos != p1.end()
175  && (stop.node == pos->node)
176  && (stop.agg_cost < pos->agg_cost)) {
177  /* both share the same node &
178  * the second path has the smallest
179  * So erasing from the first path */
180  p1.erase(pos);
181  }
182  }
183  }
184  }
185 
186  /* sort paths by start_id */
187  std::sort(paths.begin(), paths.end(),
188  [](const Path &e1, const Path &e2)->bool {
189  return e1.start_id() < e2.start_id();
190  });
191 
192  /* sort each path by agg_cost, node */
193  for (auto &path : paths) {
194  /* least influential data first */
195  std::sort(path.begin(), path.end(),
196  [](const Path_t &l, const Path_t &r)
197  { return l.node < r.node;});
198  /* preserve the order of what we did before */
199  std::stable_sort(path.begin(), path.end(),
200  [](const Path_t &l, const Path_t &r)
201  { return l.agg_cost < r.agg_cost;});
202  }
203  }
204 
205  friend size_t count_tuples(const std::deque< Path > &paths) {
206  size_t count(0);
207  for (const Path &e : paths) {
208  count += e.path.size();
209  }
210  return count;
211  }
212 };
213 
214 
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:83
pthIt end()
void empty_path(unsigned int d_vertex)
const Path_t & operator[](size_t i) const
void reverse()
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:86
double m_tot_cost
void appendPath(const Path &o_path)
std::deque< Path_t >::iterator pthIt
bool isEqual(const Path &subpath) const