SUMO - Simulation of Urban MObility
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
AStarRouter.h
Go to the documentation of this file.
1 /****************************************************************************/
7 // A* Algorithm using euclidean distance heuristic.
8 // Based on DijkstraRouterTT. For routing by effort a novel heuristic would be needed.
9 /****************************************************************************/
10 // SUMO, Simulation of Urban MObility; see http://sumo-sim.org/
11 // Copyright (C) 2001-2013 DLR (http://www.dlr.de/) and contributors
12 /****************************************************************************/
13 //
14 // This file is part of SUMO.
15 // SUMO is free software: you can redistribute it and/or modify
16 // it under the terms of the GNU General Public License as published by
17 // the Free Software Foundation, either version 3 of the License, or
18 // (at your option) any later version.
19 //
20 /****************************************************************************/
21 #ifndef AStarRouterTT_h
22 #define AStarRouterTT_h
23 
24 
25 // ===========================================================================
26 // included modules
27 // ===========================================================================
28 #ifdef _MSC_VER
29 #include <windows_config.h>
30 #else
31 #include <config.h>
32 #endif
33 
34 #include <cassert>
35 #include <string>
36 #include <functional>
37 #include <vector>
38 #include <set>
39 #include <limits>
40 #include <algorithm>
41 #include <iterator>
43 #include <utils/common/StdDefs.h>
44 #include <utils/common/ToString.h>
45 #include "SUMOAbstractRouter.h"
46 
47 
48 // ===========================================================================
49 // class definitions
50 // ===========================================================================
66 template<class E, class V, class PF>
67 class AStarRouterTTBase : public SUMOAbstractRouter<E, V>, public PF {
70 
71 public:
73  AStarRouterTTBase(size_t noE, bool unbuildIsWarning):
74  SUMOAbstractRouter<E, V>("AStarRouter"),
75  myErrorMsgHandler(unbuildIsWarning ? MsgHandler::getWarningInstance() : MsgHandler::getErrorInstance()) {
76  for (size_t i = 0; i < noE; i++) {
77  myEdgeInfos.push_back(EdgeInfo(i));
78  }
79  }
80 
82  virtual ~AStarRouterTTBase() {}
83 
89  class EdgeInfo {
90  public:
92  EdgeInfo(size_t id) :
93  edge(E::dictionary(id)),
94  traveltime(std::numeric_limits<SUMOReal>::max()),
95  heuristicTime(std::numeric_limits<SUMOReal>::max()),
96  prev(0),
97  visited(false)
98  {}
99 
101  const E* edge;
102 
105 
108 
111 
113  bool visited;
114 
115  inline void reset() {
116  // heuristicTime is set before adding to the frontier, thus no reset is needed
118  visited = false;
119  }
120 
121  };
122 
128  public:
130  bool operator()(const EdgeInfo* nod1, const EdgeInfo* nod2) const {
131  if (nod1->heuristicTime == nod2->heuristicTime) {
132  return nod1->edge->getNumericalID() > nod2->edge->getNumericalID();
133  }
134  return nod1->heuristicTime > nod2->heuristicTime;
135  }
136  };
137 
138  virtual SUMOReal getEffort(const E* const e, const V* const v, SUMOReal t) const = 0;
139 
140 
141  void init() {
142  // all EdgeInfos touched in the previous query are either in myFrontierList or myFound: clean those up
143  for (typename std::vector<EdgeInfo*>::iterator i = myFrontierList.begin(); i != myFrontierList.end(); i++) {
144  (*i)->reset();
145  }
146  myFrontierList.clear();
147  for (typename std::vector<EdgeInfo*>::iterator i = myFound.begin(); i != myFound.end(); i++) {
148  (*i)->reset();
149  }
150  myFound.clear();
151  }
152 
153 
155  virtual void compute(const E* from, const E* to, const V* const vehicle,
156  SUMOTime msTime, std::vector<const E*>& into) {
157  assert(from != 0 && to != 0);
158  startQuery();
159  const SUMOReal time = STEPS2TIME(msTime);
160  init();
161  // add begin node
162  EdgeInfo* const fromInfo = &(myEdgeInfos[from->getNumericalID()]);
163  fromInfo->traveltime = 0;
164  fromInfo->prev = 0;
165  myFrontierList.push_back(fromInfo);
166  // loop
167  int num_visited = 0;
168  while (!myFrontierList.empty()) {
169  num_visited += 1;
170  // use the node with the minimal length
171  EdgeInfo* const minimumInfo = myFrontierList.front();
172  const E* const minEdge = minimumInfo->edge;
173  pop_heap(myFrontierList.begin(), myFrontierList.end(), myComparator);
174  myFrontierList.pop_back();
175  myFound.push_back(minimumInfo);
176  // check whether the destination node was already reached
177  if (minEdge == to) {
178  buildPathFrom(minimumInfo, into);
179  endQuery(num_visited);
180  // DEBUG
181  //std::cout << "visited " + toString(num_visited) + " edges (final path length: " + toString(into.size()) + ")\n";
182  return;
183  }
184  minimumInfo->visited = true;
185  const SUMOReal traveltime = minimumInfo->traveltime + getEffort(minEdge, vehicle, time + minimumInfo->traveltime);
186  // check all ways from the node with the minimal length
187  unsigned int i = 0;
188  const unsigned int length_size = minEdge->getNoFollowing();
189  for (i = 0; i < length_size; i++) {
190  const E* const follower = minEdge->getFollower(i);
191  EdgeInfo* const followerInfo = &(myEdgeInfos[follower->getNumericalID()]);
192  // check whether it can be used
193  if (PF::operator()(follower, vehicle)) {
194  continue;
195  }
196  const SUMOReal oldEffort = followerInfo->traveltime;
197  if (!followerInfo->visited && traveltime < oldEffort) {
198  // admissible A* heuristic: straight line distance at maximum speed
199  const SUMOReal heuristic_remaining = minEdge->getDistanceTo(to) / vehicle->getMaxSpeed();
200  followerInfo->traveltime = traveltime;
201  followerInfo->heuristicTime = traveltime + heuristic_remaining;
202  followerInfo->prev = minimumInfo;
203  if (oldEffort == std::numeric_limits<SUMOReal>::max()) {
204  myFrontierList.push_back(followerInfo);
205  push_heap(myFrontierList.begin(), myFrontierList.end(), myComparator);
206  } else {
207  push_heap(myFrontierList.begin(),
208  find(myFrontierList.begin(), myFrontierList.end(), followerInfo) + 1,
209  myComparator);
210  }
211  }
212  }
213  }
214  endQuery(num_visited);
215  myErrorMsgHandler->inform("No connection between '" + from->getID() + "' and '" + to->getID() + "' found.");
216  }
217 
218 
219  SUMOReal recomputeCosts(const std::vector<const E*>& edges, const V* const v, SUMOTime msTime) const {
220  const SUMOReal time = STEPS2TIME(msTime);
221  SUMOReal costs = 0;
222  for (typename std::vector<const E*>::const_iterator i = edges.begin(); i != edges.end(); ++i) {
223  if (PF::operator()(*i, v)) {
224  return -1;
225  }
226  costs += getEffort(*i, v, time + costs);
227  }
228  return costs;
229  }
230 
231 public:
233  void buildPathFrom(EdgeInfo* rbegin, std::vector<const E*>& edges) {
234  std::deque<const E*> tmp;
235  while (rbegin != 0) {
236  tmp.push_front((E*) rbegin->edge); // !!!
237  rbegin = rbegin->prev;
238  }
239  std::copy(tmp.begin(), tmp.end(), std::back_inserter(edges));
240  }
241 
242 protected:
244  std::vector<EdgeInfo> myEdgeInfos;
245 
247  std::vector<EdgeInfo*> myFrontierList;
249  std::vector<EdgeInfo*> myFound;
250 
251  EdgeInfoComparator myComparator;
252 
255 
256 };
257 
258 
259 template<class E, class V, class PF>
260 class AStarRouterTT_ByProxi : public AStarRouterTTBase<E, V, PF> {
261 public:
263  typedef SUMOReal(* Operation)(const E* const, const V* const, SUMOReal);
264 
265  AStarRouterTT_ByProxi(size_t noE, bool unbuildIsWarningOnly, Operation operation):
266  AStarRouterTTBase<E, V, PF>(noE, unbuildIsWarningOnly),
267  myOperation(operation) {}
268 
269  inline SUMOReal getEffort(const E* const e, const V* const v, SUMOReal t) const {
270  return (*myOperation)(e, v, t);
271  }
272 
273 private:
276 };
277 
278 
279 template<class E, class V, class PF>
280 class AStarRouterTT_Direct : public AStarRouterTTBase<E, V, PF> {
281 public:
283  typedef SUMOReal(E::* Operation)(const V* const, SUMOReal) const;
284 
285  AStarRouterTT_Direct(size_t noE, bool unbuildIsWarningOnly, Operation operation)
286  : AStarRouterTTBase<E, V, PF>(noE, unbuildIsWarningOnly), myOperation(operation) {}
287 
288  inline SUMOReal getEffort(const E* const e, const V* const v, SUMOReal t) const {
289  return (e->*myOperation)(v, t);
290  }
291 
292 private:
294 };
295 
296 
297 #endif
298 
299 /****************************************************************************/
300