Search this API

## y.algo Class NetworkFlows

```java.lang.Object
y.algo.NetworkFlows
```

`public class NetworkFlowsextends java.lang.Object`

This class provides sophisticated algorithms for solving classical network flow problems.

### Definitions

Maximum flow problem:

Given a directed graph in which each edge has a capacity and given a source node `s` and a sink node `t`, find a flow of maximum value from `s` to `t`.

Minimum cut problem:

Given a directed graph in which each edge has a capacity and given a source node `s` and a sink node `t`, find an `s-t` cut of minimum capacity (i.e., a set of edges of minimum capacity whose removal would disconnect `t` from `s`).

Minimum cost flow problem:

Given a directed graph in which each edge has a cost and a capacity and each node has a supply or demand, find a flow of minimum total cost that satisfies the edge capacities and the node balances.

Minimum cost maximum flow problem:

Given a directed graph in which each edge has a cost and a capacity and given a source node `s` and a sink node `t`, find a flow of maximum value from `s` to `t` that has the minimum total cost.

Method Summary
`static int` ```calcMaxFlow(Graph graph, Node source, Node sink, DataProvider eCapDP, EdgeMap flowEM)```
Solves a maximum flow problem using the preflow-push method.
`static int` ```calcMaxFlowMinCut(Graph graph, Node source, Node sink, DataProvider eCapDP, EdgeMap flowEM, NodeMap sourceCutNM)```
Solves a maximum flow problem using the preflow-push method but additionally marks all nodes that belong to the minimum cut set that is associated with the source of the network.
`static int` ```minCostFlow(Graph graph, DataProvider lCapDP, DataProvider uCapDP, DataProvider cost0DP, DataProvider supplyDP, EdgeMap flowEM, NodeMap dualsNM)```
Solves a minimum cost flow problem with a capacity scaling algorithm.
`static int` ```minCostFlow(Graph graph, DataProvider uCapDP, DataProvider cost0DP, DataProvider supplyDP, EdgeMap flowEM, NodeMap dualsNM)```
Uses method `minCostFlow(Graph, DataProvider, DataProvider, DataProvider, DataProvider, EdgeMap, NodeMap)` to solve a minimum cost flow problem.
`static int` ```minCostFlow(Graph graph, Node s, Node t, DataProvider uCapDP, DataProvider cost0DP, EdgeMap flowEM, NodeMap dualsNM)```
Solves a minimum cost maximum flow problem.

Methods inherited from class java.lang.Object
`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`

Method Detail

### minCostFlow

```public static int minCostFlow(Graph graph,
DataProvider lCapDP,
DataProvider uCapDP,
DataProvider cost0DP,
DataProvider supplyDP,
EdgeMap flowEM,
NodeMap dualsNM)```
Solves a minimum cost flow problem with a capacity scaling algorithm.

This algorithm is a variant of the successive shortest path algorithm (see Ahuja,Magnanti,Orlin: Network flows, Prentice Hall, 1993, pp.320-324). It has the pseudo-polynomial running time `O(m*log U*(m+n log n))` where `n` is the number of nodes in the network, `m` the number of edges and `U` the maximal edge capacity.

Edges may have infinite capacity, which is denoted by the value `Integer.MAX_VALUE`.

There are no restriction for the costs. In particular, they can also be negative.

Parameters:
`graph` - the given network
`lCapDP` - the `DataProvider` that returns the integer lower bound for the capacity of each edge or `null` if no bound is specified
`uCapDP` - the `DataProvider` that returns the integer upper bound for the capacity of each edge
`cost0DP` - the `DataProvider` that returns a double value (cost) of each edge
`supplyDP` - the `DataProvider` that returns the supply/demand of each node; supply is denoted by a positive value, demand by a negative value
`flowEM` - the `EdgeMap` that will be filled during the execution with an integer flow for each edge
`dualsNM` - the `NodeMap` that will be filled during the execution with an integer value (dual value) for each node or `null` if no such values occur; dual values are also referred as potentials
Returns:
the total cost of the flow
`minCostFlow(Graph, DataProvider, DataProvider, DataProvider, EdgeMap, NodeMap)`, `minCostFlow(Graph, Node, Node, DataProvider, DataProvider, EdgeMap, NodeMap)`

### minCostFlow

