GISCup 2015
 All Classes Files Functions Variables Typedefs Enumerations Enumerator Macros
boostastar.hpp
Go to the documentation of this file.
1 /* Copyright 2015 Martin Werner - <martin.werner@ifi.lmu.de>
2  *
3  * This program is free software: you can redistribute it and/or modify
4  * it under the terms of the GNU General Public License as published by
5  * the Free Software Foundation, either version 3 of the License, or
6  * (at your option) any later version.
7  *
8  * This program is distributed in the hope that it will be useful,
9  * but WITHOUT ANY WARRANTY; without even the implied warranty of
10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11  * GNU General Public License for more details.
12  *
13  * You should have received a copy of the GNU General Public License
14  * along with this program. If not, see <http://www.gnu.org/licenses/>.
15  */
16 #ifndef BOOSTASTAR_HPP_INC
17 #define BOOSTASTAR_HPP_INC
18 
23 template <class Graph, class CostType, class LocMap>
24 class distance_heuristic : public astar_heuristic<Graph, CostType>
25 {
26 public:
27  typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
28  distance_heuristic(LocMap l, Vertex goal)
29  : m_location(l), m_goal(goal) {}
30  CostType operator()(Vertex u)
31  {
32  return WebMercatorDistance(m_location[u].x,m_location[u].y,
33  m_location[m_goal].x,m_location[m_goal].y);
34  }
35 private:
36  LocMap m_location;
37  Vertex m_goal;
38 };
39 
40 
41 struct found_goal {}; // will be thrown on success
42 
43 
47 template <class Vertex>
48 class astar_goal_visitor : public boost::default_astar_visitor
49 {
50  size_t &examines;
51 
52  WeightMap &weightmap;
53 public:
54  astar_goal_visitor(Vertex goal, WeightMap &_weightmap,size_t &_examines) : m_goal(goal),weightmap(_weightmap),examines(_examines) {}
55  template <class Graph>
56  void examine_vertex(Vertex u, Graph& g) {
57  if(u == m_goal)
58  throw found_goal();
59  }
60 
61  template <class Graph>
62  void examine_edge(edge_descriptor u, Graph& g) {
63  examines ++;
64  }
65 
66 private:
67  Vertex m_goal;
68 };
69 
74  std::pair<bool, double> search_reference(size_t start, size_t end)
75  {
76  lastStart = start; lastGoal = end;
77  p = vector<mygraph_t::vertex_descriptor>(num_vertices(g));
78  d = vector<cost> (num_vertices(g));
79  colors = vector<default_color_type>(num_vertices(g));
80 
81  try {
82  astar_search(g, start,
83  distance_heuristic<mygraph_t, cost, std::vector<location>>
84  (locations, end),
85  predecessor_map(&p[0]).distance_map(&d[0]).
86  color_map(&colors[0]).
87  visitor(astar_goal_visitor<mygraph_t::vertex_descriptor>(end,weightmap,stat_examines)));
88  } catch(found_goal fg) { // found a path to the goal
89  shortest_path.clear();
90  for(mygraph_t::vertex_descriptor v = end;; v = p[v]) {
91  shortest_path.push_front(v);
92  if(p[v] == v)
93  break;
94  }
95 #ifndef NO_STAT_OUTPUT
96  DEFAULT_STATS("Boost A*");
97 #endif
98  return std::make_pair(true,d[end]);
99  }
100 #ifndef NO_STAT_OUTPUT
101  DEFAULT_STATS("Boost A*");
102 #endif
103  //cout << "No path" << endl;
104  return std::make_pair(false,std::numeric_limits<double>::infinity());;
105  }
106 
107 
108 #endif