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::map< const FlippedEdge< E, N, V > , double > *toProhibit=nullptr)
	Constructor.
const std::shared_ptr< const FlippedLookupTable >	getFlippedLookup ()
	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 FlippedLookupTable >	myFlippedLookupTable
	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::map< const FlippedEdge< E, N, V > , double >	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

E	The edge class to use (MSEdge/ROEdge )
N	The node class to use (MSJunction/RONode)
V	The 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::map< const FlippedEdge< E, N, V > , double >	toProhibit = nullptr )

inline

Constructor.

Parameters

[in]	flippedEdges	The flipped (aka reversed / backward) edges
[in]	flippedPartition	The k-d tree partition of the backward graph with flipped edges
[in]	numberOfLevels	The number of levels
[in]	unbuildIsWarning	The flag indicating whether network unbuilds should issue warnings or errors
[in]	flippedOperation	The operation for a backward graph with flipped edges
[in]	flippedLookup	The lookup table for a backward graph with flipped edges
[in]	havePermissions	The boolean flag indicating whether edge permissions need to be considered or not
[in]	haveRestrictions	The boolean flag indicating whether edge restrictions need to be considered or not
[in]	toProhibit	The list of explicitly prohibited edges

Definition at line 102 of file AFBuild.h.

References myArcInfos, myCentralizedSPTree, myErrorMsgHandler, myFlippedEdges, myFlippedLookupTable, myFlippedOperation, myFlippedPartition, myHavePermissions, myHaveRestrictions, myNode2EdgeRouter, myNumberOfLevels, and myProhibited.

◆ ~AFBuild()

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

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

inline

Destructor.

Definition at line 129 of file AFBuild.h.

References myCentralizedSPTree, and myNode2EdgeRouter.

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]	msTime	The start time of the routes in milliseconds
	sHARCLevel	The SHARC level
[in]	cell	The cell
[in]	vehicle	The vehicle

Definition at line 392 of file AFBuild.h.

References computeArcFlagsAux(), AFInfo< E >::ArcInfo::effortsToBoundaryNodes, elapsedMs2string(), KDTreePartition< E, N, V >::Cell::getBoundaryFromNodes(), SysUtils::getCurrentMillis(), KDTreePartition< E, N, V >::Cell::getNumber(), KDTreePartition< E, N, V >::Cell::getOutgoingBoundaryEdges(), KDTreePartition< E, N, V >::Cell::getSupercell(), initBoundaryEdges(), initSupercellEdges(), myArcInfos, myCentralizedSPTree, myNode2EdgeRouter, 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]	msTime	The start time of the routes in milliseconds
[in]	sHARCLevel	The SHARC level
[in]	vehicle	The vehicle

Definition at line 285 of file AFBuild.h.

References computeArcFlags(), myArcInfos, myFlippedPartition, and sHARCLevel2PartitionLevel().

Referenced by computeArcFlags(), and init().

Here is the caller graph for this function:

◆ 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]	msTime	The start time of the routes in milliseconds
[in]	sHARCLevel	The SHARC level
[in]	cell	The cell
[in]	vehicle	The vehicle

Definition at line 462 of file AFBuild.h.

References AFInfo< E >::FlagInfo::edge, KDTreePartition< E, N, V >::Cell::edgeSet(), AFInfo< E >::ArcInfo::effortsToBoundaryNodes, elapsedMs2string(), EPS, SysUtils::getCurrentMillis(), Named::getIDSecure(), KDTreePartition< E, N, V >::Cell::getNumber(), KDTreePartition< E, N, V >::Cell::getSupercell(), KDTreePartition< E, N, V >::Cell::isLeftOrLowerCell(), myArcInfos, myErrorMsgHandler, myNode2EdgeRouter, KDTreePartition< E, N, V >::Cell::nodeIterators(), putArcFlag(), STEPS2TIME, SVC_IGNORING, and UNREACHABLE.

Referenced by computeArcFlags(), and computeArcFlagsNaive().

Here is the caller graph for this function:

◆ 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]	msTime	The start time of the routes in milliseconds
	sHARCLevel	The SHARC level
[in]	cell	The cell
[in]	vehicle	The vehicle

Definition at line 324 of file AFBuild.h.

