Eclipse SUMO - Simulation of Urban MObility
Loading...
Searching...
No Matches
AFBuild< E, N, V, M > Class Template Reference

Builds the flags for (multi-level) arc flag routing (Hilger et al.) in its multi-level variant (also called "stripped SHARC" by Delling et al.) More...

#include <AFBuild.h>

Collaboration diagram for AFBuild< E, N, V, M >:
[legend]

Public Types

typedef AFInfo< FlippedEdge< E, N, V > >::ArcInfo ArcInfo
 
typedef KDTreePartition< FlippedEdge< E, N, V >, FlippedNode< E, N, V >, V >::Cell Cell
 
typedef AFInfo< E >::FlagInfo FlagInfo
 
typedef AbstractLookupTable< FlippedEdge< E, N, V >, V > FlippedLookupTable
 

Public Member Functions

 AFBuild (const std::vector< FlippedEdge< E, N, V > * > &flippedEdges, const KDTreePartition< FlippedEdge< E, N, V >, FlippedNode< E, N, V >, V > *const flippedPartition, int numberOfLevels, bool unbuildIsWarning, typename SUMOAbstractRouter< FlippedEdge< E, N, V >, V >::Operation flippedOperation, const std::shared_ptr< const FlippedLookupTable > flippedLookup=nullptr, const bool havePermissions=false, const bool haveRestrictions=false, const std::vector< FlippedEdge< E, N, V > * > *toProhibit=nullptr)
 Constructor.
 
const std::shared_ptr< const FlippedLookupTablegetFlippedLookup ()
 Returns the lookup table for the backward graph with flipped edges.
 
SUMOAbstractRouter< FlippedEdge< E, N, V >, V >::Operation getFlippedOperation ()
 Returns the operation for a backward graph with flipped edges.
 
void init (SUMOTime time, const V *const vehicle, std::vector< FlagInfo * > &flagInfos)
 Initialize the arc flag build.
 
int partitionLevel2SHARCLevel (int partitionLevel)
 Converts a partition level number to a SHARC level number.
 
void setFlippedPartition (const KDTreePartition< FlippedEdge< E, N, V >, FlippedNode< E, N, V >, V > *flippedPartition)
 Set the flipped partition param[in] flippedPartition The flipped partition.
 
int sHARCLevel2PartitionLevel (int sHARCLevel)
 Converts a SHARC level number to a partition level number.
 
 ~AFBuild ()
 Destructor.
 

Data Fields

const double EPS = 0.009
 Maximum difference of two path lengths considered to be equal.
 

Protected Member Functions

void computeArcFlags (SUMOTime msTime, const int sHARCLevel, const Cell *cell, const V *const vehicle)
 Computes the arc flags for a given cell.
 
void computeArcFlags (SUMOTime msTime, int sHARCLevel, const V *const vehicle)
 Computes the arc flags for all cells at a given level.
 
void computeArcFlagsNaive (SUMOTime msTime, const int sHARCLevel, const Cell *cell, const V *const vehicle)
 Computes the arc flags for a given cell (naive version)
 
void putArcFlag (ArcInfo *arcInfo, const int sHARCLevel, const bool isLeftOrLowerCell)
 Put the arc flag of the edge in arcInfo.
 

Protected Attributes

std::vector< ArcInfo * > myArcInfos
 The container of arc informations (for the centralized shortest path tree)
 
AFCentralizedSPTree< FlippedEdge< E, N, V >, FlippedNode< E, N, V >, V > * myCentralizedSPTree
 A Dijkstra based centralized label-correcting algorithm.
 
MsgHandler *const myErrorMsgHandler
 The handler for routing errors.
 
const std::vector< FlippedEdge< E, N, V > * > & myFlippedEdges
 The flipped edges.
 
const std::shared_ptr< const FlippedLookupTablemyFlippedLookupTable
 The lookup table for travel time heuristics.
 
SUMOAbstractRouter< FlippedEdge< E, N, V >, V >::Operation myFlippedOperation
 The object's operation to perform on a backward graph with flipped edges.
 
const KDTreePartition< FlippedEdge< E, N, V >, FlippedNode< E, N, V >, V > * myFlippedPartition
 The partition for the backward graph with flipped edges.
 
