PGROUTING  2.4
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
pgr_astar.hpp
Go to the documentation of this file.
1 /*PGR-GNU*****************************************************************
2 
3 File: pgr_astar.hpp
4 
5 Copyright (c) 2015 Vicky Vergara
6 Mail: vicky_vergara@hotmail.com
7 Mail: project@pgrouting.org
8 
9 ------
10 
11 This program is free software; you can redistribute it and/or modify
12 it under the terms of the GNU General Public License as published by
13 the Free Software Foundation; either version 2 of the License, or
14 (at your option) any later version.
15 
16 This program is distributed in the hope that it will be useful,
17 but WITHOUT ANY WARRANTY; without even the implied warranty of
18 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19 GNU General Public License for more details.
20 
21 You should have received a copy of the GNU General Public License
22 along with this program; if not, write to the Free Software
23 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
24 
25 ********************************************************************PGR-GNU*/
26 
27 #ifndef SRC_ASTAR_SRC_PGR_ASTAR_HPP_
28 #define SRC_ASTAR_SRC_PGR_ASTAR_HPP_
29 #pragma once
30 
31 #include <boost/config.hpp>
32 #include <boost/graph/graph_traits.hpp>
33 #include <boost/graph/adjacency_list.hpp>
34 #include <boost/graph/astar_search.hpp>
35 
36 #include <cmath>
37 
38 
39 #include <deque>
40 #include <limits>
41 #include <algorithm>
42 #include <vector>
43 #include <set>
44 
45 #include "./../../common/src/basePath_SSEC.hpp"
46 #include "./../../common/src/pgr_base_graph.hpp"
47 
48 namespace pgrouting {
49 namespace algorithms {
50 
51 template < class G >
52 class Pgr_astar {
53  public:
54  typedef typename G::V V;
55  typedef typename G::B_G B_G;
56 
57 
58  void clear() {
59  predecessors.clear();
60  distances.clear();
61  }
62 
64 
65  Path astar(
68  G &graph,
69  int64_t start_vertex,
70  int64_t end_vertex,
71  int heuristic,
72  double factor,
73  double epsilon,
74  bool only_cost) {
75  clear();
76 
77  predecessors.resize(graph.num_vertices());
78  distances.resize(graph.num_vertices());
79 
80  if (!graph.has_vertex(start_vertex)
81  || !graph.has_vertex(end_vertex)) {
82  return Path(start_vertex, end_vertex);
83  }
84 
85  auto v_source(graph.get_V(start_vertex));
86  auto v_target(graph.get_V(end_vertex));
87 
88  // perform the algorithm
89  astar_1_to_1(graph, v_source, v_target, heuristic, factor, epsilon);
90 
91  return Path(graph,
92  v_source, v_target,
94  only_cost);
95  }
96 
98  std::deque<Path> astar(
99  G &graph,
100  int64_t start_vertex,
101  std::vector<int64_t> end_vertex,
102  int heuristic,
103  double factor,
104  double epsilon,
105  bool only_cost) {
106  clear();
107 
108  predecessors.resize(graph.num_vertices());
109  distances.resize(graph.num_vertices());
110 
111  if (!graph.has_vertex(start_vertex)) return std::deque<Path>();
112  auto v_source(graph.get_V(start_vertex));
113 
114  std::vector<V> v_targets;
115  for (const auto &vertex : end_vertex) {
116  if (graph.has_vertex(vertex)) {
117  v_targets.push_back(graph.get_V(vertex));
118  }
119  }
120 
121  astar_1_to_many(graph,
122  v_source,
123  v_targets,
124  heuristic,
125  factor,
126  epsilon);
127 
128  auto paths = get_paths(graph, v_source, v_targets, only_cost);
129 
130  std::stable_sort(paths.begin(), paths.end(),
131  [](const Path &e1, const Path &e2)->bool {
132  return e1.end_id() < e2.end_id();
133  });
134 
135  return paths;
136  }
137 
138  // preparation for many to many
139  std::deque<Path> astar(
140  G &graph,
141  std::vector<int64_t> start_vertex,
142  std::vector<int64_t> end_vertex,
143  int heuristic,
144  double factor,
145  double epsilon,
146  bool only_cost) {
147  std::deque<Path> paths;
148  for (const auto &start : start_vertex) {
149  auto r_paths = astar(graph, start, end_vertex,
150  heuristic, factor, epsilon, only_cost);
151  paths.insert(paths.begin(), r_paths.begin(), r_paths.end());
152  }
153 
154  std::sort(paths.begin(), paths.end(),
155  [](const Path &e1, const Path &e2)->bool {
156  return e1.end_id() < e2.end_id();
157  });
158  std::stable_sort(paths.begin(), paths.end(),
159  [](const Path &e1, const Path &e2)->bool {
160  return e1.start_id() < e2.start_id();
161  });
162  return paths;
163  }
165 
166 
167 
168  private:
170 
171  struct found_goals{};
172  std::vector< V > predecessors;
173  std::vector< double > distances;
174  std::deque< V > nodesInDistance;
176 
177  // euclidean distance heuristic for one goal
178  class distance_heuristic : public boost::astar_heuristic< B_G, double > {
179  public:
180  distance_heuristic(B_G &g, V goal, int heuristic, double factor)
181  : m_g(g),
182  m_factor(factor),
183  m_heuristic(heuristic) {
184  m_goals.insert(goal);
185  }
187  B_G &g,
188  std::vector< V > goals,
189  int heuristic,
190  double factor)
191  : m_g(g),
192  m_goals(goals.begin(), goals.end()),
193  m_factor(factor),
194  m_heuristic(heuristic) {}
195 
196  double operator()(V u) {
197  if (m_heuristic == 0) return 0;
198  if (m_goals.empty()) return 0;
199  double best_h((std::numeric_limits<double>::max)());
200  for (auto goal : m_goals) {
201  double current((std::numeric_limits<double>::max)());
202  double dx = m_g[goal].x() - m_g[u].x();
203  double dy = m_g[goal].y() - m_g[u].y();
204  switch (m_heuristic) {
205  case 0:
206  current = 0;
207  case 1:
208  current = std::fabs((std::max)(dx, dy)) * m_factor;
209  case 2:
210  current = std::fabs((std::min)(dx, dy)) * m_factor;
211  case 3:
212  current = (dx * dx + dy * dy) * m_factor * m_factor;
213  case 4:
214  current = std::sqrt(dx * dx + dy * dy) * m_factor;
215  case 5:
216  current = (std::fabs(dx) + std::fabs(dy)) * m_factor;
217  default:
218  current = 0;
219  }
220  if (current < best_h) {
221  best_h = current;
222  }
223  }
224  {
225  auto s_it = m_goals.find(u);
226  if (!(s_it == m_goals.end())) {
227  // found one more goal
228  m_goals.erase(s_it);
229  }
230  }
231  return best_h;
232  }
233 
234  private:
236  std::set< V > m_goals;
237  double m_factor;
239  }; // class distance_heuristic
240 
241 
243  class astar_one_goal_visitor : public boost::default_astar_visitor {
244  public:
245  explicit astar_one_goal_visitor(V goal) : m_goal(goal) {}
246  template <class B_G>
247  void examine_vertex(V u, B_G &g) {
248  if (u == m_goal)
249  throw found_goals();
250  // using g, otherwise is throws a warning
251  num_edges(g);
252  }
253  private:
255  }; // class astar_one_goal_visitor
256 
258  class astar_many_goals_visitor : public boost::default_astar_visitor {
259  public:
260  explicit astar_many_goals_visitor(std::vector< V > goals)
261  :m_goals(goals.begin(), goals.end()) {}
262  template <class B_G>
263  void examine_vertex(V u, B_G &g) {
264  auto s_it = m_goals.find(u);
265  if (s_it == m_goals.end()) return;
266  // found one more goal
267  m_goals.erase(s_it);
268  if (m_goals.size() == 0) throw found_goals();
269  num_edges(g);
270  }
271  private:
272  std::set< V > m_goals;
273  };
274 
275  /******************** IMPLEMENTTION ******************/
276 
277 
278 
281  G &graph,
282  V source,
283  V target,
284  int heuristic,
285  double factor,
286  double epsilon) {
287  bool found = false;
288  try {
289  // Call A* named parameter interface
290  boost::astar_search(
291  graph.graph, source,
292  distance_heuristic(graph.graph, target,
293  heuristic, factor * epsilon),
294  boost::predecessor_map(&predecessors[0])
295  .weight_map(get(&pgrouting::Basic_edge::cost, graph.graph))
296  .distance_map(&distances[0])
297  .visitor(astar_one_goal_visitor(target)));
298  }
299  catch(found_goals &) {
300  found = true; // Target vertex found
301  }
302  return found;
303  }
304 
305 
308  G &graph,
309  V source,
310  const std::vector< V > &targets,
311  int heuristic,
312  double factor,
313  double epsilon) {
314  bool found = false;
315  try {
316  boost::astar_search(
317  graph.graph, source,
319  graph.graph, targets,
320  heuristic, factor * epsilon),
321  boost::predecessor_map(&predecessors[0])
322  .weight_map(get(&pgrouting::Basic_edge::cost, graph.graph))
323  .distance_map(&distances[0])
324  .visitor(astar_many_goals_visitor(targets)));
325  }
326  catch(found_goals &) {
327  found = true; // Target vertex found
328  }
329  return found;
330  }
331 
332 
333  /*
334  * GET_PATHS
335  */
336 
337 
338  std::deque<Path> get_paths(
339  const G &graph,
340  V source,
341  const std::vector<V> &targets,
342  bool only_cost) const {
343  std::deque<Path> paths;
344  for (const auto &target : targets) {
345  paths.push_back(
346  Path(graph,
347  source, target,
349  only_cost));
350  }
351  return paths;
352  }
353 };
354 
355 
356 } // namespace algorithms
357 } // namespace pgrouting
358 
359 #endif // SRC_ASTAR_SRC_PGR_ASTAR_HPP_
class for stopping when all targets are found
Definition: pgr_astar.hpp:258
bool astar_1_to_1(G &graph, V source, V target, int heuristic, double factor, double epsilon)
Call to Astar 1 source to 1 target.
Definition: pgr_astar.hpp:280
distance_heuristic(B_G &g, std::vector< V > goals, int heuristic, double factor)
Definition: pgr_astar.hpp:186
visitor that terminates when we find the goal
Definition: pgr_astar.hpp:243
std::deque< Path > astar(G &graph, int64_t start_vertex, std::vector< int64_t > end_vertex, int heuristic, double factor, double epsilon, bool only_cost)
astar 1 to many
Definition: pgr_astar.hpp:98
bool astar_1_to_many(G &graph, V source, const std::vector< V > &targets, int heuristic, double factor, double epsilon)
Call to astar 1 source to many targets.
Definition: pgr_astar.hpp:307
std::deque< Path > get_paths(const G &graph, V source, const std::vector< V > &targets, bool only_cost) const
Definition: pgr_astar.hpp:338
int64_t end_id() const
Path astar(G &graph, int64_t start_vertex, int64_t end_vertex, int heuristic, double factor, double epsilon, bool only_cost)
one to one astar 1 to 1
Definition: pgr_astar.hpp:67
int64_t start_id() const
distance_heuristic(B_G &g, V goal, int heuristic, double factor)
Definition: pgr_astar.hpp:180
std::deque< Path > astar(G &graph, std::vector< int64_t > start_vertex, std::vector< int64_t > end_vertex, int heuristic, double factor, double epsilon, bool only_cost)
Definition: pgr_astar.hpp:139
std::vector< double > distances
Definition: pgr_astar.hpp:173