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