TraCIDijkstraRouter.h

Go to the documentation of this file.

/****************************************************************************/
/****************************************************************************/
// SUMO, Simulation of Urban MObility; see http://sumo.sourceforge.net/
// Copyright 2001-2010 DLR (http://www.dlr.de/) and contributors
/****************************************************************************/
//
//   This program is free software; you can redistribute it and/or modify
//   it under the terms of the GNU General Public License as published by
//   the Free Software Foundation; either version 2 of the License, or
//   (at your option) any later version.
//
/****************************************************************************/
#ifndef TRACIDIJKSTRAROUTER_H
#define TRACIDIJKSTRAROUTER_H


// ===========================================================================
// included modules
// ===========================================================================
#ifdef _MSC_VER
#include <windows_config.h>
#else
#include <config.h>
#endif

#ifndef NO_TRACI

#include "utils/common/DijkstraRouterTT.h"
#include <microsim/MSLane.h>
#include <microsim/MSEdgeWeightsStorage.h>


// ===========================================================================
// class definitions
// ===========================================================================
template<class E>
class TraCIDijkstraRouter : public SUMOAbstractRouter<E, MSVehicle> {
public:
    TraCIDijkstraRouter(size_t noE/*, bool unbuildIsWarningOnly*/)
            : myNoE(noE), myReusableEdgeLists(true), myReusableEdgeInfoLists(true) { }

    virtual ~TraCIDijkstraRouter() { }

    class EdgeInfo {
    public:
        EdgeInfo()
                : edge(0), effort(0), prev(0) {}


        EdgeInfo(const E *edgeArg, SUMOReal effortArg, EdgeInfo *prevArg)
                : edge(edgeArg), effort(effortArg), prev(prevArg) {}

        EdgeInfo(const E *edgeArg, SUMOReal effortArg, EdgeInfo *prevArg, SUMOReal distArg)
                : edge(edgeArg), effort(effortArg), prev(prevArg), dist(distArg) {}

        const E *edge;

        SUMOReal effort;

        EdgeInfo *prev;

        SUMOReal dist;

    };

    class EdgeInfoByEffortComperator {
    public:
        explicit EdgeInfoByEffortComperator() { }

        ~EdgeInfoByEffortComperator() { }

        bool operator()(EdgeInfo *nod1, EdgeInfo *nod2) const {
            return nod1->effort>nod2->effort;
        }
    };

    virtual SUMOReal getEffort(const E * const e, SUMOReal t) {
        SUMOReal value;
        if (MSNet::getInstance()->getWeightsStorage().retrieveExistingEffort(e, 0, t, value)) {
            return value;
        }
        const MSLane * const l = e->getLanes()[0];
        return l->getLength() / l->getMaxSpeed();
    }


    virtual void compute(const E *from, const E *to, const MSVehicle * const vehicle,
                         SUMOTime time, std::vector<const E*> &into) {

        // get structures to reuse
        std::vector<bool> *visited = myReusableEdgeLists.getFreeInstance();
        if (visited==0) {
            visited = new std::vector<bool>(myNoE, false);
        } else {
            for (size_t i=0; i<myNoE; i++) {
                (*visited)[i] = false; // too slow? !!!
            }
        }
        EdgeInfoCont *storage = myReusableEdgeInfoLists.getFreeInstance();
        if (storage==0) {
            storage = new EdgeInfoCont(myNoE);
        }
        storage->reset();

        // check the nodes
        if (from==0||to==0) {
            throw std::exception();
        }

        // begin computation
        std::priority_queue<EdgeInfo*,
        std::vector<EdgeInfo*>,
        EdgeInfoByEffortComperator> frontierList;
        // add begin node
        const E *actualKnot = from;
        if (from != 0) {
            EdgeInfo *ei = storage->add(actualKnot, 0, 0);
            frontierList.push(ei);
        }
        bool isFirstIteration = true;

        // loop
        while (!frontierList.empty()) {
            // use the node with the minimal length
            EdgeInfo *minimumKnot = frontierList.top();
            const E *minEdge = minimumKnot->edge;
            frontierList.pop();
            // check whether the destination node was already reached
            if ((minEdge == to) && (!isFirstIteration)) {
                buildPathFrom(minimumKnot, into);
                clearTemporaryStorages(visited, storage);
                return;
            }
            (*visited)[minEdge->getNumericalID()] = true;
            SUMOReal effort = (SUMOReal)(minimumKnot->effort + getEffort(minEdge, time + minimumKnot->effort));
            // check all ways from the node with the minimal length
            unsigned int i = 0;
            unsigned int length_size = minEdge->getNoFollowing();
            for (i=0; i<length_size; i++) {
                const E* help = minEdge->getFollower(i);

                if ((!(*visited)[help->getNumericalID()] && effort < storage->getEffort(help))
                        || (help == to)) {
//                    if (help!=from) {
                    frontierList.push(storage->add(help, effort, minimumKnot));
//                    }
                }
            }

            isFirstIteration = false;
        }
        clearTemporaryStorages(visited, storage);
    }


