![]() |
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 | 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 |
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, SUMOTime msTime, double *lengthp=nullptr) const |
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 | 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 77 of file AStarRouter.h.
typedef FullLookupTable<E, V> AStarRouter< E, V >::FLT |
Definition at line 80 of file AStarRouter.h.
typedef LandmarkLookupTable<E, V> AStarRouter< E, V >::LMLT |
Definition at line 81 of file AStarRouter.h.
typedef AbstractLookupTable<E, V> AStarRouter< E, V >::LookupTable |
Definition at line 79 of file AStarRouter.h.
|
inherited |
Type of the function that is used to retrieve the edge effort.
Definition at line 96 of file SUMOAbstractRouter.h.
|
inline |
Constructor.
Definition at line 99 of file AStarRouter.h.
References MAX2(), AStarRouter< E, V >::myEdgeInfos, and AStarRouter< E, V >::myMaxSpeed.
|
inline |
Definition at line 110 of file AStarRouter.h.
References MAX2(), AStarRouter< E, V >::myEdgeInfos, and AStarRouter< E, V >::myMaxSpeed.
|
inlinevirtual |
Destructor.
Definition at line 122 of file AStarRouter.h.
|
inline |
Builds the path from marked edges.
Definition at line 297 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 124 of file AStarRouter.h.
References MsgHandler::getWarningInstance(), AStarRouter< E, V >::myEdgeInfos, SUMOAbstractRouter< E, V >::myErrorMsgHandler, 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, time2string(), toString(), UNREACHABLE, and SUMOAbstractRouter< E, V >::updateViaEdgeCost().
|
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 130 of file SUMOAbstractRouter.h.
Referenced by MSBaseVehicle::reroute(), and MSTriggeredRerouter::rerouteParkingArea().
|
inlineinherited |
Definition at line 225 of file SUMOAbstractRouter.h.
Referenced by AStarRouter< E, V >::compute(), CHRouter< E, V >::compute(), and DijkstraRouter< E, V >::compute().
|
inlineinherited |
Definition at line 216 of file SUMOAbstractRouter.h.
Referenced by IntermodalRouter< E, L, N, V >::compute(), AStarRouter< E, V >::compute(), DijkstraRouter< E, V >::compute(), PedestrianRouter< E, L, N, V >::compute(), CHBuilder< E, V >::synchronize(), SUMOAbstractRouter< NBRouterEdge, NBVehicle >::updateViaCost(), and SUMOAbstractRouter< NBRouterEdge, NBVehicle >::updateViaEdgeCost().
|
inlineinherited |
Definition at line 165 of file SUMOAbstractRouter.h.
Referenced by AStarRouter< E, V >::compute(), DijkstraRouter< E, V >::compute(), SUMOAbstractRouter< NBRouterEdge, NBVehicle >::updateViaCost(), and SUMOAbstractRouter< NBRouterEdge, NBVehicle >::updateViaEdgeCost().
|
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 159 of file SUMOAbstractRouter.h.
Referenced by SUMOAbstractRouter< NBRouterEdge, NBVehicle >::recomputeCosts().
|
inlinevirtual |
Reimplemented from SUMOAbstractRouter< E, V >.
Definition at line 285 of file AStarRouter.h.
References AStarRouter< E, V >::myEdgeInfos, and SUMOAbstractRouter< E, V >::myProhibited.
|
inlineinherited |
Definition at line 195 of file SUMOAbstractRouter.h.
Referenced by RORouteDef::addAlternative(), AStarRouter< E, V >::compute(), SUMOAbstractRouter< NBRouterEdge, NBVehicle >::computeLooped(), ROMAAssignments::computePath(), computeRoutes(), libsumo::Simulation::findRoute(), NBPTLineCont::getCost(), LandmarkLookupTable< E, V >::LandmarkLookupTable(), MSTriggeredRerouter::notifyEnter(), MSBaseVehicle::reroute(), MSTriggeredRerouter::rerouteParkingArea(), MSVehicle::rerouteParkingArea(), and ROMAAssignments::sue().
|
inlineinherited |
Definition at line 230 of file SUMOAbstractRouter.h.
Referenced by ROMAAssignments::incremental().
|
inlineinherited |
Definition at line 220 of file SUMOAbstractRouter.h.
Referenced by AStarRouter< E, V >::compute(), CHRouter< E, V >::compute(), and DijkstraRouter< E, V >::compute().
|
inlineinherited |
Definition at line 179 of file SUMOAbstractRouter.h.
Referenced by IntermodalRouter< E, L, N, V >::compute(), and SUMOAbstractRouter< NBRouterEdge, NBVehicle >::recomputeCosts().
|
inlineinherited |
Definition at line 169 of file SUMOAbstractRouter.h.
Referenced by AStarRouter< E, V >::compute(), DijkstraRouter< E, V >::compute(), and SUMOAbstractRouter< NBRouterEdge, NBVehicle >::updateViaCost().
|
protectedinherited |
whether we are currently operating several route queries in a bulk
Definition at line 245 of file SUMOAbstractRouter.h.
Referenced by AStarRouter< E, V >::compute(), DijkstraRouter< E, V >::compute(), and SUMOAbstractRouter< NBRouterEdge, NBVehicle >::setBulkMode().
|
protected |
Definition at line 315 of file AStarRouter.h.
Referenced by AStarRouter< E, V >::compute().
|
protected |
The container of edge information.
Definition at line 308 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 236 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(), and SUMOAbstractRouter< NBRouterEdge, NBVehicle >::computeLooped().
|
protected |
list of visited Edges (for resetting)
Definition at line 313 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 311 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 248 of file SUMOAbstractRouter.h.
Referenced by CHRouter< E, V >::clone(), DijkstraRouter< E, V >::clone(), and SUMOAbstractRouter< NBRouterEdge, NBVehicle >::isProhibited().
|
protectedinherited |
whether edge restrictions need to be considered
Definition at line 251 of file SUMOAbstractRouter.h.
Referenced by CHRouter< E, V >::clone(), DijkstraRouter< E, V >::clone(), and SUMOAbstractRouter< NBRouterEdge, NBVehicle >::isProhibited().
|
protected |
the lookup table for travel time heuristics
Definition at line 318 of file AStarRouter.h.
Referenced by AStarRouter< E, V >::clone(), and AStarRouter< E, V >::compute().
|
protected |
maximum speed in the network
Definition at line 321 of file AStarRouter.h.
Referenced by AStarRouter< E, V >::AStarRouter(), and AStarRouter< E, V >::compute().
|
privateinherited |
Definition at line 261 of file SUMOAbstractRouter.h.
Referenced by SUMOAbstractRouter< NBRouterEdge, NBVehicle >::startQuery(), and SUMOAbstractRouter< NBRouterEdge, NBVehicle >::~SUMOAbstractRouter().
|
protectedinherited |
The object's operation to perform.
Definition at line 239 of file SUMOAbstractRouter.h.
Referenced by AStarRouter< E, V >::clone(), CHRouter< E, V >::clone(), CHRouterWrapper< E, V >::clone(), DijkstraRouter< E, V >::clone(), and SUMOAbstractRouter< NBRouterEdge, NBVehicle >::getEffort().
|
protectedinherited |
Definition at line 253 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 263 of file SUMOAbstractRouter.h.
Referenced by SUMOAbstractRouter< NBRouterEdge, NBVehicle >::endQuery(), and SUMOAbstractRouter< NBRouterEdge, NBVehicle >::startQuery().
|
privateinherited |
Definition at line 264 of file SUMOAbstractRouter.h.
Referenced by SUMOAbstractRouter< NBRouterEdge, NBVehicle >::endQuery(), and SUMOAbstractRouter< NBRouterEdge, NBVehicle >::~SUMOAbstractRouter().
|
privateinherited |
counters for performance logging
Definition at line 260 of file SUMOAbstractRouter.h.
Referenced by SUMOAbstractRouter< NBRouterEdge, NBVehicle >::endQuery(), and SUMOAbstractRouter< NBRouterEdge, NBVehicle >::~SUMOAbstractRouter().
|
protectedinherited |
The object's operation to perform for travel times.
Definition at line 242 of file SUMOAbstractRouter.h.
Referenced by DijkstraRouter< E, V >::clone(), and SUMOAbstractRouter< NBRouterEdge, NBVehicle >::getTravelTime().
|
privateinherited |
the type of this router
Definition at line 257 of file SUMOAbstractRouter.h.
Referenced by SUMOAbstractRouter< NBRouterEdge, NBVehicle >::~SUMOAbstractRouter().