PGROUTING  2.5
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
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
6 Mail: project@pgrouting.org
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 #include <boost/graph/adjacency_list.hpp>
39 #include <boost/graph/dijkstra_shortest_paths.hpp>
40 
41 #include <string>
42 #include <queue>
43 #include <utility>
44 #include <vector>
45 #include <limits>
46 #include <functional>
47 
48 
49 #include "cpp_common/pgr_assert.h"
50 
53 
54 
55 namespace pgrouting {
56 namespace bidirectional {
57 
58 
59 template < typename G >
61  protected:
62  typedef typename G::V V;
63  typedef typename G::E E;
64 
65  typedef std::pair<double, V> Cost_Vertex_pair;
66  typedef typename std::priority_queue<
68  std::vector<Cost_Vertex_pair>,
69  std::greater<Cost_Vertex_pair> > Priority_queue;
70 
71 
72  public:
73  explicit Pgr_bidirectional(G &pgraph):
74  graph(pgraph),
75  INF((std::numeric_limits<double>::max)()) {
76  m_log << "constructor\n";
77  };
78 
79  ~Pgr_bidirectional() = default;
80 
81  std::string log() const {return m_log.str();}
82  void clean_log() {m_log.clear();}
83  void clear() {
84  while (!forward_queue.empty()) forward_queue.pop();
85  while (!backward_queue.empty()) backward_queue.pop();
86 
87  backward_finished.clear();
88  backward_edge.clear();
89  backward_predecessor.clear();
90  backward_cost.clear();
91 
92  forward_finished.clear();
93  forward_edge.clear();
94  forward_predecessor.clear();
95  forward_cost.clear();
96  }
97 
98 
99  protected:
100  void initialize() {
101  m_log << "initializing\n";
102  clear();
103  forward_predecessor.resize(graph.num_vertices());
104  forward_finished.resize(graph.num_vertices(), false);
105  forward_edge.resize(graph.num_vertices(), -1);
106  forward_cost.resize(graph.num_vertices(), INF);
107  std::iota(forward_predecessor.begin(), forward_predecessor.end(), 0);
108 
109  backward_predecessor.resize(graph.num_vertices());
110  backward_finished.resize(graph.num_vertices(), false);
111  backward_edge.resize(graph.num_vertices(), -1);
112  backward_cost.resize(graph.num_vertices(), INF);
113  std::iota(backward_predecessor.begin(), backward_predecessor.end(), 0);
114 
115  v_min_node = -1;
116  best_cost = INF;
117  }
118 
119  Path bidirectional(bool only_cost) {
120  m_log << "bidir_astar\n";
121 
123 
124  forward_cost[v_source] = 0;
125  forward_queue.push(std::make_pair(0.0, v_source));
126 
127 
128  backward_cost[v_target] = 0;
129  backward_queue.push(std::make_pair(0.0, v_target));
130 
131  while (!forward_queue.empty() && !backward_queue.empty()) {
132  auto forward_node = forward_queue.top();
133  auto backward_node = backward_queue.top();
134  /*
135  * done: there is no path with lower cost
136  */
137  if (forward_node.first == INF || backward_node.first == INF) {
138  break;
139  }
140 
141  /*
142  * Explore from the cheapest side
143  */
144  if (backward_node.first < forward_node.first) {
145  backward_queue.pop();
146  if (!backward_finished[backward_node.second]) {
147  explore_backward(backward_node);
148  }
149  if (found(backward_node.second)) {
150  break;
151  }
152  } else {
153  forward_queue.pop();
154  if (!forward_finished[forward_node.second]) {
155  explore_forward(forward_node);
156  }
157  if (found(forward_node.second)) {
158  break;
159  }
160  }
161  }
162 
163  if (best_cost == INF) return Path();
164 
165  Path forward_path(
166  graph,
167  v_source,
168  v_min_node,
170  forward_cost,
171  only_cost,
172  true);
173  Path backward_path(
174  graph,
175  v_target,
176  v_min_node,
179  only_cost,
180  false);
181  m_log << forward_path;
182  backward_path.reverse();
183  m_log << backward_path;
184  forward_path.append(backward_path);
185  m_log << forward_path;
186  return forward_path;
187  }
188 
189 
190 
191  bool found(const V &node) {
192  /*
193  * Update common node
194  */
195  if (forward_finished[node] && backward_finished[node]) {
196  if (best_cost >= forward_cost[node] + backward_cost[node]) {
197  v_min_node = node;
198  best_cost = forward_cost[node] + backward_cost[node];
199  return false;
200  } else {
201  return true;
202  }
203  }
204  return false;
205  }
206 
207  virtual
208  void explore_forward(const Cost_Vertex_pair &node) = 0;
209 
210  virtual
211  void explore_backward(const Cost_Vertex_pair &node) = 0;
212 
213  protected:
214  G &graph;
218 
219  double INF;
220 
221  mutable std::ostringstream m_log;
224 
225  double best_cost;
226  bool cost_only;
227 
228  std::vector<bool> backward_finished;
229  std::vector<int64_t> backward_edge;
230  std::vector<V> backward_predecessor;
231  std::vector<double> backward_cost;
232 
233  std::vector<bool> forward_finished;
234  std::vector<int64_t> forward_edge;
235  std::vector<V> forward_predecessor;
236  std::vector<double> forward_cost;
237 };
238 
239 } // namespace bidirectional
240 } // namespace pgrouting
241 
242 #endif // INCLUDE_CPP_COMMON_PGR_BIDIRECTIONAL_HPP_
virtual void explore_forward(const Cost_Vertex_pair &node)=0
void reverse()
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...
std::priority_queue< Cost_Vertex_pair, std::vector< Cost_Vertex_pair >, std::greater< Cost_Vertex_pair > > Priority_queue
Assertions Handling.
virtual void explore_backward(const Cost_Vertex_pair &node)=0