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