SUMO - Simulation of Urban MObility
|
00001 /****************************************************************************/ 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 TRACIDIJKSTRAROUTER_H 00023 #define TRACIDIJKSTRAROUTER_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 #ifndef NO_TRACI 00036 00037 #include "utils/common/DijkstraRouterTT.h" 00038 #include <microsim/MSLane.h> 00039 #include <microsim/MSEdgeWeightsStorage.h> 00040 00041 00042 // =========================================================================== 00043 // class definitions 00044 // =========================================================================== 00061 template<class E> 00062 class TraCIDijkstraRouter : public SUMOAbstractRouter<E, MSVehicle> { 00063 public: 00065 TraCIDijkstraRouter(size_t noE/*, bool unbuildIsWarningOnly*/) : 00066 SUMOAbstractRouter<E, MSVehicle>("TraciDijkstraRouter"), 00067 myNoE(noE), myReusableEdgeLists(true), myReusableEdgeInfoLists(true) { } 00068 00070 virtual ~TraCIDijkstraRouter() { } 00071 00077 class EdgeInfo { 00078 public: 00080 EdgeInfo() 00081 : edge(0), effort(0), prev(0) {} 00082 00083 00085 EdgeInfo(const E* edgeArg, SUMOReal effortArg, EdgeInfo* prevArg) 00086 : edge(edgeArg), effort(effortArg), prev(prevArg) {} 00087 00089 EdgeInfo(const E* edgeArg, SUMOReal effortArg, EdgeInfo* prevArg, SUMOReal distArg) 00090 : edge(edgeArg), effort(effortArg), prev(prevArg), dist(distArg) {} 00091 00093 const E* edge; 00094 00096 SUMOReal effort; 00097 00099 EdgeInfo* prev; 00100 00102 SUMOReal dist; 00103 00104 }; 00105 00110 class EdgeInfoByEffortComperator { 00111 public: 00113 explicit EdgeInfoByEffortComperator() { } 00114 00116 ~EdgeInfoByEffortComperator() { } 00117 00119 bool operator()(EdgeInfo* nod1, EdgeInfo* nod2) const { 00120 return nod1->effort > nod2->effort; 00121 } 00122 }; 00123 00124 virtual SUMOReal getEffort(const E* const e, SUMOReal t) const { 00125 SUMOReal value; 00126 if (MSNet::getInstance()->getWeightsStorage().retrieveExistingEffort(e, 0, t, value)) { 00127 return value; 00128 } 00129 const MSLane* const l = e->getLanes()[0]; 00130 return l->getLength() / l->getMaxSpeed(); 00131 } 00132 00133 00136 virtual void compute(const E* from, const E* to, const MSVehicle* const vehicle, 00137 SUMOTime msTime, std::vector<const E*> &into) { 00138 UNUSED_PARAMETER(vehicle); 00139 const SUMOReal time = STEPS2TIME(msTime); 00140 // get structures to reuse 00141 std::vector<bool> *visited = myReusableEdgeLists.getFreeInstance(); 00142 if (visited == 0) { 00143 visited = new std::vector<bool>(myNoE, false); 00144 } else { 00145 for (size_t i = 0; i < myNoE; i++) { 00146 (*visited)[i] = false; // too slow? !!! 00147 } 00148 } 00149 EdgeInfoCont* storage = myReusableEdgeInfoLists.getFreeInstance(); 00150 if (storage == 0) { 00151 storage = new EdgeInfoCont(myNoE); 00152 } 00153 storage->reset(); 00154 00155 // check the nodes 00156 if (from == 0 || to == 0) { 00157 throw std::exception(); 00158 } 00159 00160 // begin computation 00161 std::priority_queue < EdgeInfo*, 00162 std::vector<EdgeInfo*>, 00163 EdgeInfoByEffortComperator > frontierList; 00164 // add begin node 00165 const E* actualKnot = from; 00166 if (from != 0) { 00167 EdgeInfo* ei = storage->add(actualKnot, 0, 0); 00168 frontierList.push(ei); 00169 } 00170 bool isFirstIteration = true; 00171 00172 // loop 00173 while (!frontierList.empty()) { 00174 // use the node with the minimal length 00175 EdgeInfo* minimumKnot = frontierList.top(); 00176 const E* minEdge = minimumKnot->edge; 00177 frontierList.pop(); 00178 // check whether the destination node was already reached 00179 if ((minEdge == to) && (!isFirstIteration)) { 00180 buildPathFrom(minimumKnot, into); 00181 clearTemporaryStorages(visited, storage); 00182 return; 00183 } 00184 (*visited)[minEdge->getNumericalID()] = true; 00185 const SUMOReal effort = (SUMOReal)(minimumKnot->effort + getEffort(minEdge, time + minimumKnot->effort)); 00186 // check all ways from the node with the minimal length 00187 unsigned int i = 0; 00188 const unsigned int length_size = minEdge->getNoFollowing(); 00189 for (i = 0; i < length_size; i++) { 00190 const E* help = minEdge->getFollower(i); 00191 00192 if ((!(*visited)[help->getNumericalID()] && effort < storage->getEffort(help)) 00193 || (help == to)) { 00194 // if (help!=from) { 00195 frontierList.push(storage->add(help, effort, minimumKnot)); 00196 // } 00197 } 00198 } 00199 00200 isFirstIteration = false; 00201 } 00202 clearTemporaryStorages(visited, storage); 00203 } 00204 00205 00206 SUMOReal recomputeCosts(const std::vector<const E*> &edges, const MSVehicle* const v, SUMOTime msTime) const { 00207 UNUSED_PARAMETER(v); 00208 const SUMOReal time = STEPS2TIME(msTime); 00209 SUMOReal costs = 0; 00210 for (typename std::vector<const E*>::const_iterator i = edges.begin(); i != edges.end(); i++) { 00211 costs += getEffort(*i, time + costs); 00212 } 00213 return costs; 00214 } 00215 00216 public: 00218 void buildPathFrom(EdgeInfo* rbegin, std::vector<const E*> &edges) { 00219 std::deque<const E*> tmp; 00220 EdgeInfo* last = rbegin; 00221 while (rbegin != 0) { 00222 tmp.push_front((E*) rbegin->edge); // !!! 00223 rbegin = rbegin->prev; 00224 if (rbegin == last) { 00225 tmp.push_front((E*) rbegin->edge); 00226 break; 00227 } 00228 } 00229 std::copy(tmp.begin(), tmp.end(), std::back_inserter(edges)); 00230 } 00231 00232 public: 00240 class EdgeInfoCont { 00241 public: 00243 EdgeInfoCont(size_t toAlloc) 00244 : myEdgeInfos(toAlloc + 1, EdgeInfo()) { } 00245 00247 ~EdgeInfoCont() { } 00248 00250 EdgeInfo* add(const E* edgeArg, SUMOReal effortArg, EdgeInfo* prevArg) { 00251 EdgeInfo* ret = &(myEdgeInfos[edgeArg->getNumericalID()]); 00252 ret->edge = edgeArg; // !!! may be set within the constructor 00253 ret->effort = effortArg; 00254 ret->prev = prevArg; 00255 ret->dist = 0; 00256 return ret; 00257 } 00258 00260 EdgeInfo* add(const E* edgeArg, SUMOReal effortArg, EdgeInfo* prevArg, 00261 SUMOReal distArg) { 00262 EdgeInfo* ret = &(myEdgeInfos[edgeArg->getNumericalID()]); 00263 ret->edge = edgeArg; // !!! may be set within the constructor 00264 ret->effort = effortArg; 00265 ret->prev = prevArg; 00266 ret->dist = distArg; 00267 return ret; 00268 } 00269 00271 void reset() { 00272 for (typename std::vector<EdgeInfo>::iterator i = myEdgeInfos.begin(); i != myEdgeInfos.end(); i++) { 00273 (*i).effort = std::numeric_limits<SUMOReal>::max(); 00274 } 00275 } 00276 00277 00280 SUMOReal getEffort(const E* to) const { 00281 return myEdgeInfos[to->getNumericalID()].effort; 00282 } 00283 00284 private: 00286 std::vector<EdgeInfo> myEdgeInfos; 00287 00288 }; 00289 00290 protected: 00292 void clearTemporaryStorages(std::vector<bool> *edgeList, 00293 EdgeInfoCont* consecutionList) { 00294 myReusableEdgeLists.addFreeInstance(edgeList); 00295 myReusableEdgeInfoLists.addFreeInstance(consecutionList); 00296 } 00297 00298 00299 protected: 00301 size_t myNoE; 00302 00304 InstancePool<std::vector<bool> > myReusableEdgeLists; 00305 00307 InstancePool<EdgeInfoCont> myReusableEdgeInfoLists; 00308 }; 00309 00310 #endif 00311 00312 #endif 00313