const bool myHavePermissions
 The boolean flag indicating whether edge permissions need to be considered or not.
 
const bool myHaveRestrictions
 The boolean flag indicating whether edge restrictions need to be considered or not.
 
Node2EdgeRouter< FlippedEdge< E, N, V >, FlippedNode< E, N, V >, V, M > * myNode2EdgeRouter
 The node-to-edge router (for a backward graph with flipped edges)
 
const int myNumberOfLevels
 The number of levels.
 
const std::vector< FlippedEdge< E, N, V > * > * myProhibited
 The list of explicitly prohibited edges.
 

Private Member Functions

void computeArcFlagsAux (SUMOTime msTime, const int sHARCLevel, const Cell *cell, const V *const vehicle)
 Helper method for computeArcFlags(), which computes the arc flags for a given cell.
 
void initBoundaryEdges (const std::unordered_set< const FlippedEdge< E, N, V > * > &boundaryEdges)
 Initialize the boundary edges param[in] boundaryEdges The boundary edges.
 
void initSupercellEdges (const Cell *supercell, const std::unordered_set< const FlippedEdge< E, N, V > * > &boundaryEdges, size_t numberOfBoundaryNodes)
 Initialize the supercell edges.
 

Detailed Description

template<class E, class N, class V, class M>
class AFBuild< E, N, V, M >

Builds the flags for (multi-level) arc flag routing (Hilger et al.) in its multi-level variant (also called "stripped SHARC" by Delling et al.)

The template parameters are:

Parameters
EThe edge class to use (MSEdge/ROEdge )
NThe node class to use (MSJunction/RONode)
VThe vehicle class to use (MSVehicle/ROVehicle)

Definition at line 82 of file AFBuild.h.

Member Typedef Documentation

◆ ArcInfo

template<class E , class N , class V , class M >
typedef AFInfo<FlippedEdge<E,N,V>>::ArcInfo AFBuild< E, N, V, M >::ArcInfo

Definition at line 87 of file AFBuild.h.

◆ Cell

template<class E , class N , class V , class M >
typedef KDTreePartition<FlippedEdge<E,N,V>,FlippedNode<E,N,V>,V>::Cell AFBuild< E, N, V, M >::Cell

Definition at line 86 of file AFBuild.h.

◆ FlagInfo

template<class E , class N , class V , class M >
typedef AFInfo<E>::FlagInfo AFBuild< E, N, V, M >::FlagInfo

Definition at line 88 of file AFBuild.h.

◆ FlippedLookupTable

template<class E , class N , class V , class M >
typedef AbstractLookupTable<FlippedEdge<E, N, V>, V> AFBuild< E, N, V, M >::FlippedLookupTable

Definition at line 89 of file AFBuild.h.

Constructor & Destructor Documentation

◆ AFBuild()

template<class E , class N , class V , class M >
AFBuild< E, N, V, M >::AFBuild ( const std::vector< FlippedEdge< E, N, V > * > &  flippedEdges,
const KDTreePartition< FlippedEdge< E, N, V >, FlippedNode< E, N, V >, V > *const  flippedPartition,
int  numberOfLevels,
bool  unbuildIsWarning,
typename SUMOAbstractRouter< FlippedEdge< E, N, V >, V >::Operation  flippedOperation,
const std::shared_ptr< const FlippedLookupTable flippedLookup = nullptr,
const bool  havePermissions = false,
const bool  haveRestrictions = false,
const std::vector< FlippedEdge< E, N, V > * > *  toProhibit = nullptr 
)
inline

Constructor.

Parameters
[in]flippedEdgesThe flipped (aka reversed / backward) edges
[in]flippedPartitionThe k-d tree partition of the backward graph with flipped edges
[in]numberOfLevelsThe number of levels
[in]unbuildIsWarningThe flag indicating whether network unbuilds should issue warnings or errors
[in]flippedOperationThe operation for a backward graph with flipped edges
[in]flippedLookupThe lookup table for a backward graph with flipped edges
[in]havePermissionsThe boolean flag indicating whether edge permissions need to be considered or not
[in]haveRestrictionsThe boolean flag indicating whether edge restrictions need to be considered or not
[in]toProhibitThe list of explicitly prohibited edges

