CapacityAnnotation Class Reference

Capacity-based annotation for use in the Dijkstra algorithm. More...

Inheritance diagram for CapacityAnnotation:

Data Structures
struct	Comparator
	Comparator for std containers. More...

Public Member Functions
	CapacityAnnotation (NodeID n, bool source=false)
	Constructor.
bool	IsBetter (const CapacityAnnotation *base, uint cap, int free_cap, uint dist) const
	Determines if an extension to the given Path with the given parameters is better than this path.
int	GetAnnotation () const
	Return the actual value of the annotation, in this case the capacity.
void	UpdateAnnotation ()
	Update the cached annotation value.
Public Member Functions inherited from Path
	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.

Private Attributes
int	cached_annotation

Additional Inherited Members
Static Public Member Functions inherited from Path
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 inherited from Path
static Path *	invalid_path = new Path(INVALID_NODE, true)
	Static instance of an invalid path.
Protected Attributes inherited from Path
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 inherited from Path
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

Capacity-based annotation for use in the Dijkstra algorithm.

This annotation rates paths according to the maximum capacity of their edges. The Dijkstra algorithm still gives meaningful results like this as the capacity of a path can only decrease or stay the same if you add more edges.

Definition at line 54 of file mcf.cpp.

Constructor & Destructor Documentation

CapacityAnnotation()

CapacityAnnotation::CapacityAnnotation ( NodeID  n, bool  source = false  )

inline

Constructor.

Parameters

n	ID of node to be annotated.
source	If the node is the source of its path.

Definition at line 64 of file mcf.cpp.

Member Function Documentation

GetAnnotation()

int CapacityAnnotation::GetAnnotation ( ) const

inline

Return the actual value of the annotation, in this case the capacity.

Returns

Capacity.

Definition at line 72 of file mcf.cpp.

IsBetter()

bool CapacityAnnotation::IsBetter	(	const CapacityAnnotation *	base,
		uint	cap,
		int	free_cap,
		uint	dist
	)		const

Determines if an extension to the given Path with the given parameters is better than this path.

Parameters

base	Other path.
free_cap	Capacity of the new edge to be added to base.
dist	Distance of the new edge.

Returns

True if base + the new edge would be better than the path associated with this annotation.

Definition at line 233 of file mcf.cpp.

References Path::capacity, Path::distance, Path::free_capacity, and Path::GetCapacityRatio().

UpdateAnnotation()

void CapacityAnnotation::UpdateAnnotation ( )

inline

Update the cached annotation value.

Definition at line 77 of file mcf.cpp.

References Path::GetCapacityRatio().

Field Documentation

cached_annotation

int CapacityAnnotation::cached_annotation

private

Definition at line 55 of file mcf.cpp.

---

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

• src/linkgraph/mcf.cpp