TraCIDijkstraRouter< E > Class Template Reference

#include <TraCIDijkstraRouter.h>

Inheritance diagram for TraCIDijkstraRouter< E >:

Detailed Description

template<class E>
class TraCIDijkstraRouter< E >

Computes the shortest path through a network using the dijkstra algorithm.

The template parameters are:

Parameters:

E

The edge class to use (MSEdge/ROEdge)

This router is basically the same as the SUMODijkstraRouter, except for the following: If start and destination edge are the same, the computed route does not consist of just the starting edge. Instead, if there is a path from the starting edge through the network back to itself, the route will consist of this path, containing the same edge both at the beginning and at the end. Furthermore, no vehicle is regarded to determine the efforts of the edges, therefore no prohibition function is used.

Definition at line 59 of file TraCIDijkstraRouter.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 MSVehicle const vehicle, SUMOTime time, std::vector< const E > &into)
	Builds the route between the given edges using the minimum effort at the given time The definition of the effort depends on the wished routing scheme.
virtual SUMOReal	getEffort (const E *const e, SUMOReal t)
SUMOReal	recomputeCosts (const std::vector< const E * > &edges, const MSVehicle *const v, SUMOTime time) throw ()
	TraCIDijkstraRouter (size_t noE)
	Constructor.
virtual	~TraCIDijkstraRouter ()
	Destructor.
Protected Member Functions
void	clearTemporaryStorages (std::vector< bool > edgeList, EdgeInfoCont consecutionList)
	Saves the temporary storages for further usage.
Protected Attributes
size_t	myNoE
	The network to use.
InstancePool< EdgeInfoCont >	myReusableEdgeInfoLists
	A container for reusage of edge consecution lists.
InstancePool< std::vector< bool > >	myReusableEdgeLists
	A container for reusage of examined edges lists.
Data Structures
struct	EdgeInfo
class	EdgeInfoByEffortComperator
class	EdgeInfoCont

Constructor & Destructor Documentation

template<class E>

TraCIDijkstraRouter< E >::TraCIDijkstraRouter ( size_t noE ) [inline]

Constructor.

Definition at line 62 of file TraCIDijkstraRouter.h.

00063             : myNoE(noE), myReusableEdgeLists(true), myReusableEdgeInfoLists(true) { }

template<class E>

virtual TraCIDijkstraRouter< E >::~TraCIDijkstraRouter ( ) [inline, virtual]

Destructor.

Definition at line 66 of file TraCIDijkstraRouter.h.

00066 { }

Member Function Documentation

template<class E>

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

Builds the path from marked edges.

Definition at line 211 of file TraCIDijkstraRouter.h.

References TraCIDijkstraRouter< E >::EdgeInfo::edge, and TraCIDijkstraRouter< E >::EdgeInfo::prev.

Referenced by TraCIDijkstraRouter< E >::compute().

00211                                                                       {
00212         std::deque<const E*> tmp;
00213         EdgeInfo* last = rbegin;
00214         while (rbegin!=0) {
00215             tmp.push_front((E *) rbegin->edge); // !!!
00216             rbegin = rbegin->prev;
00217             if (rbegin == last) {
00218                 tmp.push_front((E *) rbegin->edge);
00219                 break;
00220             }
00221         }
00222         std::copy(tmp.begin(), tmp.end(), std::back_inserter(edges));
00223     }

template<class E>

void TraCIDijkstraRouter< E >::clearTemporaryStorages	(	std::vector< bool > *	edgeList,
		EdgeInfoCont *	consecutionList
	)			`[inline, protected]`

Saves the temporary storages for further usage.

Definition at line 285 of file TraCIDijkstraRouter.h.

References InstancePool< T >::addFreeInstance(), TraCIDijkstraRouter< E >::myReusableEdgeInfoLists, and TraCIDijkstraRouter< E >::myReusableEdgeLists.

Referenced by TraCIDijkstraRouter< E >::compute().

00286                                                                {
00287         myReusableEdgeLists.addFreeInstance(edgeList);
00288         myReusableEdgeInfoLists.addFreeInstance(consecutionList);
00289     }

template<class E>

virtual void TraCIDijkstraRouter< E >::compute	(	const E *	from,
		const E *	to,
		const MSVehicle *const	vehicle,
		SUMOTime	time,
		std::vector< const E * > &	into
	)			`[inline, virtual]`

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

