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 CHBuilder.h
15 : /// @author Jakob Erdmann
16 : /// @author Laura Bieker
17 : /// @author Michael Behrisch
18 : /// @date February 2012
19 : ///
20 : // Contraction Hierarchy Builder for the shortest path search
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 <utils/common/SysUtils.h>
33 : #include <utils/common/MsgHandler.h>
34 : #include <utils/common/StdDefs.h>
35 : #include <utils/router/SUMOAbstractRouter.h>
36 : #include "SPTree.h"
37 :
38 : //#define CHRouter_DEBUG_CONTRACTION
39 : //#define CHRouter_DEBUG_CONTRACTION_WITNESSES
40 : //#define CHRouter_DEBUG_CONTRACTION_QUEUE
41 : //#define CHRouter_DEBUG_CONTRACTION_DEGREE
42 : //#define CHRouter_DEBUG_WEIGHTS
43 :
44 : // ===========================================================================
45 : // class definitions
46 : // ===========================================================================
47 : /**
48 : * @class CHRouter
49 : * @brief Computes the shortest path through a contracted network
50 : *
51 : * The template parameters are:
52 : * @param E The edge class to use (MSEdge/ROEdge)
53 : * @param V The vehicle class to use (MSVehicle/ROVehicle)
54 : * @param PF The prohibition function to use (prohibited_withPermissions/noProhibitions)
55 : *
56 : * The router is edge-based. It must know the number of edges for internal reasons
57 : * and whether a missing connection between two given edges (unbuild route) shall
58 : * be reported as an error or as a warning.
59 : *
60 : */
61 : template<class E, class V>
62 : class CHBuilder {
63 :
64 : public:
65 : /// @brief Forward/backward connection with associated forward/backward cost
66 : // forward connections are used only in forward search
67 : // backward connections are used only in backwards search
68 : class Connection {
69 : public:
70 94692 : Connection(int t, double c, SVCPermissions p): target(t), cost(c), permissions(p) {}
71 : int target;
72 : double cost;
73 : SVCPermissions permissions;
74 : };
75 :
76 : typedef std::pair<const E*, const E*> ConstEdgePair;
77 : typedef std::map<ConstEdgePair, const E*> ShortcutVia;
78 : struct Hierarchy {
79 : ShortcutVia shortcuts;
80 : std::vector<std::vector<Connection> > forwardUplinks;
81 : std::vector<std::vector<Connection> > backwardUplinks;
82 : };
83 :
84 : /** @brief Constructor
85 : * @param[in] validatePermissions Whether a multi-permission hierarchy shall be built
86 : * If set to false, the net is pruned in synchronize() and the
87 : * hierarchy is tailored to the svc
88 : */
89 574 : CHBuilder(const std::vector<E*>& edges, bool unbuildIsWarning,
90 : const SUMOVehicleClass svc,
91 : bool validatePermissions):
92 574 : myEdges(edges),
93 574 : myErrorMsgHandler(unbuildIsWarning ? MsgHandler::getWarningInstance() : MsgHandler::getErrorInstance()),
94 574 : mySPTree(new SPTree<CHInfo, CHConnection>(4, validatePermissions)),
95 574 : mySVC(svc),
96 1148 : myUpdateCount(0) {
97 34589 : for (const E* const e : edges) {
98 34015 : myCHInfos.push_back(CHInfo(e));
99 : }
100 574 : }
101 :
102 : /// Destructor
103 1148 : virtual ~CHBuilder() {
104 574 : delete mySPTree;
105 1722 : }
106 :
107 :
108 588 : Hierarchy* buildContractionHierarchy(SUMOTime time, const V* const vehicle, const SUMOAbstractRouter<E, V>* effortProvider) {
109 588 : Hierarchy* result = new Hierarchy();
110 588 : const int numEdges = (int)myCHInfos.size();
111 1166 : const std::string vClass = (mySPTree->validatePermissions() ?
112 578 : "all vehicle classes " : "vClass='" + SumoVehicleClassStrings.getString(mySVC) + "' ");
113 2940 : PROGRESS_BEGIN_MESSAGE("Building Contraction Hierarchy for " + vClass
114 : + "and time=" + time2string(time) + " (" + toString(numEdges) + " edges)\n");
115 588 : const long startMillis = SysUtils::getCurrentMillis();
116 : // init queue
117 : std::vector<CHInfo*> queue; // max heap: edge to be contracted is front
118 : // reset previous connections etc
119 32571 : for (int i = 0; i < numEdges; i++) {
120 31983 : myCHInfos[i].resetContractionState();
121 31983 : result->forwardUplinks.push_back(std::vector<Connection>());
122 31983 : result->backwardUplinks.push_back(std::vector<Connection>());
123 : }
124 : // copy connections from the original net
125 588 : const double time_seconds = STEPS2TIME(time); // timelines store seconds!
126 32571 : for (int i = 0; i < numEdges; i++) {
127 31983 : synchronize(myCHInfos[i], time_seconds, vehicle, effortProvider);
128 : }
129 : // synchronization is finished. now we can compute priorities for the first time
130 32571 : for (int i = 0; i < numEdges; i++) {
131 31983 : myCHInfos[i].updatePriority(mySPTree);
132 31983 : queue.push_back(&(myCHInfos[i]));
133 : }
134 588 : std::make_heap(queue.begin(), queue.end(), myCmp);
135 : int contractionRank = 0;
136 : // contraction loop
137 32571 : while (!queue.empty()) {
138 40682 : while (tryUpdateFront(queue)) {}
139 31983 : CHInfo* max = queue.front();
140 31983 : max->rank = contractionRank;
141 : #ifdef CHRouter_DEBUG_CONTRACTION
142 : std::cout << "contracting '" << max->edge->getID() << "' with prio: " << max->priority << " (rank " << contractionRank << ")\n";
143 : #endif
144 31983 : const E* const edge = max->edge;
145 : // add outgoing connections to the forward search
146 : const int edgeID = edge->getNumericalID();
147 88163 : for (const CHConnection& con : max->followers) {
148 56180 : result->forwardUplinks[edgeID].push_back(Connection(con.target->edge->getNumericalID(), con.cost, con.permissions));
149 56180 : disconnect(con.target->approaching, max);
150 56180 : con.target->updatePriority(0);
151 : }
152 : // add incoming connections to the backward search
153 70495 : for (const CHConnection& con : max->approaching) {
154 38512 : result->backwardUplinks[edgeID].push_back(Connection(con.target->edge->getNumericalID(), con.cost, con.permissions));
155 38512 : disconnect(con.target->followers, max);
156 38512 : con.target->updatePriority(0);
157 : }
158 : // add shortcuts to the net
159 85091 : for (const Shortcut& s : max->shortcuts) {
160 53108 : const ConstEdgePair& edgePair = s.edgePair;
161 53108 : result->shortcuts[edgePair] = edge;
162 53108 : CHInfo* from = getCHInfo(edgePair.first);
163 53108 : CHInfo* to = getCHInfo(edgePair.second);
164 106216 : from->followers.push_back(CHConnection(to, s.cost, s.permissions, s.underlying));
165 53108 : to->approaching.push_back(CHConnection(from, s.cost, s.permissions, s.underlying));
166 : }
167 : // if you need to debug the chrouter with MSVC uncomment the following line, hierarchy building will get slower and the hierarchy may change though
168 : //std::make_heap(queue.begin(), queue.end(), myCmp);
169 : // remove from queue
170 31983 : std::pop_heap(queue.begin(), queue.end(), myCmp);
171 : queue.pop_back();
172 : /*
173 : if (contractionRank % 10000 == 0) {
174 : // update all and rebuild queue
175 : for (typename std::vector<CHInfo*>::iterator it = queue.begin(); it != queue.end(); ++it) {
176 : (*it)->updatePriority(mySPTree);
177 : }
178 : std::make_heap(queue.begin(), queue.end(), myCmp);
179 : }
180 : */
181 31983 : contractionRank++;
182 : }
183 : // reporting
184 588 : const long duration = SysUtils::getCurrentMillis() - startMillis;
185 1176 : WRITE_MESSAGE("Created " + toString(result->shortcuts.size()) + " shortcuts.");
186 1176 : WRITE_MESSAGE("Recomputed priority " + toString(myUpdateCount) + " times.");
187 1176 : MsgHandler::getMessageInstance()->endProcessMsg("done (" + toString(duration) + "ms).");
188 588 : PROGRESS_DONE_MESSAGE();
189 588 : myUpdateCount = 0;
190 588 : return result;
191 588 : }
192 :
193 : private:
194 : struct Shortcut {
195 278833 : Shortcut(ConstEdgePair e, double c, int u, SVCPermissions p):
196 278833 : edgePair(e), cost(c), underlying(u), permissions(p) {}
197 : ConstEdgePair edgePair;
198 : double cost;
199 : int underlying;
200 : SVCPermissions permissions;
201 : };
202 :
203 :
204 : class CHInfo;
205 :
206 : /// @brief Forward/backward connection with associated FORWARD cost
207 : class CHConnection {
208 : public:
209 189384 : CHConnection(CHInfo* t, double c, SVCPermissions p, int u):
210 53108 : target(t), cost(c), permissions(p), underlying(u) {}
211 : CHInfo* target;
212 : double cost;
213 : SVCPermissions permissions;
214 : /// the number of connections underlying this connection
215 : int underlying;
216 : };
217 :
218 : typedef std::vector<CHConnection> CHConnections;
219 : typedef std::pair<const CHConnection*, const CHConnection*> CHConnectionPair;
220 : typedef std::vector<CHConnectionPair> CHConnectionPairs;
221 :
222 : /* @brief container class to use when building the contraction hierarchy.
223 : * instances are reused every time the hierarchy is rebuilt (new time slice)
224 : * but they must be synchronized first */
225 : class CHInfo {
226 : public:
227 : /// @brief Constructor
228 34015 : CHInfo(const E* const e) :
229 34015 : edge(e),
230 34015 : priority(0.),
231 34015 : contractedNeighbors(0),
232 34015 : rank(-1),
233 34015 : level(0),
234 34015 : underlyingTotal(0),
235 34015 : visited(false),
236 34015 : traveltime(std::numeric_limits<double>::max()),
237 34015 : depth(0),
238 34015 : permissions(SVC_IGNORING) {
239 : }
240 :
241 : /// @brief recompute the contraction priority and report whether it changed
242 167357 : bool updatePriority(SPTree<CHInfo, CHConnection>* spTree) {
243 167357 : if (spTree != nullptr) {
244 72665 : updateShortcuts(spTree);
245 72665 : updateLevel();
246 : } else {
247 94692 : contractedNeighbors += 1; // called when a connected edge was contracted
248 : }
249 167357 : const double oldPriority = priority;
250 : // priority term as used by abraham []
251 167357 : const int edge_difference = (int)followers.size() + (int)approaching.size() - 2 * (int)shortcuts.size();
252 167357 : priority = (double)(2 * edge_difference - contractedNeighbors - underlyingTotal - 5 * level);
253 167357 : return priority != oldPriority;
254 : }
255 :
256 : /// compute needed shortcuts when contracting this edge
257 72665 : void updateShortcuts(SPTree<CHInfo, CHConnection>* spTree) {
258 : const bool validatePermissions = spTree->validatePermissions();
259 : #ifdef CHRouter_DEBUG_CONTRACTION_DEGREE
260 : const int degree = (int)approaching.size() + (int)followers.size();
261 : std::cout << "computing shortcuts for '" + edge->getID() + "' with degree " + toString(degree) + "\n";
262 : #endif
263 : shortcuts.clear();
264 72665 : underlyingTotal = 0;
265 201020 : for (const CHConnection& aInfo : approaching) {
266 : // build shortest path tree in a fixed neighborhood
267 128355 : spTree->rebuildFrom(aInfo.target, this);
268 982230 : for (const CHConnection& fInfo : followers) {
269 853875 : const double viaCost = aInfo.cost + fInfo.cost;
270 853875 : const SVCPermissions viaPermissions = (aInfo.permissions & fInfo.permissions);
271 853875 : if (fInfo.target->traveltime > viaCost) {
272 : // found no faster path -> we need a shortcut via edge
273 : #ifdef CHRouter_DEBUG_CONTRACTION_WITNESSES
274 : debugNoWitness(aInfo, fInfo);
275 : #endif
276 278813 : const int underlying = aInfo.underlying + fInfo.underlying;
277 278813 : underlyingTotal += underlying;
278 278813 : shortcuts.push_back(Shortcut(ConstEdgePair(aInfo.target->edge, fInfo.target->edge),
279 : viaCost, underlying, viaPermissions));
280 :
281 575062 : } else if (validatePermissions) {
282 20 : if ((fInfo.target->permissions & viaPermissions) != viaPermissions) {
283 : // witness has weaker restrictions. try to find another witness
284 : spTree->registerForValidation(&aInfo, &fInfo);
285 : } else {
286 : #ifdef CHRouter_DEBUG_CONTRACTION_WITNESSES
287 : debugNoWitness(aInfo, fInfo);
288 : #endif
289 : }
290 : } else {
291 : #ifdef CHRouter_DEBUG_CONTRACTION_WITNESSES
292 : debugNoWitness(aInfo, fInfo);
293 : #endif
294 : }
295 : }
296 : }
297 : // insert shortcuts needed due to unmet permissions
298 72665 : if (validatePermissions) {
299 220 : for (const CHConnectionPair& chcp : spTree->getNeededShortcuts(this)) {
300 20 : const CHConnection* aInfo = chcp.first;
301 20 : const CHConnection* fInfo = chcp.second;
302 20 : const double viaCost = aInfo->cost + fInfo->cost;
303 20 : const SVCPermissions viaPermissions = (aInfo->permissions & fInfo->permissions);
304 20 : const int underlying = aInfo->underlying + fInfo->underlying;
305 20 : underlyingTotal += underlying;
306 20 : shortcuts.push_back(Shortcut(ConstEdgePair(aInfo->target->edge, fInfo->target->edge),
307 : viaCost, underlying, viaPermissions));
308 : }
309 : }
310 72665 : }
311 :
312 :
313 : // update level as defined by Abraham
314 72665 : void updateLevel() {
315 : int maxLower = std::numeric_limits<int>::min();
316 201020 : for (const CHConnection& con : approaching) {
317 128355 : if (con.target->rank < rank) {
318 : maxLower = MAX2(rank, maxLower);
319 : }
320 : }
321 218948 : for (const CHConnection& con : followers) {
322 146283 : if (con.target->rank < rank) {
323 : maxLower = MAX2(rank, maxLower);
324 : }
325 : }
326 72665 : if (maxLower == std::numeric_limits<int>::min()) {
327 72665 : level = 0;
328 : } else {
329 0 : level = maxLower + 1;
330 : }
331 72665 : }
332 :
333 : // resets state before rebuilding the hierarchy
334 : void resetContractionState() {
335 31983 : priority = 0.;
336 : shortcuts.clear();
337 31983 : contractedNeighbors = 0;
338 31983 : rank = -1;
339 31983 : level = 0;
340 31983 : underlyingTotal = 0;
341 : followers.clear();
342 : approaching.clear();
343 : reset(); // just to make sure
344 : }
345 :
346 :
347 : /// @brief The current edge
348 : const E* const edge;
349 : /// @brief The contraction priority
350 : double priority;
351 : /// @brief The needed shortcuts
352 : std::vector<Shortcut> shortcuts;
353 : /// @brief priority subterms
354 : int contractedNeighbors;
355 : int rank;
356 : int level;
357 : int underlyingTotal;
358 :
359 : /// @brief connections (only valid after synchronization)
360 : CHConnections followers;
361 : CHConnections approaching;
362 :
363 : /// @name members used in SPTree
364 : /// @{
365 :
366 : /// whether the edge has been visited during shortest path search
367 : bool visited;
368 : /// Effort to reach the edge
369 : double traveltime;
370 : /// number of edges from start
371 : int depth;
372 : /// the permissions when reaching this edge on the fastest path
373 : // @note: we may miss some witness paths by making traveltime the only
374 : // criteria durinng search
375 : SVCPermissions permissions;
376 :
377 : inline void reset() {
378 8659918 : traveltime = std::numeric_limits<double>::max();
379 8659918 : visited = false;
380 8659918 : depth = 0;
381 8659918 : permissions = SVC_IGNORING;
382 : }
383 :
384 : /// @}
385 :
386 : /// debugging methods
387 : inline void debugNoWitness(const CHConnection& aInfo, const CHConnection& fInfo) {
388 : std::cout << "adding shortcut between " << aInfo.target->edge->getID() << ", " << fInfo.target->edge->getID() << " via " << edge->getID() << "\n";
389 : }
390 :
391 : inline void debugWitness(const CHConnection& aInfo, const CHConnection& fInfo) {
392 : const double viaCost = aInfo.cost + fInfo.cost;
393 : std::cout << "found witness with length " << fInfo.target->traveltime << " against via " << edge->getID() << " (length " << viaCost << ") for " << aInfo.target->edge->getID() << ", " << fInfo.target->edge->getID() << "\n";
394 : }
395 :
396 : };
397 :
398 :
399 : /**
400 : * @class EdgeInfoByRankComparator
401 : * Class to compare (and so sort) nodes by their contraction priority
402 : */
403 : class CHInfoComparator {
404 : public:
405 : /// Comparing method
406 : bool operator()(const CHInfo* a, const CHInfo* b) const {
407 398705 : if (a->priority == b->priority) {
408 233319 : return a->edge->getNumericalID() > b->edge->getNumericalID();
409 : } else {
410 165386 : return a->priority < b->priority;
411 : };
412 : }
413 : };
414 :
415 :
416 : inline CHInfo* getCHInfo(const E* const edge) {
417 94692 : return &(myCHInfos[edge->getNumericalID()]);
418 : }
419 :
420 :
421 : /// @brief copy connections from the original net (modified destructively during contraction)
422 31983 : void synchronize(CHInfo& info, double time, const V* const vehicle, const SUMOAbstractRouter<E, V>* effortProvider) {
423 : // forward and backward connections are used only in forward search,
424 : // thus approaching costs are those of the approaching edge and not of the edge itself
425 31983 : const bool prune = !mySPTree->validatePermissions();
426 31983 : const E* const edge = info.edge;
427 31983 : if (prune && ((edge->getPermissions() & mySVC) != mySVC)) {
428 : return;
429 : }
430 : const double baseCost = effortProvider->getEffort(edge, vehicle, time);
431 :
432 72858 : for (const std::pair<const E*, const E*>& successor : edge->getViaSuccessors(mySVC)) {
433 41600 : const E* fEdge = successor.first;
434 41600 : if (prune && ((fEdge->getPermissions() & mySVC) != mySVC)) {
435 16 : continue;
436 : }
437 : CHInfo* const follower = getCHInfo(fEdge);
438 41584 : const SVCPermissions permissions = (edge->getPermissions() & fEdge->getPermissions());
439 : double cost = baseCost;
440 41584 : const E* viaEdge = successor.second;
441 59546 : while (viaEdge != nullptr && viaEdge->isInternal()) {
442 17962 : cost += effortProvider->getEffort(viaEdge, vehicle, time);
443 17962 : viaEdge = viaEdge->getViaSuccessors().front().first;
444 : }
445 41584 : info.followers.push_back(CHConnection(follower, cost, permissions, 1));
446 41584 : follower->approaching.push_back(CHConnection(&info, cost, permissions, 1));
447 : }
448 : #ifdef CHRouter_DEBUG_WEIGHTS
449 : std::cout << time << ": " << edge->getID() << " baseCost: " << baseCost << "\n";
450 : #endif
451 : // @todo: check whether we even need to save approaching in ROEdge;
452 : }
453 :
454 :
455 : /// @brief remove all connections to/from the given edge (assume it exists only once)
456 : void disconnect(CHConnections& connections, CHInfo* other) {
457 447935 : for (typename CHConnections::iterator it = connections.begin(); it != connections.end(); it++) {
458 447935 : if (it->target == other) {
459 : connections.erase(it);
460 : return;
461 : }
462 : }
463 : assert(false);
464 : }
465 :
466 : /** @brief tries to update the priority of the first edge
467 : * @return wether updating changed the first edge
468 : */
469 40682 : bool tryUpdateFront(std::vector<CHInfo*>& queue) {
470 40682 : myUpdateCount++;
471 40682 : CHInfo* max = queue.front();
472 : #ifdef CHRouter_DEBUG_CONTRACTION_QUEUE
473 : std::cout << "updating '" << max->edge->getID() << "'\n";
474 : debugPrintQueue(queue);
475 : #endif
476 40682 : if (max->updatePriority(mySPTree)) {
477 8699 : std::pop_heap(queue.begin(), queue.end(), myCmp);
478 : std::push_heap(queue.begin(), queue.end(), myCmp);
479 8699 : return true;
480 : } else {
481 : return false;
482 : }
483 : }
484 :
485 : #ifdef CHRouter_DEBUG_CONTRACTION_QUEUE
486 : // helper method for debugging
487 : void debugPrintQueue(std::vector<CHInfo*>& queue) {
488 : for (const CHInfo* const chInfo : queue) {
489 : std::cout << "(" << chInfo->edge->getID() << "," << chInfo->priority << ") ";
490 : }
491 : std::cout << "\n";
492 : }
493 : #endif
494 :
495 : private:
496 : /// @brief all edges with numerical ids
497 : const std::vector<E*>& myEdges;
498 :
499 : /// @brief the handler for routing errors
500 : MsgHandler* const myErrorMsgHandler;
501 :
502 : /// @brief static vector for lookup
503 : std::vector<CHInfo> myCHInfos;
504 :
505 : /// @brief Comparator for contraction priority
506 : CHInfoComparator myCmp;
507 :
508 : /// @brief the shortest path tree to use when searching for shortcuts
509 : SPTree<CHInfo, CHConnection>* mySPTree;
510 :
511 : /// @brief the permissions for which the hierarchy was constructed
512 : const SUMOVehicleClass mySVC;
513 :
514 : /// @brief counters for performance logging
515 : int myUpdateCount;
516 :
517 : private:
518 : /// @brief Invalidated assignment operator
519 : CHBuilder& operator=(const CHBuilder& s);
520 : };
|