    SUMOReal recomputeCosts(const std::vector<const E*> &edges, const MSVehicle * const v, SUMOTime time) throw() {
        SUMOReal costs = 0;
        for (typename std::vector<const E*>::const_iterator i=edges.begin(); i!=edges.end(); i++) {
            costs += getEffort(*i, (SUMOTime)(time + costs));
        }
        return costs;
    }

public:
    void buildPathFrom(EdgeInfo *rbegin, std::vector<const E *> &edges) {
        std::deque<const E*> tmp;
        EdgeInfo* last = rbegin;
        while (rbegin!=0) {
            tmp.push_front((E *) rbegin->edge); // !!!
            rbegin = rbegin->prev;
            if (rbegin == last) {
                tmp.push_front((E *) rbegin->edge);
                break;
            }
        }
        std::copy(tmp.begin(), tmp.end(), std::back_inserter(edges));
    }

public:
    class EdgeInfoCont {
    public:
        EdgeInfoCont(size_t toAlloc)
                : myEdgeInfos(toAlloc+1, EdgeInfo()) { }

        ~EdgeInfoCont() { }

        EdgeInfo *add(const E *edgeArg, SUMOReal effortArg, EdgeInfo *prevArg) {
            EdgeInfo *ret = &(myEdgeInfos[edgeArg->getNumericalID()]);
            ret->edge = edgeArg; // !!! may be set within the constructor
            ret->effort = effortArg;
            ret->prev = prevArg;
            ret->dist = 0;
            return ret;
        }

        EdgeInfo *add(const E *edgeArg, SUMOReal effortArg, EdgeInfo *prevArg,
                      SUMOReal distArg) {
            EdgeInfo *ret = &(myEdgeInfos[edgeArg->getNumericalID()]);
            ret->edge = edgeArg; // !!! may be set within the constructor
            ret->effort = effortArg;
            ret->prev = prevArg;
            ret->dist = distArg;
            return ret;
        }

        void reset() {
            for (typename std::vector<EdgeInfo>::iterator i=myEdgeInfos.begin(); i!=myEdgeInfos.end(); i++) {
                (*i).effort = std::numeric_limits<SUMOReal>::max();
            }
        }


        SUMOReal getEffort(const E *to) const {
            return myEdgeInfos[to->getNumericalID()].effort;
        }

    private:
        std::vector<EdgeInfo> myEdgeInfos;

    };

protected:
    void clearTemporaryStorages(std::vector<bool> *edgeList,
                                EdgeInfoCont *consecutionList) {
        myReusableEdgeLists.addFreeInstance(edgeList);
        myReusableEdgeInfoLists.addFreeInstance(consecutionList);
    }


protected:
    size_t myNoE;

    InstancePool<std::vector<bool> > myReusableEdgeLists;

    InstancePool<EdgeInfoCont> myReusableEdgeInfoLists;
};

#endif

#endif