SUMO - Simulation of Urban MObility
|
Computes the shortest path through a contracted network. More...
#include <CHRouter.h>
Data Structures | |
class | CHConnection |
Forward/backward connection with associated FORWARD cost. More... | |
class | CHInfo |
class | CHInfoComparator |
class | Connection |
Forward/backward connection with associated forward/backward cost. More... | |
struct | EdgeInfo |
struct | Shortcut |
class | Unidirectional |
Public Types | |
typedef std::pair< const CHConnection *, const CHConnection * > | CHConnectionPair |
typedef std::vector < CHConnectionPair > | CHConnectionPairs |
typedef std::vector< CHConnection > | CHConnections |
typedef std::pair< const E *, const E * > | ConstEdgePair |
contraction related members More... | |
typedef std::pair< E *, E * > | EdgePair |
typedef std::set< const E * > | EdgeSet |
A set of (found) Edges. More... | |
typedef std::pair< const EdgeInfo *, const EdgeInfo * > | Meeting |
A meeting point of the two search scopes. More... | |
typedef SUMOReal(* | Operation )(const E *const, const V *const, SUMOReal) |
Type of the function that is used to retrieve the edge effort. More... | |
typedef std::vector< const E * > | Result |
The found route (used as output parameter) More... | |
typedef std::vector< Shortcut > | Shortcuts |
typedef std::map < ConstEdgePair, const E * > | ShortcutVia |
Public Member Functions | |
void | buildPathFromMeeting (Meeting meeting, Result &into) |
normal routing methods More... | |
CHRouter (size_t numEdges, bool unbuildIsWarning, Operation operation, const SUMOVehicleClass svc, SUMOTime weightPeriod, bool validatePermissions) | |
Constructor. More... | |
virtual SUMOAbstractRouter< E, V > * | clone () const |
virtual void | compute (const E *from, const E *to, const V *const vehicle, SUMOTime msTime, std::vector< const E * > &into)=0 |
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. More... | |
virtual void | compute (const E *from, const E *to, const V *const vehicle, SUMOTime msTime, Result &into) |
Builds the route between the given edges using the minimum traveltime in the contracted graph. More... | |
void | endQuery (int visits) |
SUMOReal | getEffort (const E *const e, const V *const v, SUMOReal t) const |
virtual void | prepare (const E *, const V *, bool) |
SUMOReal | recomputeCosts (const std::vector< const E * > &edges, const V *const v, SUMOTime msTime) const |
void | startQuery () |
virtual | ~CHRouter () |
Destructor. More... | |
Protected Attributes | |
Operation | myOperation |
The object's operation to perform. More... | |
Private Member Functions | |
void | buildContractionHierarchy (SUMOTime time, const V *const vehicle) |
void | debugPrintQueue (std::vector< CHInfo * > &queue) |
void | disconnect (CHConnections &connections, CHInfo *other) |
remove all connections to/from the given edge (assume it exists only once) More... | |
CHInfo * | getCHInfo (const E *const edge) |
const E * | getVia (const E *forwardFrom, const E *forwardTo) |
void | synchronize (CHInfo &info, SUMOReal time, const V *const vehicle) |
copy connections from the original net (modified destructively during contraction) More... | |
bool | tryUpdateFront (std::vector< CHInfo * > &queue) |
tries to update the priority of the first edge More... | |
Private Attributes | |
Unidirectional | myBackwardSearch |
std::vector< CHInfo > | myCHInfos |
static vector for lookup More... | |
CHInfoComparator | myCmp |
Comparator for contraction priority. More... | |
MsgHandler *const | myErrorMsgHandler |
the handler for routing errors More... | |
Unidirectional | myForwardSearch |
the unidirectional search queues More... | |
ShortcutVia | myShortcuts |
map from (forward) shortcut to via-Edge More... | |
SPTree< CHInfo, CHConnection > * | mySPTree |
the shortest path tree to use when searching for shortcuts More... | |
SUMOVehicleClass | mySVC |
the permissions for which the hierarchy was constructed More... | |
int | myUpdateCount |
counters for performance logging 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_withRestrictions/prohibited_noRestrictions) |
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 74 of file CHRouter.h.
typedef std::pair<const CHConnection*, const CHConnection*> CHRouter< E, V, PF >::CHConnectionPair |
Definition at line 312 of file CHRouter.h.
typedef std::vector<CHConnectionPair> CHRouter< E, V, PF >::CHConnectionPairs |
Definition at line 313 of file CHRouter.h.
typedef std::vector<CHConnection> CHRouter< E, V, PF >::CHConnections |
Definition at line 311 of file CHRouter.h.
typedef std::pair<const E*, const E*> CHRouter< E, V, PF >::ConstEdgePair |
contraction related members
Definition at line 446 of file CHRouter.h.
Definition at line 447 of file CHRouter.h.
A set of (found) Edges.
Definition at line 86 of file CHRouter.h.
typedef std::pair<const EdgeInfo*, const EdgeInfo*> CHRouter< E, V, PF >::Meeting |
A meeting point of the two search scopes.
Definition at line 83 of file CHRouter.h.
typedef SUMOReal(* CHRouter< E, V, PF >::Operation)(const E *const, const V *const, SUMOReal) |
Type of the function that is used to retrieve the edge effort.
Definition at line 80 of file CHRouter.h.
The found route (used as output parameter)
Definition at line 89 of file CHRouter.h.
Definition at line 458 of file CHRouter.h.
typedef std::map<ConstEdgePair, const E*> CHRouter< E, V, PF >::ShortcutVia |
Definition at line 459 of file CHRouter.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 vClass of the defaultVehicle |
Definition at line 321 of file CHRouter.h.
References CHRouter< E, V, PF >::myCHInfos.
|
inlineprivate |
Definition at line 698 of file CHRouter.h.
References CHRouter< E, V, PF >::CHInfo::approaching, CHRouter< E, V, PF >::CHConnection::cost, CHRouter< E, V, PF >::disconnect(), CHRouter< E, V, PF >::CHInfo::edge, MsgHandler::endProcessMsg(), CHRouter< E, V, PF >::CHInfo::followers, CHRouter< E, V, PF >::getCHInfo(), SysUtils::getCurrentMillis(), CHRouter< E, V, PF >::Unidirectional::getEdgeInfo(), MsgHandler::getMessageInstance(), max, CHRouter< E, V, PF >::myBackwardSearch, CHRouter< E, V, PF >::myCHInfos, CHRouter< E, V, PF >::myCmp, CHRouter< E, V, PF >::myForwardSearch, CHRouter< E, V, PF >::myShortcuts, CHRouter< E, V, PF >::mySPTree, CHRouter< E, V, PF >::mySVC, CHRouter< E, V, PF >::myUpdateCount, CHRouter< E, V, PF >::myValidUntil, CHRouter< E, V, PF >::myWeightPeriod, CHRouter< E, V, PF >::CHConnection::permissions, CHRouter< E, V, PF >::CHInfo::permissions, CHRouter< E, V, PF >::CHInfo::priority, PROGRESS_BEGIN_MESSAGE, PROGRESS_DONE_MESSAGE, CHRouter< E, V, PF >::EdgeInfo::rank, CHRouter< E, V, PF >::CHInfo::rank, CHRouter< E, V, PF >::Unidirectional::reset(), CHRouter< E, V, PF >::CHInfo::shortcuts, STEPS2TIME, SUMOReal, SumoVehicleClassStrings, CHRouter< E, V, PF >::synchronize(), CHRouter< E, V, PF >::CHConnection::target, time2string(), toString(), CHRouter< E, V, PF >::tryUpdateFront(), CHRouter< E, V, PF >::CHInfo::updatePriority(), CHRouter< E, V, PF >::EdgeInfo::upward, and WRITE_MESSAGE.
Referenced by CHRouter< E, V, PF >::compute().
|
inline |
normal routing methods
Builds the path from marked edges
Definition at line 412 of file CHRouter.h.
References CHRouter< E, V, PF >::EdgeInfo::edge, CHRouter< E, V, PF >::getVia(), and CHRouter< E, V, PF >::EdgeInfo::prev.
Referenced by CHRouter< E, V, PF >::compute().
|
inlinevirtual |
Implements SUMOAbstractRouter< E, V >.
Definition at line 345 of file CHRouter.h.
References MsgHandler::getWarningInstance(), CHRouter< E, V, PF >::myCHInfos, CHRouter< E, V, PF >::myErrorMsgHandler, SUMOAbstractRouter< E, V >::myOperation, CHRouter< E, V, PF >::mySPTree, CHRouter< E, V, PF >::mySVC, and CHRouter< E, V, PF >::myWeightPeriod.
|
pure virtualinherited |
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.
Implemented in PedestrianRouter< E, L, N, INTERNALROUTER >, PedestrianRouter< E, L, N, DijkstraRouterTT< PedestrianEdge< E, L, N >, PedestrianTrip< E, N >, prohibited_withRestrictions< PedestrianEdge< E, L, N >, PedestrianTrip< E, N > > > >, BulkStarRouter< E, V, PF >, AStarRouter< E, V, PF >, AStarRouter< MSEdge, SUMOVehicle, prohibited_withRestrictions< MSEdge, SUMOVehicle > >, DijkstraRouterEffort< E, V, PF >, DijkstraRouterEffort< MSEdge, SUMOVehicle, prohibited_withRestrictions< MSEdge, SUMOVehicle > >, DijkstraRouterTT< E, V, PF >, DijkstraRouterTT< PedestrianEdge< E, L, N >, PedestrianTrip< E, N >, prohibited_withRestrictions< PedestrianEdge< E, L, N >, PedestrianTrip< E, N > > >, DijkstraRouterTT< MSEdge, SUMOVehicle, prohibited_withRestrictions< MSEdge, SUMOVehicle > >, and CHRouterWrapper< E, V, PF >.
Referenced by TraCIServerAPI_Simulation::commandDistanceRequest(), ROMAAssignments::getKPaths(), ROMAAssignments::incremental(), MSTriggeredRerouter::notifyEnter(), RORouteDef::preComputeCurrentRoute(), TraCIServerAPI_Vehicle::processSet(), RORouteDef::repairCurrentRoute(), MSBaseVehicle::reroute(), and ROMAAssignments::sue().
|
inlinevirtual |
Builds the route between the given edges using the minimum traveltime in the contracted graph.
Definition at line 354 of file CHRouter.h.
References CHRouter< E, V, PF >::buildContractionHierarchy(), CHRouter< E, V, PF >::buildPathFromMeeting(), SUMOAbstractRouter< E, V >::endQuery(), MsgHandler::inform(), CHRouter< E, V, PF >::Unidirectional::init(), max, CHRouter< E, V, PF >::myBackwardSearch, CHRouter< E, V, PF >::myErrorMsgHandler, CHRouter< E, V, PF >::myForwardSearch, CHRouter< E, V, PF >::mySPTree, CHRouter< E, V, PF >::mySVC, CHRouter< E, V, PF >::myValidUntil, CHRouter< E, V, PF >::myWeightPeriod, SUMOAbstractRouter< E, V >::startQuery(), CHRouter< E, V, PF >::Unidirectional::step(), SUMOReal, SVC_IGNORING, and toString().
|
inlineprivate |
Definition at line 825 of file CHRouter.h.
References CHRouter< E, V, PF >::CHInfo::edge, and CHRouter< E, V, PF >::CHInfo::priority.
Referenced by CHRouter< E, V, PF >::tryUpdateFront().
|
inlineprivate |
remove all connections to/from the given edge (assume it exists only once)
Definition at line 687 of file CHRouter.h.
Referenced by CHRouter< E, V, PF >::buildContractionHierarchy().
|
inlineinherited |
Definition at line 100 of file SUMOAbstractRouter.h.
Referenced by DijkstraRouterTT< MSEdge, SUMOVehicle, prohibited_withRestrictions< MSEdge, SUMOVehicle > >::compute(), DijkstraRouterEffort< MSEdge, SUMOVehicle, prohibited_withRestrictions< MSEdge, SUMOVehicle > >::compute(), AStarRouter< MSEdge, SUMOVehicle, prohibited_withRestrictions< MSEdge, SUMOVehicle > >::compute(), BulkStarRouter< E, V, PF >::compute(), and CHRouter< E, V, PF >::compute().
|
inlineprivate |
Definition at line 652 of file CHRouter.h.
References CHRouter< E, V, PF >::myCHInfos.
Referenced by CHRouter< E, V, PF >::buildContractionHierarchy(), and CHRouter< E, V, PF >::synchronize().
|
inlineinherited |
Definition at line 91 of file SUMOAbstractRouter.h.
Referenced by DijkstraRouterTT< MSEdge, SUMOVehicle, prohibited_withRestrictions< MSEdge, SUMOVehicle > >::compute(), DijkstraRouterEffort< MSEdge, SUMOVehicle, prohibited_withRestrictions< MSEdge, SUMOVehicle > >::compute(), AStarRouter< MSEdge, SUMOVehicle, prohibited_withRestrictions< MSEdge, SUMOVehicle > >::compute(), BulkStarRouter< E, V, PF >::compute(), CHRouterWrapper< E, V, PF >::recomputeCosts(), DijkstraRouterEffort< MSEdge, SUMOVehicle, prohibited_withRestrictions< MSEdge, SUMOVehicle > >::recomputeCosts(), DijkstraRouterTT< MSEdge, SUMOVehicle, prohibited_withRestrictions< MSEdge, SUMOVehicle > >::recomputeCosts(), AStarRouter< MSEdge, SUMOVehicle, prohibited_withRestrictions< MSEdge, SUMOVehicle > >::recomputeCosts(), BulkStarRouter< E, V, PF >::recomputeCosts(), CHRouter< E, V, PF >::recomputeCosts(), and CHRouter< E, V, PF >::synchronize().
|
inlineprivate |
Definition at line 794 of file CHRouter.h.
References CHRouter< E, V, PF >::myShortcuts.
Referenced by CHRouter< E, V, PF >::buildPathFromMeeting().
|
inlinevirtualinherited |
Reimplemented in BulkStarRouter< E, V, PF >.
Definition at line 87 of file SUMOAbstractRouter.h.
Referenced by RORouteAggregator::processAllRoutes().
|
inlinevirtual |
Implements SUMOAbstractRouter< E, V >.
Definition at line 397 of file CHRouter.h.
References SUMOAbstractRouter< E, V >::getEffort(), STEPS2TIME, and SUMOReal.
|
inlineinherited |
Definition at line 95 of file SUMOAbstractRouter.h.
Referenced by DijkstraRouterTT< MSEdge, SUMOVehicle, prohibited_withRestrictions< MSEdge, SUMOVehicle > >::compute(), DijkstraRouterEffort< MSEdge, SUMOVehicle, prohibited_withRestrictions< MSEdge, SUMOVehicle > >::compute(), AStarRouter< MSEdge, SUMOVehicle, prohibited_withRestrictions< MSEdge, SUMOVehicle > >::compute(), BulkStarRouter< E, V, PF >::compute(), and CHRouter< E, V, PF >::compute().
|
inlineprivate |
copy connections from the original net (modified destructively during contraction)
Definition at line 658 of file CHRouter.h.
References CHRouter< E, V, PF >::CHInfo::approaching, CHRouter< E, V, PF >::CHInfo::edge, CHRouter< E, V, PF >::CHInfo::followers, CHRouter< E, V, PF >::getCHInfo(), SUMOAbstractRouter< E, V >::getEffort(), CHRouter< E, V, PF >::mySPTree, CHRouter< E, V, PF >::mySVC, and SUMOReal.
Referenced by CHRouter< E, V, PF >::buildContractionHierarchy().
|
inlineprivate |
tries to update the priority of the first edge
Definition at line 808 of file CHRouter.h.
References CHRouter< E, V, PF >::debugPrintQueue(), CHRouter< E, V, PF >::CHInfo::edge, max, CHRouter< E, V, PF >::myCmp, CHRouter< E, V, PF >::mySPTree, CHRouter< E, V, PF >::myUpdateCount, and CHRouter< E, V, PF >::CHInfo::updatePriority().
Referenced by CHRouter< E, V, PF >::buildContractionHierarchy().
|
private |
Definition at line 839 of file CHRouter.h.
Referenced by CHRouter< E, V, PF >::buildContractionHierarchy(), and CHRouter< E, V, PF >::compute().
static vector for lookup
Definition at line 845 of file CHRouter.h.
Referenced by CHRouter< E, V, PF >::buildContractionHierarchy(), CHRouter< E, V, PF >::CHRouter(), CHRouter< E, V, PF >::clone(), and CHRouter< E, V, PF >::getCHInfo().
|
private |
Comparator for contraction priority.
Definition at line 848 of file CHRouter.h.
Referenced by CHRouter< E, V, PF >::buildContractionHierarchy(), and CHRouter< E, V, PF >::tryUpdateFront().
|
private |
the handler for routing errors
Definition at line 835 of file CHRouter.h.
Referenced by CHRouter< E, V, PF >::clone(), and CHRouter< E, V, PF >::compute().
|
private |
the unidirectional search queues
Definition at line 838 of file CHRouter.h.
Referenced by CHRouter< E, V, PF >::buildContractionHierarchy(), and CHRouter< E, V, PF >::compute().
|
protectedinherited |
The object's operation to perform.
Definition at line 107 of file SUMOAbstractRouter.h.
Referenced by DijkstraRouterEffort< MSEdge, SUMOVehicle, prohibited_withRestrictions< MSEdge, SUMOVehicle > >::clone(), DijkstraRouterTT< MSEdge, SUMOVehicle, prohibited_withRestrictions< MSEdge, SUMOVehicle > >::clone(), AStarRouter< MSEdge, SUMOVehicle, prohibited_withRestrictions< MSEdge, SUMOVehicle > >::clone(), CHRouterWrapper< E, V, PF >::clone(), BulkStarRouter< E, V, PF >::clone(), CHRouter< E, V, PF >::clone(), and SUMOAbstractRouter< E, PedestrianTrip< E, N > >::getEffort().
|
private |
map from (forward) shortcut to via-Edge
Definition at line 842 of file CHRouter.h.
Referenced by CHRouter< E, V, PF >::buildContractionHierarchy(), and CHRouter< E, V, PF >::getVia().
|
private |
the shortest path tree to use when searching for shortcuts
Definition at line 851 of file CHRouter.h.
Referenced by CHRouter< E, V, PF >::buildContractionHierarchy(), CHRouter< E, V, PF >::clone(), CHRouter< E, V, PF >::compute(), CHRouter< E, V, PF >::synchronize(), CHRouter< E, V, PF >::tryUpdateFront(), and CHRouter< E, V, PF >::~CHRouter().
|
private |
the permissions for which the hierarchy was constructed
Definition at line 860 of file CHRouter.h.
Referenced by CHRouter< E, V, PF >::buildContractionHierarchy(), CHRouter< E, V, PF >::clone(), CHRouter< E, V, PF >::compute(), and CHRouter< E, V, PF >::synchronize().
counters for performance logging
Definition at line 863 of file CHRouter.h.
Referenced by CHRouter< E, V, PF >::buildContractionHierarchy(), and CHRouter< E, V, PF >::tryUpdateFront().
the validity duration of the current hierarchy (exclusive)
Definition at line 857 of file CHRouter.h.
Referenced by CHRouter< E, V, PF >::buildContractionHierarchy(), and CHRouter< E, V, PF >::compute().
the validity duration of one weight interval
Definition at line 854 of file CHRouter.h.
Referenced by CHRouter< E, V, PF >::buildContractionHierarchy(), CHRouter< E, V, PF >::clone(), and CHRouter< E, V, PF >::compute().