Implements SUMOAbstractRouter< E, MSVehicle >.

Definition at line 132 of file TraCIDijkstraRouter.h.

Referenced by traci::TraCIServer::commandDistanceRequest().

00133                                                                    {
00134 
00135         // get structures to reuse
00136         std::vector<bool> *visited = myReusableEdgeLists.getFreeInstance();
00137         if (visited==0) {
00138             visited = new std::vector<bool>(myNoE, false);
00139         } else {
00140             for (size_t i=0; i<myNoE; i++) {
00141                 (*visited)[i] = false; // too slow? !!!
00142             }
00143         }
00144         EdgeInfoCont *storage = myReusableEdgeInfoLists.getFreeInstance();
00145         if (storage==0) {
00146             storage = new EdgeInfoCont(myNoE);
00147         }
00148         storage->reset();
00149 
00150         // check the nodes
00151         if (from==0||to==0) {
00152             throw std::exception();
00153         }
00154 
00155         // begin computation
00156         std::priority_queue<EdgeInfo*,
00157         std::vector<EdgeInfo*>,
00158         EdgeInfoByEffortComperator> frontierList;
00159         // add begin node
00160         const E *actualKnot = from;
00161         if (from != 0) {
00162             EdgeInfo *ei = storage->add(actualKnot, 0, 0);
00163             frontierList.push(ei);
00164         }
00165         bool isFirstIteration = true;
00166 
00167         // loop
00168         while (!frontierList.empty()) {
00169             // use the node with the minimal length
00170             EdgeInfo *minimumKnot = frontierList.top();
00171             const E *minEdge = minimumKnot->edge;
00172             frontierList.pop();
00173             // check whether the destination node was already reached
00174             if ((minEdge == to) && (!isFirstIteration)) {
00175                 buildPathFrom(minimumKnot, into);
00176                 clearTemporaryStorages(visited, storage);
00177                 return;
00178             }
00179             (*visited)[minEdge->getNumericalID()] = true;
00180             SUMOReal effort = (SUMOReal)(minimumKnot->effort + getEffort(minEdge, time + minimumKnot->effort));
00181             // check all ways from the node with the minimal length
00182             unsigned int i = 0;
00183             unsigned int length_size = minEdge->getNoFollowing();
00184             for (i=0; i<length_size; i++) {
00185                 const E* help = minEdge->getFollower(i);
00186 
00187                 if ((!(*visited)[help->getNumericalID()] && effort < storage->getEffort(help))
00188                         || (help == to)) {
00189 //                    if (help!=from) {
00190                     frontierList.push(storage->add(help, effort, minimumKnot));
00191 //                    }
00192                 }
00193             }
00194 
00195             isFirstIteration = false;
00196         }
00197         clearTemporaryStorages(visited, storage);
00198     }

template<class E>

virtual SUMOReal TraCIDijkstraRouter< E >::getEffort	(	const E *const	e,
		SUMOReal	t
	)			`[inline, virtual]`

Definition at line 120 of file TraCIDijkstraRouter.h.

References MSNet::getInstance(), MSLane::getLength(), MSLane::getMaxSpeed(), and SUMOReal.

Referenced by TraCIDijkstraRouter< E >::compute(), and TraCIDijkstraRouter< E >::recomputeCosts().

00120                                                               {
00121         SUMOReal value;
00122         if (MSNet::getInstance()->getWeightsStorage().retrieveExistingEffort(e, 0, t, value)) {
00123             return value;
00124         }
00125         const MSLane * const l = e->getLanes()[0];
00126         return l->getLength() / l->getMaxSpeed();
00127     }

template<class E>

SUMOReal TraCIDijkstraRouter< E >::recomputeCosts	(	const std::vector< const E * > &	edges,
		const MSVehicle *const	v,
		SUMOTime	time
	)			throw () `[inline, virtual]`

Implements SUMOAbstractRouter< E, MSVehicle >.

Definition at line 201 of file TraCIDijkstraRouter.h.

References TraCIDijkstraRouter< E >::getEffort(), and SUMOReal.

00201                                                                                                                 {
00202         SUMOReal costs = 0;
00203         for (typename std::vector<const E*>::const_iterator i=edges.begin(); i!=edges.end(); i++) {
00204             costs += getEffort(*i, (SUMOTime)(time + costs));
00205         }
00206         return costs;
00207     }