Eclipse SUMO - Simulation of Urban MObility
Loading...
Searching...
No Matches
CHRouter.h
Go to the documentation of this file.
1/****************************************************************************/
2// Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.dev/sumo
3// Copyright (C) 2001-2024 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>
37#include "CHBuilder.h"
38
39//#define CHRouter_DEBUG_QUERY
40//#define CHRouter_DEBUG_QUERY_PERF
41
42// ===========================================================================
43// class definitions
44// ===========================================================================
58template<class E, class V>
59class CHRouter: public SUMOAbstractRouter<E, V> {
60
61public:
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) {
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,
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 && myHierarchy != nullptr) {
261 // we only need one hierarchy
264 }
267 }
268
269
270 virtual void prohibit(const std::vector<E*>& toProhibit) {
271 if (toProhibit.size() > 0) {
272 WRITE_WARNINGF(TL("Routing algorithm CH does not support dynamic closing of edges%"), "");
273 }
274 }
275
276
278 virtual void reset(const V* const vehicle) {
279 if (myValidUntil == 0) {
281 }
282 typename CHBuilder<E, V>::Hierarchy* newHierarchy = myHierarchyBuilder->buildContractionHierarchy(myValidUntil - myWeightPeriod, vehicle, this);
283 if (myHierarchy == nullptr) {
284 myHierarchy = newHierarchy;
285 } else {
286 *myHierarchy = *newHierarchy;
287 delete newHierarchy;
288 }
289 }
290
295 virtual bool compute(const E* from, const E* to, const V* const vehicle,
296 SUMOTime msTime, std::vector<const E*>& into, bool silent = false) {
297 assert(from != nullptr && to != nullptr);
298 // assert(myHierarchyBuilder.mySPTree->validatePermissions() || vehicle->getVClass() == mySVC || mySVC == SVC_IGNORING);
299 // do we need to rebuild the hierarchy?
300 if (msTime >= myValidUntil) {
301 assert(myHierarchyBuilder != nullptr); // only time independent clones do not have a builder
302 while (msTime >= myValidUntil) {
304 }
305 this->reset(vehicle);
306 }
307 // ready for routing
308 this->startQuery();
309 myForwardSearch.init(from, vehicle);
310 myBackwardSearch.init(to, vehicle);
311 double minTTSeen = std::numeric_limits<double>::max();
312 Meeting meeting(nullptr, nullptr);
313 bool continueForward = true;
314 bool continueBackward = true;
315 int num_visited_fw = 0;
316 int num_visited_bw = 0;
317 bool result = true;
318 while (continueForward || continueBackward) {
319 if (continueForward) {
320 continueForward = myForwardSearch.step(myHierarchy->forwardUplinks, myBackwardSearch, minTTSeen, meeting);
321 num_visited_fw += 1;
322 }
323 if (continueBackward) {
324 continueBackward = myBackwardSearch.step(myHierarchy->backwardUplinks, myForwardSearch, minTTSeen, meeting);
325 num_visited_bw += 1;
326 }
327 }
328 if (minTTSeen < std::numeric_limits<double>::max()) {
329 buildPathFromMeeting(meeting, into);
330 } else {
331 if (!silent) {
332 this->myErrorMsgHandler->informf(TL("No connection between edge '%' and edge '%' found."), from->getID(), to->getID());
333 }
334 result = false;
335 }
336#ifdef CHRouter_DEBUG_QUERY_PERF
337 std::cout << "visited " << num_visited_fw + num_visited_bw << " edges (" << num_visited_fw << "," << num_visited_bw << ") ,final path length: " + toString(into.size()) + ")\n";
338#endif
339 this->endQuery(num_visited_bw + num_visited_fw);
340 return result;
341 }
342
344
346 void buildPathFromMeeting(Meeting meeting, std::vector<const E*>& into) const {
347 std::deque<const E*> tmp;
348 const auto* backtrack = meeting.first;
349 while (backtrack != 0) {
350 tmp.push_front((E*) backtrack->edge); // !!!
351 backtrack = backtrack->prev;
352 }
353 backtrack = meeting.second->prev; // don't use central edge twice
354 while (backtrack != 0) {
355 tmp.push_back((E*) backtrack->edge); // !!!
356 backtrack = backtrack->prev;
357 }
358 // expand shortcuts
359 const E* prev = 0;
360 while (!tmp.empty()) {
361 const E* cur = tmp.front();
362 tmp.pop_front();
363 if (prev == 0) {
364 into.push_back(cur);
365 prev = cur;
366 } else {
367 const E* via = getVia(prev, cur);
368 if (via == 0) {
369 into.push_back(cur);
370 prev = cur;
371 } else {
372 tmp.push_front(cur);
373 tmp.push_front(via);
374 }
375 }
376 }
377 }
378
379private:
380 // retrieve the via edge for a shortcut
381 const E* getVia(const E* forwardFrom, const E* forwardTo) const {
382 typename CHBuilder<E, V>::ConstEdgePair forward(forwardFrom, forwardTo);
383 typename CHBuilder<E, V>::ShortcutVia::const_iterator it = myHierarchy->shortcuts.find(forward);
384 if (it != myHierarchy->shortcuts.end()) {
385 return it->second;
386 } else {
387 return 0;
388 }
389 }
390
391
392private:
394 const std::vector<E*>& myEdges;
395
399
402
405
408
411};
long long int SUMOTime
Definition GUI.h:36
#define WRITE_WARNINGF(...)
Definition MsgHandler.h:296
#define TL(string)
Definition MsgHandler.h:315
#define SUMOTime_MAX
Definition SUMOTime.h:34
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:46
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
SUMOAbstractRouter< E, V >::EdgeInfo * getEdgeInfo(const E *const edge)
Definition CHRouter.h:84
EdgeInfoByTTComparator myComparator
Definition CHRouter.h:207
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
const SUMOAbstractRouter< E, V >::EdgeInfo * getEdgeInfo(const E *const edge) const
Definition CHRouter.h:88
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 SUMOAbstractRouter< E, V > * clone()
Definition CHRouter.h:259
virtual ~CHRouter()
Destructor.
Definition CHRouter.h:251
const SUMOTime myWeightPeriod
the validity duration of one weight interval
Definition CHRouter.h:404
const E * getVia(const E *forwardFrom, const E *forwardTo) const
Definition CHRouter.h:381
SUMOTime myValidUntil
the validity duration of the current hierarchy (exclusive)
Definition CHRouter.h:407
Unidirectional myBackwardSearch
Definition CHRouter.h:398
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
CHBuilder< E, V >::Hierarchy * myHierarchy
Definition CHRouter.h:401
Unidirectional myForwardSearch
the unidirectional search queues
Definition CHRouter.h:397
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:295
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:346
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:400
virtual void reset(const V *const vehicle)
trigger hierarchy rebuild
Definition CHRouter.h:278
const std::vector< E * > & myEdges
all edges with numerical ids
Definition CHRouter.h:394
virtual void prohibit(const std::vector< E * > &toProhibit)
Definition CHRouter.h:270
const SUMOVehicleClass mySVC
the permissions for which the hierarchy was constructed
Definition CHRouter.h:410
static MsgHandler * getWarningInstance()
Returns the instance to add warnings to.
void informf(const std::string &format, T value, Targs... Fargs)
adds a new formatted message
Definition MsgHandler.h:122
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)