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-2016 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);
75 
81  class EdgeInfo {
82  public:
84  EdgeInfo(const E* e)
85  : edge(e), traveltime(std::numeric_limits<SUMOReal>::max()), prev(0), visited(false) {}
86 
88  const E* edge;
89 
92 
95 
97  bool visited;
98 
99  inline void reset() {
100  traveltime = std::numeric_limits<SUMOReal>::max();
101  visited = false;
102  }
103  };
104 
110  public:
112  bool operator()(const EdgeInfo* nod1, const EdgeInfo* nod2) const {
113  if (nod1->traveltime == nod2->traveltime) {
114  return nod1->edge->getNumericalID() > nod2->edge->getNumericalID();
115  }
116  return nod1->traveltime > nod2->traveltime;
117  }
118  };
119 
121  DijkstraRouterTT(const std::vector<E*>& edges, bool unbuildIsWarning, Operation operation) :
122  SUMOAbstractRouter<E, V>(operation, "DijkstraRouterTT"),
123  myErrorMsgHandler(unbuildIsWarning ? MsgHandler::getWarningInstance() : MsgHandler::getErrorInstance()) {
124  for (typename std::vector<E*>::const_iterator i = edges.begin(); i != edges.end(); ++i) {
125  myEdgeInfos.push_back(EdgeInfo(*i));
126  }
127  }
128 
129  DijkstraRouterTT(const std::vector<EdgeInfo>& edgeInfos, bool unbuildIsWarning, Operation operation) :
130  SUMOAbstractRouter<E, V>(operation, "DijkstraRouterTT"),
131  myErrorMsgHandler(unbuildIsWarning ? MsgHandler::getWarningInstance() : MsgHandler::getErrorInstance()) {
132  for (typename std::vector<EdgeInfo>::const_iterator i = edgeInfos.begin(); i != edgeInfos.end(); ++i) {
133  myEdgeInfos.push_back(*i);
134  }
135  }
136 
138  virtual ~DijkstraRouterTT() { }
139 
142  }
143 
144  void init() {
145  // all EdgeInfos touched in the previous query are either in myFrontierList or myFound: clean those up
146  for (typename std::vector<EdgeInfo*>::iterator i = myFrontierList.begin(); i != myFrontierList.end(); i++) {
147  (*i)->reset();
148  }
149  myFrontierList.clear();
150  for (typename std::vector<EdgeInfo*>::iterator i = myFound.begin(); i != myFound.end(); i++) {
151  (*i)->reset();
152  }
153  myFound.clear();
154  }
155 
156 
159  virtual bool compute(const E* from, const E* to, const V* const vehicle,
160  SUMOTime msTime, std::vector<const E*>& into) {
161  assert(from != 0 && (vehicle == 0 || to != 0));
162  // check whether from and to can be used
163  if (PF::operator()(from, vehicle)) {
164  myErrorMsgHandler->inform("Vehicle '" + vehicle->getID() + "' is not allowed on from edge '" + from->getID() + "'.");
165  return false;
166  }
167  if (PF::operator()(to, vehicle)) {
168  myErrorMsgHandler->inform("Vehicle '" + vehicle->getID() + "' is not allowed on to edge '" + to->getID() + "'.");
169  return false;
170  }
171  this->startQuery();
172  const SUMOVehicleClass vClass = vehicle == 0 ? SVC_IGNORING : vehicle->getVClass();
173  const SUMOReal time = STEPS2TIME(msTime);
174  if (this->myBulkMode) {
175  const EdgeInfo& toInfo = myEdgeInfos[to->getNumericalID()];
176  if (toInfo.visited) {
177  buildPathFrom(&toInfo, into);
178  this->endQuery(1);
179  return true;
180  }
181  } else {
182  init();
183  // add begin node
184  EdgeInfo* const fromInfo = &(myEdgeInfos[from->getNumericalID()]);
185  fromInfo->traveltime = 0;
186  fromInfo->prev = 0;
187  myFrontierList.push_back(fromInfo);
188  }
189  // loop
190  int num_visited = 0;
191  while (!myFrontierList.empty()) {
192  num_visited += 1;
193  // use the node with the minimal length
194  EdgeInfo* const minimumInfo = myFrontierList.front();
195  const E* const minEdge = minimumInfo->edge;
196  // check whether the destination node was already reached
197  if (minEdge == to) {
198  buildPathFrom(minimumInfo, into);
199  this->endQuery(num_visited);
200 #ifdef DijkstraRouterTT_DEBUG_QUERY_PERF
201  std::cout << "visited " + toString(num_visited) + " edges (final path length: " + toString(into.size()) + ")\n";
202 #endif
203  return true;
204  }
205  pop_heap(myFrontierList.begin(), myFrontierList.end(), myComparator);
206  myFrontierList.pop_back();
207  myFound.push_back(minimumInfo);
208  minimumInfo->visited = true;
209 #ifdef DijkstraRouterTT_DEBUG_QUERY
210  std::cout << "DEBUG: hit '" << minEdge->getID() << "' TT: " << minimumInfo->traveltime << " Q: ";
211  for (typename std::vector<EdgeInfo*>::iterator it = myFrontierList.begin(); it != myFrontierList.end(); it++) {
212  std::cout << (*it)->traveltime << "," << (*it)->edge->getID() << " ";
213  }
214  std::cout << "\n";
215 #endif
216  const SUMOReal traveltime = minimumInfo->traveltime + this->getEffort(minEdge, vehicle, time + minimumInfo->traveltime);
217  // check all ways from the node with the minimal length
218  const std::vector<E*>& successors = minEdge->getSuccessors(vClass);
219  for (typename std::vector<E*>::const_iterator it = successors.begin(); it != successors.end(); ++it) {
220  const E* const follower = *it;
221  EdgeInfo* const followerInfo = &(myEdgeInfos[follower->getNumericalID()]);
222  // check whether it can be used
223  if (PF::operator()(follower, vehicle)) {
224  continue;
225  }
226  const SUMOReal oldEffort = followerInfo->traveltime;
227  if (!followerInfo->visited && traveltime < oldEffort) {
228  followerInfo->traveltime = traveltime;
229  followerInfo->prev = minimumInfo;
230  if (oldEffort == std::numeric_limits<SUMOReal>::max()) {
231  myFrontierList.push_back(followerInfo);
232  push_heap(myFrontierList.begin(), myFrontierList.end(), myComparator);
233  } else {
234  push_heap(myFrontierList.begin(),
235  find(myFrontierList.begin(), myFrontierList.end(), followerInfo) + 1,
236  myComparator);
237  }
238  }
239  }
240  }
241  this->endQuery(num_visited);
242 #ifdef DijkstraRouterTT_DEBUG_QUERY_PERF
243  std::cout << "visited " + toString(num_visited) + " edges (final path length: " + toString(into.size()) + ")\n";
244 #endif
245  if (to != 0) {
246  myErrorMsgHandler->inform("No connection between edge '" + from->getID() + "' and edge '" + to->getID() + "' found.");
247  }
248  return false;
249  }
250 
251 
252  SUMOReal recomputeCosts(const std::vector<const E*>& edges, const V* const v, SUMOTime msTime) const {
253  const SUMOReal time = STEPS2TIME(msTime);
254  SUMOReal costs = 0;
255  for (typename std::vector<const E*>::const_iterator i = edges.begin(); i != edges.end(); ++i) {
256  if (PF::operator()(*i, v)) {
257  return -1;
258  }
259  costs += this->getEffort(*i, v, time + costs);
260  }
261  return costs;
262  }
263 
264 public:
266  void buildPathFrom(const EdgeInfo* rbegin, std::vector<const E*>& edges) {
267  std::vector<const E*> tmp;
268  while (rbegin != 0) {
269  tmp.push_back(rbegin->edge);
270  rbegin = rbegin->prev;
271  }
272  std::copy(tmp.rbegin(), tmp.rend(), std::back_inserter(edges));
273  }
274 
275  const EdgeInfo& getEdgeInfo(int index) const {
276  return myEdgeInfos[index];
277  }
278 
279 private:
281  std::vector<EdgeInfo> myEdgeInfos;
282 
284  std::vector<EdgeInfo*> myFrontierList;
286  std::vector<EdgeInfo*> myFound;
287 
288  EdgeInfoByTTComparator myComparator;
289 
292 };
293 
294 
295 #endif
296 
297 /****************************************************************************/
298 
const EdgeInfo & getEdgeInfo(int index) const
static MsgHandler * getWarningInstance()
Returns the instance to add warnings to.
Definition: MsgHandler.cpp:71
virtual ~DijkstraRouterTT()
Destructor.
SUMOReal recomputeCosts(const std::vector< const E * > &edges, const V *const v, SUMOTime msTime) const
DijkstraRouterTT(const std::vector< E * > &edges, bool unbuildIsWarning, Operation operation)
Constructor.
long long int SUMOTime
Definition: SUMOTime.h:43
bool visited
The previous edge.
SUMOVehicleClass
Definition of vehicle classes to differ between different lane usage and authority types...
const E * edge
The current edge.
EdgeInfo(const E *e)
Constructor.
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:55
virtual bool 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)
std::vector< EdgeInfo > myEdgeInfos
The container of edge information.
void inform(std::string msg, bool addType=true)
adds a new error to the list
Definition: MsgHandler.cpp:89
virtual SUMOAbstractRouter< E, V > * clone()
std::vector< EdgeInfo * > myFrontierList
A container for reusage of the min edge heap.
#define SUMOReal
Definition: config.h:213
void endQuery(int visits)
EdgeInfo * prev
The previous edge.
SUMOReal getEffort(const E *const e, const V *const v, SUMOReal t) const
vehicles ignoring classes
DijkstraRouterTT(const std::vector< EdgeInfo > &edgeInfos, bool unbuildIsWarning, Operation operation)