GISCup 2015
 All Classes Files Functions Variables Typedefs Enumerations Enumerator Macros
ALT.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 ALT_HPP_INC
17 #define ALT_HPP_INC
18 
19 #ifdef ALT_DEBUG
20 #define LATE(fmt, ...) {if(numRuns > 1E7) printf(fmt, ##__VA_ARGS__);}
21 #else
22 #define LATE(fmt, ...) {}
23 #define ALT_USE_TIGHTEST_SUBSET
24 #endif
25 
26 
35 class landmark_t{
36  public:
37  std::vector<cost> d_from;
38  std::vector<cost> d_to;
39  mygraph_t::vertex_descriptor l;
40 
41  landmark_t(mygraph_t::vertex_descriptor _l):l(_l){};
42 };
43 
44  std::vector<landmark_t> landmarks;
45 
48  double WebMercatorEdge(mygraph_t::vertex_descriptor s, mygraph_t::vertex_descriptor e)
49  {
50  return WebMercatorDistance(locations[s].y,locations[s].x,locations[e].y,locations[e].x);
51  }
52 
55  bool recreateLandmark(size_t which, size_t where)
56  {
57  while (landmarks.size() <= which)
58  landmarks.push_back(landmark_t(where));
59  return createLandmark(which,where);
60  }
61 
66  bool createLandmark(size_t which, size_t where)
67  {
68  reverse_graph<mygraph_t> g_dual(g);
69  if (which >= landmarks.size())
70  return false;
71  landmarks[which].l = where;
72 
73  landmarks[which].d_from.resize(num_vertices(g));
74  landmarks[which].d_to.resize(num_vertices(g));
75 
76  // distance from by searching on graph
77  dijkstra_shortest_paths(g,landmarks[which].l,predecessor_map(&p[0]).
78  distance_map(&(landmarks[which].d_from[0])));
79  // distance to landmark by searching on reverse_graph
80  dijkstra_shortest_paths(g_dual,landmarks[which].l,predecessor_map(&p[0]).
81  distance_map(&(landmarks[which].d_to[0])));
82  return true;
83  }
84 
85 
86 
87 
88 
95  bool localCheckFeasibility(mygraph_t::vertex_descriptor t)
96  {
97  // feasible if reduced length l_pi non-negative
98  mygraph_t::edge_iterator oe, oe_end;
99  for (tie(oe, oe_end) = edges(g);
100  oe != oe_end;
101  ++oe)
102  {
103  double l = weightmap[*oe];
104  auto v = source(*oe,g);
105  auto w = target(*oe,g);
106  double l_pi=weightmap[*oe] - pi(source(*oe,g),t) + pi(target(*oe,g),t);
107 
108  if (l_pi < 0 && -l_pi > 10E-6)
109  return false;
110  }
111  return true;
112  }
113 
114 
124  template<class vd>
125  double pi(vd v, vd w)
126  {
127  // d(v,w) <= d(v) -d (w) for distance to L
128  double pi = 0;
129  size_t l = landmarks.size();
130 #ifndef ALT_USE_TIGHTEST_SUBSET
131  for (size_t i=0; i < l; i++)
132 
133 #else
134  for (auto i:landmark_selection)
135 #endif
136  {
137  pi = std::max(pi, landmarks[i].d_to[v]-landmarks[i].d_to[w] );
138  pi = std::max(pi, landmarks[i].d_from[w]-landmarks[i].d_from[v] );
139  }
140  return pi;
141  }
142 
143  std::vector<size_t> landmark_selection;
144 
145 
153  template<class vd>
154  double select_tightest(vd v, vd w, size_t num)
155  {
156  // Calculate true distance
157  double d = WebMercatorEdge(v,w);
158  std::vector<std::pair<double, size_t>> tightness;
159 
160  double pi;
161  size_t l = landmarks.size();
162  tightness.resize(l);
163  // Calculate tightness value for each landmark
164  for (size_t i=0; i < l; i++)
165  {
166  pi = std::max(pi, landmarks[i].d_to[v]-landmarks[i].d_to[w] );
167  pi = std::max(pi, landmarks[i].d_from[w]-landmarks[i].d_from[v] );
168  tightness[i] = make_pair(-(pi / d),i);
169  }
170  // Sort for tightest landmarks
171  std::sort(tightness.begin(), tightness.end());
172  // Get selection from sort ordering...
173  landmark_selection.resize(num);
174  for (size_t i=0; i < num; i++)
175  landmark_selection[i] = tightness[i].second;
176  return pi;
177  }
178 
185  bool preprocess_ALT(size_t numLandmarks = 25)
186  {
187  p.resize(num_vertices(g));
188 
189  landmarks.clear();
190  cout << "Generating "<< numLandmarks << " landmarks" << endl;
191  for (size_t i=0; i< numLandmarks; i++)
192  {
193  landmarks.push_back(landmark_t(random_v()));
194  }
195 
196  // And now search
197  cout << "Preparing " << landmarks.size() << " landmarks" << endl;
198  #pragma omp parallel for
199  for (size_t i=0; i < landmarks.size(); i++)
200  {
201 
202  createLandmark(i,landmarks[i].l);
203  }
204  cout << "Preparation complete" << endl;
205  return true;
206  }
207 
208 
214  std::pair<bool, double> search_ALT(size_t s, size_t end)
215  {
216  lastStart = s; lastGoal = end;
217 #ifdef __WXWINDOWS__
218  if (landmarks.size() < 3)
219  {
220  wxMessageBox(_("You cannot use ALT with fewer than three landmarks in this implementation..."));
221  return std::pair<bool,double>(false,std::numeric_limits<double>::infinity());
222  }
223 #endif //__WXWINDOWS__
224  select_tightest(s,end,3);
225  /*
226  * Use the priority_queue and push element each time you
227  * would like to update it. Accept the fact that you will
228  * have useless entries in the queue. When popping the
229  * top value, check if it contains the up-to-date value.
230  * If not, ignore it and pop the next.
231  *
232  * This way you delay the removal of the updated element
233  * until it comes to the top. I noticed this approach being
234  * used by top programmers realizing Dijkstra algorithm.
235  * */
236 
238  mygraph_t::out_edge_iterator oe, oe_end;
239 
240  // Initialize all data structures
241  for (boost::tie(u, u_end) = vertices(g); u != u_end; ++u)
242  {
243  d[*u] = std::numeric_limits<double>::infinity();
244  colors[*u] = Color::white();
245  p[*u] = *u;
246  }
247  // Start Search
248 
249  queue_t Q;
250  colors[s] = Color::gray();
251  d[s] = 0;
252  f[s] = pi(s,end);
253  Q.push(make_pair(f[s],s));
254 
255  while(!Q.empty())
256  {
257  auto u = Q.top();
258  Q.pop();
259  if (u.first != f[u.second])
260  continue;
261 
262  if (u.second == end)
263  {
264  shortest_path.clear();
265  for(mygraph_t::vertex_descriptor v = end;; v = p[v]) {
266  shortest_path.push_front(v);
267  if(p[v] == v)
268  break;
269  }
270 #ifndef NO_STAT_OUTPUT
271  DEFAULT_STATS("My ALT");
272 #endif
273 
274  return make_pair(true,d[end]);
275  }
276 
277  for (tie(oe, oe_end) = out_edges(u.second,g);
278  oe != oe_end;
279  ++oe)
280  {
281  STAT_EXAMINE();
282  auto v = target(*oe,g);
283  double pi_v_end = pi(v,end);
284 
285  if (d[u.second] +
286  weightmap[*oe]
287  + pi_v_end < d[v] + pi_v_end)
288  {
289  d[v] = d[u.second] + weightmap[*oe];
290  p[v] = u.second;
291  f[v] = d[v]+pi_v_end;
292  if (colors[v] == Color::white())
293  {
294  // discover
295  colors[v] = Color::gray();
296  Q.push(make_pair(f[v],v));
297  }else
298  if(colors[v] == Color::black())
299  {
300  // reopen should not be needed
301  colors[v] = Color::gray();
302  Q.push(make_pair(f[v],v));
303  }else if(colors[v] == Color::gray())
304  {
305  // update in queue (we have found a shorter path)
306  Q.push(make_pair(f[v],v));
307 
308  }
309  }
310  }// end for
311  colors[u.second] = Color::black();
312  }// while
313 
314 #ifndef NO_STAT_OUTPUT
315 DEFAULT_STATS("ALT");
316 #endif
317 
318  return make_pair(false,std::numeric_limits<double>::infinity());
319  };
320 
321  #endif