PGROUTING  2.6
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 
27 #ifndef INCLUDE_CPP_COMMON_BASEPATH_SSEC_HPP_
28 #define INCLUDE_CPP_COMMON_BASEPATH_SSEC_HPP_
29 #pragma once
30 
31 
32 #include <boost/config.hpp>
33 #include <boost/graph/adjacency_list.hpp>
34 
35 
36 #include <deque>
37 #include <vector>
38 #include <iostream>
39 #include <algorithm>
40 
42 #include "cpp_common/path_t.h"
44 
45 
46 class Path {
47  typedef std::deque< Path_t >::iterator pthIt;
48  typedef std::deque< Path_t >::const_iterator ConstpthIt;
49 
50  private:
51  std::deque< Path_t > path;
52  int64_t m_start_id;
53  int64_t m_end_id;
54  double m_tot_cost;
55 
56  public:
57  Path(): m_tot_cost(0) {}
58  Path(int64_t s_id, int64_t e_id)
59  : m_start_id(s_id), m_end_id(e_id), m_tot_cost(0)
60  {}
61  Path(const Path&) = default;
62 
63  int64_t start_id() const {return m_start_id;}
64  void start_id(int64_t value) {m_start_id = value;}
65  int64_t end_id() const {return m_end_id;}
66  void end_id(int64_t value) {m_end_id = value;}
67  double tot_cost() const {return m_tot_cost;}
68 
69  size_t size() const {return path.size();}
70  bool empty() const {return path.empty();}
71 
72  void push_front(Path_t data);
73  void push_back(Path_t data);
74  const Path_t& operator[](size_t i) const {return path[i];}
75  Path_t& operator[](size_t i) {return path[i];}
76  Path& renumber_vertices(int64_t value);
77 
78  pthIt begin() {return path.begin();}
79  pthIt end() {return path.end();}
80  ConstpthIt begin() const {return path.begin();}
81  ConstpthIt end() const {return path.end();}
82 
83 
84  void erase(pthIt pos) {path.erase(pos);}
85  const Path_t& back() const {return path.back();}
86  Path_t& back() {return path.back();}
87  const Path_t& front() const {return path.front();}
88  Path_t& front() {return path.front();}
89  void sort_by_node_agg_cost();
90 
91  void recalculate_agg_cost();
92 
93 
95  int64_t d_from,
96  int64_t d_to,
97  int64_t d_vertex,
98  int64_t d_edge,
99  double d_cost,
100  double d_tot_cost);
101 
102  void push_front(
103  int64_t d_vertex,
104  int64_t d_edge,
105  double d_cost,
106  double d_tot_cost);
107  void clear();
108 
109  friend std::ostream& operator<<(std::ostream &log, const Path &p);
110 
111 
112  void reverse();
113 
114  Path getSubpath(unsigned int j) const;
115 
116 
117  bool isEqual(const Path &subpath) const;
118  void appendPath(const Path &o_path);
119  void append(const Path &other);
120  void empty_path(unsigned int d_vertex);
121 
122  void get_pg_dd_path(
123  General_path_element_t **ret_path,
124  size_t &sequence) const;
125 
126  void get_pg_ksp_path(
127  General_path_element_t **ret_path,
128  size_t &sequence, int routeId) const;
129 
131  General_path_element_t **postgres_data,
132  size_t &sequence) const;
133 
134  friend size_t collapse_paths(
135  General_path_element_t **ret_path,
136  const std::deque< Path > &paths);
137 
138 
140  friend void equi_cost(std::deque< Path > &paths);
142  friend size_t count_tuples(const std::deque< Path > &paths);
143 
144  /*
145  * TEMPLATES
146  */
147  template <typename G , typename V> Path(
148  G &graph,
149  int64_t source,
150  double distance,
151  const std::vector<V> &predecessors,
152  const std::vector<double> &distances) :
153  m_start_id(source),
154  m_end_id(source) {
155  for (V i = 0; i < distances.size(); ++i) {
156  if (distances[i] <= distance) {
157  auto cost = distances[i] - distances[predecessors[i]];
158  auto edge_id = graph.get_edge_id(predecessors[i], i, cost);
159  push_back(
160  {graph[i].id,
161  edge_id, cost,
162  distances[i]});
163  }
164  }
165  }
166 
167 
168  template <typename G , typename V> Path(
169  G &graph,
170  V v_source,
171  double distance,
172  const std::vector<V> &predecessors,
173  const std::vector<double> &distances) :
174  m_start_id(graph.graph[v_source].id),
175  m_end_id(graph.graph[v_source].id) {
176  for (V i = 0; i < distances.size(); ++i) {
177  if (distances[i] <= distance) {
178  auto cost = distances[i] - distances[predecessors[i]];
179  auto edge_id = graph.get_edge_id(predecessors[i], i, cost);
180  push_back(
181  {graph[i].id,
182  edge_id, cost,
183  distances[i]});
184  }
185  }
186  }
187 
188 
189 
190  template <typename G , typename V> Path(
191  const G &graph,
192  const V v_source,
193  const V v_target,
194  const std::vector<V> &predecessors,
195  const std::vector<double> &distances,
196  bool only_cost,
197  bool normal = true) :
198  m_start_id(graph.graph[v_source].id),
199  m_end_id(graph.graph[v_target].id) {
200  if (!only_cost) {
201  complete_path(graph,
202  v_source,
203  v_target,
204  predecessors,
205  distances,
206  normal);
207  return;
208  }
209  /*
210  * only_cost
211  */
212  if (v_target != predecessors[v_target]) {
213  push_front(
214  {graph.graph[v_target].id,
215  -1,
216  distances[v_target],
217  distances[v_target]});
218  }
219  return;
220  }
221 
226  template <typename G , typename V> void complete_path(
227  const G &graph,
228  const V v_source,
229  const V v_target,
230  const std::vector<V> &predecessors,
231  const std::vector<double> &distances,
232  bool normal) {
233  // no path was found
234  if (v_target == predecessors[v_target]) {
235  return;
236  }
237 
238  /*
239  * set the target
240  */
241  auto target = v_target;
242 
243  /*
244  * the last stop is the target
245  */
246  push_front(
247  {graph.graph[target].id, -1,
248  0, distances[target]});
249 
250  /*
251  * get the path
252  */
253  while (target != v_source) {
254  /*
255  * done when the predecesor of the target is the target
256  */
257  if (target == predecessors[target]) break;
258 
259  /*
260  * Inserting values in the path
261  */
262  auto cost = distances[target] - distances[predecessors[target]];
263  auto vertex_id = graph.graph[predecessors[target]].id;
264  auto edge_id = normal?
265  graph.get_edge_id(predecessors[target], target, cost)
266  : graph.get_edge_id(target, predecessors[target], cost);
267 
268  push_front({
269  vertex_id,
270  edge_id,
271  cost,
272  distances[target] - cost});
273  target = predecessors[target];
274  }
275 
276  return;
277  }
278 };
279 
280 
281 #endif // INCLUDE_CPP_COMMON_BASEPATH_SSEC_HPP_
int64_t m_end_id
void push_front(Path_t data)
std::deque< Path_t >::const_iterator ConstpthIt
Path_t & front()
Path(G &graph, int64_t source, double distance, const std::vector< V > &predecessors, const std::vector< double > &distances)
int64_t m_start_id
void recalculate_agg_cost()
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)
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
Path_t & operator[](size_t i)
ConstpthIt end() const
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
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)
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...
Definition: path_t.h:36
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 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