OpenTTD Source  20241121-master-g67a0fccfad
MultiCommodityFlow Class Reference

Multi-commodity flow calculating base class. More...

#include <mcf.h>

Inheritance diagram for MultiCommodityFlow:
MCF1stPass MCF2ndPass

Protected Member Functions

 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

LinkGraphJobjob
 Job we're working with.
 
uint max_saturation
 Maximum saturation for edges.
 

Detailed Description

Multi-commodity flow calculating base class.

Definition at line 13 of file mcf.h.

Constructor & Destructor Documentation

◆ MultiCommodityFlow()

MultiCommodityFlow::MultiCommodityFlow ( LinkGraphJob job)
inlineprotected

Constructor.

Parameters
jobLink graph job being executed.

Definition at line 19 of file mcf.h.

Member Function Documentation

◆ CleanupPaths()

void MultiCommodityFlow::CleanupPaths ( NodeID  source_id,
PathVector &  paths 
)
protected

Clean up paths that lead nowhere and the root path.

Parameters
source_idID of the root node.
pathsPaths to be cleaned up.

Definition at line 312 of file mcf.cpp.

References Path::Detach(), Path::GetFlow(), Path::GetNode(), Path::GetNumChildren(), and Path::GetParent().

◆ Dijkstra()

template<class Tannotation , class Tedge_iterator >
void MultiCommodityFlow::Dijkstra ( NodeID  source_node,
PathVector &  paths 
)
protected

A slightly modified Dijkstra algorithm.

Grades the paths not necessarily by distance, but by the value Tannotation computes. It uses the max_saturation setting to artificially decrease capacities.

Template Parameters
TannotationAnnotation to be used.
Tedge_iteratorIterator to be used for getting outgoing edges.
Parameters
source_nodeNode where the algorithm starts.
pathsContainer for the paths to be calculated.

Definition at line 257 of file mcf.cpp.

References job.

◆ PushFlow()

uint MultiCommodityFlow::PushFlow ( Node node,
NodeID  to,
Path path,
uint  accuracy,
uint  max_saturation 
)
protected

Push flow along a path and update the unsatisfied_demand of the associated edge.

Parameters
nodeNode where the path starts.
toNode where the path ends.
pathEnd of the path the flow should be pushed on.
accuracyAccuracy of the calculation.
max_saturationIf < UINT_MAX only push flow up to the given saturation, otherwise the path can be "overloaded".

Definition at line 344 of file mcf.cpp.

References Path::AddFlow(), Clamp(), and job.


The documentation for this class was generated from the following files: