y.algo
Class NetworkFlows

java.lang.Object
  y.algo.NetworkFlows

public class NetworkFlows
extends 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

See Also:

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

See Also:

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

See Also:

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

See Also:

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

See Also:

calcMaxFlow(Graph, Node, Node, DataProvider, EdgeMap)