SUMO - Simulation of Urban MObility
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
DijkstraRouterTT.h
Go to the documentation of this file.
1 /****************************************************************************/
9 // Dijkstra shortest path algorithm using travel time
10 /****************************************************************************/
11 // SUMO, Simulation of Urban MObility; see http://sumo.sourceforge.net/
12 // Copyright (C) 2001-2012 DLR (http://www.dlr.de/) and contributors
13 /****************************************************************************/
14 //
15 // This file is part of SUMO.
16 // SUMO is free software: you can redistribute it and/or modify
17 // it under the terms of the GNU General Public License as published by
18 // the Free Software Foundation, either version 3 of the License, or
19 // (at your option) any later version.
20 //
21 /****************************************************************************/
22 #ifndef DijkstraRouterTT_h
23 #define DijkstraRouterTT_h
24 
25 
26 // ===========================================================================
27 // included modules
28 // ===========================================================================
29 #ifdef _MSC_VER
30 #include <windows_config.h>
31 #else
32 #include <config.h>
33 #endif
34 
35 #include <string>
36 #include <functional>
37 #include <vector>
38 #include <set>
39 #include <limits>
40 #include <algorithm>
41 #include <iterator>
42 #include <utils/common/ToString.h>
45 #include <utils/common/StdDefs.h>
46 #include "SUMOAbstractRouter.h"
47 
48 //#define DijkstraRouterTT_DEBUG_QUERY
49 //#define DijkstraRouterTT_DEBUG_QUERY_PERF
50 
51 // ===========================================================================
52 // class definitions
53 // ===========================================================================
69 template<class E, class V, class PF>
70 class DijkstraRouterTTBase : public SUMOAbstractRouter<E, V>, public PF {
73 
74 public:
76  DijkstraRouterTTBase(size_t noE, bool unbuildIsWarning) :
77  SUMOAbstractRouter<E, V>("DijkstraRouterTT"),
78  myErrorMsgHandler(unbuildIsWarning ? MsgHandler::getWarningInstance() : MsgHandler::getErrorInstance())
79  {
80  for (size_t i = 0; i < noE; i++) {
81  myEdgeInfos.push_back(EdgeInfo(i));
82  }
83  }
84 
86  virtual ~DijkstraRouterTTBase() { }
87 
93  class EdgeInfo {
94  public:
96  EdgeInfo(size_t id)
97  : edge(E::dictionary(id)), traveltime(std::numeric_limits<SUMOReal>::max()), prev(0), visited(false) {}
98 
100  const E* edge;
101 
104 
107 
109  bool visited;
110 
111  inline void reset() {
113  visited = false;
114  }
115  };
116 
122  public:
124  bool operator()(const EdgeInfo* nod1, const EdgeInfo* nod2) const {
125  if (nod1->traveltime == nod2->traveltime) {
126  return nod1->edge->getNumericalID() > nod2->edge->getNumericalID();
127  }
128  return nod1->traveltime > nod2->traveltime;
129  }
130  };
131 
132  virtual SUMOReal getEffort(const E* const e, const V* const v, SUMOReal t) const = 0;
133 
134 
135  void init() {
136  // all EdgeInfos touched in the previous query are either in myFrontierList or myFound: clean those up
137  for (typename std::vector<EdgeInfo*>::iterator i = myFrontierList.begin(); i != myFrontierList.end(); i++) {
138  (*i)->reset();
139  }
140  myFrontierList.clear();
141  for (typename std::vector<EdgeInfo*>::iterator i = myFound.begin(); i != myFound.end(); i++) {
142  (*i)->reset();
143  }
144  myFound.clear();
145  }
146 
147 
150  virtual void compute(const E* from, const E* to, const V* const vehicle,
151  SUMOTime msTime, std::vector<const E*> &into) {
152  assert(from != 0 && to != 0);
153  startQuery();
154  const SUMOReal time = STEPS2TIME(msTime);
155  init();
156  // add begin node
157  EdgeInfo* const fromInfo = &(myEdgeInfos[from->getNumericalID()]);
158  fromInfo->traveltime = 0;
159  fromInfo->prev = 0;
160  myFrontierList.push_back(fromInfo);
161  // loop
162  int num_visited = 0;
163  while (!myFrontierList.empty()) {
164  num_visited += 1;
165  // use the node with the minimal length
166  EdgeInfo* const minimumInfo = myFrontierList.front();
167  const E* const minEdge = minimumInfo->edge;
168  pop_heap(myFrontierList.begin(), myFrontierList.end(), myComparator);
169  myFrontierList.pop_back();
170  myFound.push_back(minimumInfo);
171 #ifdef DijkstraRouterTT_DEBUG_QUERY
172  std::cout << "DEBUG: hit '" << minEdge->getID() << "' Q: ";
173  for (typename std::vector<EdgeInfo*>::iterator it = myFrontierList.begin(); it != myFrontierList.end(); it++) {
174  std::cout << (*it)->traveltime << "," << (*it)->edge->getID() << " ";
175  }
176  std::cout << "\n";
177 #endif
178  // check whether the destination node was already reached
179  if (minEdge == to) {
180  buildPathFrom(minimumInfo, into);
181  endQuery(num_visited);
182 #ifdef DijkstraRouterTT_DEBUG_QUERY_PERF
183  std::cout << "visited " + toString(num_visited) + " edges (final path length: " + toString(into.size()) + ")\n";
184 #endif
185  return;
186  }
187  minimumInfo->visited = true;
188  const SUMOReal traveltime = minimumInfo->traveltime + getEffort(minEdge, vehicle, time + minimumInfo->traveltime);
189  // check all ways from the node with the minimal length
190  unsigned int i = 0;
191  const unsigned int length_size = minEdge->getNoFollowing();
192  for (i = 0; i < length_size; i++) {
193  const E* const follower = minEdge->getFollower(i);
194  EdgeInfo* const followerInfo = &(myEdgeInfos[follower->getNumericalID()]);
195  // check whether it can be used
196  if (PF::operator()(follower, vehicle)) {
197  continue;
198  }
199  const SUMOReal oldEffort = followerInfo->traveltime;
200  if (!followerInfo->visited && traveltime < oldEffort) {
201  followerInfo->traveltime = traveltime;
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 #ifdef DijkstraRouterTT_DEBUG_QUERY_PERF
216  std::cout << "visited " + toString(num_visited) + " edges (final path length: " + toString(into.size()) + ")\n";
217 #endif
218  myErrorMsgHandler->inform("No connection between '" + from->getID() + "' and '" + to->getID() + "' found.");
219  }
220 
221 
222  SUMOReal recomputeCosts(const std::vector<const E*> &edges, const V* const v, SUMOTime msTime) const {
223  const SUMOReal time = STEPS2TIME(msTime);
224  SUMOReal costs = 0;
225  for (typename std::vector<const E*>::const_iterator i = edges.begin(); i != edges.end(); ++i) {
226  if (PF::operator()(*i, v)) {
227  return -1;
228  }
229  costs += getEffort(*i, v, time + costs);
230  }
231  return costs;
232  }
233 
234 public:
236  void buildPathFrom(EdgeInfo* rbegin, std::vector<const E*> &edges) {
237  std::deque<const E*> tmp;
238  while (rbegin != 0) {
239  tmp.push_front((E*) rbegin->edge); // !!!
240  rbegin = rbegin->prev;
241  }
242  std::copy(tmp.begin(), tmp.end(), std::back_inserter(edges));
243  }
244 
245 protected:
247  std::vector<EdgeInfo> myEdgeInfos;
248 
250  std::vector<EdgeInfo*> myFrontierList;
252  std::vector<EdgeInfo*> myFound;
253 
255 
258 };
259 
260 
261 template<class E, class V, class PF, class EC>
263 public:
265  typedef SUMOReal(EC::* Operation)(const E* const, const V* const, SUMOReal) const;
266 
267  DijkstraRouterTT_ByProxi(size_t noE, bool unbuildIsWarningOnly, EC* receiver, Operation operation)
268  : DijkstraRouterTTBase<E, V, PF>(noE, unbuildIsWarningOnly),
269  myReceiver(receiver), myOperation(operation) {}
270 
271  inline SUMOReal getEffort(const E* const e, const V* const v, SUMOReal t) const {
272  return (myReceiver->*myOperation)(e, v, t);
273  }
274 
275 private:
278 
281 
282 
283 };
284 
285 
286 template<class E, class V, class PF>
288 public:
290  typedef SUMOReal(E::* Operation)(const V* const, SUMOReal) const;
291 
292  DijkstraRouterTT_Direct(size_t noE, bool unbuildIsWarningOnly, Operation operation)
293  : DijkstraRouterTTBase<E, V, PF>(noE, unbuildIsWarningOnly), myOperation(operation) {}
294 
295  inline SUMOReal getEffort(const E* const e, const V* const v, SUMOReal t) const {
296  return (e->*myOperation)(v, t);
297  }
298 
299 private:
301 
302 };
303 
304 
305 #endif
306 
307 /****************************************************************************/
308