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