![]() |
Eclipse SUMO - Simulation of Urban MObility
|
Computes the shortest path through a contracted network. More...
#include <CHRouter.h>
Data Structures | |
class | Unidirectional |
Public Types | |
typedef std::pair< const typename SUMOAbstractRouter< E, V >::EdgeInfo *, const typename SUMOAbstractRouter< E, V >::EdgeInfo * > | Meeting |
A meeting point of the two search scopes. More... | |
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 | |
void | buildPathFrom (const typename SUMOAbstractRouter< E, V >::EdgeInfo *rbegin, std::vector< const E * > &edges) |
Builds the path from marked edges. More... | |
void | buildPathFromMeeting (Meeting meeting, std::vector< const E * > &into) const |
normal routing methods More... | |
CHRouter (const std::vector< E * > &edges, bool unbuildIsWarning, typename SUMOAbstractRouter< E, V >::Operation operation, const SUMOVehicleClass svc, SUMOTime weightPeriod, const bool havePermissions, const bool haveRestrictions) | |
Constructor. More... | |
CHRouter (const std::vector< E * > &edges, bool unbuildIsWarning, typename SUMOAbstractRouter< E, V >::Operation operation, const SUMOVehicleClass svc, typename CHBuilder< E, V >::Hierarchy *hierarchy, const bool havePermissions, const bool haveRestrictions) | |
Cloning constructor, should be used only for time independent instances which build a hierarchy only once. More... | |
virtual SUMOAbstractRouter< E, V > * | clone () |
virtual 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 traveltime in the contracted graph. 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) |
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 |
virtual 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) |
trigger hierarchy rebuild More... | |
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 | ~CHRouter () |
Destructor. More... | |
Protected Attributes | |
bool | myAmClean |
whether we are already initialized More... | |
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... | |
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... | |
Operation | myOperation |
The object's operation to perform. More... | |
std::vector< E * > | myProhibited |
The list of explicitly prohibited edges. More... | |
Operation | myTTOperation |
The object's operation to perform for travel times. More... | |
Private Member Functions | |
const E * | getVia (const E *forwardFrom, const E *forwardTo) const |
Private Attributes | |
Unidirectional | myBackwardSearch |
const std::vector< E * > & | myEdges |
all edges with numerical ids More... | |
Unidirectional | myForwardSearch |
the unidirectional search queues More... | |
CHBuilder< E, V >::Hierarchy * | myHierarchy |
CHBuilder< E, V > * | myHierarchyBuilder |
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 SUMOVehicleClass | mySVC |
the permissions for which the hierarchy was constructed More... | |
const std::string | myType |
the type of this router More... | |
SUMOTime | myValidUntil |
the validity duration of the current hierarchy (exclusive) More... | |
const SUMOTime | myWeightPeriod |
the validity duration of one weight interval More... | |
Computes the shortest path through a contracted network.
The template parameters are:
E | The edge class to use (MSEdge/ROEdge) |
V | The vehicle class to use (MSVehicle/ROVehicle) |
PF | The prohibition function to use (prohibited_withPermissions/noProhibitions) |
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.
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 59 of file CHRouter.h.
typedef std::pair<const typename SUMOAbstractRouter<E, V>::EdgeInfo*, const typename SUMOAbstractRouter<E, V>::EdgeInfo*> CHRouter< E, V >::Meeting |
A meeting point of the two search scopes.
Definition at line 63 of file CHRouter.h.
|
inherited |
Type of the function that is used to retrieve the edge effort.
Definition at line 96 of file SUMOAbstractRouter.h.
|
inline |
Constructor.
[in] | validatePermissions | Whether a multi-permission hierarchy shall be built If set to false, the net is pruned in synchronize() and the hierarchy is tailored to the svc |
Definition at line 218 of file CHRouter.h.
|
inline |
Cloning constructor, should be used only for time independent instances which build a hierarchy only once.
Definition at line 235 of file CHRouter.h.
Destructor.
Definition at line 251 of file CHRouter.h.
References CHRouter< E, V >::myHierarchy, and CHRouter< E, V >::myHierarchyBuilder.
|
inlineinherited |
Builds the path from marked edges.
Definition at line 363 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().
|
inline |
normal routing methods
Builds the path from marked edges
Definition at line 346 of file CHRouter.h.
References CHRouter< E, V >::getVia().
Referenced by CHRouter< E, V >::compute().
|
inlinevirtual |
Implements SUMOAbstractRouter< E, V >.
Definition at line 259 of file CHRouter.h.
References MsgHandler::getWarningInstance(), CHRouter< E, V >::myEdges, SUMOAbstractRouter< E, V >::myErrorMsgHandler, SUMOAbstractRouter< E, V >::myHavePermissions, SUMOAbstractRouter< E, V >::myHaveRestrictions, CHRouter< E, V >::myHierarchy, SUMOAbstractRouter< E, V >::myOperation, CHRouter< E, V >::mySVC, CHRouter< E, V >::myWeightPeriod, and SUMOTime_MAX.
|
inlinevirtual |
Builds the route between the given edges using the minimum traveltime in the contracted graph.
Implements SUMOAbstractRouter< E, V >.
Definition at line 295 of file CHRouter.h.
References CHRouter< E, V >::buildPathFromMeeting(), SUMOAbstractRouter< E, V >::endQuery(), MsgHandler::informf(), CHRouter< E, V >::Unidirectional::init(), CHRouter< E, V >::myBackwardSearch, SUMOAbstractRouter< E, V >::myErrorMsgHandler, CHRouter< E, V >::myForwardSearch, CHRouter< E, V >::myHierarchy, CHRouter< E, V >::myHierarchyBuilder, CHRouter< E, V >::myValidUntil, CHRouter< E, V >::myWeightPeriod, CHRouter< E, V >::reset(), SUMOAbstractRouter< E, V >::startQuery(), CHRouter< E, V >::Unidirectional::step(), and toString().
|
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 187 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 202 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(), and MSBaseVehicle::reroute().
|
inlineinherited |
Definition at line 338 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 173 of file SUMOAbstractRouter.h.
References SUMOAbstractRouter< E, V >::myEdgeInfos.
|
inlineinherited |
Definition at line 329 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(), SUMOAbstractRouter< E, V >::setHint(), CHBuilder< E, V >::synchronize(), SUMOAbstractRouter< E, V >::updateViaCost(), and SUMOAbstractRouter< E, V >::updateViaEdgeCost().
|
inlineinherited |
Definition at line 235 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 169 of file SUMOAbstractRouter.h.
References SUMOAbstractRouter< E, V >::myType.
|
inlineprivate |
Definition at line 381 of file CHRouter.h.
References CHRouter< E, V >::myHierarchy.
Referenced by CHRouter< E, V >::buildPathFromMeeting().
|
inlineinherited |
Definition at line 140 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 231 of file SUMOAbstractRouter.h.
References SUMOAbstractRouter< E, V >::myHavePermissions, and SUMOAbstractRouter< E, V >::myHaveRestrictions.
Referenced by SUMOAbstractRouter< E, V >::recomputeCosts(), and SUMOAbstractRouter< E, V >::setHint().
|
inlinevirtual |
Reimplemented from SUMOAbstractRouter< E, V >.
Definition at line 270 of file CHRouter.h.
References WRITE_WARNINGF.
|
inlineinherited |
Definition at line 286 of file SUMOAbstractRouter.h.
References SUMOAbstractRouter< E, V >::getEffort(), SUMOAbstractRouter< E, V >::recomputeCosts(), and STEPS2TIME.
|
inlineinherited |
Definition at line 265 of file SUMOAbstractRouter.h.
References SUMOAbstractRouter< E, V >::isProhibited(), STEPS2TIME, and SUMOAbstractRouter< E, V >::updateViaCost().
Referenced by RORouteDef::addAlternative(), MSTriggeredRerouter::addParkValues(), AStarRouter< E, V >::compute(), DijkstraRouter< 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(), MSBaseVehicle::replaceStop(), MSBaseVehicle::reroute(), MSVehicle::rerouteParkingArea(), and ROMAAssignments::sue().
|
inlinevirtual |
trigger hierarchy rebuild
Reimplemented from SUMOAbstractRouter< E, V >.
Definition at line 278 of file CHRouter.h.
References CHRouter< E, V >::myHierarchy, CHRouter< E, V >::myHierarchyBuilder, CHRouter< E, V >::myValidUntil, and CHRouter< E, V >::myWeightPeriod.
Referenced by CHRouter< E, V >::compute().
|
inlineinherited |
Definition at line 347 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 343 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 298 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 333 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 249 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(), SUMOAbstractRouter< E, V >::recomputeCosts(), and SUMOAbstractRouter< E, V >::setHint().
|
inlineinherited |
Definition at line 239 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 389 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 386 of file SUMOAbstractRouter.h.
Referenced by DijkstraRouter< E, V >::clone(), DijkstraRouter< E, V >::compute(), and SUMOAbstractRouter< E, V >::setAutoBulkMode().
|
private |
Definition at line 398 of file CHRouter.h.
Referenced by CHRouter< E, V >::compute().
|
protectedinherited |
whether we are currently operating several route queries in a bulk
Definition at line 383 of file SUMOAbstractRouter.h.
Referenced by AStarRouter< E, V >::compute(), DijkstraRouter< E, V >::compute(), and SUMOAbstractRouter< E, V >::setBulkMode().
|
protectedinherited |
The container of edge information.
Definition at line 401 of file SUMOAbstractRouter.h.
Referenced by AStarRouter< E, V >::AStarRouter(), AStarRouter< E, V >::clone(), DijkstraRouter< E, V >::clone(), AStarRouter< E, V >::compute(), DijkstraRouter< E, V >::compute(), DijkstraRouter< E, V >::DijkstraRouter(), SUMOAbstractRouter< E, V >::getEdgeInfo(), SUMOAbstractRouter< E, V >::init(), SUMOAbstractRouter< E, V >::prohibit(), and SUMOAbstractRouter< E, V >::setHint().
|
private |
all edges with numerical ids
Definition at line 394 of file CHRouter.h.
Referenced by CHRouter< E, V >::clone().
|
protectedinherited |
the handler for routing errors
Definition at line 374 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 |
the unidirectional search queues
Definition at line 397 of file CHRouter.h.
Referenced by CHRouter< E, V >::compute().
|
protectedinherited |
list of visited Edges (for resetting)
Definition at line 406 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 404 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 392 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 395 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().
Definition at line 401 of file CHRouter.h.
Referenced by CHRouter< E, V >::clone(), CHRouter< E, V >::compute(), CHRouter< E, V >::getVia(), CHRouter< E, V >::reset(), and CHRouter< E, V >::~CHRouter().
Definition at line 400 of file CHRouter.h.
Referenced by CHRouter< E, V >::compute(), CHRouter< E, V >::reset(), and CHRouter< E, V >::~CHRouter().
|
privateinherited |
Definition at line 414 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 377 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 |
The list of explicitly prohibited edges.
Definition at line 398 of file SUMOAbstractRouter.h.
Referenced by SUMOAbstractRouter< E, V >::prohibit().
|
privateinherited |
the time spent querying in milliseconds
Definition at line 416 of file SUMOAbstractRouter.h.
Referenced by SUMOAbstractRouter< E, V >::endQuery(), and SUMOAbstractRouter< E, V >::startQuery().
|
privateinherited |
Definition at line 417 of file SUMOAbstractRouter.h.
Referenced by SUMOAbstractRouter< E, V >::endQuery(), and SUMOAbstractRouter< E, V >::~SUMOAbstractRouter().
|
privateinherited |
counters for performance logging
Definition at line 413 of file SUMOAbstractRouter.h.
Referenced by SUMOAbstractRouter< E, V >::endQuery(), and SUMOAbstractRouter< E, V >::~SUMOAbstractRouter().
|
private |
the permissions for which the hierarchy was constructed
Definition at line 410 of file CHRouter.h.
Referenced by CHRouter< E, V >::clone().
|
protectedinherited |
The object's operation to perform for travel times.
Definition at line 380 of file SUMOAbstractRouter.h.
Referenced by DijkstraRouter< E, V >::clone(), and SUMOAbstractRouter< E, V >::getTravelTime().
|
privateinherited |
the type of this router
Definition at line 410 of file SUMOAbstractRouter.h.
Referenced by SUMOAbstractRouter< E, V >::getType(), and SUMOAbstractRouter< E, V >::~SUMOAbstractRouter().
the validity duration of the current hierarchy (exclusive)
Definition at line 407 of file CHRouter.h.
Referenced by CHRouter< E, V >::compute(), and CHRouter< E, V >::reset().
the validity duration of one weight interval
Definition at line 404 of file CHRouter.h.
Referenced by CHRouter< E, V >::clone(), CHRouter< E, V >::compute(), and CHRouter< E, V >::reset().