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-2017 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 double(* Operation)(const E* const, const V* const, double);
75 
81  class EdgeInfo {
82  public:
84  EdgeInfo(const E* e)
85  : edge(e), traveltime(std::numeric_limits<double>::max()), prev(0), visited(false) {}
86 
88  const E* edge;
89 
91  double traveltime;
92 
95 
97  bool visited;
98 
99  inline void reset() {
100  traveltime = std::numeric_limits<double>::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(EdgeInfo(i->edge));
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 source edge '" + from->getID() + "'.");
165  return false;
166  }
167  if (PF::operator()(to, vehicle)) {
168  myErrorMsgHandler->inform("Vehicle '" + vehicle->getID() + "' is not allowed on destination edge '" + to->getID() + "'.");
169  return false;
170  }
171  this->startQuery();
172 #ifdef DijkstraRouterTT_DEBUG_QUERY
173  std::cout << "DEBUG: starting search for '" << vehicle->getID() << "' time: " << STEPS2TIME(msTime) << "\n";
174 #endif
175  const SUMOVehicleClass vClass = vehicle == 0 ? SVC_IGNORING : vehicle->getVClass();
176  const double time = STEPS2TIME(msTime);
177  if (this->myBulkMode) {
178  const EdgeInfo& toInfo = myEdgeInfos[to->getNumericalID()];
179  if (toInfo.visited) {
180  buildPathFrom(&toInfo, into);
181  this->endQuery(1);
182  return true;
183  }
184  } else {
185  init();
186  // add begin node
187  EdgeInfo* const fromInfo = &(myEdgeInfos[from->getNumericalID()]);
188  fromInfo->traveltime = 0;
189  fromInfo->prev = 0;
190  myFrontierList.push_back(fromInfo);
191  }
192  // loop
193  int num_visited = 0;
194  while (!myFrontierList.empty()) {
195  num_visited += 1;
196  // use the node with the minimal length
197  EdgeInfo* const minimumInfo = myFrontierList.front();
198  const E* const minEdge = minimumInfo->edge;
199  // check whether the destination node was already reached
200  if (minEdge == to) {
201  buildPathFrom(minimumInfo, into);
202  this->endQuery(num_visited);
203 #ifdef DijkstraRouterTT_DEBUG_QUERY_PERF
204  std::cout << "visited " + toString(num_visited) + " edges (final path length=" + toString(into.size()) + " edges=" + toString(into) + ")\n";
205 #endif
206  return true;
207  }
208  pop_heap(myFrontierList.begin(), myFrontierList.end(), myComparator);
209  myFrontierList.pop_back();
210  myFound.push_back(minimumInfo);
211  minimumInfo->visited = true;
212 #ifdef DijkstraRouterTT_DEBUG_QUERY
213  std::cout << "DEBUG: hit '" << minEdge->getID() << "' TT: " << minimumInfo->traveltime << " Q: ";
214  for (typename std::vector<EdgeInfo*>::iterator it = myFrontierList.begin(); it != myFrontierList.end(); it++) {
215  std::cout << (*it)->traveltime << "," << (*it)->edge->getID() << " ";
216  }
217  std::cout << "\n";
218 #endif
219  const double traveltime = minimumInfo->traveltime + this->getEffort(minEdge, vehicle, time + minimumInfo->traveltime);
220  // check all ways from the node with the minimal length
221  const std::vector<E*>& successors = minEdge->getSuccessors(vClass);
222  for (typename std::vector<E*>::const_iterator it = successors.begin(); it != successors.end(); ++it) {
223  const E* const follower = *it;
224  EdgeInfo* const followerInfo = &(myEdgeInfos[follower->getNumericalID()]);
225  // check whether it can be used
226  if (PF::operator()(follower, vehicle)) {
227  continue;
228  }
229  const double oldEffort = followerInfo->traveltime;
230  if (!followerInfo->visited && traveltime < oldEffort) {
231  followerInfo->traveltime = traveltime;
232  followerInfo->prev = minimumInfo;
233  if (oldEffort == std::numeric_limits<double>::max()) {
234  myFrontierList.push_back(followerInfo);
235  push_heap(myFrontierList.begin(), myFrontierList.end(), myComparator);
236  } else {
237  push_heap(myFrontierList.begin(),
238  find(myFrontierList.begin(), myFrontierList.end(), followerInfo) + 1,
239  myComparator);
240  }
241  }
242  }
243  }
244  this->endQuery(num_visited);
245 #ifdef DijkstraRouterTT_DEBUG_QUERY_PERF
246  std::cout << "visited " + toString(num_visited) + " edges (unsuccesful path length: " + toString(into.size()) + ")\n";
247 #endif
248  if (to != 0) {
249  myErrorMsgHandler->inform("No connection between edge '" + from->getID() + "' and edge '" + to->getID() + "' found.");
250  }
251  return false;
252  }
253 
254 
255  double recomputeCosts(const std::vector<const E*>& edges, const V* const v, SUMOTime msTime) const {
256  const double time = STEPS2TIME(msTime);
257  double costs = 0;
258  for (typename std::vector<const E*>::const_iterator i = edges.begin(); i != edges.end(); ++i) {
259  if (PF::operator()(*i, v)) {
260  return -1;
261  }
262  costs += this->getEffort(*i, v, time + costs);
263  }
264  return costs;
265  }
266 
267 public:
269  void buildPathFrom(const EdgeInfo* rbegin, std::vector<const E*>& edges) {
270  std::vector<const E*> tmp;
271  while (rbegin != 0) {
272  tmp.push_back(rbegin->edge);
273  rbegin = rbegin->prev;
274  }
275  std::copy(tmp.rbegin(), tmp.rend(), std::back_inserter(edges));
276  }
277 
278  const EdgeInfo& getEdgeInfo(int index) const {
279  return myEdgeInfos[index];
280  }
281 
282 private:
284  std::vector<EdgeInfo> myEdgeInfos;
285 
287  std::vector<EdgeInfo*> myFrontierList;
289  std::vector<EdgeInfo*> myFound;
290 
291  EdgeInfoByTTComparator myComparator;
292 
295 };
296 
297 
298 #endif
299 
300 /****************************************************************************/
301 
static MsgHandler * getWarningInstance()
Returns the instance to add warnings to.
Definition: MsgHandler.cpp:67
double getEffort(const E *const e, const V *const v, double t) const
virtual ~DijkstraRouterTT()
Destructor.
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.
#define max(a, b)
Definition: polyfonts.c:65
MsgHandler *const myErrorMsgHandler
the handler for routing errors
const EdgeInfo & getEdgeInfo(int index) const
std::string toString(const T &t, std::streamsize accuracy=gPrecision)
Definition: ToString.h:56
double traveltime
Effort to reach the edge.
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...
bool myBulkMode
whether we are currently operating several route queries in a bulk
#define STEPS2TIME(x)
Definition: SUMOTime.h:65
double(* Operation)(const E *const, const V *const, double)
EdgeInfoByTTComparator myComparator
Operation myOperation
The object&#39;s operation to perform.
std::vector< EdgeInfo * > myFound
list of visited Edges (for resetting)
std::vector< EdgeInfo > myEdgeInfos
The container of edge information.
double recomputeCosts(const std::vector< const E *> &edges, const V *const v, SUMOTime msTime) const
void inform(std::string msg, bool addType=true)
adds a new error to the list
Definition: MsgHandler.cpp:85
virtual SUMOAbstractRouter< E, V > * clone()
DijkstraRouterTT(const std::vector< E *> &edges, bool unbuildIsWarning, Operation operation)
Constructor.
std::vector< EdgeInfo * > myFrontierList
A container for reusage of the min edge heap.
void endQuery(int visits)
EdgeInfo * prev
The previous edge.
long long int SUMOTime
Definition: TraCIDefs.h:52
vehicles ignoring classes
DijkstraRouterTT(const std::vector< EdgeInfo > &edgeInfos, bool unbuildIsWarning, Operation operation)
bool operator()(const EdgeInfo *nod1, const EdgeInfo *nod2) const
Comparing method.