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 SPTree.h 11 /// @author Laura Bieker 12 /// @author Michael Behrisch 13 /// @date February 2012 14 /// @version $Id$ 15 /// 16 // Shortest Path tree of limited depth using Dijkstras algorithm 17 /****************************************************************************/ 18 #ifndef SPTree_h 19 #define SPTree_h 20 21 22 // =========================================================================== 23 // included modules 24 // =========================================================================== 25 #include <config.h> 26 27 #include <string> 28 #include <functional> 29 #include <vector> 30 #include <set> 31 #include <limits> 32 #include <algorithm> 33 #include <iterator> 34 #include <utils/common/MsgHandler.h> 35 #include <utils/common/StdDefs.h> 36 37 38 template<class E, class C> 39 class SPTree { 40 41 public: 42 typedef std::vector<C> CHConnections; 43 typedef std::pair<const C*, const C*> CHConnectionPair; 44 typedef std::vector<CHConnectionPair> CHConnectionPairs; 45 46 /** 47 * @class EdgeInfoByEffortComparator 48 * Class to compare (and so sort) nodes by their effort 49 */ 50 class EdgeByTTComparator { 51 public: 52 /// Comparing method operator()53 bool operator()(const E* a, const E* b) const { 54 if (a->traveltime == b->traveltime) { 55 return a->edge->getNumericalID() > b->edge->getNumericalID(); 56 } 57 return a->traveltime > b->traveltime; 58 } 59 }; 60 61 62 /** 63 * @brief Constructor 64 */ SPTree(int maxDepth,bool validatePermissions)65 SPTree(int maxDepth, bool validatePermissions) : 66 myMaxDepth(maxDepth), 67 myValidatePermissions(validatePermissions) { 68 } 69 70 init()71 void init() { 72 // all EdgeInfos touched in the previous query are either in myFrontier or myFound: clean those up 73 for (typename std::vector<E*>::iterator i = myFrontier.begin(); i != myFrontier.end(); i++) { 74 (*i)->reset(); 75 } 76 myFrontier.clear(); 77 for (typename std::vector<E*>::iterator i = myFound.begin(); i != myFound.end(); i++) { 78 (*i)->reset(); 79 } 80 myFound.clear(); 81 } 82 83 84 /** 85 * @brief build a shortest path tree from start to a depth of myMaxdepth. The given 86 * edge is excluded from this tree 87 */ rebuildFrom(E * start,const E * excluded)88 void rebuildFrom(E* start, const E* excluded) { 89 init(); 90 start->traveltime = 0; 91 start->depth = 0; 92 start->permissions = start->edge->getPermissions(); 93 myFrontier.push_back(start); 94 // build SPT 95 while (!myFrontier.empty()) { 96 E* min = myFrontier.front(); 97 std::pop_heap(myFrontier.begin(), myFrontier.end(), myCmp); 98 myFrontier.pop_back(); 99 myFound.push_back(min); 100 min->visited = true; 101 if (min->depth < myMaxDepth) { 102 for (typename CHConnections::iterator it = min->followers.begin(); it != min->followers.end(); it++) { 103 C& con = *it; 104 E* follower = con.target; 105 if (follower == excluded) { 106 continue; 107 } 108 const double traveltime = min->traveltime + con.cost; 109 const double oldTraveltime = follower->traveltime; 110 if (!follower->visited && traveltime < oldTraveltime) { 111 follower->traveltime = traveltime; 112 follower->depth = min->depth + 1; 113 follower->permissions = (min->permissions & con.permissions); 114 if (oldTraveltime == std::numeric_limits<double>::max()) { 115 myFrontier.push_back(follower); 116 std::push_heap(myFrontier.begin(), myFrontier.end(), myCmp); 117 } else { 118 std::push_heap(myFrontier.begin(), 119 std::find(myFrontier.begin(), myFrontier.end(), follower) + 1, 120 myCmp); 121 } 122 } 123 } 124 } 125 } 126 } 127 128 129 /// @brief whether permissions should be validated; validatePermissions()130 inline bool validatePermissions() { 131 return myValidatePermissions; 132 } 133 134 /// @brief save source/target pair for later validation registerForValidation(const C * aInfo,const C * fInfo)135 void registerForValidation(const C* aInfo, const C* fInfo) { 136 assert(myValidatePermissions); 137 myShortcutsToValidate.push_back(CHConnectionPair(aInfo, fInfo)); 138 } 139 140 141 /* @brief for each path source->excluded->target try to find a witness with a witness 142 * with equal permissions */ getNeededShortcuts(const E * excluded)143 const CHConnectionPairs& getNeededShortcuts(const E* excluded) { 144 assert(myValidatePermissions); 145 myNeededShortcuts.clear(); 146 for (typename CHConnectionPairs::iterator it = myShortcutsToValidate.begin(); it != myShortcutsToValidate.end(); ++it) { 147 const C* const aInfo = it->first; 148 const C* const fInfo = it->second; 149 const double bestWitness = dijkstraTT( 150 aInfo->target, fInfo->target, excluded, (aInfo->permissions & fInfo->permissions)); 151 const double viaCost = aInfo->cost + fInfo->cost; 152 if (viaCost < bestWitness) { 153 myNeededShortcuts.push_back(*it); 154 } 155 } 156 myShortcutsToValidate.clear(); 157 return myNeededShortcuts; 158 } 159 160 161 private: 162 // perform dijkstra search under permission constraints dijkstraTT(E * start,E * dest,const E * excluded,SVCPermissions permissions)163 double dijkstraTT(E* start, E* dest, const E* excluded, SVCPermissions permissions) { 164 init(); 165 start->traveltime = 0; 166 start->depth = 0; 167 myFrontier.push_back(start); 168 // build SPT 169 while (!myFrontier.empty()) { 170 E* min = myFrontier.front(); 171 if (min == dest) { 172 return dest->traveltime; 173 } 174 std::pop_heap(myFrontier.begin(), myFrontier.end(), myCmp); 175 myFrontier.pop_back(); 176 myFound.push_back(min); 177 min->visited = true; 178 if (min->depth < myMaxDepth) { 179 for (typename CHConnections::iterator it = min->followers.begin(); it != min->followers.end(); it++) { 180 C& con = *it; 181 E* follower = con.target; 182 if (follower == excluded) { 183 continue; 184 } 185 if ((con.permissions & permissions) != permissions) { 186 continue; 187 } 188 const double traveltime = min->traveltime + con.cost; 189 const double oldTraveltime = follower->traveltime; 190 if (!follower->visited && traveltime < oldTraveltime) { 191 follower->traveltime = traveltime; 192 follower->depth = min->depth + 1; 193 follower->permissions = (min->permissions & con.permissions); 194 if (oldTraveltime == std::numeric_limits<double>::max()) { 195 myFrontier.push_back(follower); 196 std::push_heap(myFrontier.begin(), myFrontier.end(), myCmp); 197 } else { 198 std::push_heap(myFrontier.begin(), 199 std::find(myFrontier.begin(), myFrontier.end(), follower) + 1, 200 myCmp); 201 } 202 } 203 } 204 } 205 } 206 return dest->traveltime; 207 } 208 209 210 // helper method for debugging debugPrintVector(std::vector<E * > & vec,E * start,const E * excluded)211 void debugPrintVector(std::vector<E*>& vec, E* start, const E* excluded) { 212 std::cout << "computed SPT from '" << start->edge->getID() << "' (excluding " << excluded->edge->getID() << ") with " << myFound.size() << " edges\n"; 213 for (typename std::vector<E*>::iterator it = vec.begin(); it != vec.end(); it++) { 214 E* e = *it; 215 std::cout << "(" << e->edge->getID() << "," << e->traveltime << ") "; 216 } 217 std::cout << "\n"; 218 } 219 220 /// @brief the min edge heap 221 std::vector<E*> myFrontier; 222 /// @brief the list of visited edges (used when resetting) 223 std::vector<E*> myFound; 224 225 /// @brief comparator for search queue 226 EdgeByTTComparator myCmp; 227 228 /// @brief maximum search depth 229 int myMaxDepth; 230 231 /// @brief whether permissions should be validated 232 bool myValidatePermissions; 233 234 /// @brief vector of needed shortcuts after validation 235 CHConnectionPairs myShortcutsToValidate; 236 /// @brief vector of needed shortcuts after validation 237 CHConnectionPairs myNeededShortcuts; 238 }; 239 240 #endif 241 242 /****************************************************************************/ 243 244