Metric-independent RoutingKit CCH topology over the PURE road graph. More...

#include <CCHGraph.h>

Collaboration diagram for CCHGraph< E, V >:

Public Types
typedef double(*	EffortOperation) (const E const, const V const, double)
	effort callback signature, matching SUMOAbstractRouter::Operation

Public Member Functions
unsigned	arcCount () const
	number of input arcs (== number of mapped connections)

const std::vector< unsigned > &	arcsOfEdge (const E *e) const
	the arcs whose weight depends on the given edge (arcs it heads plus arcs whose folded via chain contains it), for sparse re-customization; empty for edges that are not part of the graph

const RoutingKit::CustomizableContractionHierarchy &	cch () const
	the immutable CCH (share const& across clones)

	CCHGraph (const std::vector< E * > &allEdges)
	Build the union line graph + CCH from the given edges.

unsigned	computeArcWeight (unsigned a, EffortOperation effort, SUMOVehicleClass maskClass, const V *veh, double time) const
	Recompute the input weight of one arc – the exact per-arc body of fillInputWeights (same masking, folding and rounding), exposed so a sparse update can refresh only the arcs of edges that actually moved.

unsigned	edgeIdSpace () const
	size of the edge numerical-id space the graph was built over (for callers keeping per-edge-id side arrays, e.g. CCHMetricFamily)

const E *	edgeOf (unsigned node) const
	the edge backing a RoutingKit node

void	expandNodePath (const std::vector< unsigned > &nodePath, std::vector< const E * > &into) const
	Map a RoutingKit node path back to the edge sequence.

void	fillInputWeights (EffortOperation effort, SUMOVehicleClass maskClass, const V *veh, double time, std::vector< unsigned > &weight) const
	Fill a centisecond input-weight buffer for one vehicle class.

void	invalidateClassMasks () const
	Drop every primed connection mask so the next fill re-primes from the CURRENT successor lists.

unsigned	nodeOf (const E *e) const
	RoutingKit node index for an edge, or INVALID_NODE if not a node.

const std::vector< unsigned > &	tazSinks (const E *taz) const
	road member nodes of a TAZ-sink connector (its exit edges), to seed multi-TARGET queries; empty if `taz` is not a known TAZ sink.

const std::vector< unsigned > &	tazSources (const E *taz) const
	road member nodes of a TAZ-source connector (its entry edges), to seed multi-SOURCE queries; empty if `taz` is not a known TAZ source.

virtual	~CCHGraph ()

Static Public Member Functions
static double	viaChainEffort (const E via, EffortOperation effort, const V veh, double time)
	effort accumulated crossing the internal/via chain that leads from one real edge onto its successor (mirrors SUMOAbstractRouter::updateViaEdgeCost).

Static Public Attributes
static const unsigned	INVALID_NODE = RoutingKit::invalid_id
	sentinel for "not a routable node"

Private Member Functions
	CCHGraph (const CCHGraph &)=delete

unsigned	computeArcWeightRaw (unsigned a, EffortOperation effort, const V *veh, double time) const
	The unmasked weight of one arc: via-chain effort + head-edge effort, rounded to centiseconds and clamped below inf_weight (NaN / inf / overflow become inf_weight = forbidden).

CCHGraph &	operator= (const CCHGraph &)=delete

void	primeClassMask (SUMOVehicleClass vClass) const
	Record which arcs `vClass` may traverse in the per-arc CONNECTION-level permission bitmask – exactly the arcs getViaSuccessors(vClass) yields (edge-level getPermissions() is too coarse on mixed-lane edges). No-op if the class was primed before.

Static Private Member Functions
static bool	isStarConnector (const E *e)
	whether the edge is a district star connector (the paired "<taz>-source"/"-sink" phantom edge) as opposed to a legacy function="connector" net edge, which stays routable

Private Attributes
std::vector< unsigned >	myArcHead

std::map< std::pair< unsigned, unsigned >, unsigned >	myArcOf
	(tail node, head node) -> arc index