```public static int minCostFlow(Graph graph,
DataProvider uCapDP,
DataProvider cost0DP,
DataProvider supplyDP,
EdgeMap flowEM,
NodeMap dualsNM)```
Uses method `minCostFlow(Graph, DataProvider, DataProvider, DataProvider, DataProvider, EdgeMap, NodeMap)` to solve a minimum cost flow problem.

Parameters:
`graph` - the given network
`uCapDP` - the `DataProvider` that returns the integer capacity of each edge
`cost0DP` - the `DataProvider` that returns a double value (cost) for each edge
`supplyDP` - the `DataProvider` that returns the supply/demand of each node; supply is denoted by a positive value, demand by a negative value
`flowEM` - the `EdgeMap` that will be filled during the execution with an integer flow for each edge
`dualsNM` - the `NodeMap` that will be filled during the execution with an integer value (dual value) for each node or `null` if no such values occur; dual values are also referred as potentials
Returns:
the total cost of the flow
`minCostFlow(Graph, Node, Node, DataProvider, DataProvider, EdgeMap, NodeMap)`, `minCostFlow(Graph, DataProvider, DataProvider, DataProvider, DataProvider, EdgeMap, NodeMap)`

### minCostFlow

```public static int minCostFlow(Graph graph,
Node s,
Node t,
DataProvider uCapDP,
DataProvider cost0DP,
EdgeMap flowEM,
NodeMap dualsNM)```
Solves a minimum cost maximum flow problem.

Parameters:
`graph` - the given network
`s` - the source node of the network
`t` - the sink node of the network
`uCapDP` - the `DataProvider` that returns the integer capacity of each edge
`cost0DP` - the `DataProvider` that returns a double value (cost) for each edge
`flowEM` - the `EdgeMap` that will be filled during the execution with an integer flow for each edge
`dualsNM` - the `NodeMap` that will be filled during the execution with an integer value (dual value) for each node or `null` if no such values occur; dual values are also referred as potentials
Returns:
the total cost of the flow
`minCostFlow(Graph, DataProvider, DataProvider, DataProvider, DataProvider, EdgeMap, NodeMap)`, `minCostFlow(Graph, DataProvider, DataProvider, DataProvider, EdgeMap, NodeMap)`

### calcMaxFlow

```public static int calcMaxFlow(Graph graph,
Node source,
Node sink,
DataProvider eCapDP,
EdgeMap flowEM)```
Solves a maximum flow problem using the preflow-push method. The implementation is based on
• Mehlhorn, Naeher: LEDA: a platform for combinatorial and geometric computing, Cambridge University Press, 2000, pp. 443-488.

The worst case running time is `O(mdeg * n^2 * m^(1/2))`, where `n` is the number of nodes in the network, `m` the number of edges and `mdeg` the maximal degree of any node.

Edges may have infinite capacity, which is denoted by the value `Integer.MAX_VALUE`.

Parameters:
`graph` - the given network
`source` - the source node of the network
`sink` - the sink node of the network
`eCapDP` - the `EdgeMap` that returns the integer capacity for each edge. `Integer.MAX_VALUE` denotes infinite capacity for an edge
`flowEM` - the `EdgeMap` that will be filled during the execution with an integer flow for each edge
Returns:
the maximum flow value
`calcMaxFlowMinCut(Graph, Node, Node, DataProvider, EdgeMap, NodeMap)`

### calcMaxFlowMinCut

```public static int calcMaxFlowMinCut(Graph graph,
Node source,
Node sink,
DataProvider eCapDP,
EdgeMap flowEM,
NodeMap sourceCutNM)```
Solves a maximum flow problem using the preflow-push method but additionally marks all nodes that belong to the minimum cut set that is associated with the source of the network.

Parameters:
`graph` - the given network
`source` - the source node of the network
`sink` - the sink node of the network
`eCapDP` - the `EdgeMap` that returns the integer capacity for each edge. `Integer.MAX_VALUE` denotes infinite capacity for an edge
`flowEM` - the `EdgeMap` that will be filled during the execution with an integer flow for each edge
`sourceCutNM` - the `NodeMap` that will be filled during the execution and returns a boolean value indicating whether or not a node belongs to the cut set associated with the source of the network
Returns:
the maximum flow value
`calcMaxFlow(Graph, Node, Node, DataProvider, EdgeMap)`