SUMO - Simulation of Urban MObility
|
00001 /****************************************************************************/ 00009 // Dijkstra shortest path algorithm using other values 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 DijkstraRouterEffort_h 00023 #define DijkstraRouterEffort_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 <utils/common/InstancePool.h> 00042 #include <utils/common/MsgHandler.h> 00043 #include <utils/common/StdDefs.h> 00044 #include "SUMOAbstractRouter.h" 00045 00046 00047 // =========================================================================== 00048 // class definitions 00049 // =========================================================================== 00065 template<class E, class V, class PF> 00066 class DijkstraRouterEffortBase : public SUMOAbstractRouter<E, V>, public PF { 00067 using SUMOAbstractRouter<E, V>::startQuery; 00068 using SUMOAbstractRouter<E, V>::endQuery; 00069 00070 public: 00072 DijkstraRouterEffortBase(size_t noE, bool unbuildIsWarning) : 00073 SUMOAbstractRouter<E, V>("DijkstraRouterEffort"), 00074 myErrorMsgHandler(unbuildIsWarning ? MsgHandler::getWarningInstance() : MsgHandler::getErrorInstance()) 00075 { 00076 for (size_t i = 0; i < noE; i++) { 00077 myEdgeInfos.push_back(EdgeInfo(i)); 00078 } 00079 } 00080 00082 virtual ~DijkstraRouterEffortBase() { } 00083 00089 class EdgeInfo { 00090 public: 00092 EdgeInfo(size_t id) 00093 : edge(E::dictionary(id)), effort(std::numeric_limits<SUMOReal>::max()), leaveTime(0), prev(0), visited(false) {} 00094 00096 const E* edge; 00097 00099 SUMOReal effort; 00100 00102 SUMOReal leaveTime; 00103 00105 EdgeInfo* prev; 00106 00108 bool visited; 00109 00110 inline void reset() { 00111 effort = std::numeric_limits<SUMOReal>::max(); 00112 visited = false; 00113 } 00114 }; 00115 00120 class EdgeInfoByEffortComparator { 00121 public: 00123 bool operator()(EdgeInfo* nod1, EdgeInfo* nod2) const { 00124 if (nod1->effort == nod2->effort) { 00125 return nod1->edge->getNumericalID() > nod2->edge->getNumericalID(); 00126 } 00127 return nod1->effort > nod2->effort; 00128 } 00129 }; 00130 00131 virtual SUMOReal getEffort(const E* const e, const V* const v, SUMOReal t) const = 0; 00132 virtual SUMOReal getTravelTime(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 init(); 00155 // add begin node 00156 EdgeInfo* const fromInfo = &(myEdgeInfos[from->getNumericalID()]); 00157 fromInfo->effort = 0; 00158 fromInfo->prev = 0; 00159 fromInfo->leaveTime = STEPS2TIME(msTime); 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 // check whether the destination node was already reached 00172 if (minEdge == to) { 00173 buildPathFrom(minimumInfo, into); 00174 endQuery(num_visited); 00175 return; 00176 } 00177 minimumInfo->visited = true; 00178 const SUMOReal effort = minimumInfo->effort + getEffort(minEdge, vehicle, minimumInfo->leaveTime); 00179 const SUMOReal leaveTime = minimumInfo->leaveTime + getTravelTime(minEdge, vehicle, minimumInfo->leaveTime); 00180 // check all ways from the node with the minimal length 00181 unsigned int i = 0; 00182 const unsigned int length_size = minEdge->getNoFollowing(); 00183 for (i = 0; i < length_size; i++) { 00184 const E* const follower = minEdge->getFollower(i); 00185 EdgeInfo* const followerInfo = &(myEdgeInfos[follower->getNumericalID()]); 00186 // check whether it can be used 00187 if (PF::operator()(follower, vehicle)) { 00188 continue; 00189 } 00190 const SUMOReal oldEffort = followerInfo->effort; 00191 if (!followerInfo->visited && effort < oldEffort) { 00192 followerInfo->effort = effort; 00193 followerInfo->leaveTime = leaveTime; 00194 followerInfo->prev = minimumInfo; 00195 if (oldEffort == std::numeric_limits<SUMOReal>::max()) { 00196 myFrontierList.push_back(followerInfo); 00197 push_heap(myFrontierList.begin(), myFrontierList.end(), myComparator); 00198 } else { 00199 push_heap(myFrontierList.begin(), 00200 find(myFrontierList.begin(), myFrontierList.end(), followerInfo) + 1, 00201 myComparator); 00202 } 00203 } 00204 } 00205 } 00206 endQuery(num_visited); 00207 myErrorMsgHandler->inform("No connection between '" + from->getID() + "' and '" + to->getID() + "' found."); 00208 } 00209 00210 00211 SUMOReal recomputeCosts(const std::vector<const E*> &edges, const V* const v, SUMOTime msTime) const { 00212 SUMOReal costs = 0; 00213 SUMOReal t = STEPS2TIME(msTime); 00214 for (typename std::vector<const E*>::const_iterator i = edges.begin(); i != edges.end(); ++i) { 00215 if (PF::operator()(*i, v)) { 00216 return -1; 00217 } 00218 costs += getEffort(*i, v, t); 00219 t += getTravelTime(*i, v, t); 00220 } 00221 return costs; 00222 } 00223 00224 public: 00226 void buildPathFrom(EdgeInfo* rbegin, std::vector<const E*> &edges) { 00227 std::deque<const E*> tmp; 00228 while (rbegin != 0) { 00229 tmp.push_front((E*) rbegin->edge); // !!! 00230 rbegin = rbegin->prev; 00231 } 00232 std::copy(tmp.begin(), tmp.end(), std::back_inserter(edges)); 00233 } 00234 00235 protected: 00237 std::vector<EdgeInfo> myEdgeInfos; 00238 00240 std::vector<EdgeInfo*> myFrontierList; 00242 std::vector<EdgeInfo*> myFound; 00243 00244 EdgeInfoByEffortComparator myComparator; 00245 00247 MsgHandler* const myErrorMsgHandler; 00248 00249 }; 00250 00251 00252 template<class E, class V, class PF, class EC> 00253 class DijkstraRouterEffort_ByProxi : public DijkstraRouterEffortBase<E, V, PF> { 00254 public: 00256 typedef SUMOReal(EC::* Operation)(const E* const, const V* const, SUMOReal) const; 00257 00258 DijkstraRouterEffort_ByProxi(size_t noE, bool unbuildIsWarningOnly, EC* receiver, Operation effortOperation, Operation ttOperation) 00259 : DijkstraRouterEffortBase<E, V, PF>(noE, unbuildIsWarningOnly), 00260 myReceiver(receiver), myEffortOperation(effortOperation), myTTOperation(ttOperation) {} 00261 00262 inline SUMOReal getEffort(const E* const e, const V* const v, SUMOReal t) const { 00263 return (myReceiver->*myEffortOperation)(e, v, t); 00264 } 00265 00266 inline SUMOReal getTravelTime(const E* const e, const V* const v, SUMOReal t) const { 00267 return (myReceiver->*myTTOperation)(e, v, t); 00268 } 00269 00270 private: 00272 EC* myReceiver; 00273 00275 Operation myEffortOperation; 00276 00278 Operation myTTOperation; 00279 00280 }; 00281 00282 00283 template<class E, class V, class PF> 00284 class DijkstraRouterEffort_Direct : public DijkstraRouterEffortBase<E, V, PF> { 00285 public: 00287 typedef SUMOReal(E::* Operation)(const V* const, SUMOReal) const; 00288 00289 DijkstraRouterEffort_Direct(size_t noE, bool unbuildIsWarningOnly, Operation effortOperation, Operation ttOperation) 00290 : DijkstraRouterEffortBase<E, V, PF>(noE, unbuildIsWarningOnly), 00291 myEffortOperation(effortOperation), myTTOperation(ttOperation) {} 00292 00293 inline SUMOReal getEffort(const E* const e, const V* const v, SUMOReal t) const { 00294 return (e->*myEffortOperation)(v, t); 00295 } 00296 00297 inline SUMOReal getTravelTime(const E* const e, const V* const v, SUMOReal t) const { 00298 return (e->*myTTOperation)(v, t); 00299 } 00300 00301 private: 00303 Operation myEffortOperation; 00304 00306 Operation myTTOperation; 00307 00308 00309 }; 00310 00311 00312 #endif 00313 00314 /****************************************************************************/ 00315