SUMO - Simulation of Urban MObility
|
00001 /****************************************************************************/ 00009 // Dijkstra shortest path algorithm using travel time 00010 /****************************************************************************/ 00011 // SUMO, Simulation of Urban MObility; see http://sumo.sourceforge.net/ 00012 // Copyright (C) 2001-2012 DLR (http://www.dlr.de/) and contributors 00013 /****************************************************************************/ 00014 // 00015 // This file is part of SUMO. 00016 // SUMO is free software: you can redistribute it and/or modify 00017 // it under the terms of the GNU General Public License as published by 00018 // the Free Software Foundation, either version 3 of the License, or 00019 // (at your option) any later version. 00020 // 00021 /****************************************************************************/ 00022 #ifndef DijkstraRouterTT_h 00023 #define DijkstraRouterTT_h 00024 00025 00026 // =========================================================================== 00027 // included modules 00028 // =========================================================================== 00029 #ifdef _MSC_VER 00030 #include <windows_config.h> 00031 #else 00032 #include <config.h> 00033 #endif 00034 00035 #include <string> 00036 #include <functional> 00037 #include <vector> 00038 #include <set> 00039 #include <limits> 00040 #include <algorithm> 00041 #include <iterator> 00042 #include <utils/common/ToString.h> 00043 #include <utils/common/InstancePool.h> 00044 #include <utils/common/MsgHandler.h> 00045 #include <utils/common/StdDefs.h> 00046 #include "SUMOAbstractRouter.h" 00047 00048 //#define DijkstraRouterTT_DEBUG_QUERY 00049 //#define DijkstraRouterTT_DEBUG_QUERY_PERF 00050 00051 // =========================================================================== 00052 // class definitions 00053 // =========================================================================== 00069 template<class E, class V, class PF> 00070 class DijkstraRouterTTBase : public SUMOAbstractRouter<E, V>, public PF { 00071 using SUMOAbstractRouter<E, V>::startQuery; 00072 using SUMOAbstractRouter<E, V>::endQuery; 00073 00074 public: 00076 DijkstraRouterTTBase(size_t noE, bool unbuildIsWarning) : 00077 SUMOAbstractRouter<E, V>("DijkstraRouterTT"), 00078 myErrorMsgHandler(unbuildIsWarning ? MsgHandler::getWarningInstance() : MsgHandler::getErrorInstance()) 00079 { 00080 for (size_t i = 0; i < noE; i++) { 00081 myEdgeInfos.push_back(EdgeInfo(i)); 00082 } 00083 } 00084 00086 virtual ~DijkstraRouterTTBase() { } 00087 00093 class EdgeInfo { 00094 public: 00096 EdgeInfo(size_t id) 00097 : edge(E::dictionary(id)), traveltime(std::numeric_limits<SUMOReal>::max()), prev(0), visited(false) {} 00098 00100 const E* edge; 00101 00103 SUMOReal traveltime; 00104 00106 EdgeInfo* prev; 00107 00109 bool visited; 00110 00111 inline void reset() { 00112 traveltime = std::numeric_limits<SUMOReal>::max(); 00113 visited = false; 00114 } 00115 }; 00116 00121 class EdgeInfoByTTComparator { 00122 public: 00124 bool operator()(const EdgeInfo* nod1, const EdgeInfo* nod2) const { 00125 if (nod1->traveltime == nod2->traveltime) { 00126 return nod1->edge->getNumericalID() > nod2->edge->getNumericalID(); 00127 } 00128 return nod1->traveltime > nod2->traveltime; 00129 } 00130 }; 00131 00132 virtual SUMOReal getEffort(const E* const e, const V* const v, SUMOReal t) const = 0; 00133 00134 00135 void init() { 00136 // all EdgeInfos touched in the previous query are either in myFrontierList or myFound: clean those up 00137 for (typename std::vector<EdgeInfo*>::iterator i = myFrontierList.begin(); i != myFrontierList.end(); i++) { 00138 (*i)->reset(); 00139 } 00140 myFrontierList.clear(); 00141 for (typename std::vector<EdgeInfo*>::iterator i = myFound.begin(); i != myFound.end(); i++) { 00142 (*i)->reset(); 00143 } 00144 myFound.clear(); 00145 } 00146 00147 00150 virtual void compute(const E* from, const E* to, const V* const vehicle, 00151 SUMOTime msTime, std::vector<const E*> &into) { 00152 assert(from != 0 && to != 0); 00153 startQuery(); 00154 const SUMOReal time = STEPS2TIME(msTime); 00155 init(); 00156 // add begin node 00157 EdgeInfo* const fromInfo = &(myEdgeInfos[from->getNumericalID()]); 00158 fromInfo->traveltime = 0; 00159 fromInfo->prev = 0; 00160 myFrontierList.push_back(fromInfo); 00161 // loop 00162 int num_visited = 0; 00163 while (!myFrontierList.empty()) { 00164 num_visited += 1; 00165 // use the node with the minimal length 00166 EdgeInfo* const minimumInfo = myFrontierList.front(); 00167 const E* const minEdge = minimumInfo->edge; 00168 pop_heap(myFrontierList.begin(), myFrontierList.end(), myComparator); 00169 myFrontierList.pop_back(); 00170 myFound.push_back(minimumInfo); 00171 #ifdef DijkstraRouterTT_DEBUG_QUERY 00172 std::cout << "DEBUG: hit '" << minEdge->getID() << "' Q: "; 00173 for (typename std::vector<EdgeInfo*>::iterator it = myFrontierList.begin(); it != myFrontierList.end(); it++) { 00174 std::cout << (*it)->traveltime << "," << (*it)->edge->getID() << " "; 00175 } 00176 std::cout << "\n"; 00177 #endif 00178 // check whether the destination node was already reached 00179 if (minEdge == to) { 00180 buildPathFrom(minimumInfo, into); 00181 endQuery(num_visited); 00182 #ifdef DijkstraRouterTT_DEBUG_QUERY_PERF 00183 std::cout << "visited " + toString(num_visited) + " edges (final path length: " + toString(into.size()) + ")\n"; 00184 #endif 00185 return; 00186 } 00187 minimumInfo->visited = true; 00188 const SUMOReal traveltime = minimumInfo->traveltime + getEffort(minEdge, vehicle, time + minimumInfo->traveltime); 00189 // check all ways from the node with the minimal length 00190 unsigned int i = 0; 00191 const unsigned int length_size = minEdge->getNoFollowing(); 00192 for (i = 0; i < length_size; i++) { 00193 const E* const follower = minEdge->getFollower(i); 00194 EdgeInfo* const followerInfo = &(myEdgeInfos[follower->getNumericalID()]); 00195 // check whether it can be used 00196 if (PF::operator()(follower, vehicle)) { 00197 continue; 00198 } 00199 const SUMOReal oldEffort = followerInfo->traveltime; 00200 if (!followerInfo->visited && traveltime < oldEffort) { 00201 followerInfo->traveltime = traveltime; 00202 followerInfo->prev = minimumInfo; 00203 if (oldEffort == std::numeric_limits<SUMOReal>::max()) { 00204 myFrontierList.push_back(followerInfo); 00205 push_heap(myFrontierList.begin(), myFrontierList.end(), myComparator); 00206 } else { 00207 push_heap(myFrontierList.begin(), 00208 find(myFrontierList.begin(), myFrontierList.end(), followerInfo) + 1, 00209 myComparator); 00210 } 00211 } 00212 } 00213 } 00214 endQuery(num_visited); 00215 #ifdef DijkstraRouterTT_DEBUG_QUERY_PERF 00216 std::cout << "visited " + toString(num_visited) + " edges (final path length: " + toString(into.size()) + ")\n"; 00217 #endif 00218 myErrorMsgHandler->inform("No connection between '" + from->getID() + "' and '" + to->getID() + "' found."); 00219 } 00220 00221 00222 SUMOReal recomputeCosts(const std::vector<const E*> &edges, const V* const v, SUMOTime msTime) const { 00223 const SUMOReal time = STEPS2TIME(msTime); 00224 SUMOReal costs = 0; 00225 for (typename std::vector<const E*>::const_iterator i = edges.begin(); i != edges.end(); ++i) { 00226 if (PF::operator()(*i, v)) { 00227 return -1; 00228 } 00229 costs += getEffort(*i, v, time + costs); 00230 } 00231 return costs; 00232 } 00233 00234 public: 00236 void buildPathFrom(EdgeInfo* rbegin, std::vector<const E*> &edges) { 00237 std::deque<const E*> tmp; 00238 while (rbegin != 0) { 00239 tmp.push_front((E*) rbegin->edge); // !!! 00240 rbegin = rbegin->prev; 00241 } 00242 std::copy(tmp.begin(), tmp.end(), std::back_inserter(edges)); 00243 } 00244 00245 protected: 00247 std::vector<EdgeInfo> myEdgeInfos; 00248 00250 std::vector<EdgeInfo*> myFrontierList; 00252 std::vector<EdgeInfo*> myFound; 00253 00254 EdgeInfoByTTComparator myComparator; 00255 00257 MsgHandler* const myErrorMsgHandler; 00258 }; 00259 00260 00261 template<class E, class V, class PF, class EC> 00262 class DijkstraRouterTT_ByProxi : public DijkstraRouterTTBase<E, V, PF> { 00263 public: 00265 typedef SUMOReal(EC::* Operation)(const E* const, const V* const, SUMOReal) const; 00266 00267 DijkstraRouterTT_ByProxi(size_t noE, bool unbuildIsWarningOnly, EC* receiver, Operation operation) 00268 : DijkstraRouterTTBase<E, V, PF>(noE, unbuildIsWarningOnly), 00269 myReceiver(receiver), myOperation(operation) {} 00270 00271 inline SUMOReal getEffort(const E* const e, const V* const v, SUMOReal t) const { 00272 return (myReceiver->*myOperation)(e, v, t); 00273 } 00274 00275 private: 00277 EC* myReceiver; 00278 00280 Operation myOperation; 00281 00282 00283 }; 00284 00285 00286 template<class E, class V, class PF> 00287 class DijkstraRouterTT_Direct : public DijkstraRouterTTBase<E, V, PF> { 00288 public: 00290 typedef SUMOReal(E::* Operation)(const V* const, SUMOReal) const; 00291 00292 DijkstraRouterTT_Direct(size_t noE, bool unbuildIsWarningOnly, Operation operation) 00293 : DijkstraRouterTTBase<E, V, PF>(noE, unbuildIsWarningOnly), myOperation(operation) {} 00294 00295 inline SUMOReal getEffort(const E* const e, const V* const v, SUMOReal t) const { 00296 return (e->*myOperation)(v, t); 00297 } 00298 00299 private: 00300 Operation myOperation; 00301 00302 }; 00303 00304 00305 #endif 00306 00307 /****************************************************************************/ 00308