SUMO - Simulation of Urban MObility
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules 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.dlr.de/
12 // Copyright (C) 2001-2015 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>
46 #include <utils/common/StdDefs.h>
47 #include "SUMOAbstractRouter.h"
48 
49 //#define DijkstraRouterTT_DEBUG_QUERY
50 //#define DijkstraRouterTT_DEBUG_QUERY_PERF
51 
52 // ===========================================================================
53 // class definitions
54 // ===========================================================================
70 template<class E, class V, class PF>
71 class DijkstraRouterTT : public SUMOAbstractRouter<E, V>, public PF {
72 
73 public:
74  typedef SUMOReal(* Operation)(const E* const, const V* const, SUMOReal);
76  DijkstraRouterTT(size_t noE, bool unbuildIsWarning, Operation operation) :
77  SUMOAbstractRouter<E, V>(operation, "DijkstraRouterTT"),
78  myErrorMsgHandler(unbuildIsWarning ? MsgHandler::getWarningInstance() : MsgHandler::getErrorInstance()) {
79  for (size_t i = 0; i < noE; i++) {
80  myEdgeInfos.push_back(EdgeInfo(i));
81  }
82  }
83 
85  virtual ~DijkstraRouterTT() { }
86 
87  virtual SUMOAbstractRouter<E, V>* clone() const {
89  }
90 
96  class EdgeInfo {
97  public:
99  EdgeInfo(size_t id)
100  : edge(E::dictionary(id)), traveltime(std::numeric_limits<SUMOReal>::max()), prev(0), visited(false) {}
101 
103  const E* edge;
104 
107 
110 
112  bool visited;
113 
114  inline void reset() {
115  traveltime = std::numeric_limits<SUMOReal>::max();
116  visited = false;
117  }
118  };
119 
125  public:
127  bool operator()(const EdgeInfo* nod1, const EdgeInfo* nod2) const {
128  if (nod1->traveltime == nod2->traveltime) {
129  return nod1->edge->getNumericalID() > nod2->edge->getNumericalID();
130  }
131  return nod1->traveltime > nod2->traveltime;
132  }
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 && (vehicle == 0 || to != 0));
153  this->startQuery();
154  const SUMOVehicleClass vClass = vehicle == 0 ? SVC_IGNORING : vehicle->getVClass();
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() << "' TT: " << minimumInfo->traveltime << " 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  this->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 + this->getEffort(minEdge, vehicle, time + minimumInfo->traveltime);
190  // check all ways from the node with the minimal length
191  const std::vector<E*>& successors = minEdge->getSuccessors(vClass);
192  for (typename std::vector<E*>::const_iterator it = successors.begin(); it != successors.end(); ++it) {
193  const E* const follower = *it;
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  this->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  if (to != 0) {
219  myErrorMsgHandler->inform("No connection between '" + from->getID() + "' and '" + to->getID() + "' found.");
220  }
221  }
222 
223 
224  SUMOReal recomputeCosts(const std::vector<const E*>& edges, const V* const v, SUMOTime msTime) const {
225  const SUMOReal time = STEPS2TIME(msTime);
226  SUMOReal costs = 0;
227  for (typename std::vector<const E*>::const_iterator i = edges.begin(); i != edges.end(); ++i) {
228  if (PF::operator()(*i, v)) {
229  return -1;
230  }
231  costs += this->getEffort(*i, v, time + costs);
232  }
233  return costs;
234  }
235 
236 public:
238  void buildPathFrom(EdgeInfo* rbegin, std::vector<const E*>& edges) {
239  std::deque<const E*> tmp;
240  while (rbegin != 0) {
241  tmp.push_front((E*) rbegin->edge); // !!!
242  rbegin = rbegin->prev;
243  }
244  std::copy(tmp.begin(), tmp.end(), std::back_inserter(edges));
245  }
246 
247  const EdgeInfo& getEdgeInfo(size_t index) const {
248  return myEdgeInfos[index];
249  }
250 
251 private:
253  std::vector<EdgeInfo> myEdgeInfos;
254 
256  std::vector<EdgeInfo*> myFrontierList;
258  std::vector<EdgeInfo*> myFound;
259 
260  EdgeInfoByTTComparator myComparator;
261 
264 };
265 
266 
267 #endif
268 
269 /****************************************************************************/
270 
static MsgHandler * getWarningInstance()
Returns the instance to add warnings to.
Definition: MsgHandler.cpp:71
EdgeInfo(size_t id)
Constructor.
virtual ~DijkstraRouterTT()
Destructor.
SUMOReal recomputeCosts(const std::vector< const E * > &edges, const V *const v, SUMOTime msTime) const
bool visited
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...
void buildPathFrom(EdgeInfo *rbegin, std::vector< const E * > &edges)
Builds the path from marked edges.
SUMOVehicleClass
Definition of vehicle classes to differ between different lane usage and authority types...
const E * edge
The current edge.
SUMOReal(* Operation)(const E *const, const V *const, SUMOReal)
const EdgeInfo & getEdgeInfo(size_t index) const
Computes the shortest path through a network using the Dijkstra algorithm.
SUMOReal traveltime
Effort to reach the edge.
bool operator()(const EdgeInfo *nod1, const EdgeInfo *nod2) const
Comparing method.
#define max(a, b)
Definition: polyfonts.c:65
MsgHandler *const myErrorMsgHandler
the handler for routing errors
#define STEPS2TIME(x)
Definition: SUMOTime.h:65
EdgeInfoByTTComparator myComparator
Operation myOperation
The object's operation to perform.
std::string toString(const T &t, std::streamsize accuracy=OUTPUT_ACCURACY)
Definition: ToString.h:53
std::vector< EdgeInfo * > myFound
list of visited Edges (for resetting)
std::vector< EdgeInfo > myEdgeInfos
The container of edge information.
virtual SUMOAbstractRouter< E, V > * clone() const
void inform(std::string msg, bool addType=true)
adds a new error to the list
Definition: MsgHandler.cpp:89
int SUMOTime
Definition: SUMOTime.h:43
std::vector< EdgeInfo * > myFrontierList
A container for reusage of the min edge heap.
#define SUMOReal
Definition: config.h:218
void endQuery(int visits)
EdgeInfo * prev
The previous edge.
DijkstraRouterTT(size_t noE, bool unbuildIsWarning, Operation operation)
Constructor.
SUMOReal getEffort(const E *const e, const V *const v, SUMOReal t) const
vehicles ignoring classes