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