Definition at line 102 of file AFBuild.h.

References AFBuild< E, N, V, M >::myArcInfos, AFBuild< E, N, V, M >::myCentralizedSPTree, AFBuild< E, N, V, M >::myFlippedEdges, AFBuild< E, N, V, M >::myHavePermissions, AFBuild< E, N, V, M >::myHaveRestrictions, AFBuild< E, N, V, M >::myNode2EdgeRouter, and SUMOAbstractRouter< E, V >::prohibit().

◆ ~AFBuild()

template<class E , class N , class V , class M >
AFBuild< E, N, V, M >::~AFBuild ( )
inline

Member Function Documentation

◆ computeArcFlags() [1/2]

template<class E , class N , class V , class M >
void AFBuild< E, N, V, M >::computeArcFlags ( SUMOTime  msTime,
const int  sHARCLevel,
const Cell cell,
const V *const  vehicle 
)
protected

Computes the arc flags for a given cell.

Parameters
[in]msTimeThe start time of the routes in milliseconds
sHARCLevelThe SHARC level
[in]cellThe cell
[in]vehicleThe vehicle

Definition at line 392 of file AFBuild.h.

References AFInfo< E >::ArcInfo::effortsToBoundaryNodes, elapsedMs2string(), SysUtils::getCurrentMillis(), and UNREACHABLE.

◆ computeArcFlags() [2/2]

template<class E , class N , class V , class M >
void AFBuild< E, N, V, M >::computeArcFlags ( SUMOTime  msTime,
int  sHARCLevel,
const V *const  vehicle 
)
protected

Computes the arc flags for all cells at a given level.

Parameters
[in]msTimeThe start time of the routes in milliseconds
[in]sHARCLevelThe SHARC level
[in]vehicleThe vehicle

Definition at line 285 of file AFBuild.h.

◆ computeArcFlagsAux()

template<class E , class N , class V , class M >
void AFBuild< E, N, V, M >::computeArcFlagsAux ( SUMOTime  msTime,
const int  sHARCLevel,
const Cell cell,
const V *const  vehicle 
)
private

Helper method for computeArcFlags(), which computes the arc flags for a given cell.

Parameters
[in]msTimeThe start time of the routes in milliseconds
[in]sHARCLevelThe SHARC level
[in]cellThe cell
[in]vehicleThe vehicle

Definition at line 462 of file AFBuild.h.

References AFInfo< E >::FlagInfo::edge, AFInfo< E >::ArcInfo::effortsToBoundaryNodes, elapsedMs2string(), SysUtils::getCurrentMillis(), Named::getIDSecure(), STEPS2TIME, SVC_IGNORING, and UNREACHABLE.

◆ computeArcFlagsNaive()

template<class E , class N , class V , class M >
void AFBuild< E, N, V, M >::computeArcFlagsNaive ( SUMOTime  msTime,
const int  sHARCLevel,
const Cell cell,
const V *const  vehicle 
)
protected

Computes the arc flags for a given cell (naive version)

Parameters
[in]msTimeThe start time of the routes in milliseconds
sHARCLevelThe SHARC level
[in]cellThe cell
[in]vehicleThe vehicle

Definition at line 324 of file AFBuild.h.

References AFInfo< E >::ArcInfo::effortsToBoundaryNodes, elapsedMs2string(), SysUtils::getCurrentMillis(), and UNREACHABLE.

◆ getFlippedLookup()

template<class E , class N , class V , class M >
const std::shared_ptr< const FlippedLookupTable > AFBuild< E, N, V, M >::getFlippedLookup ( )
inline

Returns the lookup table for the backward graph with flipped edges.

Definition at line 139 of file AFBuild.h.

References AFBuild< E, N, V, M >::myFlippedLookupTable.

◆ getFlippedOperation()

template<class E , class N , class V , class M >
SUMOAbstractRouter< FlippedEdge< E, N, V >, V >::Operation AFBuild< E, N, V, M >::getFlippedOperation ( )
inline

Returns the operation for a backward graph with flipped edges.

Definition at line 135 of file AFBuild.h.

References AFBuild< E, N, V, M >::myFlippedOperation.

◆ init()

