SUMO - Simulation of Urban MObility
CHRouter.h
Go to the documentation of this file.
1 /****************************************************************************/
2 // Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.org/sumo
3 // Copyright (C) 2001-2018 German Aerospace Center (DLR) and others.
4 // This program and the accompanying materials
5 // are made available under the terms of the Eclipse Public License v2.0
6 // which accompanies this distribution, and is available at
7 // http://www.eclipse.org/legal/epl-v20.html
8 // SPDX-License-Identifier: EPL-2.0
9 /****************************************************************************/
17 // Shortest Path search using a Contraction Hierarchy
18 /****************************************************************************/
19 #ifndef CHRouter_h
20 #define CHRouter_h
21 
22 
23 // ===========================================================================
24 // included modules
25 // ===========================================================================
26 #include <config.h>
27 
28 #include <string>
29 #include <functional>
30 #include <vector>
31 #include <set>
32 #include <limits>
33 #include <algorithm>
34 #include <iterator>
35 #include <deque>
36 #include <utils/common/SysUtils.h>
38 #include <utils/common/StdDefs.h>
40 #include "CHBuilder.h"
41 
42 //#define CHRouter_DEBUG_QUERY
43 //#define CHRouter_DEBUG_QUERY_PERF
44 
45 // ===========================================================================
46 // class definitions
47 // ===========================================================================
62 template<class E, class V, class BASE>
63 class CHRouter: public BASE {
64 
65 public:
67  typedef double(* Operation)(const E* const, const V* const, double);
68 
70  typedef std::pair<const typename BASE::EdgeInfo*, const typename BASE::EdgeInfo*> Meeting;
71 
77  public:
79  Unidirectional(const std::vector<E*>& edges, bool forward):
80  myAmForward(forward),
81  myVehicle(0) {
82  for (const E* const e: edges) {
83  myEdgeInfos.push_back(typename BASE::EdgeInfo(e));
84  }
85  }
86 
87  inline bool found(const E* const edge) const {
88  return myFound.count(edge) > 0;
89  }
90 
91  inline typename BASE::EdgeInfo* getEdgeInfo(const E* const edge) {
92  return &(myEdgeInfos[edge->getNumericalID()]);
93  }
94 
95  inline const typename BASE::EdgeInfo* getEdgeInfo(const E* const edge) const {
96  return &(myEdgeInfos[edge->getNumericalID()]);
97  }
98 
104  public:
106  bool operator()(const typename BASE::EdgeInfo* nod1, const typename BASE::EdgeInfo* nod2) const {
107  if (nod1->effort == nod2->effort) {
108  return nod1->edge->getNumericalID() > nod2->edge->getNumericalID();
109  }
110  return nod1->effort > nod2->effort;
111  }
112  };
113 
114 
115  void init(const E* const start, const V* const vehicle) {
116  assert(vehicle != 0);
117  // all EdgeInfos touched in the previous query are either in myFrontier or myFound: clean those up
118  for (auto ei : myFrontier) {
119  ei->reset();
120  }
121  myFrontier.clear();
122  for (auto edge : myFound) {
123  getEdgeInfo(edge)->reset();
124  }
125  myFound.clear();
126  myVehicle = vehicle;
127  auto startInfo = getEdgeInfo(start);
128  startInfo->effort = 0.;
129  startInfo->prev = nullptr;
130  myFrontier.push_back(startInfo);
131  }
132 
133 
134  typedef std::vector<typename CHBuilder<E, V>::Connection> ConnectionVector;
139  bool step(const std::vector<ConnectionVector>& uplinks, const Unidirectional& otherSearch, double& minTTSeen, Meeting& meeting) {
140  // pop the node with the minimal length
141  auto* const minimumInfo = myFrontier.front();
142  pop_heap(myFrontier.begin(), myFrontier.end(), myComparator);
143  myFrontier.pop_back();
144  // check for a meeting with the other search
145  const E* const minEdge = minimumInfo->edge;
146 #ifdef CHRouter_DEBUG_QUERY
147  std::cout << "DEBUG: " << (myAmForward ? "Forward" : "Backward") << " hit '" << minEdge->getID() << "' Q: ";
148  for (typename std::vector<EdgeInfo*>::iterator it = myFrontier.begin(); it != myFrontier.end(); it++) {
149  std::cout << (*it)->traveltime << "," << (*it)->edge->getID() << " ";
150  }
151  std::cout << "\n";
152 #endif
153  if (otherSearch.found(minEdge)) {
154  const auto* const otherInfo = otherSearch.getEdgeInfo(minEdge);
155  const double ttSeen = minimumInfo->effort + otherInfo->effort;
156 #ifdef CHRouter_DEBUG_QUERY
157  std::cout << "DEBUG: " << (myAmForward ? "Forward" : "Backward") << "-Search hit other search at '" << minEdge->getID() << "', tt: " << ttSeen << " \n";
158 #endif
159  if (ttSeen < minTTSeen) {
160  minTTSeen = ttSeen;
161  if (myAmForward) {
162  meeting.first = minimumInfo;
163  meeting.second = otherInfo;
164  } else {
165  meeting.first = otherInfo;
166  meeting.second = minimumInfo;
167  }
168  }
169  }
170  // prepare next steps
171  minimumInfo->visited = true;
172  // XXX we only need to keep found elements if they have a higher rank than the lowest rank in the other search queue
173  myFound.insert(minimumInfo->edge);
174  for (const auto& uplink : uplinks[minEdge->getNumericalID()]) {
175  const auto upwardInfo = &myEdgeInfos[uplink.target];
176  const double effort = minimumInfo->effort + uplink.cost;
177  const SUMOVehicleClass svc = myVehicle->getVClass();
178  // check whether it can be used
179  if ((uplink.permissions & svc) != svc) {
180  continue;
181  }
182  const double oldEffort = upwardInfo->effort;
183  if (!upwardInfo->visited && effort < oldEffort) {
184  upwardInfo->effort = effort;
185  upwardInfo->prev = minimumInfo;
186  if (oldEffort == std::numeric_limits<double>::max()) {
187  myFrontier.push_back(upwardInfo);
188  push_heap(myFrontier.begin(), myFrontier.end(), myComparator);
189  } else {
190  push_heap(myFrontier.begin(),
191  find(myFrontier.begin(), myFrontier.end(), upwardInfo) + 1,
192  myComparator);
193  }
194  }
195  }
196  // @note: this effectively does a full dijkstra search.
197  // the effort compared to the naive stopping criterion is thus
198  // quadrupled. We could implement a better stopping criterion (Holte)
199  // However since the search shall take place in a contracted graph
200  // it probably does not matter
201  return !myFrontier.empty() && myFrontier.front()->effort < minTTSeen;
202  }
203 
204  private:
208  std::vector<typename BASE::EdgeInfo*> myFrontier;
210  std::set<const E*> myFound;
212  std::vector<typename BASE::EdgeInfo> myEdgeInfos;
213 
215 
216  const V* myVehicle;
217 
218  };
219 
225  CHRouter(const std::vector<E*>& edges, bool unbuildIsWarning, typename BASE::Operation operation,
226  const SUMOVehicleClass svc,
227  SUMOTime weightPeriod,
228  bool validatePermissions):
229  BASE("CHRouter", operation),
230  myEdges(edges),
231  myErrorMsgHandler(unbuildIsWarning ? MsgHandler::getWarningInstance() : MsgHandler::getErrorInstance()),
232  myForwardSearch(edges, true),
233  myBackwardSearch(edges, false),
234  myHierarchyBuilder(new CHBuilder<E, V>(edges, unbuildIsWarning, svc, validatePermissions)),
235  myHierarchy(0),
236  myWeightPeriod(weightPeriod),
237  myValidUntil(0),
238  mySVC(svc) {
239  }
240 
243  CHRouter(const std::vector<E*>& edges, bool unbuildIsWarning, typename BASE::Operation operation,
244  const SUMOVehicleClass svc,
245  SUMOTime weightPeriod,
246  const typename CHBuilder<E, V>::Hierarchy* hierarchy) :
247  BASE("CHRouterClone", operation),
248  myEdges(edges),
249  myErrorMsgHandler(unbuildIsWarning ? MsgHandler::getWarningInstance() : MsgHandler::getErrorInstance()),
250  myForwardSearch(edges, true),
251  myBackwardSearch(edges, false),
253  myHierarchy(hierarchy),
254  myWeightPeriod(weightPeriod),
255  myValidUntil(0),
256  mySVC(svc) {
257  }
258 
260  virtual ~CHRouter() {
261  if (myHierarchyBuilder != 0) {
262  delete myHierarchy;
263  delete myHierarchyBuilder;
264  }
265  }
266 
267 
269  WRITE_MESSAGE("Cloning Contraction Hierarchy for " + SumoVehicleClassStrings.getString(mySVC) + " and time " + time2string(myValidUntil) + ".");
272  clone->myValidUntil = myValidUntil;
273  return clone;
274  }
275 
280  virtual bool compute(const E* from, const E* to, const V* const vehicle,
281  SUMOTime msTime, std::vector<const E*>& into) {
282  assert(from != 0 && to != 0);
283  // assert(myHierarchyBuilder.mySPTree->validatePermissions() || vehicle->getVClass() == mySVC || mySVC == SVC_IGNORING);
284  // do we need to rebuild the hierarchy?
285  if (msTime >= myValidUntil) {
286  while (msTime >= myValidUntil) {
288  }
290  }
291  // ready for routing
292  this->startQuery();
293  myForwardSearch.init(from, vehicle);
294  myBackwardSearch.init(to, vehicle);
295  double minTTSeen = std::numeric_limits<double>::max();
296  Meeting meeting(nullptr, nullptr);
297  bool continueForward = true;
298  bool continueBackward = true;
299  int num_visited_fw = 0;
300  int num_visited_bw = 0;
301  bool result = true;
302  while (continueForward || continueBackward) {
303  if (continueForward) {
304  continueForward = myForwardSearch.step(myHierarchy->forwardUplinks, myBackwardSearch, minTTSeen, meeting);
305  num_visited_fw += 1;
306  }
307  if (continueBackward) {
308  continueBackward = myBackwardSearch.step(myHierarchy->backwardUplinks, myForwardSearch, minTTSeen, meeting);
309  num_visited_bw += 1;
310  }
311  }
312  if (minTTSeen < std::numeric_limits<double>::max()) {
313  buildPathFromMeeting(meeting, into);
314  } else {
315  myErrorMsgHandler->inform("No connection between edge '" + from->getID() + "' and edge '" + to->getID() + "' found.");
316  result = false;
317  }
318 #ifdef CHRouter_DEBUG_QUERY_PERF
319  std::cout << "visited " << num_visited_fw + num_visited_bw << " edges (" << num_visited_fw << "," << num_visited_bw << ") ,final path length: " + toString(into.size()) + ")\n";
320 #endif
321  this->endQuery(num_visited_bw + num_visited_fw);
322  return result;
323  }
324 
326 
328  void buildPathFromMeeting(Meeting meeting, std::vector<const E*>& into) const {
329  std::deque<const E*> tmp;
330  const auto* backtrack = meeting.first;
331  while (backtrack != 0) {
332  tmp.push_front((E*) backtrack->edge); // !!!
333  backtrack = backtrack->prev;
334  }
335  backtrack = meeting.second->prev; // don't use central edge twice
336  while (backtrack != 0) {
337  tmp.push_back((E*) backtrack->edge); // !!!
338  backtrack = backtrack->prev;
339  }
340  // expand shortcuts
341  const E* prev = 0;
342  while (!tmp.empty()) {
343  const E* cur = tmp.front();
344  tmp.pop_front();
345  if (prev == 0) {
346  into.push_back(cur);
347  prev = cur;
348  } else {
349  const E* via = getVia(prev, cur);
350  if (via == 0) {
351  into.push_back(cur);
352  prev = cur;
353  } else {
354  tmp.push_front(cur);
355  tmp.push_front(via);
356  }
357  }
358  }
359  }
360 
361  void buildContractionHierarchy(SUMOTime time, const V* const vehicle) {
362  if (myHierarchyBuilder != 0) {
363  delete myHierarchy;
364  myHierarchy = myHierarchyBuilder->buildContractionHierarchy(time, vehicle, this);
365  }
366  // declare new validUntil (prevent overflow)
367  if (myWeightPeriod < std::numeric_limits<int>::max()) {
368  myValidUntil = time + myWeightPeriod;
369  } else {
371  }
372  }
373 
374 private:
375  // retrieve the via edge for a shortcut
376  const E* getVia(const E* forwardFrom, const E* forwardTo) const {
377  typename CHBuilder<E, V>::ConstEdgePair forward(forwardFrom, forwardTo);
378  typename CHBuilder<E, V>::ShortcutVia::const_iterator it = myHierarchy->shortcuts.find(forward);
379  if (it != myHierarchy->shortcuts.end()) {
380  return it->second;
381  } else {
382  return 0;
383  }
384  }
385 
386 
387 private:
389  const std::vector<E*>& myEdges;
390 
393 
397 
400 
403 
406 
409 };
410 
411 
412 #endif
413 
414 /****************************************************************************/
415 
Computes the shortest path through a contracted network.
Definition: CHRouter.h:63
const SUMOVehicleClass mySVC
the permissions for which the hierarchy was constructed
Definition: CHRouter.h:408
static MsgHandler * getWarningInstance()
Returns the instance to add warnings to.
Definition: MsgHandler.cpp:67
long long int SUMOTime
Definition: SUMOTime.h:36
SUMOTime myValidUntil
the validity duration of the current hierarchy (exclusive)
Definition: CHRouter.h:405
SUMOVehicleClass
Definition of vehicle classes to differ between different lane usage and authority types...
std::vector< typename CHBuilder< E, V >::Connection > ConnectionVector
Definition: CHRouter.h:134
void buildContractionHierarchy(SUMOTime time, const V *const vehicle)
Definition: CHRouter.h:361
std::string time2string(SUMOTime t)
Definition: SUMOTime.cpp:65
void init(const E *const start, const V *const vehicle)
Definition: CHRouter.h:115
void buildPathFromMeeting(Meeting meeting, std::vector< const E *> &into) const
normal routing methods
Definition: CHRouter.h:328
bool operator()(const typename BASE::EdgeInfo *nod1, const typename BASE::EdgeInfo *nod2) const
Comparing method.
Definition: CHRouter.h:106
virtual ~CHRouter()
Destructor.
Definition: CHRouter.h:260
CHRouter(const std::vector< E *> &edges, bool unbuildIsWarning, typename BASE::Operation operation, const SUMOVehicleClass svc, SUMOTime weightPeriod, bool validatePermissions)
Constructor.
Definition: CHRouter.h:225
Unidirectional myBackwardSearch
Definition: CHRouter.h:396
std::vector< typename BASE::EdgeInfo * > myFrontier
the min edge heap
Definition: CHRouter.h:208
std::vector< typename BASE::EdgeInfo > myEdgeInfos
The container of edge information.
Definition: CHRouter.h:212
std::string toString(const T &t, std::streamsize accuracy=gPrecision)
Definition: ToString.h:49
const CHBuilder< E, V >::Hierarchy * myHierarchy
Definition: CHRouter.h:399
BASE::EdgeInfo * getEdgeInfo(const E *const edge)
Definition: CHRouter.h:91
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:280
const E * getVia(const E *forwardFrom, const E *forwardTo) const
Definition: CHRouter.h:376
const std::vector< E * > & myEdges
all edges with numerical ids
Definition: CHRouter.h:389
MsgHandler *const myErrorMsgHandler
the handler for routing errors
Definition: CHRouter.h:392
std::pair< const E *, const E * > ConstEdgePair
Definition: CHBuilder.h:79
StringBijection< SUMOVehicleClass > SumoVehicleClassStrings(sumoVehicleClassStringInitializer, SVC_CUSTOM2, false)
bool found(const E *const edge) const
Definition: CHRouter.h:87
std::set< const E * > myFound
the set of visited (settled) Edges
Definition: CHRouter.h:210
const SUMOTime myWeightPeriod
the validity duration of one weight interval
Definition: CHRouter.h:402
void inform(std::string msg, bool addType=true)
adds a new error to the list
Definition: MsgHandler.cpp:113
double(* Operation)(const E *const, const V *const, double)
Type of the function that is used to retrieve the edge effort.
Definition: CHRouter.h:67
const BASE::EdgeInfo * getEdgeInfo(const E *const edge) const
Definition: CHRouter.h:95
Unidirectional(const std::vector< E *> &edges, bool forward)
Constructor.
Definition: CHRouter.h:79
Unidirectional myForwardSearch
the unidirectional search queues
Definition: CHRouter.h:395
virtual SUMOAbstractRouter< E, V > * clone()
Definition: CHRouter.h:268
bool myAmForward
the role of this search
Definition: CHRouter.h:206
#define WRITE_MESSAGE(msg)
Definition: MsgHandler.h:242
EdgeInfoByTTComparator myComparator
Definition: CHRouter.h:214
std::pair< const typename BASE::EdgeInfo *, const typename BASE::EdgeInfo * > Meeting
A meeting point of the two search scopes.
Definition: CHRouter.h:70
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:139
CHBuilder< E, V > * myHierarchyBuilder
Definition: CHRouter.h:398
CHRouter(const std::vector< E *> &edges, bool unbuildIsWarning, typename BASE::Operation operation, const SUMOVehicleClass svc, SUMOTime weightPeriod, const typename CHBuilder< E, V >::Hierarchy *hierarchy)
Cloning constructor.
Definition: CHRouter.h:243