OpenTTD Source
20241121-master-g67a0fccfad
|
A leg of a path in the link graph. More...
#include <linkgraphjob.h>
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 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. | |
A leg of a path in the link graph.
Paths can form trees by being "forked".
Definition at line 275 of file linkgraphjob.h.
Path::Path | ( | NodeID | n, |
bool | source = false |
||
) |
Create a leg of a path in the link graph.
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.
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.
new_flow | Amount of flow to push. |
job | Link graph job this node belongs to. |
max_saturation | Maximum saturation of edges. |
Definition at line 221 of file linkgraphjob.cpp.
References AddFlow(), LinkGraphJob::EdgeAnnotation::AddFlow(), LinkGraphJob::EdgeAnnotation::base, LinkGraph::BaseEdge::capacity, LinkGraphJob::EdgeAnnotation::Flow(), flow, node, and parent.
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.
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.
|
inline |
Get capacity ratio of this path.
Definition at line 313 of file linkgraphjob.h.
References capacity, and free_capacity.
Referenced by CapacityAnnotation::IsBetter(), and CapacityAnnotation::UpdateAnnotation().
|
inlinestatic |
Get ratio of free * 16 (so that we get fewer 0) / max(total capacity, 1) (so that we don't divide by 0).
free | Free capacity. |
total | Total capacity. |
Definition at line 304 of file linkgraphjob.h.
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().