Eclipse 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-2019 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  std::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  std::push_heap(myFrontier.begin(), myFrontier.end(), myComparator);
189  } else {
190  std::push_heap(myFrontier.begin(),
191  std::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", unbuildIsWarning, operation),
230  myEdges(edges),
231  myForwardSearch(edges, true),
232  myBackwardSearch(edges, false),
233  myHierarchyBuilder(new CHBuilder<E, V>(edges, unbuildIsWarning, svc, validatePermissions)),
234  myHierarchy(0),
235  myWeightPeriod(weightPeriod),
236  myValidUntil(0),
237  mySVC(svc) {
238  }
239 
242  CHRouter(const std::vector<E*>& edges, bool unbuildIsWarning, typename BASE::Operation operation,
243  const SUMOVehicleClass svc,
244  SUMOTime weightPeriod,
245  const typename CHBuilder<E, V>::Hierarchy* hierarchy) :
246  BASE("CHRouterClone", unbuildIsWarning, operation),
247  myEdges(edges),
248  myForwardSearch(edges, true),
249  myBackwardSearch(edges, false),
251  myHierarchy(hierarchy),
252  myWeightPeriod(weightPeriod),
253  myValidUntil(0),
254  mySVC(svc) {
255  }
256 
258  virtual ~CHRouter() {
259  if (myHierarchyBuilder != 0) {
260  delete myHierarchy;
261  delete myHierarchyBuilder;
262  }
263  }
264 
265 
267  WRITE_MESSAGE("Cloning Contraction Hierarchy for " + SumoVehicleClassStrings.getString(mySVC) + " and time " + time2string(myValidUntil) + ".");
268  CHRouter<E, V, BASE>* clone = new CHRouter<E, V, BASE>(myEdges, this->myErrorMsgHandler == MsgHandler::getWarningInstance(), this->myOperation,
270  clone->myValidUntil = myValidUntil;
271  return clone;
272  }
273 
278  virtual bool compute(const E* from, const E* to, const V* const vehicle,
279  SUMOTime msTime, std::vector<const E*>& into, bool silent = false) {
280  assert(from != 0 && to != 0);
281  // assert(myHierarchyBuilder.mySPTree->validatePermissions() || vehicle->getVClass() == mySVC || mySVC == SVC_IGNORING);
282  // do we need to rebuild the hierarchy?
283  if (msTime >= myValidUntil) {
284  while (msTime >= myValidUntil) {
286  }
288  }
289  // ready for routing
290  this->startQuery();
291  myForwardSearch.init(from, vehicle);
292  myBackwardSearch.init(to, vehicle);
293  double minTTSeen = std::numeric_limits<double>::max();
294  Meeting meeting(nullptr, nullptr);
295  bool continueForward = true;
296  bool continueBackward = true;
297  int num_visited_fw = 0;
298  int num_visited_bw = 0;
299  bool result = true;
300  while (continueForward || continueBackward) {
301  if (continueForward) {
302  continueForward = myForwardSearch.step(myHierarchy->forwardUplinks, myBackwardSearch, minTTSeen, meeting);
303  num_visited_fw += 1;
304  }
305  if (continueBackward) {
306  continueBackward = myBackwardSearch.step(myHierarchy->backwardUplinks, myForwardSearch, minTTSeen, meeting);
307  num_visited_bw += 1;
308  }
309  }
310  if (minTTSeen < std::numeric_limits<double>::max()) {
311  buildPathFromMeeting(meeting, into);
312  } else {
313  if (!silent) {
314  this->myErrorMsgHandler->inform("No connection between edge '" + from->getID() + "' and edge '" + to->getID() + "' found.");
315  }
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 
394 
397 
400 
403 
406 };
407 
408 
409 #endif
410 
411 /****************************************************************************/
412 
CHRouter::Unidirectional::myEdgeInfos
std::vector< typename BASE::EdgeInfo > myEdgeInfos
The container of edge information.
Definition: CHRouter.h:212
CHBuilder::ConstEdgePair
std::pair< const E *, const E * > ConstEdgePair
Definition: CHBuilder.h:79
CHRouter::CHRouter
CHRouter(const std::vector< E * > &edges, bool unbuildIsWarning, typename BASE::Operation operation, const SUMOVehicleClass svc, SUMOTime weightPeriod, bool validatePermissions)
Constructor.
Definition: CHRouter.h:225
SUMOVehicleClass
SUMOVehicleClass
Definition of vehicle classes to differ between different lane usage and authority types.
Definition: SUMOVehicleClass.h:134
CHBuilder
Definition: CHBuilder.h:65
CHRouter::Unidirectional::myFrontier
std::vector< typename BASE::EdgeInfo * > myFrontier
the min edge heap
Definition: CHRouter.h:208
CHRouter::myForwardSearch
Unidirectional myForwardSearch
the unidirectional search queues
Definition: CHRouter.h:392
CHBuilder.h
MsgHandler.h
CHRouter::Unidirectional::Unidirectional
Unidirectional(const std::vector< E * > &edges, bool forward)
Constructor.
Definition: CHRouter.h:79
CHRouter::Unidirectional::getEdgeInfo
BASE::EdgeInfo * getEdgeInfo(const E *const edge)
Definition: CHRouter.h:91
CHRouter::CHRouter
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:242
SUMOTime
long long int SUMOTime
Definition: SUMOTime.h:35
CHBuilder::Hierarchy
Definition: CHBuilder.h:81
CHRouter::myEdges
const std::vector< E * > & myEdges
all edges with numerical ids
Definition: CHRouter.h:389
CHRouter::compute
virtual bool compute(const E *from, const E *to, const V *const vehicle, SUMOTime msTime, std::vector< const E * > &into, bool silent=false)
Builds the route between the given edges using the minimum traveltime in the contracted graph.
Definition: CHRouter.h:278
CHRouter::myHierarchy
const CHBuilder< E, V >::Hierarchy * myHierarchy
Definition: CHRouter.h:396
CHRouter::Unidirectional::found
bool found(const E *const edge) const
Definition: CHRouter.h:87
CHRouter::Unidirectional::step
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
SumoVehicleClassStrings
StringBijection< SUMOVehicleClass > SumoVehicleClassStrings(sumoVehicleClassStringInitializer, SVC_CUSTOM2, false)
CHRouter::myValidUntil
SUMOTime myValidUntil
the validity duration of the current hierarchy (exclusive)
Definition: CHRouter.h:402
CHRouter::buildContractionHierarchy
void buildContractionHierarchy(SUMOTime time, const V *const vehicle)
Definition: CHRouter.h:361
CHRouter::Unidirectional::myVehicle
const V * myVehicle
Definition: CHRouter.h:216
CHRouter::Unidirectional::myAmForward
bool myAmForward
the role of this search
Definition: CHRouter.h:206
MsgHandler::getWarningInstance
static MsgHandler * getWarningInstance()
Returns the instance to add warnings to.
Definition: MsgHandler.cpp:72
SysUtils.h
CHRouter::myBackwardSearch
Unidirectional myBackwardSearch
Definition: CHRouter.h:393
CHRouter::Unidirectional::init
void init(const E *const start, const V *const vehicle)
Definition: CHRouter.h:115
time2string
std::string time2string(SUMOTime t)
Definition: SUMOTime.cpp:65
CHRouter::Unidirectional::EdgeInfoByTTComparator::operator()
bool operator()(const typename BASE::EdgeInfo *nod1, const typename BASE::EdgeInfo *nod2) const
Comparing method.
Definition: CHRouter.h:106
CHRouter::Unidirectional::EdgeInfoByTTComparator
Definition: CHRouter.h:103
SUMOAbstractRouter
Definition: SUMOAbstractRouter.h:47
CHRouter::Meeting
std::pair< const typename BASE::EdgeInfo *, const typename BASE::EdgeInfo * > Meeting
A meeting point of the two search scopes.
Definition: CHRouter.h:70
toString
std::string toString(const T &t, std::streamsize accuracy=gPrecision)
Definition: ToString.h:48
CHRouter
Computes the shortest path through a contracted network.
Definition: CHRouter.h:63
CHRouter::myHierarchyBuilder
CHBuilder< E, V > * myHierarchyBuilder
Definition: CHRouter.h:395
CHRouter::clone
virtual SUMOAbstractRouter< E, V > * clone()
Definition: CHRouter.h:266
CHRouter::getVia
const E * getVia(const E *forwardFrom, const E *forwardTo) const
Definition: CHRouter.h:376
CHRouter::mySVC
const SUMOVehicleClass mySVC
the permissions for which the hierarchy was constructed
Definition: CHRouter.h:405
CHRouter::Unidirectional::myFound
std::set< const E * > myFound
the set of visited (settled) Edges
Definition: CHRouter.h:210
CHRouter::Unidirectional::myComparator
EdgeInfoByTTComparator myComparator
Definition: CHRouter.h:214
config.h
StdDefs.h
CHRouter::buildPathFromMeeting
void buildPathFromMeeting(Meeting meeting, std::vector< const E * > &into) const
normal routing methods
Definition: CHRouter.h:328
CHRouter::myWeightPeriod
const SUMOTime myWeightPeriod
the validity duration of one weight interval
Definition: CHRouter.h:399
CHRouter::Unidirectional::getEdgeInfo
const BASE::EdgeInfo * getEdgeInfo(const E *const edge) const
Definition: CHRouter.h:95
SUMOAbstractRouter.h
CHRouter::Operation
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
CHRouter::Unidirectional::ConnectionVector
std::vector< typename CHBuilder< E, V >::Connection > ConnectionVector
Definition: CHRouter.h:134
WRITE_MESSAGE
#define WRITE_MESSAGE(msg)
Definition: MsgHandler.h:240
CHRouter::~CHRouter
virtual ~CHRouter()
Destructor.
Definition: CHRouter.h:258
CHRouter::Unidirectional
Definition: CHRouter.h:76