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