OpenTTD Source
20241108-master-g80f628063a
|
Distance-based annotation for use in the Dijkstra algorithm. More...
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. | |
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... | |
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 Path * | invalid_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. | |
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 |
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.
|
inline |
|
inline |
Return the actual value of the annotation, in this case the distance.
Definition at line 33 of file mcf.cpp.
References Path::distance.
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.
base | Other path. |
free_cap | Capacity of the new edge to be added to base. |
dist | Distance of the new edge. |
Definition at line 199 of file mcf.cpp.
References Path::distance, and Path::free_capacity.