y.algo
Class NetworkFlows

java.lang.Object
  y.algo.NetworkFlows

public class NetworkFlows
extends Object

Provides sophisticated algorithms for solving classical network flow problems like MinCostFlow or MaxFlow.

Constructor Summary

NetworkFlows()

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) Like calcMaxFlow(Graph,Node,Node,DataProvider,EdgeMap) this method solves a maximum flow problem.
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) Solves a min-cost flow optimization problem.
static int	minCostFlow(Graph graph, Node s, Node t, DataProvider uCapDP, DataProvider cost0DP, EdgeMap flowEM, NodeMap dualsNM) Solves a min-cost max-flow optimization problem.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

NetworkFlows

public NetworkFlows()

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. (see Ahuja,Magnanti,Orlin: Network flows, Prentice Hall, 1993, pp.360-362). 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, especially they can be negative. Solves a min-cost flow optimization problem.

Parameters:

graph - the network.

lCapDP - the lower bound on the arc flow. May be null.

uCapDP - the capacity of the arcs. Infinite capacity is denoted by Integer.MAX_VALUE

cost0DP - the costs of the arcs.

supplyDP - the supply/demand of the nodes. Supply is denoted by a positive value, demand by a negative value.

flowEM - here the resulting flow is stored.

dualsNM - here the resulting dual values are stored. Dual values are also referred as potentials. May be null.

Returns:

the cost of the flow.

minCostFlow

public static int minCostFlow(Graph graph,
                              DataProvider uCapDP,
                              DataProvider cost0DP,
                              DataProvider supplyDP,
                              EdgeMap flowEM,
                              NodeMap dualsNM)

Solves a min-cost flow optimization problem.

Parameters:

graph - the network.

uCapDP - the capacity of the arcs. Infinite capacity is denoted by Integer.MAX_VALUE

cost0DP - the costs of the arcs.

supplyDP - the supply/demand of the nodes. Supply is denoted by a positive value, demand by a negative value.

flowEM - here the resulting flow is stored.

dualsNM - here the resulting dual values are stored. Dual values are also referred as potentials.

Returns:

the cost of the flow.

minCostFlow

public static int minCostFlow(Graph graph,
                              Node s,
                              Node t,
                              DataProvider uCapDP,
                              DataProvider cost0DP,
                              EdgeMap flowEM,
                              NodeMap dualsNM)

Solves a min-cost max-flow optimization problem.

Parameters:

graph - the network.

s - source of the network.

t - sink of the network.

uCapDP - the capacity of the arcs. Infinite capacity is denoted by Integer.MAX_VALUE

cost0DP - the costs of the arcs.

flowEM - here the resulting flow is stored.

dualsNM - here the resulting dual values are stored. Dual values are also referred as potentials.

Returns:

the cost of the flow.

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. (see 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 network.

source - the source of the network.

sink - the sink of the network.

eCapDP - the capacity of the arcs. Infinite capacity is denoted by Integer.MAX_VALUE

flowEM - here the resulting flow is stored.

Returns:

the maximum flow value.

calcMaxFlowMinCut

public static int calcMaxFlowMinCut(Graph graph,
                                    Node source,
                                    Node sink,
                                    DataProvider eCapDP,
                                    EdgeMap flowEM,
                                    NodeMap sourceCutNM)

Like calcMaxFlow(Graph,Node,Node,DataProvider,EdgeMap) this method solves a maximum flow problem. Additionally, this method marks all nodes that belong to the minimum cut set that is associated with the source of the network.

Parameters:

sourceCutNM - return value. This map will provide a boolean value for each node that indicates whether or not a node belongs to the cut set associated with the source of the network.

Returns:

the maximum flow value which also corresponds to the capacity of all edges that cross from the cut set associated with the network source to the cut set associated with the network sink.