|
OpenTTD Source
1.11.0-beta2
|
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 Types | |
| enum | PathCapacityBoundaries { PATH_CAP_MULTIPLIER = 16, PATH_CAP_MIN_FREE = (INT_MIN + 1) / PATH_CAP_MULTIPLIER, PATH_CAP_MAX_FREE = (INT_MAX - 1) / PATH_CAP_MULTIPLIER } |
| Some boundaries to clamp against in order to avoid integer overflows. | |
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 365 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 273 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 246 of file linkgraphjob.cpp.
References LinkGraphJob::Edge::AddFlow(), LinkGraph::EdgeWrapper< Tedge >::Capacity(), and LinkGraphJob::Edge::Flow().
| 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 224 of file linkgraphjob.cpp.
References capacity, distance, free_capacity, num_children, and origin.
|
inline |
Get capacity ratio of this path.
Definition at line 402 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 393 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 367 of file linkgraphjob.h.
Referenced by MCF1stPass::EliminateCycles().