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-sim.org/
12 // Copyright (C) 2001-2013 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 <cassert>
36 #include <string>
37 #include <functional>
38 #include <vector>
39 #include <deque>
40 #include <set>
41 #include <limits>
42 #include <algorithm>
43 #include <iterator>
44 #include <utils/common/ToString.h>
47 #include <utils/common/StdDefs.h>
48 #include "SUMOAbstractRouter.h"
49 
50 //#define DijkstraRouterTT_DEBUG_QUERY
51 //#define DijkstraRouterTT_DEBUG_QUERY_PERF
52 
53 // ===========================================================================
54 // class definitions
55 // ===========================================================================
71 template<class E, class V, class PF>
72 class DijkstraRouterTTBase : public SUMOAbstractRouter<E, V>, public PF {
75 
76 public:
78  DijkstraRouterTTBase(size_t noE, bool unbuildIsWarning) :
79  SUMOAbstractRouter<E, V>("DijkstraRouterTT"),
80  myErrorMsgHandler(unbuildIsWarning ? MsgHandler::getWarningInstance() : MsgHandler::getErrorInstance()) {
81  for (size_t i = 0; i < noE; i++) {
82  myEdgeInfos.push_back(EdgeInfo(i));
83  }
84  }
85 
87  virtual ~DijkstraRouterTTBase() { }
88 
94  class EdgeInfo {
95  public:
97  EdgeInfo(size_t id)
98  : edge(E::dictionary(id)), traveltime(std::numeric_limits<SUMOReal>::max()), prev(0), visited(false) {}
99 
101  const E* edge;
102 
105 
108 
110  bool visited;
111 
112  inline void reset() {
114  visited = false;
115  }
116  };
117 
123  public:
125  bool operator()(const EdgeInfo* nod1, const EdgeInfo* nod2) const {
126  if (nod1->traveltime == nod2->traveltime) {
127  return nod1->edge->getNumericalID() > nod2->edge->getNumericalID();
128  }
129  return nod1->traveltime > nod2->traveltime;
130  }
131  };
132 
133  virtual SUMOReal getEffort(const E* const e, const V* const v, SUMOReal t) const = 0;
134 
135 
136  void init() {
137  // all EdgeInfos touched in the previous query are either in myFrontierList or myFound: clean those up
138  for (typename std::vector<EdgeInfo*>::iterator i = myFrontierList.begin(); i != myFrontierList.end(); i++) {
139  (*i)->reset();
140  }
141  myFrontierList.clear();
142  for (typename std::vector<EdgeInfo*>::iterator i = myFound.begin(); i != myFound.end(); i++) {
143  (*i)->reset();
144  }
145  myFound.clear();
146  }
147 
148 
151  virtual void compute(const E* from, const E* to, const V* const vehicle,
152  SUMOTime msTime, std::vector<const E*>& into) {
153  assert(from != 0 && to != 0);
154  startQuery();
155  const SUMOReal time = STEPS2TIME(msTime);
156  init();
157  // add begin node
158  EdgeInfo* const fromInfo = &(myEdgeInfos[from->getNumericalID()]);
159  fromInfo->traveltime = 0;
160  fromInfo->prev = 0;
161  myFrontierList.push_back(fromInfo);
162  // loop
163  int num_visited = 0;
164  while (!myFrontierList.empty()) {
165  num_visited += 1;
166  // use the node with the minimal length
167  EdgeInfo* const minimumInfo = myFrontierList.front();
168  const E* const minEdge = minimumInfo->edge;
169  pop_heap(myFrontierList.begin(), myFrontierList.end(), myComparator);
170  myFrontierList.pop_back();
171  myFound.push_back(minimumInfo);
172 #ifdef DijkstraRouterTT_DEBUG_QUERY
173  std::cout << "DEBUG: hit '" << minEdge->getID() << "' Q: ";
174  for (typename std::vector<EdgeInfo*>::iterator it = myFrontierList.begin(); it != myFrontierList.end(); it++) {
175  std::cout << (*it)->traveltime << "," << (*it)->edge->getID() << " ";
176  }
177  std::cout << "\n";
178 #endif
179  // check whether the destination node was already reached
180  if (minEdge == to) {
181  buildPathFrom(minimumInfo, into);
182  endQuery(num_visited);
183 #ifdef DijkstraRouterTT_DEBUG_QUERY_PERF
184  std::cout << "visited " + toString(num_visited) + " edges (final path length: " + toString(into.size()) + ")\n";
185 #endif
186  return;
187  }
188  minimumInfo->visited = true;
189  const SUMOReal traveltime = minimumInfo->traveltime + getEffort(minEdge, vehicle, time + minimumInfo->traveltime);
190  // check all ways from the node with the minimal length
191  unsigned int i = 0;
192  const unsigned int length_size = minEdge->getNoFollowing();
193  for (i = 0; i < length_size; i++) {
194  const E* const follower = minEdge->getFollower(i);
195  EdgeInfo* const followerInfo = &(myEdgeInfos[follower->getNumericalID()]);
196  // check whether it can be used
197  if (PF::operator()(follower, vehicle)) {
198  continue;
199  }
200  const SUMOReal oldEffort = followerInfo->traveltime;
201  if (!followerInfo->visited && traveltime < oldEffort) {
202  followerInfo->traveltime = traveltime;
203  followerInfo->prev = minimumInfo;
204  if (oldEffort == std::numeric_limits<SUMOReal>::max()) {
205  myFrontierList.push_back(followerInfo);
206  push_heap(myFrontierList.begin(), myFrontierList.end(), myComparator);
207  } else {
208  push_heap(myFrontierList.begin(),
209  find(myFrontierList.begin(), myFrontierList.end(), followerInfo) + 1,
210  myComparator);
211  }
212  }
213  }
214  }
215  endQuery(num_visited);
216 #ifdef DijkstraRouterTT_DEBUG_QUERY_PERF
217  std::cout << "visited " + toString(num_visited) + " edges (final path length: " + toString(into.size()) + ")\n";
218 #endif
219  myErrorMsgHandler->inform("No connection between '" + from->getID() + "' and '" + to->getID() + "' found.");
220  }
221 
222 
223  SUMOReal recomputeCosts(const std::vector<const E*>& edges, const V* const v, SUMOTime msTime) const {
224  const SUMOReal time = STEPS2TIME(msTime);
225  SUMOReal costs = 0;
226  for (typename std::vector<const E*>::const_iterator i = edges.begin(); i != edges.end(); ++i) {
227  if (PF::operator()(*i, v)) {
228  return -1;
229  }
230  costs += getEffort(*i, v, time + costs);
231  }
232  return costs;
233  }
234 
235 public:
237  void buildPathFrom(EdgeInfo* rbegin, std::vector<const E*>& edges) {
238  std::deque<const E*> tmp;
239  while (rbegin != 0) {
240  tmp.push_front((E*) rbegin->edge); // !!!
241  rbegin = rbegin->prev;
242  }
243  std::copy(tmp.begin(), tmp.end(), std::back_inserter(edges));
244  }
245 
246 protected:
248  std::vector<EdgeInfo> myEdgeInfos;
249 
251  std::vector<EdgeInfo*> myFrontierList;
253  std::vector<EdgeInfo*> myFound;
254 
255  EdgeInfoByTTComparator myComparator;
256 
259 };
260 
261 
262 template<class E, class V, class PF>
264 public:
266  typedef SUMOReal(* Operation)(const E* const, const V* const, SUMOReal);
267 
268  DijkstraRouterTT_ByProxi(size_t noE, bool unbuildIsWarningOnly, Operation operation):
269  DijkstraRouterTTBase<E, V, PF>(noE, unbuildIsWarningOnly),
270  myOperation(operation) {}
271 
272  inline SUMOReal getEffort(const E* const e, const V* const v, SUMOReal t) const {
273  return (*myOperation)(e, v, t);
274  }
275 
276 private:
279 
280 
281 };
282 
283 
284 template<class E, class V, class PF>
286 public:
288  typedef SUMOReal(E::* Operation)(const V* const, SUMOReal) const;
289 
290  DijkstraRouterTT_Direct(size_t noE, bool unbuildIsWarningOnly, Operation operation)
291  : DijkstraRouterTTBase<E, V, PF>(noE, unbuildIsWarningOnly), myOperation(operation) {}
292 
293  inline SUMOReal getEffort(const E* const e, const V* const v, SUMOReal t) const {
294  return (e->*myOperation)(v, t);
295  }
296 
297 private:
299 
300 };
301 
302 
303 #endif
304 
305 /****************************************************************************/
306 
virtual SUMOReal getEffort(const E *const e, const V *const v, SUMOReal t) const =0
EdgeInfo(size_t id)
Constructor.
SUMOReal(* Operation)(const E *const, const V *const, SUMOReal)
Type of the function that is used to retrieve the edge effort.
DijkstraRouterTT_Direct(size_t noE, bool unbuildIsWarningOnly, Operation operation)
SUMOReal traveltime
Effort to reach the edge.
DijkstraRouterTTBase(size_t noE, bool unbuildIsWarning)
Constructor.
EdgeInfo * prev
The previous edge.
virtual void compute(const E *from, const E *to, const V *const vehicle, SUMOTime msTime, std::vector< const E * > &into)
Builds the route between the given edges using the minimum effort at the given time The definition of...
std::vector< EdgeInfo * > myFound
list of visited Edges (for resetting)
SUMOReal getEffort(const E *const e, const V *const v, SUMOReal t) const
const E * edge
The current edge.
SUMOReal recomputeCosts(const std::vector< const E * > &edges, const V *const v, SUMOTime msTime) const
MsgHandler *const myErrorMsgHandler
the handler for routing errors
#define max(a, b)
Definition: polyfonts.c:61
void buildPathFrom(EdgeInfo *rbegin, std::vector< const E * > &edges)
Builds the path from marked edges.
#define STEPS2TIME(x)
Definition: SUMOTime.h:65
std::vector< EdgeInfo > myEdgeInfos
The container of edge information.
EdgeInfoByTTComparator myComparator
DijkstraRouterTT_ByProxi(size_t noE, bool unbuildIsWarningOnly, Operation operation)
std::string toString(const T &t, std::streamsize accuracy=OUTPUT_ACCURACY)
Definition: ToString.h:51
Operation myOperation
The object&#39;s operation to perform.
SUMOReal(E::* Operation)(const V *const, SUMOReal) const
Type of the function that is used to retrieve the edge effort.
SUMOReal getEffort(const E *const e, const V *const v, SUMOReal t) const
bool operator()(const EdgeInfo *nod1, const EdgeInfo *nod2) const
Comparing method.
void inform(std::string msg, bool addType=true)
adds a new error to the list
Definition: MsgHandler.cpp:89
std::vector< EdgeInfo * > myFrontierList
A container for reusage of the min edge heap.
#define SUMOReal
Definition: config.h:221
void endQuery(int visits)
virtual ~DijkstraRouterTTBase()
Destructor.
bool visited
The previous edge.