DijkstraRouterTTBase< E, V, PF > Class Template Reference

#include <DijkstraRouterTT.h>

Inheritance diagram for DijkstraRouterTTBase< E, V, PF >:

Detailed Description

template<class E, class V, class PF>
class DijkstraRouterTTBase< E, V, PF >

Definition at line 63 of file DijkstraRouterTT.h.


Public Member Functions
void	buildPathFrom (EdgeInfo rbegin, std::vector< const E > &edges)
	Builds the path from marked edges.
virtual void	compute (const E from, const E to, const V const vehicle, SUMOTime msTime, std::vector< const E > &into)
	Builds the route between the given edges using the minimum afford at the given time The definition of the afford depends on the wished routing scheme.
	DijkstraRouterTTBase (size_t noE, bool unbuildIsWarningOnly)
	Constructor.
virtual SUMOReal	getEffort (const E const e, const V const v, SUMOReal t)=0
SUMOReal	recomputeCosts (const std::vector< const E * > &edges, const V *const v, SUMOTime msTime) throw ()
virtual	~DijkstraRouterTTBase ()
	Destructor.
Protected Attributes
EdgeInfoByTTComparator	myComparator
std::vector< EdgeInfo >	myEdgeInfos
	The container of edge information.
std::vector< EdgeInfo * >	myFrontierList
	A container for reusage of the min edge heap.
bool	myUnbuildIsWarningOnly
Data Structures
struct	EdgeInfo
class	EdgeInfoByTTComparator

Constructor & Destructor Documentation

template<class E, class V, class PF>

DijkstraRouterTTBase< E, V, PF >::DijkstraRouterTTBase	(	size_t	noE,
		bool	unbuildIsWarningOnly
	)			`[inline]`

Constructor.

Definition at line 66 of file DijkstraRouterTT.h.

References DijkstraRouterTTBase< E, V, PF >::myEdgeInfos.

00067             : myUnbuildIsWarningOnly(unbuildIsWarningOnly) {
00068         for (size_t i = 0; i < noE; i++) {
00069             myEdgeInfos.push_back(EdgeInfo(i));
00070         }
00071     }

template<class E, class V, class PF>

virtual DijkstraRouterTTBase< E, V, PF >::~DijkstraRouterTTBase ( ) [inline, virtual]

Destructor.

Definition at line 74 of file DijkstraRouterTT.h.

00074 { }

Member Function Documentation

template<class E, class V, class PF>

void DijkstraRouterTTBase< E, V, PF >::buildPathFrom	(	EdgeInfo *	rbegin,
		std::vector< const E * > &	edges
	)			`[inline]`

Builds the path from marked edges.

Definition at line 197 of file DijkstraRouterTT.h.

References DijkstraRouterTTBase< E, V, PF >::EdgeInfo::edge, and DijkstraRouterTTBase< E, V, PF >::EdgeInfo::prev.

Referenced by DijkstraRouterTTBase< E, V, PF >::compute().

00197                                                                       {
00198         std::deque<const E*> tmp;
00199         while (rbegin!=0) {
00200             tmp.push_front((E *) rbegin->edge); // !!!
00201             rbegin = rbegin->prev;
00202         }
00203         std::copy(tmp.begin(), tmp.end(), std::back_inserter(edges));
00204     }

template<class E, class V, class PF>

virtual void DijkstraRouterTTBase< E, V, PF >::compute	(	const E *	from,
		const E *	to,
		const V *const	vehicle,
		SUMOTime	msTime,
		std::vector< const E * > &	into
	)			`[inline, virtual]`

Builds the route between the given edges using the minimum afford at the given time The definition of the afford depends on the wished routing scheme.

Implements SUMOAbstractRouter< E, V >.

Definition at line 121 of file DijkstraRouterTT.h.

Referenced by TraCIServerAPI_Vehicle::processSet(), and MSTriggeredRerouter::reroute().

