Line data Source code
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 : /****************************************************************************/
14 : /// @file CHRouter.h
15 : /// @author Jakob Erdmann
16 : /// @author Laura Bieker
17 : /// @author Michael Behrisch
18 : /// @date February 2012
19 : ///
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>
34 : #include <utils/common/MsgHandler.h>
35 : #include <utils/common/StdDefs.h>
36 : #include <utils/router/SUMOAbstractRouter.h>
37 : #include "CHBuilder.h"
38 :
39 : //#define CHRouter_DEBUG_QUERY
40 : //#define CHRouter_DEBUG_QUERY_PERF
41 :
42 : // ===========================================================================
43 : // class definitions
44 : // ===========================================================================
45 : /**
46 : * @class CHRouter
47 : * @brief Computes the shortest path through a contracted network
48 : *
49 : * The template parameters are:
50 : * @param E The edge class to use (MSEdge/ROEdge)
51 : * @param V The vehicle class to use (MSVehicle/ROVehicle)
52 : *
53 : * The router is edge-based. It must know the number of edges for internal reasons
54 : * and whether a missing connection between two given edges (unbuild route) shall
55 : * be reported as an error or as a warning.
56 : *
57 : */
58 : template<class E, class V>
59 : class CHRouter: public SUMOAbstractRouter<E, V> {
60 :
61 : public:
62 : /// A meeting point of the two search scopes
63 : typedef std::pair<const typename SUMOAbstractRouter<E, V>::EdgeInfo*, const typename SUMOAbstractRouter<E, V>::EdgeInfo*> Meeting;
64 :
65 : /**
66 : * @class Unidirectional
67 : * class for searching in one direction
68 : */
69 : class Unidirectional {
70 : public:
71 : /// @brief Constructor
72 1150 : Unidirectional(const std::vector<E*>& edges, bool forward):
73 1150 : myAmForward(forward),
74 1150 : myVehicle(0) {
75 68994 : for (const E* const e : edges) {
76 67844 : myEdgeInfos.push_back(typename SUMOAbstractRouter<E, V>::EdgeInfo(e));
77 : }
78 1150 : }
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 942714 : return &(myEdgeInfos[edge->getNumericalID()]);
86 : }
87 :
88 : inline const typename SUMOAbstractRouter<E, V>::EdgeInfo* getEdgeInfo(const E* const edge) const {
89 159500 : return &(myEdgeInfos[edge->getNumericalID()]);
90 : }
91 :
92 : /**
93 : * @class EdgeInfoByEffortComparator
94 : * Class to compare (and so sort) nodes by their effort
95 : */
96 : class EdgeInfoByTTComparator {
97 : public:
98 : /// Comparing method
99 : bool operator()(const typename SUMOAbstractRouter<E, V>::EdgeInfo* nod1, const typename SUMOAbstractRouter<E, V>::EdgeInfo* nod2) const {
100 6747591 : if (nod1->effort == nod2->effort) {
101 634704 : return nod1->edge->getNumericalID() > nod2->edge->getNumericalID();
102 : }
103 6112887 : return nod1->effort > nod2->effort;
104 : }
105 : };
106 :
107 :
108 36406 : 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 576589 : for (auto ei : myFrontier) {
112 : ei->reset();
113 : }
114 : myFrontier.clear();
115 942714 : for (auto edge : myFound) {
116 : getEdgeInfo(edge)->reset();
117 : }
118 : myFound.clear();
119 36406 : myVehicle = vehicle;
120 36406 : auto startInfo = getEdgeInfo(start);
121 36406 : startInfo->effort = 0.;
122 36406 : startInfo->prev = nullptr;
123 36406 : myFrontier.push_back(startInfo);
124 36406 : }
125 :
126 :
127 : typedef std::vector<typename CHBuilder<E, V>::Connection> ConnectionVector;
128 : /** @brief explore on element from the frontier,update minTTSeen and meeting
129 : * if an EdgeInfo found by the otherSearch is encountered
130 : * returns whether stepping should continue
131 : */
132 910903 : bool step(const std::vector<ConnectionVector>& uplinks, const Unidirectional& otherSearch, double& minTTSeen, Meeting& meeting) {
133 : // pop the node with the minimal length
134 910903 : auto* const minimumInfo = myFrontier.front();
135 910903 : std::pop_heap(myFrontier.begin(), myFrontier.end(), myComparator);
136 : myFrontier.pop_back();
137 : // check for a meeting with the other search
138 910903 : 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 159500 : 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 159500 : if (ttSeen < minTTSeen) {
153 25471 : minTTSeen = ttSeen;
154 25471 : if (myAmForward) {
155 14081 : meeting.first = minimumInfo;
156 14081 : meeting.second = otherInfo;
157 : } else {
158 11390 : meeting.first = otherInfo;
159 11390 : meeting.second = minimumInfo;
160 : }
161 : }
162 : }
163 : // prepare next steps
164 910903 : 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 910903 : myFound.insert(minimumInfo->edge);
167 9422776 : for (const auto& uplink : uplinks[minEdge->getNumericalID()]) {
168 8511873 : const auto upwardInfo = &myEdgeInfos[uplink.target];
169 8511873 : const double effort = minimumInfo->effort + uplink.cost;
170 8511873 : const SUMOVehicleClass svc = myVehicle->getVClass();
171 : // check whether it can be used
172 8511873 : if ((uplink.permissions & svc) != svc) {
173 10 : continue;
174 : }
175 8511863 : const double oldEffort = upwardInfo->effort;
176 8511863 : if (!upwardInfo->visited && effort < oldEffort) {
177 1911222 : upwardInfo->effort = effort;
178 1911222 : upwardInfo->prev = minimumInfo;
179 1911222 : if (oldEffort == std::numeric_limits<double>::max()) {
180 1415379 : myFrontier.push_back(upwardInfo);
181 : std::push_heap(myFrontier.begin(), myFrontier.end(), myComparator);
182 : } else {
183 : std::push_heap(myFrontier.begin(),
184 495843 : 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 910903 : return !myFrontier.empty() && myFrontier.front()->effort < minTTSeen;
195 : }
196 :
197 : private:
198 : /// @brief the role of this search
199 : bool myAmForward;
200 : /// @brief the min edge heap
201 : std::vector<typename SUMOAbstractRouter<E, V>::EdgeInfo*> myFrontier;
202 : /// @brief the set of visited (settled) Edges
203 : std::set<const E*> myFound;
204 : /// @brief The container of edge information
205 : std::vector<typename SUMOAbstractRouter<E, V>::EdgeInfo> myEdgeInfos;
206 :
207 : EdgeInfoByTTComparator myComparator;
208 :
209 : const V* myVehicle;
210 :
211 : };
212 :
213 : /** @brief Constructor
214 : * @param[in] validatePermissions Whether a multi-permission hierarchy shall be built
215 : * If set to false, the net is pruned in synchronize() and the
216 : * hierarchy is tailored to the svc
217 : */
218 566 : 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 566 : myEdges(edges),
224 566 : myForwardSearch(edges, true),
225 566 : myBackwardSearch(edges, false),
226 566 : myHierarchyBuilder(new CHBuilder<E, V>(edges, unbuildIsWarning, svc, havePermissions)),
227 566 : myHierarchy(nullptr),
228 566 : myWeightPeriod(weightPeriod),
229 566 : myValidUntil(0),
230 1132 : mySVC(svc) {
231 566 : }
232 :
233 : /** @brief Cloning constructor, should be used only for time independent instances which build a hierarchy only once
234 : */
235 9 : 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 9 : myEdges(edges),
241 9 : myForwardSearch(edges, true),
242 9 : myBackwardSearch(edges, false),
243 9 : myHierarchyBuilder(nullptr),
244 9 : myHierarchy(hierarchy),
245 9 : myWeightPeriod(SUMOTime_MAX),
246 9 : myValidUntil(SUMOTime_MAX),
247 18 : mySVC(svc) {
248 9 : }
249 :
250 : /// Destructor
251 1150 : virtual ~CHRouter() {
252 575 : if (myHierarchyBuilder != nullptr) {
253 566 : delete myHierarchy;
254 566 : delete myHierarchyBuilder;
255 : }
256 1716 : }
257 :
258 :
259 12 : virtual SUMOAbstractRouter<E, V>* clone() {
260 12 : if (myWeightPeriod == SUMOTime_MAX && myHierarchy != nullptr) {
261 : // we only need one hierarchy
262 18 : return new CHRouter<E, V>(myEdges, this->myErrorMsgHandler == MsgHandler::getWarningInstance(), this->myOperation,
263 9 : mySVC, myHierarchy, this->myHavePermissions, this->myHaveRestrictions);
264 : }
265 6 : return new CHRouter<E, V>(myEdges, this->myErrorMsgHandler == MsgHandler::getWarningInstance(), this->myOperation,
266 3 : mySVC, myWeightPeriod, this->myHavePermissions, this->myHaveRestrictions);
267 : }
268 :
269 :
270 4 : virtual void prohibit(const std::vector<E*>& toProhibit) {
271 4 : if (toProhibit.size() > 0) {
272 8 : WRITE_WARNINGF(TL("Routing algorithm CH does not support dynamic closing of edges%"), "");
273 : }
274 4 : }
275 :
276 :
277 : /// trigger hierarchy rebuild
278 580 : virtual void reset(const V* const vehicle) {
279 580 : if (myValidUntil == 0) {
280 3 : myValidUntil = myWeightPeriod;
281 : }
282 580 : typename CHBuilder<E, V>::Hierarchy* newHierarchy = myHierarchyBuilder->buildContractionHierarchy(myValidUntil - myWeightPeriod, vehicle, this);
283 580 : if (myHierarchy == nullptr) {
284 532 : myHierarchy = newHierarchy;
285 : } else {
286 48 : *myHierarchy = *newHierarchy;
287 48 : delete newHierarchy;
288 : }
289 580 : }
290 :
291 : /** @brief Builds the route between the given edges using the minimum traveltime in the contracted graph
292 : * @note: since the contracted graph is static (weights averaged over time)
293 : * the computed routes only approximated shortest paths in the real graph
294 : * */
295 18203 : 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 18203 : if (msTime >= myValidUntil) {
301 : assert(myHierarchyBuilder != nullptr); // only time independent clones do not have a builder
302 8216 : while (msTime >= myValidUntil) {
303 7679 : myValidUntil += myWeightPeriod;
304 : }
305 537 : this->reset(vehicle);
306 : }
307 : // ready for routing
308 : this->startQuery();
309 18203 : myForwardSearch.init(from, vehicle);
310 18203 : myBackwardSearch.init(to, vehicle);
311 18203 : double minTTSeen = std::numeric_limits<double>::max();
312 18203 : 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 586192 : while (continueForward || continueBackward) {
319 567989 : if (continueForward) {
320 452861 : continueForward = myForwardSearch.step(myHierarchy->forwardUplinks, myBackwardSearch, minTTSeen, meeting);
321 452861 : num_visited_fw += 1;
322 : }
323 567989 : if (continueBackward) {
324 458042 : continueBackward = myBackwardSearch.step(myHierarchy->backwardUplinks, myForwardSearch, minTTSeen, meeting);
325 458042 : num_visited_bw += 1;
326 : }
327 : }
328 18203 : if (minTTSeen < std::numeric_limits<double>::max()) {
329 17980 : buildPathFromMeeting(meeting, into);
330 : } else {
331 223 : if (!silent) {
332 669 : 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 18203 : this->endQuery(num_visited_bw + num_visited_fw);
340 18203 : return result;
341 : }
342 :
343 : /// normal routing methods
344 :
345 : /// Builds the path from marked edges
346 17980 : void buildPathFromMeeting(Meeting meeting, std::vector<const E*>& into) const {
347 : std::deque<const E*> tmp;
348 17980 : const auto* backtrack = meeting.first;
349 71261 : while (backtrack != 0) {
350 53281 : tmp.push_front((E*) backtrack->edge); // !!!
351 53281 : backtrack = backtrack->prev;
352 : }
353 17980 : backtrack = meeting.second->prev; // don't use central edge twice
354 46884 : while (backtrack != 0) {
355 28904 : tmp.push_back((E*) backtrack->edge); // !!!
356 28904 : backtrack = backtrack->prev;
357 : }
358 : // expand shortcuts
359 : const E* prev = 0;
360 176459 : while (!tmp.empty()) {
361 158479 : const E* cur = tmp.front();
362 158479 : tmp.pop_front();
363 158479 : if (prev == 0) {
364 17980 : into.push_back(cur);
365 : prev = cur;
366 : } else {
367 140499 : const E* via = getVia(prev, cur);
368 140499 : if (via == 0) {
369 102352 : into.push_back(cur);
370 : prev = cur;
371 : } else {
372 : tmp.push_front(cur);
373 : tmp.push_front(via);
374 : }
375 : }
376 : }
377 17980 : }
378 :
379 : private:
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 140499 : typename CHBuilder<E, V>::ShortcutVia::const_iterator it = myHierarchy->shortcuts.find(forward);
384 140499 : if (it != myHierarchy->shortcuts.end()) {
385 38147 : return it->second;
386 : } else {
387 : return 0;
388 : }
389 : }
390 :
391 :
392 : private:
393 : /// @brief all edges with numerical ids
394 : const std::vector<E*>& myEdges;
395 :
396 : /// @brief the unidirectional search queues
397 : Unidirectional myForwardSearch;
398 : Unidirectional myBackwardSearch;
399 :
400 : CHBuilder<E, V>* myHierarchyBuilder;
401 : typename CHBuilder<E, V>::Hierarchy* myHierarchy;
402 :
403 : /// @brief the validity duration of one weight interval
404 : const SUMOTime myWeightPeriod;
405 :
406 : /// @brief the validity duration of the current hierarchy (exclusive)
407 : SUMOTime myValidUntil;
408 :
409 : /// @brief the permissions for which the hierarchy was constructed
410 : const SUMOVehicleClass mySVC;
411 : };
|
