SUMO - Simulation of Urban MObility
CHRouter.h
Go to the documentation of this file.
1 /****************************************************************************/
9 // Shortest Path search using a Contraction Hierarchy
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 CHRouter_h
23 #define CHRouter_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 <string>
36 #include <functional>
37 #include <vector>
38 #include <set>
39 #include <limits>
40 #include <algorithm>
41 #include <iterator>
42 #include <utils/common/SysUtils.h>
44 #include <utils/common/StdDefs.h>
46 #include "CHBuilder.h"
47 
48 //#define CHRouter_DEBUG_QUERY
49 //#define CHRouter_DEBUG_QUERY_PERF
50 
51 // ===========================================================================
52 // class definitions
53 // ===========================================================================
68 template<class E, class V, class PF>
69 class CHRouter: public SUMOAbstractRouter<E, V>, public PF {
70 
71 public:
73  typedef double(* Operation)(const E* const, const V* const, double);
74 
80  class EdgeInfo {
81  public:
83  EdgeInfo(const E* e) :
84  edge(e),
85  traveltime(std::numeric_limits<double>::max()),
86  prev(0),
87  visited(false) {
88  }
89 
91  const E* edge;
92 
94  double traveltime;
95 
98 
100  bool visited;
101 
102  inline void reset() {
103  traveltime = std::numeric_limits<double>::max();
104  visited = false;
105  }
106  };
107 
108 
110  typedef std::pair<const EdgeInfo*, const EdgeInfo*> Meeting;
111 
116  class Unidirectional: public PF {
117  public:
119  Unidirectional(const std::vector<E*>& edges, bool forward):
120  myAmForward(forward),
121  myVehicle(0) {
122  for (typename std::vector<E*>::const_iterator i = edges.begin(); i != edges.end(); ++i) {
123  myEdgeInfos.push_back(EdgeInfo(*i));
124  }
125  }
126 
127  inline bool found(const E* edge) const {
128  return myFound.count(edge) > 0;
129  }
130 
131  inline EdgeInfo* getEdgeInfo(const E* const edge) {
132  return &(myEdgeInfos[edge->getNumericalID()]);
133  }
134 
135  inline const EdgeInfo* getEdgeInfo(const E* const edge) const {
136  return &(myEdgeInfos[edge->getNumericalID()]);
137  }
138 
144  public:
146  bool operator()(const EdgeInfo* nod1, const EdgeInfo* nod2) const {
147  if (nod1->traveltime == nod2->traveltime) {
148  return nod1->edge->getNumericalID() > nod2->edge->getNumericalID();
149  }
150  return nod1->traveltime > nod2->traveltime;
151  }
152  };
153 
154 
155  void init(const E* const start, const V* const vehicle) {
156  assert(vehicle != 0);
157  // all EdgeInfos touched in the previous query are either in myFrontier or myFound: clean those up
158  for (typename std::vector<EdgeInfo*>::iterator i = myFrontier.begin(); i != myFrontier.end(); i++) {
159  (*i)->reset();
160  }
161  myFrontier.clear();
162  for (typename std::set<const E*>::const_iterator i = myFound.begin(); i != myFound.end(); i++) {
163  getEdgeInfo(*i)->reset();
164  }
165  myFound.clear();
166  myVehicle = vehicle;
167  EdgeInfo* startInfo = getEdgeInfo(start);
168  startInfo->traveltime = 0;
169  startInfo->prev = 0;
170  myFrontier.push_back(startInfo);
171  }
172 
173 
174  typedef std::vector<typename CHBuilder<E, V>::Connection> ConnectionVector;
179  bool step(const std::vector<ConnectionVector>& uplinks, const Unidirectional& otherSearch, double& minTTSeen, Meeting& meeting) {
180  // pop the node with the minimal length
181  EdgeInfo* const minimumInfo = myFrontier.front();
182  pop_heap(myFrontier.begin(), myFrontier.end(), myComparator);
183  myFrontier.pop_back();
184  // check for a meeting with the other search
185  const E* const minEdge = minimumInfo->edge;
186 #ifdef CHRouter_DEBUG_QUERY
187  std::cout << "DEBUG: " << (myAmForward ? "Forward" : "Backward") << " hit '" << minEdge->getID() << "' Q: ";
188  for (typename std::vector<EdgeInfo*>::iterator it = myFrontier.begin(); it != myFrontier.end(); it++) {
189  std::cout << (*it)->traveltime << "," << (*it)->edge->getID() << " ";
190  }
191  std::cout << "\n";
192 #endif
193  if (otherSearch.found(minEdge)) {
194  const EdgeInfo* const otherInfo = otherSearch.getEdgeInfo(minEdge);
195  const double ttSeen = minimumInfo->traveltime + otherInfo->traveltime;
196 #ifdef CHRouter_DEBUG_QUERY
197  std::cout << "DEBUG: " << (myAmForward ? "Forward" : "Backward") << "-Search hit other search at '" << minEdge->getID() << "', tt: " << ttSeen << " \n";
198 #endif
199  if (ttSeen < minTTSeen) {
200  minTTSeen = ttSeen;
201  if (myAmForward) {
202  meeting.first = minimumInfo;
203  meeting.second = otherInfo;
204  } else {
205  meeting.first = otherInfo;
206  meeting.second = minimumInfo;
207  }
208  }
209  }
210  // prepare next steps
211  minimumInfo->visited = true;
212  // XXX we only need to keep found elements if they have a higher rank than the lowest rank in the other search queue
213  myFound.insert(minimumInfo->edge);
214  const ConnectionVector& upward = uplinks[minEdge->getNumericalID()];
215  for (typename ConnectionVector::const_iterator it = upward.begin(); it != upward.end(); it++) {
216  EdgeInfo* upwardInfo = &myEdgeInfos[it->target];
217  const double traveltime = minimumInfo->traveltime + it->cost;
218  const SUMOVehicleClass svc = myVehicle->getVClass();
219  // check whether it can be used
220  if ((it->permissions & svc) != svc) {
221  continue;
222  }
223  const double oldTraveltime = upwardInfo->traveltime;
224  if (!upwardInfo->visited && traveltime < oldTraveltime) {
225  upwardInfo->traveltime = traveltime;
226  upwardInfo->prev = minimumInfo;
227  if (oldTraveltime == std::numeric_limits<double>::max()) {
228  myFrontier.push_back(upwardInfo);
229  push_heap(myFrontier.begin(), myFrontier.end(), myComparator);
230  } else {
231  push_heap(myFrontier.begin(),
232  find(myFrontier.begin(), myFrontier.end(), upwardInfo) + 1,
233  myComparator);
234  }
235  }
236  }
237  // @note: this effectively does a full dijkstra search.
238  // the effort compared to the naive stopping criterion is thus
239  // quadrupled. We could implement a better stopping criterion (Holte)
240  // However since the search shall take place in a contracted graph
241  // it probably does not matter
242  return !myFrontier.empty() && myFrontier.front()->traveltime < minTTSeen;
243  }
244 
245  private:
249  std::vector<EdgeInfo*> myFrontier;
251  std::set<const E*> myFound;
253  std::vector<EdgeInfo> myEdgeInfos;
254 
256 
257  const V* myVehicle;
258 
259  };
260 
266  CHRouter(const std::vector<E*>& edges, bool unbuildIsWarning, Operation operation,
267  const SUMOVehicleClass svc,
268  SUMOTime weightPeriod,
269  bool validatePermissions):
270  SUMOAbstractRouter<E, V>(operation, "CHRouter"),
271  myEdges(edges),
272  myErrorMsgHandler(unbuildIsWarning ? MsgHandler::getWarningInstance() : MsgHandler::getErrorInstance()),
273  myForwardSearch(edges, true),
274  myBackwardSearch(edges, false),
275  myHierarchyBuilder(new CHBuilder<E, V>(edges, unbuildIsWarning, svc, validatePermissions)),
276  myHierarchy(0),
277  myWeightPeriod(weightPeriod),
278  myValidUntil(0),
279  mySVC(svc) {
280  }
281 
284  CHRouter(const std::vector<E*>& edges, bool unbuildIsWarning, Operation operation,
285  const SUMOVehicleClass svc,
286  SUMOTime weightPeriod,
287  const typename CHBuilder<E, V>::Hierarchy* hierarchy) :
288  SUMOAbstractRouter<E, V>(operation, "CHRouter"),
289  myEdges(edges),
290  myErrorMsgHandler(unbuildIsWarning ? MsgHandler::getWarningInstance() : MsgHandler::getErrorInstance()),
291  myForwardSearch(edges, true),
292  myBackwardSearch(edges, false),
294  myHierarchy(hierarchy),
295  myWeightPeriod(weightPeriod),
296  myValidUntil(0),
297  mySVC(svc) {
298  }
299 
301  virtual ~CHRouter() {
302  if (myHierarchyBuilder != 0) {
303  delete myHierarchy;
304  delete myHierarchyBuilder;
305  }
306  }
307 
308 
310  WRITE_MESSAGE("Cloning Contraction Hierarchy for " + SumoVehicleClassStrings.getString(mySVC) + " and time " + time2string(myValidUntil) + ".");
313  clone->myValidUntil = myValidUntil;
314  return clone;
315  }
316 
321  virtual bool compute(const E* from, const E* to, const V* const vehicle,
322  SUMOTime msTime, std::vector<const E*>& into) {
323  assert(from != 0 && to != 0);
324  // assert(myHierarchyBuilder.mySPTree->validatePermissions() || vehicle->getVClass() == mySVC || mySVC == SVC_IGNORING);
325  // do we need to rebuild the hierarchy?
326  if (msTime >= myValidUntil) {
327  while (msTime >= myValidUntil) {
329  }
331  }
332  // ready for routing
333  this->startQuery();
334  myForwardSearch.init(from, vehicle);
335  myBackwardSearch.init(to, vehicle);
336  double minTTSeen = std::numeric_limits<double>::max();
337  Meeting meeting(static_cast<EdgeInfo*>(0), static_cast<EdgeInfo*>(0));
338  bool continueForward = true;
339  bool continueBackward = true;
340  int num_visited_fw = 0;
341  int num_visited_bw = 0;
342  bool result = true;
343  while (continueForward || continueBackward) {
344  if (continueForward) {
345  continueForward = myForwardSearch.step(myHierarchy->forwardUplinks, myBackwardSearch, minTTSeen, meeting);
346  num_visited_fw += 1;
347  }
348  if (continueBackward) {
349  continueBackward = myBackwardSearch.step(myHierarchy->backwardUplinks, myForwardSearch, minTTSeen, meeting);
350  num_visited_bw += 1;
351  }
352  }
353  if (minTTSeen < std::numeric_limits<double>::max()) {
354  buildPathFromMeeting(meeting, into);
355  } else {
356  myErrorMsgHandler->inform("No connection between edge '" + from->getID() + "' and edge '" + to->getID() + "' found.");
357  result = false;
358  }
359 #ifdef CHRouter_DEBUG_QUERY_PERF
360  std::cout << "visited " << num_visited_fw + num_visited_bw << " edges (" << num_visited_fw << "," << num_visited_bw << ") ,final path length: " + toString(into.size()) + ")\n";
361 #endif
362  this->endQuery(num_visited_bw + num_visited_fw);
363  return result;
364  }
365 
366 
367  double recomputeCosts(const std::vector<const E*>& edges, const V* const v, SUMOTime msTime) const {
368  const double time = STEPS2TIME(msTime);
369  double costs = 0;
370  for (typename std::vector<const E*>::const_iterator i = edges.begin(); i != edges.end(); ++i) {
371  if (PF::operator()(*i, v)) {
372  return -1;
373  }
374  costs += this->getEffort(*i, v, time + costs);
375  }
376  return costs;
377  }
378 
380 
382  void buildPathFromMeeting(Meeting meeting, std::vector<const E*>& into) const {
383  std::deque<const E*> tmp;
384  const EdgeInfo* backtrack = meeting.first;
385  while (backtrack != 0) {
386  tmp.push_front((E*) backtrack->edge); // !!!
387  backtrack = backtrack->prev;
388  }
389  backtrack = meeting.second->prev; // don't use central edge twice
390  while (backtrack != 0) {
391  tmp.push_back((E*) backtrack->edge); // !!!
392  backtrack = backtrack->prev;
393  }
394  // expand shortcuts
395  const E* prev = 0;
396  while (!tmp.empty()) {
397  const E* cur = tmp.front();
398  tmp.pop_front();
399  if (prev == 0) {
400  into.push_back(cur);
401  prev = cur;
402  } else {
403  const E* via = getVia(prev, cur);
404  if (via == 0) {
405  into.push_back(cur);
406  prev = cur;
407  } else {
408  tmp.push_front(cur);
409  tmp.push_front(via);
410  }
411  }
412  }
413  }
414 
415  void buildContractionHierarchy(SUMOTime time, const V* const vehicle) {
416  if (myHierarchyBuilder != 0) {
417  delete myHierarchy;
418  myHierarchy = myHierarchyBuilder->buildContractionHierarchy(time, vehicle, this);
419  }
420  // declare new validUntil (prevent overflow)
422  myValidUntil = time + myWeightPeriod;
423  } else {
425  }
426  }
427 
428 private:
429  // retrieve the via edge for a shortcut
430  const E* getVia(const E* forwardFrom, const E* forwardTo) const {
431  typename CHBuilder<E, V>::ConstEdgePair forward(forwardFrom, forwardTo);
432  typename CHBuilder<E, V>::ShortcutVia::const_iterator it = myHierarchy->shortcuts.find(forward);
433  if (it != myHierarchy->shortcuts.end()) {
434  return it->second;
435  } else {
436  return 0;
437  }
438  }
439 
440 
441 private:
443  const std::vector<E*>& myEdges;
444 
447 
451 
454 
457 
460 
463 };
464 
465 
466 #endif
467 
468 /****************************************************************************/
469 
Computes the shortest path through a contracted network.
Definition: CHRouter.h:69
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
double(* Operation)(const E *const, const V *const, double)
Type of the function that is used to retrieve the edge effort.
Definition: CHRouter.h:73
const SUMOTime myWeightPeriod
the validity duration of one weight interval
Definition: CHRouter.h:456
EdgeInfo * getEdgeInfo(const E *const edge)
Definition: CHRouter.h:131
std::vector< typename CHBuilder< E, V >::Connection > ConnectionVector
Definition: CHRouter.h:174
SUMOVehicleClass
Definition of vehicle classes to differ between different lane usage and authority types...
virtual ~CHRouter()
Destructor.
Definition: CHRouter.h:301
Unidirectional myForwardSearch
the unidirectional search queues
Definition: CHRouter.h:449
CHBuilder< E, V > * myHierarchyBuilder
Definition: CHRouter.h:452
std::string time2string(SUMOTime t)
Definition: SUMOTime.cpp:60
std::vector< EdgeInfo * > myFrontier
the min edge heap
Definition: CHRouter.h:249
bool visited
Whether the shortest path to this edge is already found.
Definition: CHRouter.h:100
bool operator()(const EdgeInfo *nod1, const EdgeInfo *nod2) const
Comparing method.
Definition: CHRouter.h:146
EdgeInfoByTTComparator myComparator
Definition: CHRouter.h:255
CHRouter(const std::vector< E *> &edges, bool unbuildIsWarning, Operation operation, const SUMOVehicleClass svc, SUMOTime weightPeriod, bool validatePermissions)
Constructor.
Definition: CHRouter.h:266
Unidirectional myBackwardSearch
Definition: CHRouter.h:450
void buildPathFromMeeting(Meeting meeting, std::vector< const E *> &into) const
normal routing methods
Definition: CHRouter.h:382
virtual SUMOAbstractRouter< E, V > * clone()
Definition: CHRouter.h:309
#define max(a, b)
Definition: polyfonts.c:65
SUMOTime myValidUntil
the validity duration of the current hierarchy (exclusive)
Definition: CHRouter.h:459
double recomputeCosts(const std::vector< const E *> &edges, const V *const v, SUMOTime msTime) const
Definition: CHRouter.h:367
std::vector< EdgeInfo > myEdgeInfos
The container of edge information.
Definition: CHRouter.h:253
std::string toString(const T &t, std::streamsize accuracy=gPrecision)
Definition: ToString.h:56
Unidirectional(const std::vector< E *> &edges, bool forward)
Constructor.
Definition: CHRouter.h:119
void init(const E *const start, const V *const vehicle)
Definition: CHRouter.h:155
#define STEPS2TIME(x)
Definition: SUMOTime.h:65
const SUMOVehicleClass mySVC
the permissions for which the hierarchy was constructed
Definition: CHRouter.h:462
bool found(const E *edge) const
Definition: CHRouter.h:127
std::pair< const E *, const E * > ConstEdgePair
Definition: CHBuilder.h:86
double traveltime
Effort to reach the edge.
Definition: CHRouter.h:94
std::pair< const EdgeInfo *, const EdgeInfo * > Meeting
A meeting point of the two search scopes.
Definition: CHRouter.h:110
StringBijection< SUMOVehicleClass > SumoVehicleClassStrings(sumoVehicleClassStringInitializer, SVC_CUSTOM2, false)
Operation myOperation
The object&#39;s operation to perform.
const E * getVia(const E *forwardFrom, const E *forwardTo) const
Definition: CHRouter.h:430
const std::vector< E * > & myEdges
all edges with numerical ids
Definition: CHRouter.h:443
MsgHandler *const myErrorMsgHandler
the handler for routing errors
Definition: CHRouter.h:446
void inform(std::string msg, bool addType=true)
adds a new error to the list
Definition: MsgHandler.cpp:85
const EdgeInfo * getEdgeInfo(const E *const edge) const
Definition: CHRouter.h:135
bool myAmForward
the role of this search
Definition: CHRouter.h:247
void endQuery(int visits)
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 traveltime in the contracted graph...
Definition: CHRouter.h:321
long long int SUMOTime
Definition: TraCIDefs.h:52
#define WRITE_MESSAGE(msg)
Definition: MsgHandler.h:201
std::set< const E * > myFound
the set of visited (settled) Edges
Definition: CHRouter.h:251
EdgeInfo(const E *e)
Constructor.
Definition: CHRouter.h:83
const E * edge
The current edge.
Definition: CHRouter.h:91
const CHBuilder< E, V >::Hierarchy * myHierarchy
Definition: CHRouter.h:453
bool step(const std::vector< ConnectionVector > &uplinks, const Unidirectional &otherSearch, double &minTTSeen, Meeting &meeting)
explore on element from the frontier,update minTTSeen and meeting if an EdgeInfo found by the otherSe...
Definition: CHRouter.h:179
void buildContractionHierarchy(SUMOTime time, const V *const vehicle)
Definition: CHRouter.h:415
EdgeInfo * prev
The previous edge.
Definition: CHRouter.h:97
CHRouter(const std::vector< E *> &edges, bool unbuildIsWarning, Operation operation, const SUMOVehicleClass svc, SUMOTime weightPeriod, const typename CHBuilder< E, V >::Hierarchy *hierarchy)
Cloning constructor.
Definition: CHRouter.h:284