OpenTTD Source  20241108-master-g80f628063a
DistanceAnnotation Class Reference

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

Inheritance diagram for DistanceAnnotation:
Path

Data Structures

struct  Comparator
 Comparator for std containers. More...
 

Public Member Functions

 DistanceAnnotation (NodeID n, bool source=false)
 Constructor. More...
 
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. More...
 
uint GetAnnotation () const
 Return the actual value of the annotation, in this case the distance. More...
 
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. More...
 
NodeID GetNode () const
 Get the node this leg passes.
 
NodeID GetOrigin () const
 Get the overall origin of the path.
 
PathGetParent ()
 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...
 

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). More...
 
- Static Public Attributes inherited from Path
static Pathinvalid_path = new Path(INVALID_NODE, true)
 Static instance of an invalid path. More...
 
- 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.
 
Pathparent
 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
nID of node to be annotated.
sourceIf 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
baseOther path.
free_capCapacity of the new edge to be added to base.
distDistance 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.


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