template<class E , class N , class V , class M >
void AFBuild< E, N, V, M >::init ( SUMOTime  time,
const V *const  vehicle,
std::vector< FlagInfo * > &  flagInfos 
)

Initialize the arc flag build.

Parameters
[in]msTimeThe start time of the routes in milliseconds
[in]vehicleThe vehicle
[in]flagInfosThe arc flag informations

Definition at line 251 of file AFBuild.h.

◆ initBoundaryEdges()

template<class E , class N , class V , class M >
void AFBuild< E, N, V, M >::initBoundaryEdges ( const std::unordered_set< const FlippedEdge< E, N, V > * > &  boundaryEdges)
private

Initialize the boundary edges param[in] boundaryEdges The boundary edges.

Definition at line 663 of file AFBuild.h.

References AFInfo< E >::ArcInfoBase::arcFlags, and AFInfo< E >::ArcInfo::effortsToBoundaryNodes.

◆ initSupercellEdges()

template<class E , class N , class V , class M >
void AFBuild< E, N, V, M >::initSupercellEdges ( const Cell supercell,
const std::unordered_set< const FlippedEdge< E, N, V > * > &  boundaryEdges,
size_t  numberOfBoundaryNodes 
)
private

Initialize the supercell edges.

Parameters
[in]supercellThe supercell
[in]boundaryEdgesThe boundary edges
[in]numberOfBoundaryNodesThe number of boundary nodes

Definition at line 678 of file AFBuild.h.

References AFInfo< E >::ArcInfoBase::arcFlags, and AFInfo< E >::ArcInfo::effortsToBoundaryNodes.

◆ partitionLevel2SHARCLevel()

template<class E , class N , class V , class M >
int AFBuild< E, N, V, M >::partitionLevel2SHARCLevel ( int  partitionLevel)
inline

Converts a partition level number to a SHARC level number.

Parameters
[in]partitionLevelThe partition level
Returns
The SHARC level number corresponding to the given partition level number

Definition at line 158 of file AFBuild.h.

References AFBuild< E, N, V, M >::myNumberOfLevels, and AFRouter< E, N, V, M >::partitionLevel2SHARCLevel().

◆ putArcFlag()

template<class E , class N , class V , class M >
void AFBuild< E, N, V, M >::putArcFlag ( ArcInfo arcInfo,
const int  sHARCLevel,
const bool  isLeftOrLowerCell 
)
protected

Put the arc flag of the edge in arcInfo.

Note
wrt the passed SHARC level, and the boolean flag indicating whether the respective cell is a left or lower one or not
Parameters
[in]arcInfoThe arc information
[in]sHARCLevelThe SHARC level
[in]isLeftOrLowerCellThe boolean flag indicating whether the respective cell is a left or lower one or not

Definition at line 657 of file AFBuild.h.

References AFInfo< E >::ArcInfoBase::arcFlags.

◆ setFlippedPartition()

template<class E , class N , class V , class M >
void AFBuild< E, N, V, M >::setFlippedPartition ( const KDTreePartition< FlippedEdge< E, N, V >, FlippedNode< E, N, V >, V > *  flippedPartition)
inline

Set the flipped partition param[in] flippedPartition The flipped partition.

Definition at line 151 of file AFBuild.h.

References AFBuild< E, N, V, M >::myFlippedPartition.

◆ sHARCLevel2PartitionLevel()

template<class E , class N , class V , class M >
int AFBuild< E, N, V, M >::sHARCLevel2PartitionLevel ( int  sHARCLevel)
inline

Converts a SHARC level number to a partition level number.

Parameters
[in]sHARCLevelThe SHARC level
Returns
The partition level number corresponding to the given SHARC level number

Definition at line 165 of file AFBuild.h.

References AFBuild< E, N, V, M >::myNumberOfLevels, and AFRouter< E, N, V, M >::sHARCLevel2PartitionLevel().

Field Documentation

◆ EPS

template<class E , class N , class V , class M >
const double AFBuild< E, N, V, M >::EPS = 0.009

Maximum difference of two path lengths considered to be equal.

Definition at line 85 of file AFBuild.h.

◆ myArcInfos

template<class E , class N , class V , class M >
std::vector<ArcInfo*> AFBuild< E, N, V, M >::myArcInfos
protected