References computeArcFlagsAux(), AFInfo< E >::ArcInfo::effortsToBoundaryNodes, elapsedMs2string(), KDTreePartition< E, N, V >::Cell::getBoundaryFromNodes(), SysUtils::getCurrentMillis(), KDTreePartition< E, N, V >::Cell::getNumber(), KDTreePartition< E, N, V >::Cell::getOutgoingBoundaryEdges(), KDTreePartition< E, N, V >::Cell::getSupercell(), initBoundaryEdges(), initSupercellEdges(), myArcInfos, myCentralizedSPTree, myNode2EdgeRouter, 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 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 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]	msTime	The start time of the routes in milliseconds
[in]	vehicle	The vehicle
[in]	flagInfos	The arc flag informations

Definition at line 251 of file AFBuild.h.

References computeArcFlags(), myArcInfos, myFlippedEdges, and myNumberOfLevels.

◆ 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, AFInfo< E >::ArcInfo::effortsToBoundaryNodes, myArcInfos, and myFlippedPartition.

Referenced by computeArcFlags(), and computeArcFlagsNaive().

Here is the caller graph for this function:

◆ 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]	supercell	The supercell
[in]	boundaryEdges	The boundary edges
[in]	numberOfBoundaryNodes	The number of boundary nodes

Definition at line 678 of file AFBuild.h.

References AFInfo< E >::ArcInfoBase::arcFlags, AFInfo< E >::ArcInfo::effortsToBoundaryNodes, myArcInfos, myFlippedPartition, and KDTreePartition< E, N, V >::Cell::nodeIterators().

Referenced by computeArcFlags(), and computeArcFlagsNaive().

Here is the caller graph for this function:

◆ 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] partitionLevel The partition level

Returns: The SHARC level number corresponding to the given partition level number

Definition at line 158 of file AFBuild.h.

References 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]	arcInfo	The arc information
[in]	sHARCLevel	The SHARC level
[in]	isLeftOrLowerCell	The 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.

Referenced by computeArcFlagsAux().

Here is the caller graph for this function:

◆ 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 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] sHARCLevel The SHARC level

Returns: The partition level number corresponding to the given SHARC level number

Definition at line 165 of file AFBuild.h.

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

Referenced by computeArcFlags().

Here is the caller graph for this function:

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.

Referenced by computeArcFlagsAux().

◆ 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(), computeArcFlags(), computeArcFlags(), computeArcFlagsAux(), computeArcFlagsNaive(), init(), initBoundaryEdges(), and initSupercellEdges().

◆ 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(), computeArcFlags(), computeArcFlagsNaive(), and ~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.

Referenced by AFBuild(), and computeArcFlagsAux().

◆ 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(), and init().

◆ 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(), and 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(), and 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(), computeArcFlags(), initBoundaryEdges(), initSupercellEdges(), and 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().

◆ 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().

◆ 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(), computeArcFlags(), computeArcFlagsAux(), computeArcFlagsNaive(), and ~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(), init(), partitionLevel2SHARCLevel(), and sHARCLevel2PartitionLevel().

◆ myProhibited

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

const std::map<const FlippedEdge<E, N, V>*, double>* AFBuild< E, N, V, M >::myProhibited

protected

The list of explicitly prohibited edges.

Definition at line 214 of file AFBuild.h.

Referenced by AFBuild().

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

AFBuild.h

Public Types

Public Member Functions

Data Fields

Protected Member Functions

Protected Attributes

Private Member Functions

Detailed Description

Member Typedef Documentation

◆ ArcInfo

◆ Cell

◆ FlagInfo

◆ FlippedLookupTable

Constructor & Destructor Documentation

◆ AFBuild()

◆ ~AFBuild()

Member Function Documentation

◆ computeArcFlags() [1/2]

◆ computeArcFlags() [2/2]

◆ computeArcFlagsAux()

◆ computeArcFlagsNaive()

◆ getFlippedLookup()

◆ getFlippedOperation()

◆ init()

◆ initBoundaryEdges()

◆ initSupercellEdges()

◆ partitionLevel2SHARCLevel()

◆ putArcFlag()

◆ setFlippedPartition()

◆ sHARCLevel2PartitionLevel()

Field Documentation

◆ EPS

◆ myArcInfos

◆ myCentralizedSPTree

◆ myErrorMsgHandler

◆ myFlippedEdges

◆ myFlippedLookupTable

◆ myFlippedOperation

◆ myFlippedPartition

◆ myHavePermissions

◆ myHaveRestrictions

◆ myNode2EdgeRouter

◆ myNumberOfLevels

◆ myProhibited