![]() |
Eclipse SUMO - Simulation of Urban MObility
|
Computes the shortest path through a network using the A* algorithm. More...
#include <AStarRouter.h>
Data Structures | |
class | EdgeInfoComparator |
Public Types | |
typedef FullLookupTable< E, V > | FLT |
typedef LandmarkLookupTable< E, V > | LMLT |
typedef AbstractLookupTable< E, V > | LookupTable |
typedef double(* | Operation) (const E *const, const V *const, double) |
Type of the function that is used to retrieve the edge effort. More... | |
Public Member Functions | |
AStarRouter (const std::vector< E * > &edges, bool unbuildIsWarning, typename SUMOAbstractRouter< E, V >::Operation operation, const std::shared_ptr< const LookupTable > lookup=nullptr, const bool havePermissions=false, const bool haveRestrictions=false) | |
Constructor. More... | |
AStarRouter (const std::vector< typename SUMOAbstractRouter< E, V >::EdgeInfo > &edgeInfos, bool unbuildIsWarning, typename SUMOAbstractRouter< E, V >::Operation operation, const std::shared_ptr< const LookupTable > lookup=nullptr, const bool havePermissions=false, const bool haveRestrictions=false) | |
void | buildPathFrom (const typename SUMOAbstractRouter< E, V >::EdgeInfo *rbegin, std::vector< const E * > &edges) |
Builds the path from marked edges. More... | |
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 travel time. More... | |
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. More... | |
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. More... | |
void | endQuery (int visits) |
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 () |
bool | isProhibited (const E *const edge, const V *const vehicle) const |
void | prohibit (const std::vector< E * > &toProhibit) |
double | recomputeCosts (const std::vector< const E * > &edges, const V *const v, double fromPos, double toPos, SUMOTime msTime, double *lengthp=nullptr) const |
double | recomputeCosts (const std::vector< const E * > &edges, const V *const v, SUMOTime msTime, double *lengthp=nullptr) const |
virtual void | reset (const V *const vehicle) |
reset internal caches, used by CHRouter More... | |
void | setAutoBulkMode (const bool mode) |
void | setBulkMode (const bool mode) |
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 | ~AStarRouter () |
Destructor. More... | |
Protected Attributes | |
bool | myAutoBulkMode |
whether we are currently trying to detect bulk mode automatically More... | |
bool | myBulkMode |
whether we are currently operating several route queries in a bulk More... | |
EdgeInfoComparator | myComparator |
std::vector< typename SUMOAbstractRouter< E, V >::EdgeInfo > | myEdgeInfos |
The container of edge information. More... | |
MsgHandler *const | myErrorMsgHandler |
the handler for routing errors More... | |
std::vector< typename SUMOAbstractRouter< E, V >::EdgeInfo * > | myFound |
list of visited Edges (for resetting) More... | |
std::vector< typename SUMOAbstractRouter< E, V >::EdgeInfo * > | myFrontierList |
A container for reusage of the min edge heap. More... | |
const bool | myHavePermissions |
whether edge permissions need to be considered More... | |
const bool | myHaveRestrictions |
whether edge restrictions need to be considered More... | |
const std::shared_ptr< const LookupTable > | myLookupTable |
the lookup table for travel time heuristics More... | |
double | myMaxSpeed |
maximum speed in the network More... | |
Operation | myOperation |
The object's operation to perform. More... | |
std::vector< E * > | myProhibited |
Operation | myTTOperation |
The object's operation to perform for travel times. More... | |
Private Attributes | |
long long int | myNumQueries |
long long int | myQueryStartTime |
the time spent querying in milliseconds More... | |
long long int | myQueryTimeSum |
long long int | myQueryVisits |
counters for performance logging More... | |
const std::string | myType |
the type of this router More... | |
Computes the shortest path through a network using the A* algorithm.
The template parameters are:
E | The edge class to use (MSEdge/ROEdge) |
V | The vehicle class to use (MSVehicle/ROVehicle) |
BASE | The base class to use (SUMOAbstractRouterPermissions/SUMOAbstractRouter) |
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 76 of file AStarRouter.h.
typedef FullLookupTable<E, V> AStarRouter< E, V >::FLT |
Definition at line 79 of file AStarRouter.h.
typedef LandmarkLookupTable<E, V> AStarRouter< E, V >::LMLT |
Definition at line 80 of file AStarRouter.h.
typedef AbstractLookupTable<E, V> AStarRouter< E, V >::LookupTable |
Definition at line 78 of file AStarRouter.h.
|
inherited |
Type of the function that is used to retrieve the edge effort.
Definition at line 94 of file SUMOAbstractRouter.h.
|
inline |
Constructor.
Definition at line 98 of file AStarRouter.h.
References MAX2(), AStarRouter< E, V >::myEdgeInfos, and AStarRouter< E, V >::myMaxSpeed.
|
inline |
Definition at line 109 of file AStarRouter.h.
References MAX2(), AStarRouter< E, V >::myEdgeInfos, and AStarRouter< E, V >::myMaxSpeed.
|
inlinevirtual |
Destructor.
Definition at line 121 of file AStarRouter.h.
|
inline |
Builds the path from marked edges.
Definition at line 310 of file AStarRouter.h.
References SUMOAbstractRouter< E, V >::EdgeInfo::edge, and SUMOAbstractRouter< E, V >::EdgeInfo::prev.
Referenced by AStarRouter< E, V >::compute().
|
inlinevirtual |
Implements SUMOAbstractRouter< E, V >.
Definition at line 123 of file AStarRouter.h.
References MsgHandler::getWarningInstance(), AStarRouter< E, V >::myEdgeInfos, SUMOAbstractRouter< E, V >::myErrorMsgHandler, SUMOAbstractRouter< E, V >::myHavePermissions, SUMOAbstractRouter< E, V >::myHaveRestrictions, AStarRouter< E, V >::myLookupTable, and SUMOAbstractRouter< E, V >::myOperation.
|
inlinevirtual |
Builds the route between the given edges using the minimum travel time.
Implements SUMOAbstractRouter< E, V >.
Definition at line 142 of file AStarRouter.h.
References AStarRouter< E, V >::buildPathFrom(), OutputDevice::close(), SUMOAbstractRouter< E, V >::endQuery(), OutputDevice::getDevice(), SUMOAbstractRouter< E, V >::getEffort(), Named::getIDSecure(), SUMOAbstractRouter< E, V >::getTravelTime(), MsgHandler::inform(), MsgHandler::informf(), AStarRouter< E, V >::init(), MIN2(), SUMOAbstractRouter< E, V >::myBulkMode, AStarRouter< E, V >::myComparator, AStarRouter< E, V >::myEdgeInfos, SUMOAbstractRouter< E, V >::myErrorMsgHandler, AStarRouter< E, V >::myFound, AStarRouter< E, V >::myFrontierList, AStarRouter< E, V >::myLookupTable, AStarRouter< E, V >::myMaxSpeed, SUMOAbstractRouter< E, V >::recomputeCosts(), SUMOAbstractRouter< E, V >::startQuery(), STEPS2TIME, SVC_IGNORING, toString(), UNREACHABLE, and SUMOAbstractRouter< E, V >::updateViaEdgeCost().
|
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 157 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 172 of file SUMOAbstractRouter.h.
References SUMOAbstractRouter< E, V >::compute(), MsgHandler::informf(), SUMOAbstractRouter< E, V >::myErrorMsgHandler, SUMOAbstractRouter< E, V >::recomputeCosts(), and SVC_IGNORING.
Referenced by SUMOAbstractRouter< E, V >::compute(), MSBaseVehicle::reroute(), and MSTriggeredRerouter::rerouteParkingArea().
|
inlineinherited |
Definition at line 279 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 270 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(), SUMOAbstractRouter< E, V >::recomputeCosts(), CHBuilder< E, V >::synchronize(), SUMOAbstractRouter< E, V >::updateViaCost(), and SUMOAbstractRouter< E, V >::updateViaEdgeCost().
|
inlineinherited |
Definition at line 207 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 143 of file SUMOAbstractRouter.h.
References SUMOAbstractRouter< E, V >::myType.
|
inline |
Definition at line 128 of file AStarRouter.h.
References AStarRouter< E, V >::myFound, and AStarRouter< E, V >::myFrontierList.
Referenced by AStarRouter< E, V >::compute().
|
inlineinherited |
Definition at line 201 of file SUMOAbstractRouter.h.
References SUMOAbstractRouter< E, V >::myHavePermissions, and SUMOAbstractRouter< E, V >::myHaveRestrictions.
Referenced by SUMOAbstractRouter< E, V >::recomputeCosts().
|
inlinevirtual |
Reimplemented from SUMOAbstractRouter< E, V >.
Definition at line 298 of file AStarRouter.h.
References AStarRouter< E, V >::myEdgeInfos, and SUMOAbstractRouter< E, V >::myProhibited.
|
inlineinherited |
Definition at line 258 of file SUMOAbstractRouter.h.
References SUMOAbstractRouter< E, V >::getEffort(), SUMOAbstractRouter< E, V >::recomputeCosts(), and STEPS2TIME.
|
inlineinherited |
Definition at line 237 of file SUMOAbstractRouter.h.
References SUMOAbstractRouter< E, V >::isProhibited(), STEPS2TIME, and SUMOAbstractRouter< E, V >::updateViaCost().
Referenced by RORouteDef::addAlternative(), AStarRouter< E, V >::compute(), MSDispatch::computeDetourTime(), SUMOAbstractRouter< E, V >::computeLooped(), ROMAAssignments::computePath(), MSDispatch::computePickupTime(), computeRoutes(), LIBSUMO_NAMESPACE::Simulation::findRoute(), NBPTLineCont::getCost(), LandmarkLookupTable< E, V >::LandmarkLookupTable(), MSTriggeredRerouter::notifyEnter(), SUMOAbstractRouter< E, V >::recomputeCosts(), MSVehicle::replaceStop(), MSBaseVehicle::reroute(), MSTriggeredRerouter::rerouteParkingArea(), MSVehicle::rerouteParkingArea(), and ROMAAssignments::sue().
|
inlinevirtualinherited |
reset internal caches, used by CHRouter
Reimplemented in CHRouter< E, V >.
Definition at line 139 of file SUMOAbstractRouter.h.
References UNUSED_PARAMETER.
Referenced by computeRoutes(), and ROMAAssignments::incremental().
|
inlineinherited |
Definition at line 288 of file SUMOAbstractRouter.h.
References SUMOAbstractRouter< E, V >::myAutoBulkMode.
Referenced by LandmarkLookupTable< E, V >::LandmarkLookupTable().
|
inlineinherited |
Definition at line 284 of file SUMOAbstractRouter.h.
References SUMOAbstractRouter< E, V >::myBulkMode.
Referenced by ROMAAssignments::incremental().
|
inlineinherited |
Definition at line 274 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 221 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(), and SUMOAbstractRouter< E, V >::recomputeCosts().
|
inlineinherited |
Definition at line 211 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 currently trying to detect bulk mode automatically
Definition at line 306 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 303 of file SUMOAbstractRouter.h.
Referenced by AStarRouter< E, V >::compute(), DijkstraRouter< E, V >::compute(), and SUMOAbstractRouter< E, V >::setBulkMode().
|
protected |
Definition at line 328 of file AStarRouter.h.
Referenced by AStarRouter< E, V >::compute().
|
protected |
The container of edge information.
Definition at line 321 of file AStarRouter.h.
Referenced by AStarRouter< E, V >::AStarRouter(), AStarRouter< E, V >::clone(), AStarRouter< E, V >::compute(), and AStarRouter< E, V >::prohibit().
|
protectedinherited |
the handler for routing errors
Definition at line 294 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().
|
protected |
list of visited Edges (for resetting)
Definition at line 326 of file AStarRouter.h.
Referenced by AStarRouter< E, V >::compute(), and AStarRouter< E, V >::init().
|
protected |
A container for reusage of the min edge heap.
Definition at line 324 of file AStarRouter.h.
Referenced by AStarRouter< E, V >::compute(), and AStarRouter< E, V >::init().
|
protectedinherited |
whether edge permissions need to be considered
Definition at line 309 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().
|
protectedinherited |
whether edge restrictions need to be considered
Definition at line 312 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().
|
protected |
the lookup table for travel time heuristics
Definition at line 331 of file AStarRouter.h.
Referenced by AStarRouter< E, V >::clone(), and AStarRouter< E, V >::compute().
|
protected |
maximum speed in the network
Definition at line 334 of file AStarRouter.h.
Referenced by AStarRouter< E, V >::AStarRouter(), and AStarRouter< E, V >::compute().
|
privateinherited |
Definition at line 322 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 297 of file SUMOAbstractRouter.h.
Referenced by AStarRouter< E, V >::clone(), CHRouter< E, V >::clone(), CHRouterWrapper< E, V >::clone(), DijkstraRouter< E, V >::clone(), and SUMOAbstractRouter< E, V >::getEffort().
|
protectedinherited |
Definition at line 314 of file SUMOAbstractRouter.h.
Referenced by AStarRouter< E, V >::prohibit(), and DijkstraRouter< E, V >::prohibit().
|
privateinherited |
the time spent querying in milliseconds
Definition at line 324 of file SUMOAbstractRouter.h.
Referenced by SUMOAbstractRouter< E, V >::endQuery(), and SUMOAbstractRouter< E, V >::startQuery().
|
privateinherited |
Definition at line 325 of file SUMOAbstractRouter.h.
Referenced by SUMOAbstractRouter< E, V >::endQuery(), and SUMOAbstractRouter< E, V >::~SUMOAbstractRouter().
|
privateinherited |
counters for performance logging
Definition at line 321 of file SUMOAbstractRouter.h.
Referenced by SUMOAbstractRouter< E, V >::endQuery(), and SUMOAbstractRouter< E, V >::~SUMOAbstractRouter().
|
protectedinherited |
The object's operation to perform for travel times.
Definition at line 300 of file SUMOAbstractRouter.h.
Referenced by DijkstraRouter< E, V >::clone(), and SUMOAbstractRouter< E, V >::getTravelTime().
|
privateinherited |
the type of this router
Definition at line 318 of file SUMOAbstractRouter.h.
Referenced by SUMOAbstractRouter< E, V >::getType(), and SUMOAbstractRouter< E, V >::~SUMOAbstractRouter().