Minimum cost st-flow, b-flow and circulation


Enumerations

enum  abstractMixedGraph::TMethMCFST {
  abstractMixedGraph::MCF_ST_DEFAULT = -1,
  abstractMixedGraph::MCF_ST_DIJKSTRA = 0,
  abstractMixedGraph::MCF_ST_SAP = 1,
  abstractMixedGraph::MCF_ST_BFLOW = 2
}
enum  abstractMixedGraph::TMethMCF {
  abstractMixedGraph::MCF_BF_DEFAULT = -1,
  abstractMixedGraph::MCF_BF_CYCLE = 0,
  abstractMixedGraph::MCF_BF_COST = 1,
  abstractMixedGraph::MCF_BF_TIGHT = 2,
  abstractMixedGraph::MCF_BF_MEAN = 3,
  abstractMixedGraph::MCF_BF_SAP = 4,
  abstractMixedGraph::MCF_BF_SIMPLEX = 5,
  abstractMixedGraph::MCF_BF_LINEAR = 6,
  abstractMixedGraph::MCF_BF_CAPA = 7,
  abstractMixedGraph::MCF_BF_PHASE1 = 8
}

Functions

TFloat abstractMixedGraph::MinCostSTFlow (TNode source, TNode target) throw (ERRange,ERRejected)
TFloat abstractMixedGraph::MinCostSTFlow (TMethMCFST method, TNode source, TNode target) throw (ERRange,ERRejected)
TFloat abstractMixedGraph::MinCostBFlow (TMethMCF method=MCF_BF_DEFAULT) throw (ERRejected)

Enumeration Type Documentation

enum TMethMCF [inherited]
 

Alternative methods for the minimum cost b-flow solver.

Enumerator:
MCF_BF_DEFAULT  Apply the default method set in goblinController::methMCF.
MCF_BF_CYCLE  Apply the Klein cycle canceling method.
MCF_BF_COST  Apply the Goldberg / Tarjan cost scaling method.
MCF_BF_TIGHT  Apply the Goldberg / Tarjan cost scaling method with eps-tightening.
MCF_BF_MEAN  Apply minimum mean cycle canceling method.
MCF_BF_SAP  Solve by transformation to an st-flow problem.
MCF_BF_SIMPLEX  Apply the network simplex algorithm.
MCF_BF_LINEAR  Solve by transformation to a linear program.
MCF_BF_CAPA  Apply a capacity scaling method.
MCF_BF_PHASE1  Stop after an admissible b-flow has been found.

enum TMethMCFST [inherited]
 

Alternative methods for the minimum cost st-flow solver.

Enumerator:
MCF_ST_DEFAULT  Apply the default method set in goblinController::methMCFST.
MCF_ST_DIJKSTRA  Apply the Dijkstra shortest path method.
MCF_ST_SAP  Apply a label setting shortest path method.
MCF_ST_BFLOW  Solve by transformation to a b-flow problem.


Function Documentation

TFloat MinCostBFlow TMethMCF  method = MCF_BF_DEFAULT  )  throw (ERRejected) [inherited]
 

Compute a minimum cost st-flow by using the specified method.

Parameters:
method A TMethMCF value specifying the applied method
Returns:
The weight of the final b-flow or InfFloat
This is the public interface to all minimum cost b-flow methods. The result is a subgraph in which all nodes are balanced, that is, all node demands are satisfied. The optimal node potentials are exported for sake of post-optimization.

The initial subgraph and node potentials are considered.

TFloat MinCostSTFlow TMethMCFST  method,
TNode  source,
TNode  target
throw (ERRange,ERRejected) [inherited]
 

Compute a minimum cost st-flow by using the specified method.

Parameters:
method A TMethMCFST value specifying the applied method
source A node whose flow excess is minimized
target A node whose flow excess is maximized
Returns:
The weight of the final st-flow or InfFloat
This is the public interface to all minimum cost st-flow methods. The result is a subgraph in which all nodes but source and target are balanced, and the flow excess of the source node s is minimal or the target node is balanced. The optimal node potentials are exported for sake of post-optimization.

It is required that the subgraph at start is a feasible st-flow whose value does not exeed the demand of the target node. The node demands must resolve

The initial node potentials are considered. If reduced cost optimality is violated, the potentials are adjusted so that the search for shortest augmenting paths can run with non-negative arc lengths.

TFloat MinCostSTFlow TNode  source,
TNode  target
throw (ERRange,ERRejected) [inherited]
 

Compute a minimum cost st-flow by using the default method.

Parameters:
source A node whose flow excess is minimized
target A node whose flow excess is maximized
Returns:
The weight of the final st-flow or InfFloat
This method returns a subgraph in which all nodes but source and target are balanced, and the flow excess of the source node is minimal or the target node is balanced. The optimal node potentials are exported for sake of post-optimization.

It is required that the subgraph at start is a feasible st-flow whose value does not exeed the demand of the target node. The node demands must resolve

The initial node potentials are considered. If reduced cost optimality is violated, the potentials are adjusted so that the search for shortest augmenting paths can run with non-negative arc lengths.