PGROUTING  3.2
pgr_bidirectional.hpp
Go to the documentation of this file.
1 /*PGR-GNU*****************************************************************
2 File: pgr_bdAstar.hpp
3 
4 Generated with Template by:
5 Copyright (c) 2015 pgRouting developers
7 
8 Function's developer:
9 Copyright (c) 2015 Celia Virginia Vergara Castillo
10 Mail:
11 
12 ------
13 
14 This program is free software; you can redistribute it and/or modify
15 it under the terms of the GNU General Public License as published by
16 the Free Software Foundation; either version 2 of the License, or
17 (at your option) any later version.
18 
19 This program is distributed in the hope that it will be useful,
20 but WITHOUT ANY WARRANTY; without even the implied warranty of
21 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
22 GNU General Public License for more details.
23 
24 You should have received a copy of the GNU General Public License
25 along with this program; if not, write to the Free Software
26 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
27 
28  ********************************************************************PGR-GNU*/
29 
32 #ifndef INCLUDE_CPP_COMMON_PGR_BIDIRECTIONAL_HPP_
33 #define INCLUDE_CPP_COMMON_PGR_BIDIRECTIONAL_HPP_
34 #pragma once
35 
36 
37 #include <boost/config.hpp>
38 
39 #include <boost/graph/dijkstra_shortest_paths.hpp>
40 #include <boost/graph/adjacency_list.hpp>
41 
42 #include <string>
43 #include <queue>
44 #include <utility>
45 #include <vector>
46 #include <limits>
47 #include <functional>
48 #include <numeric>
49 
50 
51 #include "cpp_common/pgr_assert.h"
52 
55 
56 
57 namespace pgrouting {
58 namespace bidirectional {
59 
60 
61 template < typename G >
63  protected:
64  typedef typename G::V V;
65  typedef typename G::E E;
66 
67  typedef std::pair<double, V> Cost_Vertex_pair;
68  typedef typename std::priority_queue<
70  std::vector<Cost_Vertex_pair>,
71  std::greater<Cost_Vertex_pair> > Priority_queue;
72 
73 
74  public:
75  explicit Pgr_bidirectional(G &pgraph):
76  graph(pgraph),
77  INF((std::numeric_limits<double>::max)()),
78  best_cost(0) {
79  m_log << "constructor\n";
80  }
81 
82  ~Pgr_bidirectional() = default;
83 
84  std::string log() const {return m_log.str();}
85  void clean_log() {m_log.clear();}
86  void clear() {
87  while (!forward_queue.empty()) forward_queue.pop();
88  while (!backward_queue.empty()) backward_queue.pop();
89 
90  backward_finished.clear();
91  backward_edge.clear();
92  backward_predecessor.clear();
93  backward_cost.clear();
94 
95  forward_finished.clear();
96  forward_edge.clear();
97  forward_predecessor.clear();
98  forward_cost.clear();
99  }
100 
101 
102  protected:
103  void initialize() {
104  m_log << "initializing\n";
105  clear();
106  forward_predecessor.resize(graph.num_vertices());
107  forward_finished.resize(graph.num_vertices(), false);
108  forward_edge.resize(graph.num_vertices(), -1);
109  forward_cost.resize(graph.num_vertices(), INF);
110  std::iota(forward_predecessor.begin(), forward_predecessor.end(), 0);
111 
112  backward_predecessor.resize(graph.num_vertices());
113  backward_finished.resize(graph.num_vertices(), false);
114  backward_edge.resize(graph.num_vertices(), -1);
115  backward_cost.resize(graph.num_vertices(), INF);
116  std::iota(backward_predecessor.begin(), backward_predecessor.end(), 0);
117 
118  v_min_node = 0;
119  best_cost = INF;
120  }
121 
122  Path bidirectional(bool only_cost) {
123  m_log << "bidir_astar\n";
124 
126 
127  forward_cost[v_source] = 0;
128  forward_queue.push(std::make_pair(0.0, v_source));
129 
130 
131  backward_cost[v_target] = 0;
132  backward_queue.push(std::make_pair(0.0, v_target));
133 
134  while (!forward_queue.empty() && !backward_queue.empty()) {
135  auto forward_node = forward_queue.top();
136  auto backward_node = backward_queue.top();
137  /*
138  * done: there is no path with lower cost
139  */
140  if (forward_node.first == INF || backward_node.first == INF) {
141  break;
142  }
143 
144  /*
145  * Explore from the cheapest side
146  */
147  if (backward_node.first < forward_node.first) {
148  backward_queue.pop();
149  if (!backward_finished[backward_node.second]) {
150  explore_backward(backward_node);
151  }
152  if (found(backward_node.second)) {
153  break;
154  }
155  } else {
156  forward_queue.pop();
157  if (!forward_finished[forward_node.second]) {
158  explore_forward(forward_node);
159  }
160  if (found(forward_node.second)) {
161  break;
162  }
163  }
164  }
165 
166  if (best_cost == INF) return Path();
167 
168  Path forward_path(
169  graph,
170  v_source,
171  v_min_node,
173  forward_cost,
174  false,
175  true);
176  Path backward_path(
177  graph,
178  v_target,
179  v_min_node,
182  false,
183  false);
184  m_log << forward_path;
185  backward_path.reverse();
186  m_log << backward_path;
187  forward_path.append(backward_path);
188  auto p = Path(graph, forward_path, only_cost);
189  m_log << forward_path;
190  m_log << p;
191  return p;
192  }
193 
194 
195 
196  bool found(const V &node) {
197  /*
198  * Update common node
199  */
200  if (forward_finished[node] && backward_finished[node]) {
201  if (best_cost >= forward_cost[node] + backward_cost[node]) {
202  v_min_node = node;
203  best_cost = forward_cost[node] + backward_cost[node];
204  return false;
205  } else {
206  return true;
207  }
208  }
209  return false;
210  }
211 
212  virtual
213  void explore_forward(const Cost_Vertex_pair &node) = 0;
214 
215  virtual
216  void explore_backward(const Cost_Vertex_pair &node) = 0;
217 
218  protected:
223 
224  double INF;
225 
226  double best_cost;
227  bool cost_only;
228 
229  mutable std::ostringstream m_log;
232 
233  std::vector<bool> backward_finished;
234  std::vector<int64_t> backward_edge;
235  std::vector<V> backward_predecessor;
236  std::vector<double> backward_cost;
237 
238  std::vector<bool> forward_finished;
239  std::vector<int64_t> forward_edge;
240  std::vector<V> forward_predecessor;
241  std::vector<double> forward_cost;
242 };
243 
244 } // namespace bidirectional
245 } // namespace pgrouting
246 
247 #endif // INCLUDE_CPP_COMMON_PGR_BIDIRECTIONAL_HPP_
Path
Definition: basePath_SSEC.hpp:47
pgrouting::bidirectional::Pgr_bidirectional::forward_edge
std::vector< int64_t > forward_edge
Definition: pgr_bidirectional.hpp:239
pgr_base_graph.hpp
pgrouting::bidirectional::Pgr_bidirectional::backward_predecessor
std::vector< V > backward_predecessor
Definition: pgr_bidirectional.hpp:235
pgrouting::bidirectional::Pgr_bidirectional::clean_log
void clean_log()
Definition: pgr_bidirectional.hpp:85
pgrouting::bidirectional::Pgr_bidirectional::forward_queue
Priority_queue forward_queue
Definition: pgr_bidirectional.hpp:230
pgrouting::bidirectional::Pgr_bidirectional::explore_backward
virtual void explore_backward(const Cost_Vertex_pair &node)=0
pgrouting::bidirectional::Pgr_bidirectional::Pgr_bidirectional
Pgr_bidirectional(G &pgraph)
Definition: pgr_bidirectional.hpp:75
pgrouting::bidirectional::Pgr_bidirectional::m_log
std::ostringstream m_log
Definition: pgr_bidirectional.hpp:229
pgrouting::bidirectional::Pgr_bidirectional::v_target
V v_target
target descriptor
Definition: pgr_bidirectional.hpp:221
pgrouting::bidirectional::Pgr_bidirectional::backward_finished
std::vector< bool > backward_finished
Definition: pgr_bidirectional.hpp:233
Path::reverse
void reverse()
Definition: basePath_SSEC.cpp:57
pgrouting::bidirectional::Pgr_bidirectional::Cost_Vertex_pair
std::pair< double, V > Cost_Vertex_pair
Definition: pgr_bidirectional.hpp:67
pgrouting::bidirectional::Pgr_bidirectional::v_source
V v_source
source descriptor
Definition: pgr_bidirectional.hpp:220
pgrouting::bidirectional::Pgr_bidirectional
Definition: pgr_bidirectional.hpp:62
pgrouting::bidirectional::Pgr_bidirectional::INF
double INF
infinity
Definition: pgr_bidirectional.hpp:224
pgrouting::bidirectional::Pgr_bidirectional::found
bool found(const V &node)
Definition: pgr_bidirectional.hpp:196
pgrouting::bidirectional::Pgr_bidirectional::graph
G & graph
Definition: pgr_bidirectional.hpp:219
pgrouting::alphashape::E
boost::graph_traits< BG >::edge_descriptor E
Definition: pgr_alphaShape.h:57
pgrouting::bidirectional::Pgr_bidirectional::forward_cost
std::vector< double > forward_cost
Definition: pgr_bidirectional.hpp:241
pgrouting::bidirectional::Pgr_bidirectional::v_min_node
V v_min_node
target descriptor
Definition: pgr_bidirectional.hpp:222
pgr_assert.h
An assert functionality that uses C++ throw().
pgrouting::bidirectional::Pgr_bidirectional::forward_finished
std::vector< bool > forward_finished
Definition: pgr_bidirectional.hpp:238
pgrouting::bidirectional::Pgr_bidirectional::V
G::V V
Definition: pgr_bidirectional.hpp:64
pgrouting::bidirectional::Pgr_bidirectional::bidirectional
Path bidirectional(bool only_cost)
Definition: pgr_bidirectional.hpp:122
pgrouting::bidirectional::Pgr_bidirectional::~Pgr_bidirectional
~Pgr_bidirectional()=default
pgrouting::bidirectional::Pgr_bidirectional::backward_cost
std::vector< double > backward_cost
Definition: pgr_bidirectional.hpp:236
pgrouting::bidirectional::Pgr_bidirectional::backward_queue
Priority_queue backward_queue
Definition: pgr_bidirectional.hpp:231
pgrouting::alphashape::G
graph::Pgr_base_graph< BG, XY_vertex, Basic_edge > G
Definition: pgr_alphaShape.h:56
pgrouting::bidirectional::Pgr_bidirectional::Priority_queue
std::priority_queue< Cost_Vertex_pair, std::vector< Cost_Vertex_pair >, std::greater< Cost_Vertex_pair > > Priority_queue
Definition: pgr_bidirectional.hpp:71
pgrouting::bidirectional::Pgr_bidirectional::best_cost
double best_cost
Definition: pgr_bidirectional.hpp:226
pgrouting::bidirectional::Pgr_bidirectional::E
G::E E
Definition: pgr_bidirectional.hpp:65
pgrouting::bidirectional::Pgr_bidirectional::cost_only
bool cost_only
Definition: pgr_bidirectional.hpp:227
pgrouting::bidirectional::Pgr_bidirectional::clear
void clear()
Definition: pgr_bidirectional.hpp:86
pgrouting::alphashape::V
boost::graph_traits< BG >::vertex_descriptor V
Definition: pgr_alphaShape.h:58
Path::append
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: basePath_SSEC.cpp:192
pgrouting
Book keeping class for swapping orders between vehicles.
Definition: pgr_alphaShape.cpp:56
pgrouting::bidirectional::Pgr_bidirectional::log
std::string log() const
Definition: pgr_bidirectional.hpp:84
pgrouting::bidirectional::Pgr_bidirectional::forward_predecessor
std::vector< V > forward_predecessor
Definition: pgr_bidirectional.hpp:240
pgrouting::bidirectional::Pgr_bidirectional::initialize
void initialize()
Definition: pgr_bidirectional.hpp:103
pgrouting::bidirectional::Pgr_bidirectional::backward_edge
std::vector< int64_t > backward_edge
Definition: pgr_bidirectional.hpp:234
pgrouting::bidirectional::Pgr_bidirectional::explore_forward
virtual void explore_forward(const Cost_Vertex_pair &node)=0
basePath_SSEC.hpp