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 94526 : 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 566 : CHBuilder(const std::vector<E*>& edges, bool unbuildIsWarning,
90 : const SUMOVehicleClass svc,
91 : bool validatePermissions):
92 566 : myEdges(edges),
93 566 : myErrorMsgHandler(unbuildIsWarning ? MsgHandler::getWarningInstance() : MsgHandler::getErrorInstance()),
94 566 : mySPTree(new SPTree<CHInfo, CHConnection>(4, validatePermissions)),
95 566 : mySVC(svc),
96 1132 : myUpdateCount(0) {
97 34453 : for (const E* const e : edges) {
98 33887 : myCHInfos.push_back(CHInfo(e));
99 : }
100 566 : }
101 :
102 : /// Destructor
103 1132 : virtual ~CHBuilder() {
104 566 : delete mySPTree;
105 1698 : }
106 :
107 :
108 580 : Hierarchy* buildContractionHierarchy(SUMOTime time, const V* const vehicle, const SUMOAbstractRouter<E, V>* effortProvider) {
109 580 : Hierarchy* result = new Hierarchy();
110 580 : const int numEdges = (int)myCHInfos.size();
111 1150 : const std::string vClass = (mySPTree->validatePermissions() ?
112 570 : "all vehicle classes " : "vClass='" + SumoVehicleClassStrings.getString(mySVC) + "' ");
113 2900 : PROGRESS_BEGIN_MESSAGE("Building Contraction Hierarchy for " + vClass
114 : + "and time=" + time2string(time) + " (" + toString(numEdges) + " edges)\n");
115 580 : 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 32435 : for (int i = 0; i < numEdges; i++) {
120 31855 : myCHInfos[i].resetContractionState();
121 31855 : result->forwardUplinks.push_back(std::vector<Connection>());
122 31855 : result->backwardUplinks.push_back(std::vector<Connection>());
123 : }
124 : // copy connections from the original net
125 580 : const double time_seconds = STEPS2TIME(time); // timelines store seconds!
126 32435 : for (int i = 0; i < numEdges; i++) {
127 31855 : synchronize(myCHInfos[i], time_seconds, vehicle, effortProvider);
128 : }
129 : // synchronization is finished. now we can compute priorities for the first time
130 32435 : for (int i = 0; i < numEdges; i++) {
131 31855 : myCHInfos[i].updatePriority(mySPTree);
132 31855 : queue.push_back(&(myCHInfos[i]));
133 : }
134 580 : std::make_heap(queue.begin(), queue.end(), myCmp);
135 : int contractionRank = 0;
136 : // contraction loop
137 32435 : while (!queue.empty()) {
138 40508 : while (tryUpdateFront(queue)) {}
139 31855 : CHInfo* max = queue.front();
140 31855 : 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 31855 : const E* const edge = max->edge;
145 : // add outgoing connections to the forward search
146 : const int edgeID = edge->getNumericalID();
147 87951 : for (const CHConnection& con : max->followers) {
148 56096 : result->forwardUplinks[edgeID].push_back(Connection(con.target->edge->getNumericalID(), con.cost, con.permissions));
149 56096 : disconnect(con.target->approaching, max);
150 56096 : con.target->updatePriority(0);
151 : }
152 : // add incoming connections to the backward search
153 70285 : for (const CHConnection& con : max->approaching) {
154 38430 : result->backwardUplinks[edgeID].push_back(Connection(con.target->edge->getNumericalID(), con.cost, con.permissions));
155 38430 : disconnect(con.target->followers, max);
156 38430 : con.target->updatePriority(0);
157 : }
158 : // add shortcuts to the net
159 84949 : for (const Shortcut& s : max->shortcuts) {
160 53094 : const ConstEdgePair& edgePair = s.edgePair;
161 53094 : result->shortcuts[edgePair] = edge;
162 53094 : CHInfo* from = getCHInfo(edgePair.first);
163 53094 : CHInfo* to = getCHInfo(edgePair.second);
164 106188 : from->followers.push_back(CHConnection(to, s.cost, s.permissions, s.underlying));
165 53094 : 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 31855 : 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 31855 : contractionRank++;
182 : }
183 : // reporting
184 580 : const long duration = SysUtils::getCurrentMillis() - startMillis;
185 1160 : WRITE_MESSAGE("Created " + toString(result->shortcuts.size()) + " shortcuts.");
186 1160 : WRITE_MESSAGE("Recomputed priority " + toString(myUpdateCount) + " times.");
187 1160 : MsgHandler::getMessageInstance()->endProcessMsg("done (" + toString(duration) + "ms).");
188 580 : PROGRESS_DONE_MESSAGE();
189 580 : myUpdateCount = 0;
190 580 : return result;
191 580 : }
192 :
193 : private:
194 : struct Shortcut {
195 278651 : Shortcut(ConstEdgePair e, double c, int u, SVCPermissions p):
196 278651 : 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 189052 : CHConnection(CHInfo* t, double c, SVCPermissions p, int u):
210 53094 : 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 33887 : CHInfo(const E* const e) :
229 33887 : edge(e),
230 33887 : priority(0.),
231 33887 : contractedNeighbors(0),
232 33887 : rank(-1),
233 33887 : level(0),
234 33887 : underlyingTotal(0),
235 33887 : visited(false),
236 33887 : traveltime(std::numeric_limits<double>::max()),
237 33887 : depth(0),
238 33887 : permissions(SVC_IGNORING) {
239 : }
240 :
241 : /// @brief recompute the contraction priority and report whether it changed
242 166889 : bool updatePriority(SPTree<CHInfo, CHConnection>* spTree) {
243 166889 : if (spTree != nullptr) {
244 72363 : updateShortcuts(spTree);
245 72363 : updateLevel();
246 : } else {
247 94526 : contractedNeighbors += 1; // called when a connected edge was contracted
248 : }
249 166889 : const double oldPriority = priority;
250 : // priority term as used by abraham []
251 166889 : const int edge_difference = (int)followers.size() + (int)approaching.size() - 2 * (int)shortcuts.size();
252 166889 : priority = (double)(2 * edge_difference - contractedNeighbors - underlyingTotal - 5 * level);
253 166889 : return priority != oldPriority;
254 : }
255 :
256 : /// compute needed shortcuts when contracting this edge
257 72363 : 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 72363 : underlyingTotal = 0;
265 200458 : for (const CHConnection& aInfo : approaching) {
266 : // build shortest path tree in a fixed neighborhood
267 128095 : spTree->rebuildFrom(aInfo.target, this);
268 981700 : for (const CHConnection& fInfo : followers) {
269 853605 : const double viaCost = aInfo.cost + fInfo.cost;
270 853605 : const SVCPermissions viaPermissions = (aInfo.permissions & fInfo.permissions);
271 853605 : 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 278631 : const int underlying = aInfo.underlying + fInfo.underlying;
277 278631 : underlyingTotal += underlying;
278 278631 : shortcuts.push_back(Shortcut(ConstEdgePair(aInfo.target->edge, fInfo.target->edge),
279 : viaCost, underlying, viaPermissions));
280 :
281 574974 : } 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 72363 : 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 72363 : }
311 :
312 :
313 : // update level as defined by Abraham
314 72363 : void updateLevel() {
315 : int maxLower = std::numeric_limits<int>::min();
316 200458 : for (const CHConnection& con : approaching) {
317 128095 : if (con.target->rank < rank) {
318 : maxLower = MAX2(rank, maxLower);
319 : }
320 : }
321 218380 : for (const CHConnection& con : followers) {
322 146017 : if (con.target->rank < rank) {
323 : maxLower = MAX2(rank, maxLower);
324 : }
325 : }
326 72363 : if (maxLower == std::numeric_limits<int>::min()) {
327 72363 : level = 0;
328 : } else {
329 0 : level = maxLower + 1;
330 : }
331 72363 : }
332 :
333 : // resets state before rebuilding the hierarchy
334 : void resetContractionState() {
335 31855 : priority = 0.;
336 : shortcuts.clear();
337 31855 : contractedNeighbors = 0;
338 31855 : rank = -1;
339 31855 : level = 0;
340 31855 : 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 8658648 : traveltime = std::numeric_limits<double>::max();
379 8658648 : visited = false;
380 8658648 : depth = 0;
381 8658648 : 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 398053 : if (a->priority == b->priority) {
408 233179 : return a->edge->getNumericalID() > b->edge->getNumericalID();
409 : } else {
410 164874 : return a->priority < b->priority;
411 : };
412 : }
413 : };
414 :
415 :
416 : inline CHInfo* getCHInfo(const E* const edge) {
417 94526 : return &(myCHInfos[edge->getNumericalID()]);
418 : }
419 :
420 :
421 : /// @brief copy connections from the original net (modified destructively during contraction)
422 31855 : 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 31855 : const bool prune = !mySPTree->validatePermissions();
426 31855 : const E* const edge = info.edge;
427 31855 : if (prune && ((edge->getPermissions() & mySVC) != mySVC)) {
428 : return;
429 : }
430 : const double baseCost = effortProvider->getEffort(edge, vehicle, time);
431 :
432 72584 : for (const std::pair<const E*, const E*>& successor : edge->getViaSuccessors(mySVC)) {
433 41446 : const E* fEdge = successor.first;
434 41446 : if (prune && ((fEdge->getPermissions() & mySVC) != mySVC)) {
435 14 : continue;
436 : }
437 : CHInfo* const follower = getCHInfo(fEdge);
438 41432 : const SVCPermissions permissions = (edge->getPermissions() & fEdge->getPermissions());
439 : double cost = baseCost;
440 41432 : const E* viaEdge = successor.second;
441 59394 : while (viaEdge != nullptr && viaEdge->isInternal()) {
442 17962 : cost += effortProvider->getEffort(viaEdge, vehicle, time);
443 17962 : viaEdge = viaEdge->getViaSuccessors().front().first;
444 : }
445 41432 : info.followers.push_back(CHConnection(follower, cost, permissions, 1));
446 41432 : 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 447657 : for (typename CHConnections::iterator it = connections.begin(); it != connections.end(); it++) {
458 447657 : 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 40508 : bool tryUpdateFront(std::vector<CHInfo*>& queue) {
470 40508 : myUpdateCount++;
471 40508 : CHInfo* max = queue.front();
472 : #ifdef CHRouter_DEBUG_CONTRACTION_QUEUE
473 : std::cout << "updating '" << max->edge->getID() << "'\n";
474 : debugPrintQueue(queue);
475 : #endif
476 40508 : if (max->updatePriority(mySPTree)) {
477 8653 : std::pop_heap(queue.begin(), queue.end(), myCmp);
478 : std::push_heap(queue.begin(), queue.end(), myCmp);
479 8653 : 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 : };
|
