OpenTTD Source
20241121-master-g67a0fccfad
|
First pass of the MCF calculation. More...
#include <mcf.h>
Public Member Functions | |
MCF1stPass (LinkGraphJob &job) | |
Run the first pass of the MCF calculation. More... | |
Private Member Functions | |
bool | EliminateCycles () |
Eliminate all cycles in the graph. More... | |
bool | EliminateCycles (PathVector &path, NodeID origin_id, NodeID next_id) |
Eliminate cycles for origin_id in the graph. More... | |
void | EliminateCycle (PathVector &path, Path *cycle_begin, uint flow) |
Eliminate a cycle of the given flow in the given set of paths. More... | |
uint | FindCycleFlow (const PathVector &path, const Path *cycle_begin) |
Find the flow along a cycle including cycle_begin in path. More... | |
Additional Inherited Members | |
Protected Member Functions inherited from MultiCommodityFlow | |
MultiCommodityFlow (LinkGraphJob &job) | |
Constructor. More... | |
template<class Tannotation , class Tedge_iterator > | |
void | Dijkstra (NodeID from, PathVector &paths) |
A slightly modified Dijkstra algorithm. More... | |
uint | PushFlow (Node &node, NodeID to, Path *path, uint accuracy, uint max_saturation) |
Push flow along a path and update the unsatisfied_demand of the associated edge. More... | |
void | CleanupPaths (NodeID source, PathVector &paths) |
Clean up paths that lead nowhere and the root path. More... | |
Protected Attributes inherited from MultiCommodityFlow | |
LinkGraphJob & | job |
Job we're working with. | |
uint | max_saturation |
Maximum saturation for edges. | |
First pass of the MCF calculation.
Saturates shortest paths first, creates new paths if needed, eliminates cycles. This calculation is of exponential complexity in the number of nodes but the constant factors are sufficiently small to make it usable for most real-life link graph components. You can deal with performance problems that might occur here in multiple ways:
MCF1stPass::MCF1stPass | ( | LinkGraphJob & | job | ) |
|
private |
Eliminate a cycle of the given flow in the given set of paths.
path | Set of paths containing the cycle. |
cycle_begin | Part of the cycle to start at. |
flow | Flow along the cycle. |
Definition at line 377 of file mcf.cpp.
References Path::GetFlow(), Path::GetNode(), Path::GetParent(), MultiCommodityFlow::job, and Path::ReduceFlow().
Referenced by EliminateCycles().
|
private |
Eliminate all cycles in the graph.
Check paths starting at each node for potential cycles.
Definition at line 481 of file mcf.cpp.
Referenced by EliminateCycles().
|
private |
Eliminate cycles for origin_id in the graph.
Start searching at next_id and work recursively. Also "summarize" paths: Add up the flows along parallel paths in one.
path | Paths checked in parent calls to this method. |
origin_id | Origin of the paths to be checked. |
next_id | Next node to be checked. |
Definition at line 408 of file mcf.cpp.
References Path::AddFlow(), EliminateCycle(), EliminateCycles(), FindCycleFlow(), Path::GetFlow(), Path::GetNode(), Path::GetOrigin(), Path::invalid_path, MultiCommodityFlow::job, and Path::ReduceFlow().
|
private |
Find the flow along a cycle including cycle_begin in path.
path | Set of paths that form the cycle. |
cycle_begin | Path to start at. |
Definition at line 360 of file mcf.cpp.
References Path::GetFlow(), and Path::GetNode().
Referenced by EliminateCycles().