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 = 0
	Sum(distance of all legs up to this one).
uint	capacity = 0
	This capacity is min(capacity) fom all edges.
int	free_capacity = 0
	This capacity is min(edge.capacity - edge.flow) for the current run of Dijkstra.
uint	flow = 0
	Flow the current run of the mcf solver assigns.
NodeID	node = INVALID_NODE
	Link graph node this leg passes.
NodeID	origin = INVALID_NODE
	Link graph node this path originates from.
uint	num_children = 0
	Number of child legs that have been forked from this path.
Path *	parent = nullptr
	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 277 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 250 of file linkgraphjob.cpp.

References capacity, distance, flow, free_capacity, node, num_children, origin, and parent.

Referenced by CapacityAnnotation::CapacityAnnotation(), DistanceAnnotation::DistanceAnnotation(), Fork(), and GetParent().

Member Function Documentation

◆ AddFlow() [1/2]

void Path::AddFlow ( uint f )

inline

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

Parameters

f	The amount of flow to increase by.

Definition at line 351 of file linkgraphjob.h.

References flow.

Referenced by 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 223 of file linkgraphjob.cpp.

References 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 368 of file linkgraphjob.h.

References 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 201 of file linkgraphjob.cpp.

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

◆ GetCapacity()

uint Path::GetCapacity ( ) const

inline

Get the overall capacity of the path.

Returns: The path's capacity.

Definition at line 306 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 330 of file linkgraphjob.h.

References capacity, free_capacity, and GetCapacityRatio().

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

◆ GetCapacityRatio() [2/2]

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 321 of file linkgraphjob.h.

References Clamp().

◆ GetDistance()

uint Path::GetDistance ( ) const

inline

Get the overall distance of the path.

Returns: The path's length.

Definition at line 339 of file linkgraphjob.h.

References distance.

◆ GetFlow()

uint Path::GetFlow ( ) const

inline

Get the flow on this leg.

Returns: The accumulated flow.

Definition at line 357 of file linkgraphjob.h.

References flow.

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

◆ GetFreeCapacity()

int Path::GetFreeCapacity ( ) const

inline

Get the free capacity of the path.

Returns: The path's capacity that isn't used.

Definition at line 312 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.

Returns: The node.

Definition at line 288 of file linkgraphjob.h.

References node.

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

◆ GetNumChildren()

uint Path::GetNumChildren ( ) const

inline

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

Returns: The number of children.

Definition at line 363 of file linkgraphjob.h.

References num_children.

Referenced by MultiCommodityFlow::CleanupPaths().

◆ GetOrigin()

NodeID Path::GetOrigin ( ) const

inline

Get the overall origin of the path.

Returns: The origin node.

Definition at line 294 of file linkgraphjob.h.

References origin.

Referenced by MCF1stPass::EliminateCycles(), and FlowMapper::Run().

◆ GetParent()

Path * Path::GetParent ( )

inline

Get the parent leg of this one.

Returns: The parent of this leg.

Definition at line 300 of file linkgraphjob.h.

References parent, and Path().

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.

Parameters

f	The amount of flow to decrease by.

Definition at line 345 of file linkgraphjob.h.

References flow.

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

Field Documentation

◆ capacity

uint Path::capacity = 0

protected

This capacity is min(capacity) fom all edges.

Definition at line 389 of file linkgraphjob.h.

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

◆ distance

uint Path::distance = 0

protected

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

Definition at line 388 of file linkgraphjob.h.

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

◆ flow

uint Path::flow = 0

protected

Flow the current run of the mcf solver assigns.

Definition at line 391 of file linkgraphjob.h.

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

◆ free_capacity

int Path::free_capacity = 0

protected

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

Definition at line 390 of file linkgraphjob.h.

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

◆ 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 279 of file linkgraphjob.h.

Referenced by MCF1stPass::EliminateCycles().

◆ node

NodeID Path::node = INVALID_NODE

protected

Link graph node this leg passes.

Definition at line 392 of file linkgraphjob.h.

Referenced by AddFlow(), GetNode(), and Path().

◆ num_children

uint Path::num_children = 0

protected

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

Definition at line 394 of file linkgraphjob.h.

Referenced by GetNumChildren(), and Path().

◆ origin

NodeID Path::origin = INVALID_NODE

protected

Link graph node this path originates from.

Definition at line 393 of file linkgraphjob.h.

Referenced by Fork(), GetOrigin(), and Path().

◆ parent

Path* Path::parent = nullptr

protected

Parent leg of this one.

Definition at line 395 of file linkgraphjob.h.

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

◆ PATH_CAP_MAX_FREE

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

staticconstexprprotected

Definition at line 386 of file linkgraphjob.h.

◆ PATH_CAP_MIN_FREE

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

staticconstexprprotected

Definition at line 385 of file linkgraphjob.h.

◆ PATH_CAP_MULTIPLIER

int Path::PATH_CAP_MULTIPLIER = 16

staticconstexprprotected

Definition at line 384 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