PGROUTING  2.4
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
pgr_bdDijkstra.hpp
Go to the documentation of this file.
1 /*PGR-GNU*****************************************************************
2 
3 File: pgr_bdDijkstra.hpp
4 
5 Copyright (c) 2016 Celia Virginia Vergara Castillo
6 vicky_vergara@hotmail.com
7 
8 ------
9 
10 This program is free software; you can redistribute it and/or modify
11 it under the terms of the GNU General Public License as published by
12 the Free Software Foundation; either version 2 of the License, or
13 (at your option) any later version.
14 
15 This program is distributed in the hope that it will be useful,
16 but WITHOUT ANY WARRANTY; without even the implied warranty of
17 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 GNU General Public License for more details.
19 
20 You should have received a copy of the GNU General Public License
21 along with this program; if not, write to the Free Software
22 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
23 
24  ********************************************************************PGR-GNU*/
25 
26 #ifndef SRC_BDDIJKSTRA_SRC_PGR_BDDIJKSTRA_HPP_
27 #define SRC_BDDIJKSTRA_SRC_PGR_BDDIJKSTRA_HPP_
28 #pragma once
29 
30 
31 #include <boost/config.hpp>
32 #include <boost/graph/adjacency_list.hpp>
33 #include <boost/graph/dijkstra_shortest_paths.hpp>
34 
35 #include <string>
36 #include <queue>
37 #include <utility>
38 #include <vector>
39 #include <limits>
40 #include <functional>
41 
42 
43 #include "./../../common/src/pgr_assert.h"
44 #include "./../../common/src/basePath_SSEC.hpp"
45 #include "./../../common/src/pgr_base_graph.hpp"
46 
47 
48 
49 
50 template < typename G >
52  typedef typename G::V V;
53  typedef typename G::E E;
54 
55  typedef std::pair<double, V> Cost_Vertex_pair;
56  typedef typename std::priority_queue<
58  std::vector<Cost_Vertex_pair>,
59  std::greater<Cost_Vertex_pair> > Priority_queue;
60 
61 
62  public:
63  explicit Pgr_bdDijkstra(G &pgraph):
64  graph(pgraph),
65  INF((std::numeric_limits<double>::max)()) {
66  m_log << "constructor\n";
67  };
68 
69  ~Pgr_bdDijkstra() = default;
70 
71 
72  Path pgr_bdDijkstra(V start_vertex, V end_vertex, bool only_cost) {
73  m_log << "pgr_bdDijkstra\n";
74  v_source = start_vertex;
75  v_target = end_vertex;
76 
77  if (v_source == v_target) {
78  return Path(v_source, v_target);
79  }
80  return bidir_dijkstra(only_cost);
81  }
82 
83  std::string log() const {return m_log.str();}
84  void clean_log() {m_log.clear();}
85  void clear() {
86  while (!forward_queue.empty()) forward_queue.pop();
87  while (!backward_queue.empty()) backward_queue.pop();
88 
89  backward_finished.clear();
90  backward_edge.clear();
91  backward_predecessor.clear();
92  backward_cost.clear();
93 
94  forward_finished.clear();
95  forward_edge.clear();
96  forward_predecessor.clear();
97  forward_cost.clear();
98  }
99 
100 
101  private:
102  void initialize() {
103  m_log << "initializing\n";
104  clear();
105  forward_predecessor.resize(graph.num_vertices());
106  forward_finished.resize(graph.num_vertices(), false);
107  forward_edge.resize(graph.num_vertices(), -1);
108  forward_cost.resize(graph.num_vertices(), INF);
109  std::iota(forward_predecessor.begin(), forward_predecessor.end(), 0);
110 
111  backward_predecessor.resize(graph.num_vertices());
112  backward_finished.resize(graph.num_vertices(), false);
113  backward_edge.resize(graph.num_vertices(), -1);
114  backward_cost.resize(graph.num_vertices(), INF);
115  std::iota(backward_predecessor.begin(), backward_predecessor.end(), 0);
116 
117  v_min_node = -1;
118  best_cost = INF;
119  }
120 
121  Path bidir_dijkstra(bool only_cost) {
122  m_log << "bidir_dijkstra\n";
123 
125 
126  forward_cost[v_source] = 0;
127  forward_queue.push(std::make_pair(0.0, v_source));
128 
129  backward_cost[v_target] = 0;
130  backward_queue.push(std::make_pair(0.0, v_target));
131 
132  while (!forward_queue.empty() && !backward_queue.empty()) {
133  auto forward_node = forward_queue.top();
134  auto backward_node = backward_queue.top();
135  /*
136  * done: there is no path with lower cost
137  */
138  if (forward_node.first == INF || backward_node.first == INF) {
139  break;
140  }
141 
142  /*
143  * Explore from the cheapest side
144  */
145  if (backward_node.first < forward_node.first) {
146  backward_queue.pop();
147  if (!backward_finished[backward_node.second]) {
148  explore_backward(backward_node);
149  }
150  if (found(backward_node.second)) {
151  break;
152  }
153  } else {
154  forward_queue.pop();
155  if (!forward_finished[forward_node.second]) {
156  explore_forward(forward_node);
157  }
158  if (found(forward_node.second)) {
159  break;
160  }
161  }
162  }
163 
164  if (best_cost == INF) return Path();
165 
166  Path forward_path(
167  graph,
168  v_source,
169  v_min_node,
171  forward_cost,
172  only_cost,
173  true);
174  Path backward_path(
175  graph,
176  v_target,
177  v_min_node,
180  only_cost,
181  false);
182  m_log << forward_path;
183  backward_path.reverse();
184  m_log << backward_path;
185  forward_path.append(backward_path);
186  m_log << forward_path;
187  return forward_path;
188  }
189 
190 
191 
192  bool found(const V &node) {
193  /*
194  * Update common node
195  */
196  if (forward_finished[node] && backward_finished[node]) {
197  if (best_cost >= forward_cost[node] + backward_cost[node]) {
198  v_min_node = node;
199  best_cost = forward_cost[node] + backward_cost[node];
200  return false;
201  } else {
202  return true;
203  }
204  }
205  return false;
206  }
207 
208  void explore_forward(const Cost_Vertex_pair &node) {
209  typename G::EO_i out, out_end;
210 
211  auto current_cost = node.first;
212  auto current_node = node.second;
213 
214  for (boost::tie(out, out_end) = out_edges(current_node, graph.graph);
215  out != out_end; ++out) {
216  auto edge_cost = graph[*out].cost;
217  auto next_node = graph.adjacent(current_node, *out);
218 
219  if (forward_finished[next_node]) continue;
220 
221  if (edge_cost + current_cost < forward_cost[next_node]) {
222  forward_cost[next_node] = edge_cost + current_cost;
223  forward_predecessor[next_node] = current_node;
224  forward_edge[next_node] = graph[*out].id;
225  forward_queue.push({forward_cost[next_node], next_node});
226  }
227  }
228  forward_finished[current_node] = true;
229  }
230 
231  void explore_backward(const Cost_Vertex_pair &node) {
232  typename G::EI_i in, in_end;
233 
234  auto current_cost = node.first;
235  auto current_node = node.second;
236 
237  for (boost::tie(in, in_end) = in_edges(current_node, graph.graph);
238  in != in_end; ++in) {
239  auto edge_cost = graph[*in].cost;
240  auto next_node = graph.adjacent(current_node, *in);
241 
242  if (backward_finished[next_node]) continue;
243 
244  if (edge_cost + current_cost < backward_cost[next_node]) {
245  backward_cost[next_node] = edge_cost + current_cost;
246  backward_predecessor[next_node] = current_node;
247  backward_edge[next_node] = graph[*in].id;
248  backward_queue.push({backward_cost[next_node], next_node});
249  }
250  }
251  backward_finished[current_node] = true;
252  }
253 
254 
255  private:
256  G &graph;
260 
261  double INF;
262 
263  mutable std::ostringstream m_log;
266 
267  double best_cost;
268  bool cost_only;
269 
270  std::vector<bool> backward_finished;
271  std::vector<int64_t> backward_edge;
272  std::vector<V> backward_predecessor;
273  std::vector<double> backward_cost;
274 
275  std::vector<bool> forward_finished;
276  std::vector<int64_t> forward_edge;
277  std::vector<V> forward_predecessor;
278  std::vector<double> forward_cost;
279 };
280 
281 #endif // SRC_BDDIJKSTRA_SRC_PGR_BDDIJKSTRA_HPP_
bool found(const V &node)
std::string log() const
V v_target
target descriptor
std::vector< int64_t > forward_edge
std::vector< V > forward_predecessor
Priority_queue forward_queue
V v_source
source descriptor
Pgr_bdDijkstra(G &pgraph)
std::vector< double > backward_cost
V v_min_node
target descriptor
std::vector< double > forward_cost
std::vector< V > backward_predecessor
double INF
infinity
~Pgr_bdDijkstra()=default
std::vector< bool > forward_finished
std::vector< int64_t > backward_edge
std::ostringstream m_log
void reverse()
Path pgr_bdDijkstra(V start_vertex, V end_vertex, bool only_cost)
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...
void explore_forward(const Cost_Vertex_pair &node)
Priority_queue backward_queue
void explore_backward(const Cost_Vertex_pair &node)
std::priority_queue< Cost_Vertex_pair, std::vector< Cost_Vertex_pair >, std::greater< Cost_Vertex_pair > > Priority_queue
std::pair< double, V > Cost_Vertex_pair
std::vector< bool > backward_finished
Path bidir_dijkstra(bool only_cost)