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