SUMO - Simulation of Urban MObility
TraCIDijkstraRouter.h
Go to the documentation of this file.
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 
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Friends Defines