Eclipse SUMO - Simulation of Urban MObility
|
Computes the shortest path through a network using the Dijkstra algorithm. More...
#include <DijkstraRouter.h>
Data Structures | |
class | EdgeInfoByEffortComparator |
Public Types | |
typedef double(* | Operation) (const E *const, const V *const, double) |
Type of the function that is used to retrieve the edge effort. | |
Public Member Functions | |
void | buildPathFrom (const typename SUMOAbstractRouter< E, V >::EdgeInfo *rbegin, std::vector< const E * > &edges) |
Builds the path from marked edges. | |
virtual SUMOAbstractRouter< E, V > * | clone () |
bool | compute (const E *from, const E *to, const V *const vehicle, SUMOTime msTime, std::vector< const E * > &into, bool silent=false) |
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. | |
bool | compute (const E *from, double fromPos, const E *to, double toPos, const V *const vehicle, SUMOTime msTime, std::vector< const E * > &into, bool silent=false) |
Builds the route between the given edges using the minimum effort at the given time, also taking into account position along the edges to ensure currect handling of looped routes The definition of the effort depends on the wished routing scheme. | |
bool | computeLooped (const E *from, const E *to, const V *const vehicle, SUMOTime msTime, std::vector< const E * > &into, bool silent=false) |
Builds the route between the given edges using the minimum effort at the given time if from == to, return the shortest looped route. | |
DijkstraRouter (const std::vector< E * > &edges, bool unbuildIsWarning, typename SUMOAbstractRouter< E, V >::Operation effortOperation, typename SUMOAbstractRouter< E, V >::Operation ttOperation=nullptr, bool silent=false, EffortCalculator *calc=nullptr, const bool havePermissions=false, const bool haveRestrictions=false) | |
Constructor. | |
void | endQuery (int visits) |
const SUMOAbstractRouter< E, V >::EdgeInfo & | getEdgeInfo (int index) const |
double | getEffort (const E *const e, const V *const v, double t) const |
double | getTravelTime (const E *const e, const V *const v, const double t, const double effort) const |
const std::string & | getType () const |
void | init (const int edgeID, const SUMOTime msTime) |
bool | isProhibited (const E *const edge, const V *const vehicle) const |
bool | isValid (const std::vector< const E * > &edges, const V *const v) const |
virtual void | prohibit (const std::vector< E * > &toProhibit) |
virtual double | recomputeCosts (const std::vector< const E * > &edges, const V *const v, SUMOTime msTime, double *lengthp=nullptr) const |
double | recomputeCostsPos (const std::vector< const E * > &edges, const V *const v, double fromPos, double toPos, SUMOTime msTime, double *lengthp=nullptr) const |
virtual void | reset (const V *const vehicle) |
reset internal caches, used by CHRouter | |
void | setAutoBulkMode (const bool mode) |
virtual void | setBulkMode (const bool mode) |
double | setHint (const typename std::vector< const E * >::const_iterator routeBegin, const typename std::vector< const E * >::const_iterator routeEnd, const V *const v, SUMOTime msTime) |
void | startQuery () |
void | updateViaCost (const E *const prev, const E *const e, const V *const v, double &time, double &effort, double &length) const |
void | updateViaEdgeCost (const E *viaEdge, const V *const v, double &time, double &effort, double &length) const |
virtual | ~DijkstraRouter () |
Destructor. | |
Protected Attributes | |
bool | myAmClean |
whether we are already initialized | |
bool | myAutoBulkMode |
whether we are currently trying to detect bulk mode automatically | |
bool | myBulkMode |
whether we are currently operating several route queries in a bulk | |
std::vector< typename SUMOAbstractRouter< E, V >::EdgeInfo > | myEdgeInfos |
The container of edge information. | |
MsgHandler *const | myErrorMsgHandler |
the handler for routing errors | |
std::vector< typename SUMOAbstractRouter< E, V >::EdgeInfo * > | myFound |
list of visited Edges (for resetting) | |
std::vector< typename SUMOAbstractRouter< E, V >::EdgeInfo * > | myFrontierList |
A container for reusage of the min edge heap. | |
const bool | myHavePermissions |
whether edge permissions need to be considered | |
const bool | myHaveRestrictions |
whether edge restrictions need to be considered | |
Operation | myOperation |
The object's operation to perform. | |
std::vector< E * > | myProhibited |
The list of explicitly prohibited edges. | |
Operation | myTTOperation |
The object's operation to perform for travel times. | |
Private Member Functions | |
DijkstraRouter (const std::vector< typename SUMOAbstractRouter< E, V >::EdgeInfo > &edgeInfos, bool unbuildIsWarning, typename SUMOAbstractRouter< E, V >::Operation effortOperation, typename SUMOAbstractRouter< E, V >::Operation ttOperation, bool silent, EffortCalculator *calc, const bool havePermissions, const bool haveRestrictions) | |
Private Attributes | |
EdgeInfoByEffortComparator | myComparator |
EffortCalculator *const | myExternalEffort |
std::tuple< const E *, const V *, SUMOTime > | myLastQuery |
cache of the last query to enable automated bulk routing | |
long long int | myNumQueries |
long long int | myQueryStartTime |
the time spent querying in milliseconds | |
long long int | myQueryTimeSum |
long long int | myQueryVisits |
counters for performance logging | |
bool | mySilent |
whether to suppress warning/error if no route was found | |
const std::string | myType |
the type of this router | |
Computes the shortest path through a network using the Dijkstra algorithm.
The template parameters are:
E | The edge class to use (MSEdge/ROEdge) |
V | The vehicle class to use (MSVehicle/ROVehicle) |
The router is edge-based. It must know the number of edges for internal reasons and whether a missing connection between two given edges (unbuild route) shall be reported as an error or as a warning.
Definition at line 63 of file DijkstraRouter.h.
|
inherited |
Type of the function that is used to retrieve the edge effort.
Definition at line 92 of file SUMOAbstractRouter.h.
|
inline |
Constructor.
Definition at line 82 of file DijkstraRouter.h.
References SUMOAbstractRouter< E, V >::myEdgeInfos.
|
inlinevirtual |
Destructor.
Definition at line 93 of file DijkstraRouter.h.
|
inlineprivate |
Definition at line 248 of file DijkstraRouter.h.
References SUMOAbstractRouter< E, V >::myEdgeInfos.
|
inlineinherited |
Builds the path from marked edges.
Definition at line 364 of file SUMOAbstractRouter.h.
References SUMOAbstractRouter< E, V >::EdgeInfo::edge, and SUMOAbstractRouter< E, V >::EdgeInfo::prev.
Referenced by AStarRouter< E, V >::compute(), and DijkstraRouter< E, V >::compute().
|
inlinevirtual |
Implements SUMOAbstractRouter< E, V >.
Definition at line 95 of file DijkstraRouter.h.
References DijkstraRouter< E, V >::clone(), MsgHandler::getWarningInstance(), SUMOAbstractRouter< E, V >::myAutoBulkMode, SUMOAbstractRouter< E, V >::myEdgeInfos, SUMOAbstractRouter< E, V >::myErrorMsgHandler, DijkstraRouter< E, V >::myExternalEffort, SUMOAbstractRouter< E, V >::myHavePermissions, SUMOAbstractRouter< E, V >::myHaveRestrictions, SUMOAbstractRouter< E, V >::myOperation, DijkstraRouter< E, V >::mySilent, and SUMOAbstractRouter< E, V >::myTTOperation.
Referenced by DijkstraRouter< E, V >::clone().
|
inlinevirtual |
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, V >.
Definition at line 105 of file DijkstraRouter.h.
References SUMOAbstractRouter< E, V >::buildPathFrom(), DijkstraRouter_DEBUG_QUERY_VISITED_OUT, SUMOAbstractRouter< E, V >::endQuery(), SUMOAbstractRouter< E, V >::getEffort(), Named::getIDSecure(), SUMOAbstractRouter< E, V >::getTravelTime(), MsgHandler::inform(), MsgHandler::informf(), SUMOAbstractRouter< E, V >::init(), SUMOAbstractRouter< E, V >::myAmClean, SUMOAbstractRouter< E, V >::myAutoBulkMode, SUMOAbstractRouter< E, V >::myBulkMode, DijkstraRouter< E, V >::myComparator, SUMOAbstractRouter< E, V >::myEdgeInfos, SUMOAbstractRouter< E, V >::myErrorMsgHandler, DijkstraRouter< E, V >::myExternalEffort, SUMOAbstractRouter< E, V >::myFound, SUMOAbstractRouter< E, V >::myFrontierList, DijkstraRouter< E, V >::myLastQuery, DijkstraRouter< E, V >::mySilent, SUMOAbstractRouter< E, V >::recomputeCosts(), EffortCalculator::setInitialState(), SUMOAbstractRouter< E, V >::startQuery(), STEPS2TIME, SVC_IGNORING, time2string(), TL, toString(), EffortCalculator::update(), and SUMOAbstractRouter< E, V >::updateViaEdgeCost().
Referenced by PedestrianRouter< E, L, N, V >::compute().
|
inlineinherited |
Builds the route between the given edges using the minimum effort at the given time, also taking into account position along the edges to ensure currect handling of looped routes The definition of the effort depends on the wished routing scheme.
Definition at line 183 of file SUMOAbstractRouter.h.
References SUMOAbstractRouter< E, V >::compute(), and SUMOAbstractRouter< E, V >::computeLooped().
|
inlineinherited |
Builds the route between the given edges using the minimum effort at the given time if from == to, return the shortest looped route.
Definition at line 198 of file SUMOAbstractRouter.h.
References SUMOAbstractRouter< E, V >::compute(), MsgHandler::informf(), SUMOAbstractRouter< E, V >::myErrorMsgHandler, SUMOAbstractRouter< E, V >::recomputeCosts(), SVC_IGNORING, and TL.
Referenced by SUMOAbstractRouter< E, V >::compute(), and MSBaseVehicle::reroute().
|
inlineinherited |
Definition at line 339 of file SUMOAbstractRouter.h.
References SysUtils::getCurrentMillis(), SUMOAbstractRouter< E, V >::myQueryStartTime, SUMOAbstractRouter< E, V >::myQueryTimeSum, and SUMOAbstractRouter< E, V >::myQueryVisits.
Referenced by AStarRouter< E, V >::compute(), CHRouter< E, V >::compute(), and DijkstraRouter< E, V >::compute().
|
inlineinherited |
Definition at line 169 of file SUMOAbstractRouter.h.
References SUMOAbstractRouter< E, V >::myEdgeInfos.
|
inlineinherited |
Definition at line 330 of file SUMOAbstractRouter.h.
References SUMOAbstractRouter< E, V >::myOperation.
Referenced by IntermodalRouter< E, L, N, V >::compute(), AStarRouter< E, V >::compute(), DijkstraRouter< E, V >::compute(), PedestrianRouter< E, L, N, V >::compute(), RailwayRouter< E, V >::recomputeCosts(), SUMOAbstractRouter< E, V >::recomputeCostsPos(), SUMOAbstractRouter< E, V >::setHint(), CHBuilder< E, V >::synchronize(), SUMOAbstractRouter< E, V >::updateViaCost(), and SUMOAbstractRouter< E, V >::updateViaEdgeCost().
|
inlineinherited |
Definition at line 231 of file SUMOAbstractRouter.h.
References SUMOAbstractRouter< E, V >::myTTOperation.
Referenced by AStarRouter< E, V >::compute(), DijkstraRouter< E, V >::compute(), SUMOAbstractRouter< E, V >::updateViaCost(), and SUMOAbstractRouter< E, V >::updateViaEdgeCost().
|
inlineinherited |
Definition at line 165 of file SUMOAbstractRouter.h.
References SUMOAbstractRouter< E, V >::myType.
|
inlineinherited |
Definition at line 136 of file SUMOAbstractRouter.h.
References SUMOAbstractRouter< E, V >::myAmClean, SUMOAbstractRouter< E, V >::myEdgeInfos, SUMOAbstractRouter< E, V >::myFound, SUMOAbstractRouter< E, V >::myFrontierList, and STEPS2TIME.
Referenced by AStarRouter< E, V >::compute(), DijkstraRouter< E, V >::compute(), and SUMOAbstractRouter< E, V >::setHint().
|
inlineinherited |
Definition at line 227 of file SUMOAbstractRouter.h.
References SUMOAbstractRouter< E, V >::myHavePermissions, and SUMOAbstractRouter< E, V >::myHaveRestrictions.
Referenced by SUMOAbstractRouter< E, V >::isValid(), and SUMOAbstractRouter< E, V >::setHint().
|
inlineinherited |
Definition at line 260 of file SUMOAbstractRouter.h.
References SUMOAbstractRouter< E, V >::isProhibited().
Referenced by RORouteDef::addAlternative().
|
inlinevirtualinherited |
Reimplemented in CHRouter< E, V >, CHRouterWrapper< E, V >, IntermodalRouter< E, L, N, V >, PedestrianRouter< E, L, N, V >, and RailwayRouter< E, V >.
Definition at line 352 of file SUMOAbstractRouter.h.
References SUMOAbstractRouter< E, V >::myEdgeInfos, and SUMOAbstractRouter< E, V >::myProhibited.
Referenced by IntermodalRouter< E, L, N, V >::prohibit(), PedestrianRouter< E, L, N, V >::prohibit(), and RailwayRouter< E, V >::prohibit().
|
inlinevirtualinherited |
Reimplemented in RailwayRouter< E, V >.
Definition at line 269 of file SUMOAbstractRouter.h.
References STEPS2TIME, and SUMOAbstractRouter< E, V >::updateViaCost().
Referenced by RORouteDef::addAlternative(), AStarRouter< E, V >::compute(), DijkstraRouter< E, V >::compute(), SUMOAbstractRouter< E, V >::computeLooped(), ROMAAssignments::computePath(), MSDispatch::computePickupTime(), computeRoutes(), MSDevice_StationFinder::estimateConsumption(), MSStoppingPlaceRerouter::evaluateDestination(), LIBSUMO_NAMESPACE::Simulation::findRoute(), NBPTLineCont::getCost(), MSBaseVehicle::insertStop(), LandmarkLookupTable< E, V >::LandmarkLookupTable(), RailwayRouter< E, V >::recomputeCosts(), SUMOAbstractRouter< E, V >::recomputeCostsPos(), MSBaseVehicle::replaceStop(), MSBaseVehicle::reroute(), MSBaseVehicle::rerouteBetweenStops(), MSVehicle::rerouteParkingArea(), ROMAAssignments::sue(), and MSTriggeredRerouter::triggerRouting().
|
inlineinherited |
Definition at line 287 of file SUMOAbstractRouter.h.
References SUMOAbstractRouter< E, V >::getEffort(), SUMOAbstractRouter< E, V >::recomputeCosts(), and STEPS2TIME.
Referenced by MSDispatch::computeDetourTime().
|
inlinevirtualinherited |
reset internal caches, used by CHRouter
Reimplemented in CHRouter< E, V >.
Definition at line 161 of file SUMOAbstractRouter.h.
References UNUSED_PARAMETER.
Referenced by computeRoutes(), and ROMAAssignments::incremental().
|
inlineinherited |
Definition at line 348 of file SUMOAbstractRouter.h.
References SUMOAbstractRouter< E, V >::myAutoBulkMode.
Referenced by LandmarkLookupTable< E, V >::LandmarkLookupTable().
|
inlinevirtualinherited |
Reimplemented in IntermodalRouter< E, L, N, V >.
Definition at line 344 of file SUMOAbstractRouter.h.
References SUMOAbstractRouter< E, V >::myBulkMode.
Referenced by ROMAAssignments::computePath(), ROMAAssignments::incremental(), and IntermodalRouter< E, L, N, V >::setBulkMode().
|
inlineinherited |
Definition at line 299 of file SUMOAbstractRouter.h.
References SUMOAbstractRouter< E, V >::EdgeInfo::edge, SUMOAbstractRouter< E, V >::EdgeInfo::effort, SUMOAbstractRouter< E, V >::getEffort(), SUMOAbstractRouter< E, V >::init(), SUMOAbstractRouter< E, V >::isProhibited(), SUMOAbstractRouter< E, V >::myEdgeInfos, SUMOAbstractRouter< E, V >::myFound, STEPS2TIME, and SUMOAbstractRouter< E, V >::updateViaCost().
|
inlineinherited |
Definition at line 334 of file SUMOAbstractRouter.h.
References SysUtils::getCurrentMillis(), SUMOAbstractRouter< E, V >::myNumQueries, and SUMOAbstractRouter< E, V >::myQueryStartTime.
Referenced by AStarRouter< E, V >::compute(), CHRouter< E, V >::compute(), and DijkstraRouter< E, V >::compute().
|
inlineinherited |
Definition at line 245 of file SUMOAbstractRouter.h.
References SUMOAbstractRouter< E, V >::getEffort(), SUMOAbstractRouter< E, V >::getTravelTime(), and SUMOAbstractRouter< E, V >::updateViaEdgeCost().
Referenced by IntermodalRouter< E, L, N, V >::compute(), RailwayRouter< E, V >::recomputeCosts(), SUMOAbstractRouter< E, V >::recomputeCosts(), and SUMOAbstractRouter< E, V >::setHint().
|
inlineinherited |
Definition at line 235 of file SUMOAbstractRouter.h.
References SUMOAbstractRouter< E, V >::getEffort(), and SUMOAbstractRouter< E, V >::getTravelTime().
Referenced by AStarRouter< E, V >::compute(), DijkstraRouter< E, V >::compute(), and SUMOAbstractRouter< E, V >::updateViaCost().
|
protectedinherited |
whether we are already initialized
Definition at line 390 of file SUMOAbstractRouter.h.
Referenced by AStarRouter< E, V >::compute(), DijkstraRouter< E, V >::compute(), and SUMOAbstractRouter< E, V >::init().
|
protectedinherited |
whether we are currently trying to detect bulk mode automatically
Definition at line 387 of file SUMOAbstractRouter.h.
Referenced by DijkstraRouter< E, V >::clone(), DijkstraRouter< E, V >::compute(), and SUMOAbstractRouter< E, V >::setAutoBulkMode().
|
protectedinherited |
whether we are currently operating several route queries in a bulk
Definition at line 384 of file SUMOAbstractRouter.h.
Referenced by AStarRouter< E, V >::compute(), DijkstraRouter< E, V >::compute(), and SUMOAbstractRouter< E, V >::setBulkMode().
|
private |
Definition at line 268 of file DijkstraRouter.h.
Referenced by DijkstraRouter< E, V >::compute().
|
protectedinherited |
The container of edge information.
Definition at line 402 of file SUMOAbstractRouter.h.
Referenced by AStarRouter< E, V >::AStarRouter(), AStarRouter< E, V >::AStarRouter(), AStarRouter< E, V >::clone(), DijkstraRouter< E, V >::clone(), AStarRouter< E, V >::compute(), DijkstraRouter< E, V >::compute(), DijkstraRouter< E, V >::DijkstraRouter(), DijkstraRouter< E, V >::DijkstraRouter(), SUMOAbstractRouter< E, V >::getEdgeInfo(), SUMOAbstractRouter< E, V >::init(), SUMOAbstractRouter< E, V >::prohibit(), and SUMOAbstractRouter< E, V >::setHint().
|
protectedinherited |
the handler for routing errors
Definition at line 375 of file SUMOAbstractRouter.h.
Referenced by AStarRouter< E, V >::clone(), CHRouter< E, V >::clone(), DijkstraRouter< E, V >::clone(), AStarRouter< E, V >::compute(), CHRouter< E, V >::compute(), DijkstraRouter< E, V >::compute(), SUMOAbstractRouter< E, V >::computeLooped(), and RailwayRouter< E, V >::ensureInternalRouter().
|
private |
Definition at line 266 of file DijkstraRouter.h.
Referenced by DijkstraRouter< E, V >::clone(), and DijkstraRouter< E, V >::compute().
|
protectedinherited |
list of visited Edges (for resetting)
Definition at line 407 of file SUMOAbstractRouter.h.
Referenced by AStarRouter< E, V >::compute(), DijkstraRouter< E, V >::compute(), SUMOAbstractRouter< E, V >::init(), and SUMOAbstractRouter< E, V >::setHint().
|
protectedinherited |
A container for reusage of the min edge heap.
Definition at line 405 of file SUMOAbstractRouter.h.
Referenced by AStarRouter< E, V >::compute(), DijkstraRouter< E, V >::compute(), and SUMOAbstractRouter< E, V >::init().
|
protectedinherited |
whether edge permissions need to be considered
Definition at line 393 of file SUMOAbstractRouter.h.
Referenced by AStarRouter< E, V >::clone(), CHRouter< E, V >::clone(), CHRouterWrapper< E, V >::clone(), DijkstraRouter< E, V >::clone(), RailwayRouter< E, V >::ensureInternalRouter(), and SUMOAbstractRouter< E, V >::isProhibited().
|
protectedinherited |
whether edge restrictions need to be considered
Definition at line 396 of file SUMOAbstractRouter.h.
Referenced by AStarRouter< E, V >::clone(), CHRouter< E, V >::clone(), DijkstraRouter< E, V >::clone(), RailwayRouter< E, V >::ensureInternalRouter(), and SUMOAbstractRouter< E, V >::isProhibited().
|
private |
cache of the last query to enable automated bulk routing
Definition at line 264 of file DijkstraRouter.h.
Referenced by DijkstraRouter< E, V >::compute().
|
privateinherited |
Definition at line 415 of file SUMOAbstractRouter.h.
Referenced by SUMOAbstractRouter< E, V >::startQuery(), and SUMOAbstractRouter< E, V >::~SUMOAbstractRouter().
|
protectedinherited |
The object's operation to perform.
Definition at line 378 of file SUMOAbstractRouter.h.
Referenced by AStarRouter< E, V >::clone(), CHRouter< E, V >::clone(), CHRouterWrapper< E, V >::clone(), DijkstraRouter< E, V >::clone(), CHRouterWrapper< E, V >::compute(), and SUMOAbstractRouter< E, V >::getEffort().
|
protectedinherited |
The list of explicitly prohibited edges.
Definition at line 399 of file SUMOAbstractRouter.h.
Referenced by RailwayRouter< E, V >::_compute(), RailwayRouter< E, V >::prohibit(), and SUMOAbstractRouter< E, V >::prohibit().
|
privateinherited |
the time spent querying in milliseconds
Definition at line 417 of file SUMOAbstractRouter.h.
Referenced by SUMOAbstractRouter< E, V >::endQuery(), and SUMOAbstractRouter< E, V >::startQuery().
|
privateinherited |
Definition at line 418 of file SUMOAbstractRouter.h.
Referenced by SUMOAbstractRouter< E, V >::endQuery(), and SUMOAbstractRouter< E, V >::~SUMOAbstractRouter().
|
privateinherited |
counters for performance logging
Definition at line 414 of file SUMOAbstractRouter.h.
Referenced by SUMOAbstractRouter< E, V >::endQuery(), and SUMOAbstractRouter< E, V >::~SUMOAbstractRouter().
|
private |
whether to suppress warning/error if no route was found
Definition at line 261 of file DijkstraRouter.h.
Referenced by DijkstraRouter< E, V >::clone(), and DijkstraRouter< E, V >::compute().
|
protectedinherited |
The object's operation to perform for travel times.
Definition at line 381 of file SUMOAbstractRouter.h.
Referenced by DijkstraRouter< E, V >::clone(), and SUMOAbstractRouter< E, V >::getTravelTime().
|
privateinherited |
the type of this router
Definition at line 411 of file SUMOAbstractRouter.h.
Referenced by SUMOAbstractRouter< E, V >::getType(), and SUMOAbstractRouter< E, V >::~SUMOAbstractRouter().