MultiCommodityFlow Class Reference

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

#include <mcf.h>

Inheritance diagram for MultiCommodityFlow:

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
LinkGraphJob &	job
	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

job	Link 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_id	ID of the root node.
paths	Paths 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

Tannotation	Annotation to be used.
Tedge_iterator	Iterator to be used for getting outgoing edges.

Parameters

source_node	Node where the algorithm starts.
paths	Container 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

node	Node where the path starts.
to	Node where the path ends.
path	End of the path the flow should be pushed on.
accuracy	Accuracy of the calculation.
max_saturation	If < 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:

• src/linkgraph/mcf.h
• src/linkgraph/mcf.cpp