std::vector< SVCPermissions >	myArcPerm
	per-arc CONNECTION-level permission bitmask, accumulated per primed class (see primeClassMask); mutable lazy cache

std::vector< unsigned >	myArcTail
	per-arc endpoints

std::vector< const E * >	myArcVia
	per-arc leading via/internal edge (nullptr if none) for path re-expansion

RoutingKit::CustomizableContractionHierarchy	myCCH
	the immutable hierarchy

std::vector< std::vector< unsigned > >	myEdgeToArcs
	edge numerical id -> arcs whose weight reads that edge (head + folded via edges); the reverse image of computeArcWeightRaw's inputs

std::vector< unsigned >	myEdgeToNode
	edge numerical id -> node index (INVALID_NODE if not a node)

std::vector< const E * >	myNodeToEdge
	node index -> backing edge

SVCPermissions	myPrimedClasses
	the classes already primed into myArcPerm

std::map< const E *, std::vector< unsigned > >	myTazSnkNodes
	TAZ-sink connector edge -> its exit-edge road node ids.

std::map< const E *, std::vector< unsigned > >	myTazSrcNodes
	TAZ-source connector edge -> its entry-edge road node ids.

Detailed Description

template<class E, class V>
class CCHGraph< E, V >

Metric-independent RoutingKit CCH topology over the PURE road graph.

Nodes are the non-internal, non-TAZ edges. TAZ connectors are deliberately NOT nodes: a connector is a high-degree "star" (it links every member edge of its zone), and eliminating a degree-d node in a contraction hierarchy forms a d-clique => treewidth >= d, which poisons the whole hierarchy regardless of elimination order. Instead, TAZ connectors are kept host-side as query-time source/target SETS (the "phantom node" pattern) and resolved with RoutingKit's native multi-source/multi-target query.

Build once at start; hold a single owned instance and hand out a const reference to every router clone (the CustomizableContractionHierarchy is read-only after construction and safe to share across threads).

Template Parameters

E	the edge type (MSEdge / ROEdge)
V	the vehicle type of the effort callback (SUMOVehicle / ROVehicle)

Definition at line 86 of file CCHGraph.h.

Member Typedef Documentation

◆ EffortOperation

template<class E , class V >

typedef double(* CCHGraph< E, V >::EffortOperation) (const E *const, const V *const, double)

effort callback signature, matching SUMOAbstractRouter::Operation

Definition at line 89 of file CCHGraph.h.

Constructor & Destructor Documentation

◆ CCHGraph() [1/2]

template<class E , class V >

CCHGraph< E, V >::CCHGraph ( const std::vector< E * > & allEdges )

inlineexplicit

Build the union line graph + CCH from the given edges.

Arcs come from getViaSuccessors(SVC_IGNORING) (the raw, unfiltered successor set): the arc set must be class-independent so every class (including e.g. tram-only rail arcs) exists. Per-class permissions are applied later as inf_weight in the metric, never by removing arcs.

Definition at line 101 of file CCHGraph.h.

◆ ~CCHGraph()

template<class E , class V >

virtual CCHGraph< E, V >::~CCHGraph ( )

inlinevirtual

Definition at line 223 of file CCHGraph.h.

◆ CCHGraph() [2/2]

template<class E , class V >

CCHGraph< E, V >::CCHGraph ( const CCHGraph< E, V > & )

privatedelete

Member Function Documentation

◆ arcCount()

template<class E , class V >

unsigned CCHGraph< E, V >::arcCount ( ) const

inline

number of input arcs (== number of mapped connections)

Definition at line 231 of file CCHGraph.h.

References CCHGraph< E, V >::myArcTail.

Referenced by CCHMetricFamily< E, V, K >::buildLiveMetric(), CCHGraph< E, V >::CCHGraph(), and CCHGraph< E, V >::fillInputWeights().

Here is the caller graph for this function:

◆ arcsOfEdge()

template<class E , class V >

const std::vector< unsigned > & CCHGraph< E, V >::arcsOfEdge ( const E * e ) const

inline