The container of arc informations (for the centralized shortest path tree)

Definition at line 222 of file AFBuild.h.

Referenced by AFBuild< E, N, V, M >::AFBuild().

◆ myCentralizedSPTree

template<class E , class N , class V , class M >
AFCentralizedSPTree<FlippedEdge<E, N, V>, FlippedNode<E, N, V>, V>* AFBuild< E, N, V, M >::myCentralizedSPTree
protected

A Dijkstra based centralized label-correcting algorithm.

Definition at line 220 of file AFBuild.h.

Referenced by AFBuild< E, N, V, M >::AFBuild(), and AFBuild< E, N, V, M >::~AFBuild().

◆ myErrorMsgHandler

template<class E , class N , class V , class M >
MsgHandler* const AFBuild< E, N, V, M >::myErrorMsgHandler
protected

The handler for routing errors.

Definition at line 204 of file AFBuild.h.

◆ myFlippedEdges

template<class E , class N , class V , class M >
const std::vector<FlippedEdge<E, N, V>*>& AFBuild< E, N, V, M >::myFlippedEdges
protected

The flipped edges.

Definition at line 198 of file AFBuild.h.

Referenced by AFBuild< E, N, V, M >::AFBuild().

◆ myFlippedLookupTable

template<class E , class N , class V , class M >
const std::shared_ptr<const FlippedLookupTable> AFBuild< E, N, V, M >::myFlippedLookupTable
protected

The lookup table for travel time heuristics.

Definition at line 208 of file AFBuild.h.

Referenced by AFBuild< E, N, V, M >::getFlippedLookup().

◆ myFlippedOperation

template<class E , class N , class V , class M >
SUMOAbstractRouter<FlippedEdge<E,N,V>,V>::Operation AFBuild< E, N, V, M >::myFlippedOperation
protected

The object's operation to perform on a backward graph with flipped edges.

Definition at line 206 of file AFBuild.h.

Referenced by AFBuild< E, N, V, M >::getFlippedOperation().

◆ myFlippedPartition

template<class E , class N , class V , class M >
const KDTreePartition<FlippedEdge<E, N, V>, FlippedNode<E, N, V>, V>* AFBuild< E, N, V, M >::myFlippedPartition
protected

The partition for the backward graph with flipped edges.

Definition at line 200 of file AFBuild.h.

Referenced by AFBuild< E, N, V, M >::setFlippedPartition().

◆ myHavePermissions

template<class E , class N , class V , class M >
const bool AFBuild< E, N, V, M >::myHavePermissions
protected

The boolean flag indicating whether edge permissions need to be considered or not.

Definition at line 210 of file AFBuild.h.

Referenced by AFBuild< E, N, V, M >::AFBuild().

◆ myHaveRestrictions

template<class E , class N , class V , class M >
const bool AFBuild< E, N, V, M >::myHaveRestrictions
protected

The boolean flag indicating whether edge restrictions need to be considered or not.

Definition at line 212 of file AFBuild.h.

Referenced by AFBuild< E, N, V, M >::AFBuild().

◆ myNode2EdgeRouter

template<class E , class N , class V , class M >
Node2EdgeRouter<FlippedEdge<E, N, V>, FlippedNode<E, N, V>, V, M>* AFBuild< E, N, V, M >::myNode2EdgeRouter
protected

The node-to-edge router (for a backward graph with flipped edges)

Definition at line 216 of file AFBuild.h.

Referenced by AFBuild< E, N, V, M >::AFBuild(), and AFBuild< E, N, V, M >::~AFBuild().

◆ myNumberOfLevels

template<class E , class N , class V , class M >
const int AFBuild< E, N, V, M >::myNumberOfLevels
protected

The number of levels.

Definition at line 202 of file AFBuild.h.

Referenced by AFBuild< E, N, V, M >::partitionLevel2SHARCLevel(), and AFBuild< E, N, V, M >::sHARCLevel2PartitionLevel().

◆ myProhibited

template<class E , class N , class V , class M >
const std::vector<FlippedEdge<E, N, V>*>* AFBuild< E, N, V, M >::myProhibited
protected

The list of explicitly prohibited edges.

Definition at line 214 of file AFBuild.h.


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