GISCup 2015
 All Classes Files Functions Variables Typedefs Enumerations Enumerator Macros
boostdijkstra.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 BOOSTDIJKSTRA_HPP_INC
17 #define BOOSTDIJKSTRA_HPP_INC
18 
23 template <class Vertex>
24 class dijkstra_goal_visitor : public boost::default_dijkstra_visitor
25 {
26  size_t &examines;
27 
28  WeightMap &weightmap;
29 public:
30  dijkstra_goal_visitor(Vertex goal, WeightMap &_weightmap,size_t &_examines) : m_goal(goal),weightmap(_weightmap),examines(_examines) {}
31 
32  template <class Graph>
33  void examine_vertex(Vertex u, Graph& g) {
34  if(u == m_goal)
35  throw found_goal();
36  }
37 
38  template <class Graph>
39  void examine_edge(edge_descriptor u, Graph& g) {
40  examines ++;
41  }
42 
43 private:
44  Vertex m_goal;
45 };
46 
47 
54  std::pair<bool, double> search_boostdijkstra(size_t start, size_t end)
55  {
56  lastStart = start; lastGoal = end;
57  p = vector<mygraph_t::vertex_descriptor>(num_vertices(g));
58  d = vector<cost> (num_vertices(g));
59  colors = vector<default_color_type>(num_vertices(g));
60  /*Note: Different from the documentation, dijkstra shortest path
61  * does not pass the colormap directly, therefore the call
62  * below does not give expected results and we have to skip the
63  * named_parameter variant and use the classical (tedious, lengthy)
64  * variant*/
65 
66  /*dijkstra_shortest_paths(g, start,
67  predecessor_map(&p[0]).
68  distance_map(&d[0]).
69  color_map(make_iterator_property_map(colors.begin(), get(boost::vertex_index, g)))
70  );*/
71  weightmap = get(edge_weight,g);
72  shortest_path.clear();
73  try{
74  dijkstra_shortest_paths(g, start, &p[0],&d[0],
75  weightmap,
76  get(boost::vertex_index, g), // VertexIndexMap
77  std::less<double>(), // CompareFunction
78  closed_plus<double>(), // CombineFunction
79  std::numeric_limits<double>::max(), // DistInf
80  (double) 0.0, // DistZero
81  dijkstra_goal_visitor<mygraph_t::vertex_descriptor>(end,weightmap,stat_examines),
82  &colors[0] // ColorMap
83  );
84 
85  } catch(found_goal fg) { // found a path to the goal
86  for(mygraph_t::vertex_descriptor v = end;; v = p[v]) {
87  shortest_path.push_front(v);
88  if(p[v] == v)
89  break;
90  }
91 #ifndef NO_STAT_OUTPUT
92  DEFAULT_STATS("Reference Dijkstra");
93 #endif
94  return std::make_pair(true,d[end]);
95  }
96 #ifndef NO_STAT_OUTPUT
97  DEFAULT_STATS("Reference Dijkstra");
98 #endif
99  //cout << "No path" << endl;
100  return std::make_pair(false,std::numeric_limits<double>::infinity());
101  }
102 
103 
104 #endif