the arcs whose weight depends on the given edge (arcs it heads plus arcs whose folded via chain contains it), for sparse re-customization; empty for edges that are not part of the graph

Definition at line 273 of file CCHGraph.h.

References CCHGraph< E, V >::myEdgeToArcs.

Referenced by CCHMetricFamily< E, V, K >::customize().

Here is the caller graph for this function:

◆ cch()

template<class E , class V >

const RoutingKit::CustomizableContractionHierarchy & CCHGraph< E, V >::cch ( ) const

inline

the immutable CCH (share const& across clones)

Definition at line 226 of file CCHGraph.h.

References CCHGraph< E, V >::myCCH.

Referenced by CCHMetricFamily< E, V, K >::buildLiveMetric(), CCHMetricFamily< E, V, K >::customize(), and CCHMetricFamily< E, V, K >::get().

Here is the caller graph for this function:

◆ computeArcWeight()

template<class E , class V >

unsigned CCHGraph< E, V >::computeArcWeight	(	unsigned	a,
		EffortOperation	effort,
		SUMOVehicleClass	maskClass,
		const V *	veh,
		double	time
	)		const

inline

Recompute the input weight of one arc – the exact per-arc body of fillInputWeights (same masking, folding and rounding), exposed so a sparse update can refresh only the arcs of edges that actually moved.

Forbidden (inf_weight) if EITHER the connection does not permit the class (static, connection-level, matches getViaSuccessors(vClass); see primeClassMask) OR the destination edge does not currently permit the class (dynamic, edge-level – catches runtime closures via MSLane::setPermissions; a no-op where permissions are static).

Definition at line 318 of file CCHGraph.h.

References CCHGraph< E, V >::computeArcWeightRaw(), CCHGraph< E, V >::edgeOf(), RoutingKit::inf_weight, CCHGraph< E, V >::myArcHead, CCHGraph< E, V >::myArcPerm, and SVC_IGNORING.

Referenced by CCHMetricFamily< E, V, K >::customize(), and CCHGraph< E, V >::fillInputWeights().

Here is the caller graph for this function:

◆ computeArcWeightRaw()

template<class E , class V >

unsigned CCHGraph< E, V >::computeArcWeightRaw	(	unsigned	a,
		EffortOperation	effort,
		const V *	veh,
		double	time
	)		const

inlineprivate

The unmasked weight of one arc: via-chain effort + head-edge effort, rounded to centiseconds and clamped below inf_weight (NaN / inf / overflow become inf_weight = forbidden).

Definition at line 402 of file CCHGraph.h.

References RoutingKit::inf_weight, CCHGraph< E, V >::myArcHead, CCHGraph< E, V >::myArcVia, CCHGraph< E, V >::myNodeToEdge, and CCHGraph< E, V >::viaChainEffort().

Referenced by CCHGraph< E, V >::computeArcWeight().

Here is the caller graph for this function:

◆ edgeIdSpace()

template<class E , class V >

unsigned CCHGraph< E, V >::edgeIdSpace ( ) const

inline

size of the edge numerical-id space the graph was built over (for callers keeping per-edge-id side arrays, e.g. CCHMetricFamily)

Definition at line 237 of file CCHGraph.h.

References CCHGraph< E, V >::myEdgeToNode.

Referenced by CCHMetricFamily< E, V, K >::CCHMetricFamily().

Here is the caller graph for this function:

◆ edgeOf()

template<class E , class V >

const E * CCHGraph< E, V >::edgeOf ( unsigned node ) const

inline

the edge backing a RoutingKit node

Definition at line 250 of file CCHGraph.h.

References CCHGraph< E, V >::myNodeToEdge, and node.

Referenced by CCHGraph< E, V >::computeArcWeight().

Here is the caller graph for this function:

◆ expandNodePath()

template<class E , class V >

void CCHGraph< E, V >::expandNodePath	(	const std::vector< unsigned > &	nodePath,
		std::vector< const E * > &	into
	)		const

inline

Map a RoutingKit node path back to the edge sequence.

The result lists REAL edges only, exactly like the exact routers: junction-internal edges are never part of SUMO route vectors – their cost is folded into the arc weights for the query and re-added from consecutive real edges by SUMOAbstractRouter::recomputeCosts.

Definition at line 287 of file CCHGraph.h.

References CCHGraph< E, V >::myNodeToEdge, and node.

◆ fillInputWeights()

template<class E , class V >

void CCHGraph< E, V >::fillInputWeights	(	EffortOperation	effort,
		SUMOVehicleClass	maskClass,
		const V *	veh,
		double	time,
		std::vector< unsigned > &	weight
	)		const

inline

Fill a centisecond input-weight buffer for one vehicle class.

Primes the class's connection mask on first use (see primeClassMask for the synchronization contract), then applies computeArcWeight per arc.

Parameters

[in]	effort	the effort Operation
[in]	maskClass	arcs whose connection or destination edge does NOT permit this class become inf_weight; SVC_IGNORING masks nothing
[in]	veh	reference vehicle for the effort floor (may be null)
[in]	time	seconds, passed to the effort fn
[out]	weight	resized to arcCount(); w[a] in [0, inf_weight]

Definition at line 339 of file CCHGraph.h.

References CCHGraph< E, V >::arcCount(), CCHGraph< E, V >::computeArcWeight(), CCHGraph< E, V >::primeClassMask(), and weight.

Referenced by CCHMetricFamily< E, V, K >::customize(), and CCHMetricFamily< E, V, K >::fillStatic().

Here is the caller graph for this function:

◆ invalidateClassMasks()

template<class E , class V >

void CCHGraph< E, V >::invalidateClassMasks ( ) const

inline

Drop every primed connection mask so the next fill re-primes from the CURRENT successor lists.

Runtime permission changes (closingReroute / closingLaneReroute) alter getViaSuccessors(vClass); a mask primed before the change keeps serving the old connection set – a closure active at first customize would even outlive its re-opening. Same synchronization contract as primeClassMask: call only while no query is in flight.

Definition at line 357 of file CCHGraph.h.

References CCHGraph< E, V >::myArcPerm, and CCHGraph< E, V >::myPrimedClasses.

Referenced by MSRoutingEngine::invalidateCCHEdge().

Here is the caller graph for this function:

◆ isStarConnector()

template<class E , class V >

static bool CCHGraph< E, V >::isStarConnector ( const E * e )

inlinestaticprivate

whether the edge is a district star connector (the paired "<taz>-source"/"-sink" phantom edge) as opposed to a legacy function="connector" net edge, which stays routable

Definition at line 366 of file CCHGraph.h.

Referenced by CCHGraph< E, V >::CCHGraph().

Here is the caller graph for this function:

◆ nodeOf()

template<class E , class V >

unsigned CCHGraph< E, V >::nodeOf ( const E * e ) const

inline

RoutingKit node index for an edge, or INVALID_NODE if not a node.

Definition at line 242 of file CCHGraph.h.

References CCHGraph< E, V >::INVALID_NODE, and CCHGraph< E, V >::myEdgeToNode.

Referenced by CCHGraph< E, V >::CCHGraph(), and CCHGraph< E, V >::primeClassMask().

Here is the caller graph for this function:

◆ operator=()

template<class E , class V >

CCHGraph & CCHGraph< E, V >::operator= ( const CCHGraph< E, V > & )

privatedelete

◆ primeClassMask()

template<class E , class V >

void CCHGraph< E, V >::primeClassMask ( SUMOVehicleClass vClass ) const

inlineprivate

Record which arcs vClass may traverse in the per-arc CONNECTION-level permission bitmask – exactly the arcs getViaSuccessors(vClass) yields (edge-level getPermissions() is too coarse on mixed-lane edges). No-op if the class was primed before.

NOT internally synchronized: concurrent calls for an unprimed class must be serialized by the caller. In practice the simulation primes on the main thread at the customization barrier (no query in flight) and duarouter primes under the RODUACCHMetrics mutex; primed classes make this a lock-free bit test on the hot path.

Definition at line 380 of file CCHGraph.h.

References CCHGraph< E, V >::INVALID_NODE, CCHGraph< E, V >::myArcOf, CCHGraph< E, V >::myArcPerm, CCHGraph< E, V >::myNodeToEdge, CCHGraph< E, V >::myPrimedClasses, CCHGraph< E, V >::nodeOf(), and SVC_IGNORING.

Referenced by CCHGraph< E, V >::fillInputWeights().

Here is the caller graph for this function:

◆ tazSinks()

template<class E , class V >

const std::vector< unsigned > & CCHGraph< E, V >::tazSinks ( const E * taz ) const

inline

road member nodes of a TAZ-sink connector (its exit edges), to seed multi-TARGET queries; empty if taz is not a known TAZ sink.

Definition at line 264 of file CCHGraph.h.

References CCHGraph< E, V >::myTazSnkNodes.

◆ tazSources()

template<class E , class V >

const std::vector< unsigned > & CCHGraph< E, V >::tazSources ( const E * taz ) const

inline

road member nodes of a TAZ-source connector (its entry edges), to seed multi-SOURCE queries; empty if taz is not a known TAZ source.

Definition at line 256 of file CCHGraph.h.

References CCHGraph< E, V >::myTazSrcNodes.

◆ viaChainEffort()

template<class E , class V >

static double CCHGraph< E, V >::viaChainEffort	(	const E *	via,
		EffortOperation	effort,
		const V *	veh,
		double	time
	)

inlinestatic

effort accumulated crossing the internal/via chain that leads from one real edge onto its successor (mirrors SUMOAbstractRouter::updateViaEdgeCost).

Definition at line 297 of file CCHGraph.h.

Referenced by CCHGraph< E, V >::computeArcWeightRaw().

Here is the caller graph for this function:

Field Documentation

◆ INVALID_NODE

template<class E , class V >

const unsigned CCHGraph< E, V >::INVALID_NODE = RoutingKit::invalid_id

static

sentinel for "not a routable node"

Definition at line 92 of file CCHGraph.h.

Referenced by CCHGraph< E, V >::CCHGraph(), CCHGraph< E, V >::nodeOf(), and CCHGraph< E, V >::primeClassMask().

◆ myArcHead

template<class E , class V >

std::vector<unsigned> CCHGraph< E, V >::myArcHead

private

Definition at line 422 of file CCHGraph.h.

Referenced by CCHGraph< E, V >::CCHGraph(), CCHGraph< E, V >::computeArcWeight(), and CCHGraph< E, V >::computeArcWeightRaw().

◆ myArcOf

template<class E , class V >

std::map<std::pair<unsigned, unsigned>, unsigned> CCHGraph< E, V >::myArcOf

private

(tail node, head node) -> arc index

Definition at line 426 of file CCHGraph.h.

Referenced by CCHGraph< E, V >::CCHGraph(), and CCHGraph< E, V >::primeClassMask().

◆ myArcPerm

template<class E , class V >

std::vector<SVCPermissions> CCHGraph< E, V >::myArcPerm

mutableprivate

per-arc CONNECTION-level permission bitmask, accumulated per primed class (see primeClassMask); mutable lazy cache

Definition at line 429 of file CCHGraph.h.

Referenced by CCHGraph< E, V >::CCHGraph(), CCHGraph< E, V >::computeArcWeight(), CCHGraph< E, V >::invalidateClassMasks(), and CCHGraph< E, V >::primeClassMask().

◆ myArcTail

template<class E , class V >

std::vector<unsigned> CCHGraph< E, V >::myArcTail

private

per-arc endpoints

Definition at line 421 of file CCHGraph.h.

Referenced by CCHGraph< E, V >::arcCount(), and CCHGraph< E, V >::CCHGraph().

◆ myArcVia

template<class E , class V >

std::vector<const E*> CCHGraph< E, V >::myArcVia

private

per-arc leading via/internal edge (nullptr if none) for path re-expansion

Definition at line 424 of file CCHGraph.h.

Referenced by CCHGraph< E, V >::CCHGraph(), and CCHGraph< E, V >::computeArcWeightRaw().

◆ myCCH

template<class E , class V >

RoutingKit::CustomizableContractionHierarchy CCHGraph< E, V >::myCCH

private

the immutable hierarchy

Definition at line 440 of file CCHGraph.h.

Referenced by CCHGraph< E, V >::cch(), and CCHGraph< E, V >::CCHGraph().

◆ myEdgeToArcs

template<class E , class V >

std::vector<std::vector<unsigned> > CCHGraph< E, V >::myEdgeToArcs

private

edge numerical id -> arcs whose weight reads that edge (head + folded via edges); the reverse image of computeArcWeightRaw's inputs

Definition at line 434 of file CCHGraph.h.

Referenced by CCHGraph< E, V >::arcsOfEdge(), and CCHGraph< E, V >::CCHGraph().

◆ myEdgeToNode

template<class E , class V >

std::vector<unsigned> CCHGraph< E, V >::myEdgeToNode

private

edge numerical id -> node index (INVALID_NODE if not a node)

Definition at line 419 of file CCHGraph.h.

Referenced by CCHGraph< E, V >::CCHGraph(), CCHGraph< E, V >::edgeIdSpace(), and CCHGraph< E, V >::nodeOf().

◆ myNodeToEdge

template<class E , class V >

std::vector<const E*> CCHGraph< E, V >::myNodeToEdge

private

node index -> backing edge

Definition at line 417 of file CCHGraph.h.

Referenced by CCHGraph< E, V >::CCHGraph(), CCHGraph< E, V >::computeArcWeightRaw(), CCHGraph< E, V >::edgeOf(), CCHGraph< E, V >::expandNodePath(), and CCHGraph< E, V >::primeClassMask().

◆ myPrimedClasses

template<class E , class V >

SVCPermissions CCHGraph< E, V >::myPrimedClasses

mutableprivate

the classes already primed into myArcPerm

Definition at line 431 of file CCHGraph.h.

Referenced by CCHGraph< E, V >::CCHGraph(), CCHGraph< E, V >::invalidateClassMasks(), and CCHGraph< E, V >::primeClassMask().

◆ myTazSnkNodes

template<class E , class V >

std::map<const E*, std::vector<unsigned> > CCHGraph< E, V >::myTazSnkNodes

private

TAZ-sink connector edge -> its exit-edge road node ids.

Definition at line 438 of file CCHGraph.h.

Referenced by CCHGraph< E, V >::CCHGraph(), and CCHGraph< E, V >::tazSinks().

◆ myTazSrcNodes

template<class E , class V >

std::map<const E*, std::vector<unsigned> > CCHGraph< E, V >::myTazSrcNodes

private

TAZ-source connector edge -> its entry-edge road node ids.

Definition at line 436 of file CCHGraph.h.

Referenced by CCHGraph< E, V >::CCHGraph(), and CCHGraph< E, V >::tazSources().

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

Public Types

Public Member Functions

Static Public Member Functions

Static Public Attributes

Private Member Functions

Static Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ EffortOperation

Constructor & Destructor Documentation

◆ CCHGraph() [1/2]

◆ ~CCHGraph()

◆ CCHGraph() [2/2]

Member Function Documentation

◆ arcCount()

◆ arcsOfEdge()

◆ cch()

◆ computeArcWeight()

◆ computeArcWeightRaw()

◆ edgeIdSpace()

◆ edgeOf()

◆ expandNodePath()

◆ fillInputWeights()

◆ invalidateClassMasks()

◆ isStarConnector()

◆ nodeOf()

◆ operator=()

◆ primeClassMask()

◆ tazSinks()

◆ tazSources()

◆ viaChainEffort()

Field Documentation

◆ INVALID_NODE

◆ myArcHead

◆ myArcOf

◆ myArcPerm

◆ myArcTail

◆ myArcVia

◆ myCCH

◆ myEdgeToArcs

◆ myEdgeToNode

◆ myNodeToEdge

◆ myPrimedClasses

◆ myTazSnkNodes

◆ myTazSrcNodes