|
| CapacityAnnotation (NodeID n, bool source=false) |
| Constructor. More...
|
|
bool | IsBetter (const CapacityAnnotation *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...
|
|
int | GetAnnotation () const |
| Return the actual value of the annotation, in this case the capacity. More...
|
|
void | UpdateAnnotation () |
| Update the cached annotation value.
|
|
| 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 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 Path * | invalid_path = new Path(INVALID_NODE, true) |
| Static instance of an invalid path. More...
|
|
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 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 |
|
Capacity-based annotation for use in the Dijkstra algorithm.
This annotation rates paths according to the maximum capacity of their edges. The Dijkstra algorithm still gives meaningful results like this as the capacity of a path can only decrease or stay the same if you add more edges.
Definition at line 54 of file mcf.cpp.