Path Class Reference

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. More...
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. More...
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. More...
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. More...

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). More...

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

Protected Types
enum	PathCapacityBoundaries { PATH_CAP_MULTIPLIER = 16, PATH_CAP_MIN_FREE = (INT_MIN + 1) / PATH_CAP_MULTIPLIER, PATH_CAP_MAX_FREE = (INT_MAX - 1) / PATH_CAP_MULTIPLIER }
	Some boundaries to clamp against in order to avoid integer overflows.

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.

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

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 LinkGraphJob::EdgeAnnotation::AddFlow(), AddFlow(), LinkGraphJob::EdgeAnnotation::base, LinkGraph::BaseEdge::capacity, LinkGraphJob::EdgeAnnotation::Flow(), flow, node, and parent.

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.

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, and free_capacity.

Referenced by 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().

Field Documentation

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

---

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

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