DijkstraRouterEffortBase< E, V, PF > Class Template Reference

#include <DijkstraRouterEffort.h>

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

Detailed Description

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

Definition at line 63 of file DijkstraRouterEffort.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.
	DijkstraRouterEffortBase (size_t noE, bool unbuildIsWarningOnly)
	Constructor.
virtual SUMOReal	getEffort (const E const e, const V const v, SUMOReal t)=0
virtual SUMOReal	getTravelTime (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	~DijkstraRouterEffortBase ()
	Destructor.
Protected Attributes
EdgeInfoByEffortComparator	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	EdgeInfoByEffortComparator

Constructor & Destructor Documentation

template<class E, class V, class PF>

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

Constructor.

Definition at line 66 of file DijkstraRouterEffort.h.

References DijkstraRouterEffortBase< 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 DijkstraRouterEffortBase< E, V, PF >::~DijkstraRouterEffortBase ( ) [inline, virtual]

Destructor.

Definition at line 74 of file DijkstraRouterEffort.h.

00074 { }

Member Function Documentation

template<class E, class V, class PF>

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

Builds the path from marked edges.

Definition at line 209 of file DijkstraRouterEffort.h.

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

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

00209                                                                       {
00210         std::deque<const E*> tmp;
00211         while (rbegin!=0) {
00212             tmp.push_front((E *) rbegin->edge); // !!!
00213             rbegin = rbegin->prev;
00214         }
00215         std::copy(tmp.begin(), tmp.end(), std::back_inserter(edges));
00216     }

template<class E, class V, class PF>

virtual void DijkstraRouterEffortBase< 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 128 of file DijkstraRouterEffort.h.

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

template<class E, class V, class PF>

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

Implemented in DijkstraRouterEffort_ByProxi< E, V, PF, EC >, and DijkstraRouterEffort_Direct< E, V, PF >.

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

template<class E, class V, class PF>

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

Implemented in DijkstraRouterEffort_ByProxi< E, V, PF, EC >, and DijkstraRouterEffort_Direct< E, V, PF >.

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

template<class E, class V, class PF>

SUMOReal DijkstraRouterEffortBase< 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 193 of file DijkstraRouterEffort.h.

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

00193                                                                                                           {
00194         SUMOReal time = (SUMOReal) msTime / 1000.;
00195         SUMOReal costs = 0;
00196         SUMOReal t = (SUMOReal) time;
00197         for (typename std::vector<const E*>::const_iterator i=edges.begin(); i!=edges.end(); ++i) {
00198             if (PF::operator()(*i, v)) {
00199                 return -1;
00200             }
00201             costs += getEffort(*i, v, (SUMOTime) t);
00202             t += getTravelTime(*i, v, (SUMOTime) t);
00203         }
00204         return costs;
00205     }