PGROUTING  2.5
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
pgr_bdAstar.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 
30 #ifndef INCLUDE_BDASTAR_PGR_BDASTAR_HPP_
31 #define INCLUDE_BDASTAR_PGR_BDASTAR_HPP_
32 #pragma once
33 
34 
36 
37 #include <string>
38 #include <queue>
39 #include <utility>
40 #include <vector>
41 #include <limits>
42 #include <functional>
43 
45 
46 namespace pgrouting {
47 namespace bidirectional {
48 
49 template < typename G >
50 class Pgr_bdAstar : public Pgr_bidirectional<G> {
51  typedef typename Pgr_bidirectional<G>::V V;
52  typedef typename Pgr_bidirectional<G>::E E;
54 
59 
65 
71 
72 
74 
75 
76  public:
77  explicit Pgr_bdAstar(G &pgraph) :
78  Pgr_bidirectional<G>(pgraph),
79  m_heuristic(5),
80  m_factor(1.0) {
81  m_log << "pgr_bdAstar constructor\n";
82  }
83 
84  ~Pgr_bdAstar() = default;
85 
86  Path pgr_bdAstar(V start_vertex, V end_vertex,
87  int heuristic,
88  double factor,
89  double epsilon,
90  bool only_cost) {
91  m_log << "pgr_bdAstar\n";
92  v_source = start_vertex;
93  v_target = end_vertex;
95  m_factor = factor * epsilon;
96 
97  if (v_source == v_target) {
98  return Path(v_source, v_target);
99  }
100  return bidirectional(only_cost);
101  }
102 
105 
106  private:
107  void explore_forward(const Cost_Vertex_pair &node) {
108  typename G::EO_i out, out_end;
109 
110  auto current_cost = node.first;
111  auto current_node = node.second;
112 
113  for (boost::tie(out, out_end) = out_edges(current_node, graph.graph);
114  out != out_end; ++out) {
115  auto edge_cost = graph[*out].cost;
116  auto next_node = graph.adjacent(current_node, *out);
117 
118  if (forward_finished[next_node]) continue;
119 
120  if (edge_cost + current_cost < forward_cost[next_node]) {
121  forward_cost[next_node] = edge_cost + current_cost;
122  forward_predecessor[next_node] = current_node;
123  forward_edge[next_node] = graph[*out].id;
124  forward_queue.push({
125  forward_cost[next_node]
126  + heuristic(next_node, v_target),
127  next_node});
128  }
129  }
130  forward_finished[current_node] = true;
131  }
132 
133  void explore_backward(const Cost_Vertex_pair &node) {
134  typename G::EI_i in, in_end;
135 
136  auto current_cost = node.first;
137  auto current_node = node.second;
138 
139  for (boost::tie(in, in_end) = in_edges(current_node, graph.graph);
140  in != in_end; ++in) {
141  auto edge_cost = graph[*in].cost;
142  auto next_node = graph.adjacent(current_node, *in);
143 
144  if (backward_finished[next_node]) continue;
145 
146  if (edge_cost + current_cost < backward_cost[next_node]) {
147  backward_cost[next_node] = edge_cost + current_cost;
148  backward_predecessor[next_node] = current_node;
149  backward_edge[next_node] = graph[*in].id;
150  backward_queue.push({
151  backward_cost[next_node]
152  + heuristic(next_node, v_source),
153  next_node});
154  }
155  }
156  backward_finished[current_node] = true;
157  }
158 
159 
160  double heuristic(V v, V u) {
161  if (m_heuristic == 0) return 0;
162 
163  double dx = graph[v].x() - graph[u].x();
164  double dy = graph[v].y() - graph[u].y();
165  double current;
166 
167  switch (m_heuristic) {
168  case 0:
169  current = 0;
170  case 1:
171  current = std::fabs((std::max)(dx, dy)) * m_factor;
172  case 2:
173  current = std::fabs((std::min)(dx, dy)) * m_factor;
174  case 3:
175  current = (dx * dx + dy * dy) * m_factor * m_factor;
176  case 4:
177  current = std::sqrt(dx * dx + dy * dy) * m_factor;
178  case 5:
179  current = (std::fabs(dx) + std::fabs(dy)) * m_factor;
180  default:
181  current = 0;
182  }
183  return current;
184  }
185 
186  private:
188  double m_factor;
189 };
190 
191 } // namespace bidirectional
192 } // namespace pgrouting
193 
194 #endif // INCLUDE_BDASTAR_PGR_BDASTAR_HPP_
void explore_backward(const Cost_Vertex_pair &node)
Pgr_bidirectional< G >::Cost_Vertex_pair Cost_Vertex_pair
Definition: pgr_bdAstar.hpp:53
Pgr_bidirectional< G >::E E
Definition: pgr_bdAstar.hpp:52
Path pgr_bdAstar(V start_vertex, V end_vertex, int heuristic, double factor, double epsilon, bool only_cost)
Definition: pgr_bdAstar.hpp:86
Pgr_bidirectional< G >::V V
Definition: pgr_bdAstar.hpp:51
void explore_forward(const Cost_Vertex_pair &node)