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	minCostFlow(Graph graph, DataProvider lCapDP, DataProvider uCapDP, DataProvider cost0DP, DataProvider supplyDP, EdgeMap flowEM, NodeMap dualsNM) Solves a mimium 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 maxflow 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 mimium 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 dennoted 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 maxflow 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 dennoted 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 maxflow value.