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 /****************************************************************************/
16 // Shortest Path search using a Contraction Hierarchy
17 /****************************************************************************/
18 #ifndef CHRouter_h
19 #define CHRouter_h
20 
21 
22 // ===========================================================================
23 // included modules
24 // ===========================================================================
25 #include <config.h>
26 
27 #include <string>
28 #include <functional>
29 #include <vector>
30 #include <set>
31 #include <limits>
32 #include <algorithm>
33 #include <iterator>
34 #include <deque>
35 #include <utils/common/SysUtils.h>
37 #include <utils/common/StdDefs.h>
39 #include "CHBuilder.h"
40 
41 //#define CHRouter_DEBUG_QUERY
42 //#define CHRouter_DEBUG_QUERY_PERF
43 
44 // ===========================================================================
45 // class definitions
46 // ===========================================================================
60 template<class E, class V>
61 class CHRouter: public SUMOAbstractRouter<E, V> {
62 
63 public:
65  typedef std::pair<const typename SUMOAbstractRouter<E, V>::EdgeInfo*, const typename SUMOAbstractRouter<E, V>::EdgeInfo*> Meeting;
66 
72  public:
74  Unidirectional(const std::vector<E*>& edges, bool forward):
75  myAmForward(forward),
76  myVehicle(0) {
77  for (const E* const e : edges) {
78  myEdgeInfos.push_back(typename SUMOAbstractRouter<E, V>::EdgeInfo(e));
79  }
80  }
81 
82  inline bool found(const E* const edge) const {
83  return myFound.count(edge) > 0;
84  }
85 
86  inline typename SUMOAbstractRouter<E, V>::EdgeInfo* getEdgeInfo(const E* const edge) {
87  return &(myEdgeInfos[edge->getNumericalID()]);
88  }
89 
90  inline const typename SUMOAbstractRouter<E, V>::EdgeInfo* getEdgeInfo(const E* const edge) const {
91  return &(myEdgeInfos[edge->getNumericalID()]);
92  }
93 
99  public:
101  bool operator()(const typename SUMOAbstractRouter<E, V>::EdgeInfo* nod1, const typename SUMOAbstractRouter<E, V>::EdgeInfo* nod2) const {
102  if (nod1->effort == nod2->effort) {
103  return nod1->edge->getNumericalID() > nod2->edge->getNumericalID();
104  }
105  return nod1->effort > nod2->effort;
106  }
107  };
108 
109 
110  void init(const E* const start, const V* const vehicle) {
111  assert(vehicle != 0);
112  // all EdgeInfos touched in the previous query are either in myFrontier or myFound: clean those up
113  for (auto ei : myFrontier) {
114  ei->reset();
115  }
116  myFrontier.clear();
117  for (auto edge : myFound) {
118  getEdgeInfo(edge)->reset();
119  }
120  myFound.clear();
121  myVehicle = vehicle;
122  auto startInfo = getEdgeInfo(start);
123  startInfo->effort = 0.;
124  startInfo->prev = nullptr;
125  myFrontier.push_back(startInfo);
126  }
127 
128 
129  typedef std::vector<typename CHBuilder<E, V>::Connection> ConnectionVector;
134  bool step(const std::vector<ConnectionVector>& uplinks, const Unidirectional& otherSearch, double& minTTSeen, Meeting& meeting) {
135  // pop the node with the minimal length
136  auto* const minimumInfo = myFrontier.front();
137  std::pop_heap(myFrontier.begin(), myFrontier.end(), myComparator);
138  myFrontier.pop_back();
139  // check for a meeting with the other search
140  const E* const minEdge = minimumInfo->edge;
141 #ifdef CHRouter_DEBUG_QUERY
142  std::cout << "DEBUG: " << (myAmForward ? "Forward" : "Backward") << " hit '" << minEdge->getID() << "' Q: ";
143  for (typename std::vector<EdgeInfo*>::iterator it = myFrontier.begin(); it != myFrontier.end(); it++) {
144  std::cout << (*it)->traveltime << "," << (*it)->edge->getID() << " ";
145  }
146  std::cout << "\n";
147 #endif
148  if (otherSearch.found(minEdge)) {
149  const auto* const otherInfo = otherSearch.getEdgeInfo(minEdge);
150  const double ttSeen = minimumInfo->effort + otherInfo->effort;
151 #ifdef CHRouter_DEBUG_QUERY
152  std::cout << "DEBUG: " << (myAmForward ? "Forward" : "Backward") << "-Search hit other search at '" << minEdge->getID() << "', tt: " << ttSeen << " \n";
153 #endif
154  if (ttSeen < minTTSeen) {
155  minTTSeen = ttSeen;
156  if (myAmForward) {
157  meeting.first = minimumInfo;
158  meeting.second = otherInfo;
159  } else {
160  meeting.first = otherInfo;
161  meeting.second = minimumInfo;
162  }
163  }
164  }
165  // prepare next steps
166  minimumInfo->visited = true;
167  // XXX we only need to keep found elements if they have a higher rank than the lowest rank in the other search queue
168  myFound.insert(minimumInfo->edge);
169  for (const auto& uplink : uplinks[minEdge->getNumericalID()]) {
170  const auto upwardInfo = &myEdgeInfos[uplink.target];
171  const double effort = minimumInfo->effort + uplink.cost;
172  const SUMOVehicleClass svc = myVehicle->getVClass();
173  // check whether it can be used
174  if ((uplink.permissions & svc) != svc) {
175  continue;
176  }
177  const double oldEffort = upwardInfo->effort;
178  if (!upwardInfo->visited && effort < oldEffort) {
179  upwardInfo->effort = effort;
180  upwardInfo->prev = minimumInfo;
181  if (oldEffort == std::numeric_limits<double>::max()) {
182  myFrontier.push_back(upwardInfo);
183  std::push_heap(myFrontier.begin(), myFrontier.end(), myComparator);
184  } else {
185  std::push_heap(myFrontier.begin(),
186  std::find(myFrontier.begin(), myFrontier.end(), upwardInfo) + 1,
187  myComparator);
188  }
189  }
190  }
191  // @note: this effectively does a full dijkstra search.
192  // the effort compared to the naive stopping criterion is thus
193  // quadrupled. We could implement a better stopping criterion (Holte)
194  // However since the search shall take place in a contracted graph
195  // it probably does not matter
196  return !myFrontier.empty() && myFrontier.front()->effort < minTTSeen;
197  }
198 
199  private:
203  std::vector<typename SUMOAbstractRouter<E, V>::EdgeInfo*> myFrontier;
205  std::set<const E*> myFound;
207  std::vector<typename SUMOAbstractRouter<E, V>::EdgeInfo> myEdgeInfos;
208 
210 
211  const V* myVehicle;
212 
213  };
214 
220  CHRouter(const std::vector<E*>& edges, bool unbuildIsWarning, typename SUMOAbstractRouter<E, V>::Operation operation,
221  const SUMOVehicleClass svc,
222  SUMOTime weightPeriod,
223  const bool havePermissions, const bool haveRestrictions):
224  SUMOAbstractRouter<E, V>("CHRouter", unbuildIsWarning, operation, nullptr, havePermissions, haveRestrictions),
225  myEdges(edges),
226  myForwardSearch(edges, true),
227  myBackwardSearch(edges, false),
228  myHierarchyBuilder(new CHBuilder<E, V>(edges, unbuildIsWarning, svc, havePermissions)),
229  myHierarchy(0),
230  myWeightPeriod(weightPeriod),
231  myValidUntil(0),
232  mySVC(svc) {
233  }
234 
236  virtual ~CHRouter() {
237  if (myHierarchyBuilder != 0) {
238  delete myHierarchy;
239  delete myHierarchyBuilder;
240  }
241  }
242 
243 
245  //WRITE_MESSAGE("Cloning Contraction Hierarchy for " + SumoVehicleClassStrings.getString(mySVC) + " and time " + time2string(myValidUntil) + ".");
248  return clone;
249  }
250 
255  virtual bool compute(const E* from, const E* to, const V* const vehicle,
256  SUMOTime msTime, std::vector<const E*>& into, bool silent = false) {
257  assert(from != 0 && to != 0);
258  // assert(myHierarchyBuilder.mySPTree->validatePermissions() || vehicle->getVClass() == mySVC || mySVC == SVC_IGNORING);
259  // do we need to rebuild the hierarchy?
260  if (msTime >= myValidUntil) {
261  while (msTime >= myValidUntil) {
263  }
265  }
266  // ready for routing
267  this->startQuery();
268  myForwardSearch.init(from, vehicle);
269  myBackwardSearch.init(to, vehicle);
270  double minTTSeen = std::numeric_limits<double>::max();
271  Meeting meeting(nullptr, nullptr);
272  bool continueForward = true;
273  bool continueBackward = true;
274  int num_visited_fw = 0;
275  int num_visited_bw = 0;
276  bool result = true;
277  while (continueForward || continueBackward) {
278  if (continueForward) {
279  continueForward = myForwardSearch.step(myHierarchy->forwardUplinks, myBackwardSearch, minTTSeen, meeting);
280  num_visited_fw += 1;
281  }
282  if (continueBackward) {
283  continueBackward = myBackwardSearch.step(myHierarchy->backwardUplinks, myForwardSearch, minTTSeen, meeting);
284  num_visited_bw += 1;
285  }
286  }
287  if (minTTSeen < std::numeric_limits<double>::max()) {
288  buildPathFromMeeting(meeting, into);
289  } else {
290  if (!silent) {
291  this->myErrorMsgHandler->informf("No connection between edge '%' and edge '%' found.", from->getID(), to->getID());
292  }
293  result = false;
294  }
295 #ifdef CHRouter_DEBUG_QUERY_PERF
296  std::cout << "visited " << num_visited_fw + num_visited_bw << " edges (" << num_visited_fw << "," << num_visited_bw << ") ,final path length: " + toString(into.size()) + ")\n";
297 #endif
298  this->endQuery(num_visited_bw + num_visited_fw);
299  return result;
300  }
301 
303 
305  void buildPathFromMeeting(Meeting meeting, std::vector<const E*>& into) const {
306  std::deque<const E*> tmp;
307  const auto* backtrack = meeting.first;
308  while (backtrack != 0) {
309  tmp.push_front((E*) backtrack->edge); // !!!
310  backtrack = backtrack->prev;
311  }
312  backtrack = meeting.second->prev; // don't use central edge twice
313  while (backtrack != 0) {
314  tmp.push_back((E*) backtrack->edge); // !!!
315  backtrack = backtrack->prev;
316  }
317  // expand shortcuts
318  const E* prev = 0;
319  while (!tmp.empty()) {
320  const E* cur = tmp.front();
321  tmp.pop_front();
322  if (prev == 0) {
323  into.push_back(cur);
324  prev = cur;
325  } else {
326  const E* via = getVia(prev, cur);
327  if (via == 0) {
328  into.push_back(cur);
329  prev = cur;
330  } else {
331  tmp.push_front(cur);
332  tmp.push_front(via);
333  }
334  }
335  }
336  }
337 
338  void buildContractionHierarchy(SUMOTime time, const V* const vehicle) {
339  if (myHierarchyBuilder != 0) {
340  delete myHierarchy;
341  myHierarchy = myHierarchyBuilder->buildContractionHierarchy(time, vehicle, this);
342  }
343  // declare new validUntil (prevent overflow)
344  if (myWeightPeriod < std::numeric_limits<int>::max()) {
345  myValidUntil = time + myWeightPeriod;
346  } else {
348  }
349  }
350 
351 private:
352  // retrieve the via edge for a shortcut
353  const E* getVia(const E* forwardFrom, const E* forwardTo) const {
354  typename CHBuilder<E, V>::ConstEdgePair forward(forwardFrom, forwardTo);
355  typename CHBuilder<E, V>::ShortcutVia::const_iterator it = myHierarchy->shortcuts.find(forward);
356  if (it != myHierarchy->shortcuts.end()) {
357  return it->second;
358  } else {
359  return 0;
360  }
361  }
362 
363 
364 private:
366  const std::vector<E*>& myEdges;
367 
371 
374 
377 
380 
383 };
384 
385 
386 #endif
387 
388 /****************************************************************************/
389 
CHBuilder::ConstEdgePair
std::pair< const E *, const E * > ConstEdgePair
Definition: CHBuilder.h:78
CHRouter::Unidirectional::myComparator
EdgeInfoByTTComparator myComparator
Definition: CHRouter.h:209
CHRouter::Unidirectional::myFrontier
std::vector< typename SUMOAbstractRouter< E, V >::EdgeInfo * > myFrontier
the min edge heap
Definition: CHRouter.h:203
SUMOVehicleClass
SUMOVehicleClass
Definition of vehicle classes to differ between different lane usage and authority types.
Definition: SUMOVehicleClass.h:133
CHRouter::myWeightPeriod
const SUMOTime myWeightPeriod
the validity duration of one weight interval
Definition: CHRouter.h:376
CHRouter::Meeting
std::pair< const typename SUMOAbstractRouter< E, V >::EdgeInfo *, const typename SUMOAbstractRouter< E, V >::EdgeInfo * > Meeting
A meeting point of the two search scopes.
Definition: CHRouter.h:65
CHBuilder
Definition: CHBuilder.h:64
SUMOAbstractRouter::myHavePermissions
const bool myHavePermissions
whether edge permissions need to be considered
Definition: SUMOAbstractRouter.h:248
CHRouter::Unidirectional::myVehicle
const V * myVehicle
Definition: CHRouter.h:211
CHBuilder.h
MsgHandler.h
CHRouter::myHierarchy
const CHBuilder< E, V >::Hierarchy * myHierarchy
Definition: CHRouter.h:373
SUMOTime
long long int SUMOTime
Definition: SUMOTime.h:34
CHRouter::CHRouter
CHRouter(const std::vector< E * > &edges, bool unbuildIsWarning, typename SUMOAbstractRouter< E, V >::Operation operation, const SUMOVehicleClass svc, SUMOTime weightPeriod, const bool havePermissions, const bool haveRestrictions)
Constructor.
Definition: CHRouter.h:220
CHRouter::~CHRouter
virtual ~CHRouter()
Destructor.
Definition: CHRouter.h:236
CHRouter::mySVC
const SUMOVehicleClass mySVC
the permissions for which the hierarchy was constructed
Definition: CHRouter.h:382
CHBuilder::Hierarchy
Definition: CHBuilder.h:80
SUMOAbstractRouter::startQuery
void startQuery()
Definition: SUMOAbstractRouter.h:220
CHRouter::myValidUntil
SUMOTime myValidUntil
the validity duration of the current hierarchy (exclusive)
Definition: CHRouter.h:379
SUMOAbstractRouter::EdgeInfo::effort
double effort
Effort to reach the edge.
Definition: SUMOAbstractRouter.h:65
SUMOAbstractRouter::myOperation
Operation myOperation
The object's operation to perform.
Definition: SUMOAbstractRouter.h:239
CHRouter::clone
virtual SUMOAbstractRouter< E, V > * clone()
Definition: CHRouter.h:244
CHRouter::Unidirectional::Unidirectional
Unidirectional(const std::vector< E * > &edges, bool forward)
Constructor.
Definition: CHRouter.h:74
CHRouter::Unidirectional::myAmForward
bool myAmForward
the role of this search
Definition: CHRouter.h:201
MsgHandler::getWarningInstance
static MsgHandler * getWarningInstance()
Returns the instance to add warnings to.
Definition: MsgHandler.cpp:68
SysUtils.h
SUMOAbstractRouter::myHaveRestrictions
const bool myHaveRestrictions
whether edge restrictions need to be considered
Definition: SUMOAbstractRouter.h:251
SUMOAbstractRouter::EdgeInfo
Definition: SUMOAbstractRouter.h:53
CHRouter::myHierarchyBuilder
CHBuilder< E, V > * myHierarchyBuilder
Definition: CHRouter.h:372
CHRouter::Unidirectional::myFound
std::set< const E * > myFound
the set of visited (settled) Edges
Definition: CHRouter.h:205
CHRouter::Unidirectional::ConnectionVector
std::vector< typename CHBuilder< E, V >::Connection > ConnectionVector
Definition: CHRouter.h:129
SUMOAbstractRouter::EdgeInfo::edge
const E *const edge
The current edge.
Definition: SUMOAbstractRouter.h:62
CHRouter::Unidirectional::EdgeInfoByTTComparator
Definition: CHRouter.h:98
SUMOAbstractRouter
Definition: SUMOAbstractRouter.h:46
CHRouter::buildPathFromMeeting
void buildPathFromMeeting(Meeting meeting, std::vector< const E * > &into) const
normal routing methods
Definition: CHRouter.h:305
SUMOAbstractRouter::endQuery
void endQuery(int visits)
Definition: SUMOAbstractRouter.h:225
toString
std::string toString(const T &t, std::streamsize accuracy=gPrecision)
Definition: ToString.h:47
SUMOAbstractRouter::myErrorMsgHandler
MsgHandler *const myErrorMsgHandler
the handler for routing errors
Definition: SUMOAbstractRouter.h:236
CHRouter
Computes the shortest path through a contracted network.
Definition: CHRouter.h:61
CHRouter::myEdges
const std::vector< E * > & myEdges
all edges with numerical ids
Definition: CHRouter.h:366
CHRouter::Unidirectional::myEdgeInfos
std::vector< typename SUMOAbstractRouter< E, V >::EdgeInfo > myEdgeInfos
The container of edge information.
Definition: CHRouter.h:207
CHRouter::Unidirectional::getEdgeInfo
const SUMOAbstractRouter< E, V >::EdgeInfo * getEdgeInfo(const E *const edge) const
Definition: CHRouter.h:90
CHRouter::getVia
const E * getVia(const E *forwardFrom, const E *forwardTo) const
Definition: CHRouter.h:353
CHRouter::Unidirectional::getEdgeInfo
SUMOAbstractRouter< E, V >::EdgeInfo * getEdgeInfo(const E *const edge)
Definition: CHRouter.h:86
CHRouter::Unidirectional::init
void init(const E *const start, const V *const vehicle)
Definition: CHRouter.h:110
MsgHandler::informf
void informf(const std::string &format, T value, Targs... Fargs)
adds a new formatted message
Definition: MsgHandler.h:115
config.h
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:255
StdDefs.h
CHRouter::Unidirectional::EdgeInfoByTTComparator::operator()
bool operator()(const typename SUMOAbstractRouter< E, V >::EdgeInfo *nod1, const typename SUMOAbstractRouter< E, V >::EdgeInfo *nod2) const
Comparing method.
Definition: CHRouter.h:101
CHRouter::Unidirectional::found
bool found(const E *const edge) const
Definition: CHRouter.h:82
SUMOAbstractRouter.h
CHRouter::buildContractionHierarchy
void buildContractionHierarchy(SUMOTime time, const V *const vehicle)
Definition: CHRouter.h:338
CHRouter::myBackwardSearch
Unidirectional myBackwardSearch
Definition: CHRouter.h:370
CHRouter::myForwardSearch
Unidirectional myForwardSearch
the unidirectional search queues
Definition: CHRouter.h:369
CHRouter::Unidirectional
Definition: CHRouter.h:71
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:134