DistanceAnnotation Class Reference

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

Inheritance diagram for DistanceAnnotation:

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

Public Member Functions
	DistanceAnnotation (NodeID n, bool source=false)
	Constructor.
bool	IsBetter (const DistanceAnnotation *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.
uint	GetAnnotation () const
	Return the actual value of the annotation, in this case the distance.
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.

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

Distance-based annotation for use in the Dijkstra algorithm.

This is close to the original meaning of "annotation" in this context. Paths are rated according to the sum of distances of their edges.

Definition at line 17 of file mcf.cpp.

Constructor & Destructor Documentation

DistanceAnnotation()

DistanceAnnotation::DistanceAnnotation ( 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 25 of file mcf.cpp.

Member Function Documentation

GetAnnotation()

uint DistanceAnnotation::GetAnnotation ( ) const

inline

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

Returns

Distance.

Definition at line 33 of file mcf.cpp.

References Path::distance.

IsBetter()

bool DistanceAnnotation::IsBetter	(	const DistanceAnnotation *	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 199 of file mcf.cpp.

References Path::distance, and Path::free_capacity.

UpdateAnnotation()

void DistanceAnnotation::UpdateAnnotation ( )

inline

Update the cached annotation value.

Definition at line 38 of file mcf.cpp.

---

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

• src/linkgraph/mcf.cpp