00122                                                                      {
00123 
00124         SUMOReal time = (SUMOReal) msTime / 1000.;
00125         for (typename std::vector<EdgeInfo>::iterator i=myEdgeInfos.begin(); i!=myEdgeInfos.end(); i++) {
00126             (*i).traveltime = std::numeric_limits<SUMOReal>::max();
00127             (*i).visited = false;
00128         }
00129         assert(from!=0&&to!=0);
00130         myFrontierList.clear();
00131         // add begin node
00132         EdgeInfo* const fromInfo = &(myEdgeInfos[from->getNumericalID()]);
00133         fromInfo->traveltime = 0;
00134         fromInfo->prev = 0;
00135         myFrontierList.push_back(fromInfo);
00136         // loop
00137         while (!myFrontierList.empty()) {
00138             // use the node with the minimal length
00139             EdgeInfo * const minimumInfo = myFrontierList.front();
00140             const E * const minEdge = minimumInfo->edge;
00141             pop_heap(myFrontierList.begin(), myFrontierList.end(), myComparator);
00142             myFrontierList.pop_back();
00143             // check whether the destination node was already reached
00144             if (minEdge == to) {
00145                 buildPathFrom(minimumInfo, into);
00146                 return;
00147             }
00148             minimumInfo->visited = true;
00149             const SUMOReal traveltime = minimumInfo->traveltime + getEffort(minEdge, vehicle, time + (SUMOTime)minimumInfo->traveltime);
00150             // check all ways from the node with the minimal length
00151             unsigned int i = 0;
00152             const unsigned int length_size = minEdge->getNoFollowing();
00153             for (i=0; i<length_size; i++) {
00154                 const E* const follower = minEdge->getFollower(i);
00155                 EdgeInfo* const followerInfo = &(myEdgeInfos[follower->getNumericalID()]);
00156                 // check whether it can be used
00157                 if (PF::operator()(follower, vehicle)) {
00158                     continue;
00159                 }
00160                 const SUMOReal oldEffort = followerInfo->traveltime;
00161                 if (!followerInfo->visited && traveltime < oldEffort) {
00162                     followerInfo->traveltime = traveltime;
00163                     followerInfo->prev = minimumInfo;
00164                     if (oldEffort == std::numeric_limits<SUMOReal>::max()) {
00165                         myFrontierList.push_back(followerInfo);
00166                         push_heap(myFrontierList.begin(), myFrontierList.end(), myComparator);
00167                     } else {
00168                         push_heap(myFrontierList.begin(),
00169                                   find(myFrontierList.begin(), myFrontierList.end(), followerInfo) + 1,
00170                                   myComparator);
00171                     }
00172                 }
00173             }
00174         }
00175         if (!myUnbuildIsWarningOnly) {
00176             MsgHandler::getErrorInstance()->inform("No connection between '" + from->getID() + "' and '" + to->getID() + "' found.");
00177         } else {
00178             WRITE_WARNING("No connection between '" + from->getID() + "' and '" + to->getID() + "' found.");
00179         }
00180     }

template<class E, class V, class PF>

virtual SUMOReal DijkstraRouterTTBase< E, V, PF >::getEffort	(	const E *const	e,
		const V *const	v,
		SUMOReal	t
	)			`[pure virtual]`

Implemented in DijkstraRouterTT_ByProxi< E, V, PF, EC >, and DijkstraRouterTT_Direct< E, V, PF >.

Referenced by DijkstraRouterTTBase< E, V, PF >::compute(), and DijkstraRouterTTBase< E, V, PF >::recomputeCosts().

template<class E, class V, class PF>

SUMOReal DijkstraRouterTTBase< E, V, PF >::recomputeCosts	(	const std::vector< const E * > &	edges,
		const V *const	v,
		SUMOTime	msTime
	)			throw () `[inline, virtual]`

Implements SUMOAbstractRouter< E, V >.

Definition at line 183 of file DijkstraRouterTT.h.

References DijkstraRouterTTBase< E, V, PF >::getEffort(), and SUMOReal.

00183                                                                                                           {
00184         SUMOReal time = (SUMOReal) msTime / 1000.;
00185         SUMOReal costs = 0;
00186         for (typename std::vector<const E*>::const_iterator i=edges.begin(); i!=edges.end(); ++i) {
00187             if (PF::operator()(*i, v)) {
00188                 return -1;
00189             }
00190             costs += getEffort(*i, v, (SUMOTime)(time + costs));
00191         }
00192         return costs;
00193     }