SUMO - Simulation of Urban MObility
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Pages
CHRouter< E, V, PF > Class Template Referenceabstract

Computes the shortest path through a contracted network. More...

#include <CHRouter.h>

Inheritance diagram for CHRouter< E, V, PF >:
Inheritance graph
Collaboration diagram for CHRouter< E, V, PF >:
Collaboration graph

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< CHConnectionCHConnections
 
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< ShortcutShortcuts
 
typedef std::map
< ConstEdgePair, const E * > 
ShortcutVia
 

Public Member Functions

void buildPathFromMeeting (Meeting meeting, Result &into)
 normal routing methods More...
 
 CHRouter (const std::vector< E * > &edges, bool unbuildIsWarning, Operation operation, const SUMOVehicleClass svc, SUMOTime weightPeriod, bool validatePermissions)
 Constructor. 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)=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 bool 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
 
SUMOReal recomputeCosts (const std::vector< const E * > &edges, const V *const v, SUMOTime msTime) const
 
void setBulkMode (const bool mode)
 
void startQuery ()
 
virtual ~CHRouter ()
 Destructor. More...
 

Protected Attributes

bool myBulkMode
 whether we are currently operating several route queries in a bulk More...
 
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...
 
CHInfogetCHInfo (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< CHInfomyCHInfos
 static vector for lookup More...
 
CHInfoComparator myCmp
 Comparator for contraction priority. More...
 
const std::vector< E * > & myEdges
 all edges with numerical ids 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...
 

Detailed Description

template<class E, class V, class PF>
class CHRouter< E, V, PF >

Computes the shortest path through a contracted network.

The template parameters are:

Parameters
EThe edge class to use (MSEdge/ROEdge)
VThe vehicle class to use (MSVehicle/ROVehicle)
PFThe 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.

Definition at line 74 of file CHRouter.h.

Member Typedef Documentation

template<class E, class V, class PF>
typedef std::pair<const CHConnection*, const CHConnection*> CHRouter< E, V, PF >::CHConnectionPair

Definition at line 312 of file CHRouter.h.

template<class E, class V, class PF>
typedef std::vector<CHConnectionPair> CHRouter< E, V, PF >::CHConnectionPairs

Definition at line 313 of file CHRouter.h.

template<class E, class V, class PF>
typedef std::vector<CHConnection> CHRouter< E, V, PF >::CHConnections

Definition at line 311 of file CHRouter.h.

template<class E, class V, class PF>
typedef std::pair<const E*, const E*> CHRouter< E, V, PF >::ConstEdgePair

contraction related members

Definition at line 450 of file CHRouter.h.

template<class E, class V, class PF>
typedef std::pair<E*, E*> CHRouter< E, V, PF >::EdgePair

Definition at line 451 of file CHRouter.h.

template<class E, class V, class PF>
typedef std::set<const E*> CHRouter< E, V, PF >::EdgeSet

A set of (found) Edges.

Definition at line 86 of file CHRouter.h.

template<class E, class V, class PF>
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.

template<class E, class V, class PF>
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.

template<class E, class V, class PF>
typedef std::vector<const E*> CHRouter< E, V, PF >::Result

The found route (used as output parameter)

Definition at line 89 of file CHRouter.h.

template<class E, class V, class PF>
typedef std::vector<Shortcut> CHRouter< E, V, PF >::Shortcuts

Definition at line 462 of file CHRouter.h.

template<class E, class V, class PF>
typedef std::map<ConstEdgePair, const E*> CHRouter< E, V, PF >::ShortcutVia

Definition at line 463 of file CHRouter.h.

Constructor & Destructor Documentation

template<class E, class V, class PF>
CHRouter< E, V, PF >::CHRouter ( const std::vector< E * > &  edges,
bool  unbuildIsWarning,
Operation  operation,
const SUMOVehicleClass  svc,
SUMOTime  weightPeriod,
bool  validatePermissions 
)
inline

Constructor.

Parameters
[in]validatePermissionsWhether 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
Note
: defaultVehicle is not transient and must be kept after constructor finishes

Definition at line 321 of file CHRouter.h.

References CHRouter< E, V, PF >::myCHInfos.

template<class E, class V, class PF>
virtual CHRouter< E, V, PF >::~CHRouter ( )
inlinevirtual

Destructor.

Definition at line 341 of file CHRouter.h.

References CHRouter< E, V, PF >::mySPTree.

Member Function Documentation

template<class E, class V, class PF>
void CHRouter< E, V, PF >::buildContractionHierarchy ( SUMOTime  time,
const V *const  vehicle 
)
inlineprivate
template<class E, class V, class PF>
void CHRouter< E, V, PF >::buildPathFromMeeting ( Meeting  meeting,
Result into 
)
inline

normal routing methods

Builds the path from marked edges

Definition at line 416 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().

template<class E, class V>
virtual bool SUMOAbstractRouter< E, V >::compute ( const E *  from,
const E *  to,
const V *const  vehicle,
SUMOTime  msTime,
std::vector< const E * > &  into 
)
pure virtualinherited
template<class E, class V, class PF>
virtual bool CHRouter< E, V, PF >::compute ( const E *  from,
const E *  to,
const V *const  vehicle,
SUMOTime  msTime,
Result into 
)
inlinevirtual
template<class E, class V, class PF>
void CHRouter< E, V, PF >::debugPrintQueue ( std::vector< CHInfo * > &  queue)
inlineprivate
template<class E, class V, class PF>
void CHRouter< E, V, PF >::disconnect ( CHConnections connections,
CHInfo other 
)
inlineprivate

remove all connections to/from the given edge (assume it exists only once)

Definition at line 691 of file CHRouter.h.

Referenced by CHRouter< E, V, PF >::buildContractionHierarchy().

template<class E, class V, class PF>
CHInfo* CHRouter< E, V, PF >::getCHInfo ( const E *const  edge)
inlineprivate
template<class E, class V, class PF>
const E* CHRouter< E, V, PF >::getVia ( const E *  forwardFrom,
const E *  forwardTo 
)
inlineprivate

Definition at line 798 of file CHRouter.h.

References CHRouter< E, V, PF >::myShortcuts.

Referenced by CHRouter< E, V, PF >::buildPathFromMeeting().

template<class E, class V, class PF>
SUMOReal CHRouter< E, V, PF >::recomputeCosts ( const std::vector< const E * > &  edges,
const V *const  v,
SUMOTime  msTime 
) const
inlinevirtual

Implements SUMOAbstractRouter< E, V >.

Definition at line 401 of file CHRouter.h.

References SUMOAbstractRouter< E, V >::getEffort(), STEPS2TIME, and SUMOReal.

template<class E, class V>
void SUMOAbstractRouter< E, V >::setBulkMode ( const bool  mode)
inlineinherited

Definition at line 101 of file SUMOAbstractRouter.h.

Referenced by ROMAAssignments::incremental().

template<class E, class V, class PF>
void CHRouter< E, V, PF >::synchronize ( CHInfo info,
SUMOReal  time,
const V *const  vehicle 
)
inlineprivate
template<class E, class V, class PF>
bool CHRouter< E, V, PF >::tryUpdateFront ( std::vector< CHInfo * > &  queue)
inlineprivate

Field Documentation

template<class E, class V, class PF>
Unidirectional CHRouter< E, V, PF >::myBackwardSearch
private
template<class E, class V, class PF>
std::vector<CHInfo> CHRouter< E, V, PF >::myCHInfos
private
template<class E, class V, class PF>
CHInfoComparator CHRouter< E, V, PF >::myCmp
private

Comparator for contraction priority.

Definition at line 855 of file CHRouter.h.

Referenced by CHRouter< E, V, PF >::buildContractionHierarchy(), and CHRouter< E, V, PF >::tryUpdateFront().

template<class E, class V, class PF>
const std::vector<E*>& CHRouter< E, V, PF >::myEdges
private

all edges with numerical ids

Definition at line 839 of file CHRouter.h.

Referenced by CHRouter< E, V, PF >::clone().

template<class E, class V, class PF>
MsgHandler* const CHRouter< E, V, PF >::myErrorMsgHandler
private

the handler for routing errors

Definition at line 842 of file CHRouter.h.

Referenced by CHRouter< E, V, PF >::clone(), and CHRouter< E, V, PF >::compute().

template<class E, class V, class PF>
Unidirectional CHRouter< E, V, PF >::myForwardSearch
private

the unidirectional search queues

Definition at line 845 of file CHRouter.h.

Referenced by CHRouter< E, V, PF >::buildContractionHierarchy(), and CHRouter< E, V, PF >::compute().

template<class E, class V, class PF>
ShortcutVia CHRouter< E, V, PF >::myShortcuts
private

map from (forward) shortcut to via-Edge

Definition at line 849 of file CHRouter.h.

Referenced by CHRouter< E, V, PF >::buildContractionHierarchy(), and CHRouter< E, V, PF >::getVia().

template<class E, class V, class PF>
SPTree<CHInfo, CHConnection>* CHRouter< E, V, PF >::mySPTree
private
template<class E, class V, class PF>
SUMOVehicleClass CHRouter< E, V, PF >::mySVC
private

the permissions for which the hierarchy was constructed

Definition at line 867 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().

template<class E, class V, class PF>
int CHRouter< E, V, PF >::myUpdateCount
private

counters for performance logging

Definition at line 870 of file CHRouter.h.

Referenced by CHRouter< E, V, PF >::buildContractionHierarchy(), and CHRouter< E, V, PF >::tryUpdateFront().

template<class E, class V, class PF>
SUMOTime CHRouter< E, V, PF >::myValidUntil
private

the validity duration of the current hierarchy (exclusive)

Definition at line 864 of file CHRouter.h.

Referenced by CHRouter< E, V, PF >::buildContractionHierarchy(), and CHRouter< E, V, PF >::compute().

template<class E, class V, class PF>
const SUMOTime CHRouter< E, V, PF >::myWeightPeriod
private

the validity duration of one weight interval

Definition at line 861 of file CHRouter.h.

Referenced by CHRouter< E, V, PF >::buildContractionHierarchy(), CHRouter< E, V, PF >::clone(), and CHRouter< E, V, PF >::compute().


The documentation for this class was generated from the following file: