A leg of a path in the link graph. More...

#include <linkgraphjob.h>

Inheritance diagram for Path:

Public Member Functions
	Path (NodeID n, bool source=false)
	Create a leg of a path in the link graph.

NodeID	GetNode () const
	Get the node this leg passes.

NodeID	GetOrigin () const
	Get the overall origin of the path.

Path *	GetParent ()
	Get the parent leg of this one.

uint	GetCapacity () const
	Get the overall capacity of the path.

int	GetFreeCapacity () const
	Get the free capacity of the path.

int	GetCapacityRatio () const
	Get capacity ratio of this path.

uint	GetDistance () const
	Get the overall distance of the path.

void	ReduceFlow (uint f)
	Reduce the flow on this leg only by the specified amount.

void	AddFlow (uint f)
	Increase the flow on this leg only by the specified amount.

uint	GetFlow () const
	Get the flow on this leg.

uint	GetNumChildren () const
	Get the number of "forked off" child legs of this one.

void	Detach ()
	Detach this path from its parent.

uint	AddFlow (uint f, LinkGraphJob &job, uint max_saturation)
	Push some flow along a path and register the path in the nodes it passes if successful.

void	Fork (Path *base, uint cap, int free_cap, uint dist)
	Add this path as a new child to the given base path, thus making this path a "fork" of the base path.

Static Public Member Functions
static int	GetCapacityRatio (int free, uint total)
	Get ratio of free * 16 (so that we get fewer 0) / max(total capacity, 1) (so that we don't divide by 0).

Static Public Attributes
static Path *	invalid_path = new Path(INVALID_NODE, true)
	Static instance of an invalid path.

Protected Attributes
uint	distance
	Sum(distance of all legs up to this one).

uint	capacity
	This capacity is min(capacity) fom all edges.

int	free_capacity
	This capacity is min(edge.capacity - edge.flow) for the current run of Dijkstra.

uint	flow
	Flow the current run of the mcf solver assigns.

NodeID	node
	Link graph node this leg passes.

NodeID	origin
	Link graph node this path originates from.

uint	num_children
	Number of child legs that have been forked from this path.

Path *	parent
	Parent leg of this one.

Static Protected Attributes
static constexpr int	PATH_CAP_MULTIPLIER = 16

static constexpr int	PATH_CAP_MIN_FREE = (INT_MIN + 1) / PATH_CAP_MULTIPLIER

static constexpr int	PATH_CAP_MAX_FREE = (INT_MAX - 1) / PATH_CAP_MULTIPLIER

Detailed Description

A leg of a path in the link graph.

Paths can form trees by being "forked".

Definition at line 275 of file linkgraphjob.h.

Constructor & Destructor Documentation

◆ Path()

Path::Path	(	NodeID	n,
		bool	source = `false`
	)

Create a leg of a path in the link graph.

Parameters

n	Id of the link graph node this path passes.
source	If true, this is the first leg of the path.

Definition at line 248 of file linkgraphjob.cpp.

Member Function Documentation

◆ AddFlow() [1/2]

void Path::AddFlow ( uint f )

inline

Increase the flow on this leg only by the specified amount.

Definition at line 325 of file linkgraphjob.h.

References flow.

Referenced by AddFlow(), MCF1stPass::EliminateCycles(), and MultiCommodityFlow::PushFlow().

◆ AddFlow() [2/2]

uint Path::AddFlow	(	uint	new_flow,
		LinkGraphJob &	job,
		uint	max_saturation
	)

Push some flow along a path and register the path in the nodes it passes if successful.

Parameters

new_flow	Amount of flow to push.
job	Link graph job this node belongs to.
max_saturation	Maximum saturation of edges.

Returns: Amount of flow actually pushed.

Definition at line 221 of file linkgraphjob.cpp.

References AddFlow(), LinkGraphJob::EdgeAnnotation::AddFlow(), LinkGraphJob::EdgeAnnotation::base, LinkGraph::BaseEdge::capacity, LinkGraphJob::EdgeAnnotation::Flow(), flow, node, and parent.

◆ Detach()

void Path::Detach ( )

inline

Detach this path from its parent.

Definition at line 336 of file linkgraphjob.h.

References num_children, and parent.

Referenced by MultiCommodityFlow::CleanupPaths(), and Fork().

◆ Fork()

void Path::Fork	(	Path *	base,
		uint	cap,
		int	free_cap,
		uint	dist
	)

Add this path as a new child to the given base path, thus making this path a "fork" of the base path.

Parameters

base	Path to fork from.
cap	Maximum capacity of the new leg.
free_cap	Remaining free capacity of the new leg.
dist	Distance of the new leg.

Definition at line 199 of file linkgraphjob.cpp.

References capacity, Detach(), distance, free_capacity, num_children, origin, and parent.

◆ GetCapacity()

uint Path::GetCapacity ( ) const

inline

Get the overall capacity of the path.

Definition at line 292 of file linkgraphjob.h.

References capacity.

◆ GetCapacityRatio() [1/2]

int Path::GetCapacityRatio ( ) const

inline

Get capacity ratio of this path.

Returns: free capacity * 16 / (total capacity + 1).

Definition at line 313 of file linkgraphjob.h.

References capacity, free_capacity, and GetCapacityRatio().

Referenced by GetCapacityRatio(), CapacityAnnotation::IsBetter(), and CapacityAnnotation::UpdateAnnotation().

◆ GetCapacityRatio() [2/2]

static int Path::GetCapacityRatio	(	int	free,
		uint	total
	)

inlinestatic

Get ratio of free * 16 (so that we get fewer 0) / max(total capacity, 1) (so that we don't divide by 0).

Parameters

free	Free capacity.
total	Total capacity.

Returns: free * 16 / max(total, 1).

Definition at line 304 of file linkgraphjob.h.

References Clamp(), and free().

◆ GetDistance()

uint Path::GetDistance ( ) const

inline

Get the overall distance of the path.

Definition at line 319 of file linkgraphjob.h.

References distance.

◆ GetFlow()

uint Path::GetFlow ( ) const

inline

Get the flow on this leg.

Definition at line 328 of file linkgraphjob.h.

References flow.

Referenced by MultiCommodityFlow::CleanupPaths(), MCF1stPass::EliminateCycle(), MCF1stPass::EliminateCycles(), and MCF1stPass::FindCycleFlow().

◆ GetFreeCapacity()

int Path::GetFreeCapacity ( ) const

inline

Get the free capacity of the path.

Definition at line 295 of file linkgraphjob.h.

References free_capacity.

Referenced by MCF1stPass::MCF1stPass(), and MCF2ndPass::MCF2ndPass().

◆ GetNode()

NodeID Path::GetNode ( ) const

inline

Get the node this leg passes.

Definition at line 283 of file linkgraphjob.h.

References node.

Referenced by MultiCommodityFlow::CleanupPaths(), MCF1stPass::EliminateCycle(), MCF1stPass::EliminateCycles(), and MCF1stPass::FindCycleFlow().

◆ GetNumChildren()

uint Path::GetNumChildren ( ) const

inline

Get the number of "forked off" child legs of this one.

Definition at line 331 of file linkgraphjob.h.

References num_children.

Referenced by MultiCommodityFlow::CleanupPaths().

◆ GetOrigin()

NodeID Path::GetOrigin ( ) const

inline

Get the overall origin of the path.

Definition at line 286 of file linkgraphjob.h.

References origin.

Referenced by MCF1stPass::EliminateCycles().

◆ GetParent()

Path * Path::GetParent ( )

inline

Get the parent leg of this one.

Definition at line 289 of file linkgraphjob.h.

References parent.

Referenced by MultiCommodityFlow::CleanupPaths(), and MCF1stPass::EliminateCycle().

◆ ReduceFlow()

void Path::ReduceFlow ( uint f )

inline

Reduce the flow on this leg only by the specified amount.

Definition at line 322 of file linkgraphjob.h.

References flow.

Referenced by MCF1stPass::EliminateCycle(), and MCF1stPass::EliminateCycles().

Field Documentation

◆ capacity

uint Path::capacity

protected

This capacity is min(capacity) fom all edges.

Definition at line 357 of file linkgraphjob.h.

Referenced by Fork(), GetCapacity(), GetCapacityRatio(), and CapacityAnnotation::IsBetter().

◆ distance

uint Path::distance

protected

Sum(distance of all legs up to this one).

Definition at line 356 of file linkgraphjob.h.

Referenced by Fork(), DistanceAnnotation::GetAnnotation(), GetDistance(), CapacityAnnotation::IsBetter(), and DistanceAnnotation::IsBetter().

◆ flow

uint Path::flow

protected

Flow the current run of the mcf solver assigns.

Definition at line 359 of file linkgraphjob.h.

Referenced by AddFlow(), AddFlow(), GetFlow(), and ReduceFlow().

◆ free_capacity

int Path::free_capacity

protected

This capacity is min(edge.capacity - edge.flow) for the current run of Dijkstra.

Definition at line 358 of file linkgraphjob.h.

Referenced by Fork(), GetCapacityRatio(), GetFreeCapacity(), CapacityAnnotation::IsBetter(), and DistanceAnnotation::IsBetter().

◆ invalid_path

Path * Path::invalid_path = new Path(INVALID_NODE, true)

static

Static instance of an invalid path.

Note: This instance is created on task start. Lazy creation on first usage results in a data race between the CDist threads.

Definition at line 277 of file linkgraphjob.h.

Referenced by MCF1stPass::EliminateCycles().

◆ node

NodeID Path::node

protected

Link graph node this leg passes.

Definition at line 360 of file linkgraphjob.h.

Referenced by AddFlow(), and GetNode().

◆ num_children

uint Path::num_children

protected

Number of child legs that have been forked from this path.

Definition at line 362 of file linkgraphjob.h.

Referenced by Detach(), Fork(), and GetNumChildren().

◆ origin

NodeID Path::origin

protected

Link graph node this path originates from.

Definition at line 361 of file linkgraphjob.h.

Referenced by Fork(), and GetOrigin().

◆ parent

Path* Path::parent

protected

Parent leg of this one.

Definition at line 363 of file linkgraphjob.h.

Referenced by AddFlow(), Detach(), Fork(), and GetParent().

◆ PATH_CAP_MAX_FREE

constexpr int Path::PATH_CAP_MAX_FREE = (INT_MAX - 1) / PATH_CAP_MULTIPLIER

staticconstexprprotected

Definition at line 354 of file linkgraphjob.h.

◆ PATH_CAP_MIN_FREE

constexpr int Path::PATH_CAP_MIN_FREE = (INT_MIN + 1) / PATH_CAP_MULTIPLIER

staticconstexprprotected

Definition at line 353 of file linkgraphjob.h.

◆ PATH_CAP_MULTIPLIER

constexpr int Path::PATH_CAP_MULTIPLIER = 16

staticconstexprprotected

Definition at line 352 of file linkgraphjob.h.

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

src/linkgraph/linkgraphjob.h
src/linkgraph/linkgraphjob.cpp

Public Member Functions

Static Public Member Functions

Static Public Attributes

Protected Attributes

Static Protected Attributes

Detailed Description

Constructor & Destructor Documentation

◆ Path()

Member Function Documentation

◆ AddFlow() [1/2]

◆ AddFlow() [2/2]

◆ Detach()

◆ Fork()

◆ GetCapacity()

◆ GetCapacityRatio() [1/2]

◆ GetCapacityRatio() [2/2]

◆ GetDistance()

◆ GetFlow()

◆ GetFreeCapacity()

◆ GetNode()

◆ GetNumChildren()

◆ GetOrigin()

◆ GetParent()

◆ ReduceFlow()

Field Documentation

◆ capacity

◆ distance

◆ flow

◆ free_capacity

◆ invalid_path

◆ node

◆ num_children

◆ origin

◆ parent

◆ PATH_CAP_MAX_FREE

◆ PATH_CAP_MIN_FREE

◆ PATH_CAP_MULTIPLIER