TraCIDijkstraRouter.h

Go to the documentation of this file.

/****************************************************************************/
/****************************************************************************/
// SUMO, Simulation of Urban MObility; see http://sumo.sourceforge.net/
// Copyright (C) 2001-2012 DLR (http://www.dlr.de/) and contributors
/****************************************************************************/
//
//   This file is part of SUMO.
//   SUMO 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 3 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) const {
        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 msTime, std::vector<const E*> &into) {
        UNUSED_PARAMETER(vehicle);
        const SUMOReal time = STEPS2TIME(msTime);
        // 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;
            const SUMOReal effort = (SUMOReal)(minimumKnot->effort + getEffort(minEdge, time + minimumKnot->effort));
            // check all ways from the node with the minimal length
            unsigned int i = 0;
            const 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 msTime) const {
        UNUSED_PARAMETER(v);
        const SUMOReal time = STEPS2TIME(msTime);
        SUMOReal costs = 0;
        for (typename std::vector<const E*>::const_iterator i = edges.begin(); i != edges.end(); i++) {
            costs += getEffort(*i, 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