SUMO - Simulation of Urban MObility
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  // check whether from and to can be used
154  if (PF::operator()(from, vehicle)) {
155  myErrorMsgHandler->inform("Vehicle '" + vehicle->getID() + "' is not allowed on from edge '" + from->getID() + "'.");
156  return;
157  }
158  if (PF::operator()(to, vehicle)) {
159  myErrorMsgHandler->inform("Vehicle '" + vehicle->getID() + "' is not allowed on to edge '" + to->getID() + "'.");
160  return;
161  }
162  this->startQuery();
163  const SUMOVehicleClass vClass = vehicle == 0 ? SVC_IGNORING : vehicle->getVClass();
164  const SUMOReal time = STEPS2TIME(msTime);
165  if (this->myBulkMode) {
166  const EdgeInfo& toInfo = myEdgeInfos[to->getNumericalID()];
167  if (toInfo.visited) {
168  buildPathFrom(&toInfo, into);
169  this->endQuery(1);
170  return;
171  }
172  } else {
173  init();
174  // add begin node
175  EdgeInfo* const fromInfo = &(myEdgeInfos[from->getNumericalID()]);
176  fromInfo->traveltime = 0;
177  fromInfo->prev = 0;
178  myFrontierList.push_back(fromInfo);
179  }
180  // loop
181  int num_visited = 0;
182  while (!myFrontierList.empty()) {
183  num_visited += 1;
184  // use the node with the minimal length
185  EdgeInfo* const minimumInfo = myFrontierList.front();
186  const E* const minEdge = minimumInfo->edge;
187  // check whether the destination node was already reached
188  if (minEdge == to) {
189  buildPathFrom(minimumInfo, into);
190  this->endQuery(num_visited);
191 #ifdef DijkstraRouterTT_DEBUG_QUERY_PERF
192  std::cout << "visited " + toString(num_visited) + " edges (final path length: " + toString(into.size()) + ")\n";
193 #endif
194  return;
195  }
196  pop_heap(myFrontierList.begin(), myFrontierList.end(), myComparator);
197  myFrontierList.pop_back();
198  myFound.push_back(minimumInfo);
199  minimumInfo->visited = true;
200 #ifdef DijkstraRouterTT_DEBUG_QUERY
201  std::cout << "DEBUG: hit '" << minEdge->getID() << "' TT: " << minimumInfo->traveltime << " Q: ";
202  for (typename std::vector<EdgeInfo*>::iterator it = myFrontierList.begin(); it != myFrontierList.end(); it++) {
203  std::cout << (*it)->traveltime << "," << (*it)->edge->getID() << " ";
204  }
205  std::cout << "\n";
206 #endif
207  const SUMOReal traveltime = minimumInfo->traveltime + this->getEffort(minEdge, vehicle, time + minimumInfo->traveltime);
208  // check all ways from the node with the minimal length
209  const std::vector<E*>& successors = minEdge->getSuccessors(vClass);
210  for (typename std::vector<E*>::const_iterator it = successors.begin(); it != successors.end(); ++it) {
211  const E* const follower = *it;
212  EdgeInfo* const followerInfo = &(myEdgeInfos[follower->getNumericalID()]);
213  // check whether it can be used
214  if (PF::operator()(follower, vehicle)) {
215  continue;
216  }
217  const SUMOReal oldEffort = followerInfo->traveltime;
218  if (!followerInfo->visited && traveltime < oldEffort) {
219  followerInfo->traveltime = traveltime;
220  followerInfo->prev = minimumInfo;
221  if (oldEffort == std::numeric_limits<SUMOReal>::max()) {
222  myFrontierList.push_back(followerInfo);
223  push_heap(myFrontierList.begin(), myFrontierList.end(), myComparator);
224  } else {
225  push_heap(myFrontierList.begin(),
226  find(myFrontierList.begin(), myFrontierList.end(), followerInfo) + 1,
227  myComparator);
228  }
229  }
230  }
231  }
232  this->endQuery(num_visited);
233 #ifdef DijkstraRouterTT_DEBUG_QUERY_PERF
234  std::cout << "visited " + toString(num_visited) + " edges (final path length: " + toString(into.size()) + ")\n";
235 #endif
236  if (to != 0) {
237  myErrorMsgHandler->inform("No connection between edge '" + from->getID() + "' and edge '" + to->getID() + "' found.");
238  }
239  }
240 
241 
242  SUMOReal recomputeCosts(const std::vector<const E*>& edges, const V* const v, SUMOTime msTime) const {
243  const SUMOReal time = STEPS2TIME(msTime);
244  SUMOReal costs = 0;
245  for (typename std::vector<const E*>::const_iterator i = edges.begin(); i != edges.end(); ++i) {
246  if (PF::operator()(*i, v)) {
247  return -1;
248  }
249  costs += this->getEffort(*i, v, time + costs);
250  }
251  return costs;
252  }
253 
254 public:
256  void buildPathFrom(const EdgeInfo* rbegin, std::vector<const E*>& edges) {
257  std::vector<const E*> tmp;
258  while (rbegin != 0) {
259  tmp.push_back(rbegin->edge);
260  rbegin = rbegin->prev;
261  }
262  std::copy(tmp.rbegin(), tmp.rend(), std::back_inserter(edges));
263  }
264 
265  const EdgeInfo& getEdgeInfo(size_t index) const {
266  return myEdgeInfos[index];
267  }
268 
269 private:
271  std::vector<EdgeInfo> myEdgeInfos;
272 
274  std::vector<EdgeInfo*> myFrontierList;
276  std::vector<EdgeInfo*> myFound;
277 
278  EdgeInfoByTTComparator myComparator;
279 
282 };
283 
284 
285 #endif
286 
287 /****************************************************************************/
288 
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
long long int SUMOTime
Definition: SUMOTime.h:43
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...
SUMOVehicleClass
Definition of vehicle classes to differ between different lane usage and authority types...
const E * edge
The current edge.
const EdgeInfo & getEdgeInfo(size_t index) const
Computes the shortest path through a network using the Dijkstra algorithm.
void buildPathFrom(const EdgeInfo *rbegin, std::vector< const E * > &edges)
Builds the path from marked edges.
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
bool myBulkMode
whether we are currently operating several route queries in a bulk
#define STEPS2TIME(x)
Definition: SUMOTime.h:65
EdgeInfoByTTComparator myComparator
SUMOReal(* Operation)(const E *const, const V *const, SUMOReal)
Operation myOperation
The object&#39;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
std::vector< EdgeInfo * > myFrontierList
A container for reusage of the min edge heap.
#define SUMOReal
Definition: config.h:214
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