com.yworks.yfiles.algorithms

Class NetworkFlows

java.lang.Object

com.yworks.yfiles.algorithms.NetworkFlows

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

Modifier and Type	Method and Description
static int	calcMaxFlow(Graph graph, Node source, Node sink, IDataProvider eCapDP, IEdgeMap flowEM) Solves a maximum flow problem using the preflow-push method.
static int	calcMaxFlowMinCut(Graph graph, Node source, Node sink, IDataProvider eCapDP, IEdgeMap flowEM, INodeMap 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, IDataProvider lCapDP, IDataProvider uCapDP, IDataProvider cost0DP, IDataProvider supplyDP, IEdgeMap flowEM, INodeMap dualsNM) Solves a minimum cost flow problem with a capacity scaling algorithm.
static int	minCostFlow(Graph graph, IDataProvider uCapDP, IDataProvider cost0DP, IDataProvider supplyDP, IEdgeMap flowEM, INodeMap dualsNM) Uses method minCostFlow(Graph, IDataProvider, IDataProvider, IDataProvider, IDataProvider, IEdgeMap, INodeMap) to solve a minimum cost flow problem.
static int	minCostFlow(Graph graph, Node s, Node t, IDataProvider uCapDP, IDataProvider cost0DP, IEdgeMap flowEM, INodeMap 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

calcMaxFlow

public static final int calcMaxFlow(Graph graph,
                                    Node source,
                                    Node sink,
                                    IDataProvider eCapDP,
                                    IEdgeMap 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 IEdgeMap that returns the integer capacity of each edge or null if no bound is specified

flowEM - the IEdgeMap 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, IDataProvider, IEdgeMap, INodeMap)

calcMaxFlowMinCut

public static final int calcMaxFlowMinCut(Graph graph,
                                          Node source,
                                          Node sink,
                                          IDataProvider eCapDP,
                                          IEdgeMap flowEM,
                                          INodeMap 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 IEdgeMap that returns the integer capacity of each edge or null if no bound is specified

flowEM - the IEdgeMap that will be filled during the execution with an integer flow for each edge

sourceCutNM - the INodeMap 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, IDataProvider, IEdgeMap)

minCostFlow

public static final int minCostFlow(Graph graph,
                                    IDataProvider lCapDP,
                                    IDataProvider uCapDP,
                                    IDataProvider cost0DP,
                                    IDataProvider supplyDP,
                                    IEdgeMap flowEM,
                                    INodeMap 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 IDataProvider that returns the integer lower bound for the capacity of each edge or null if no bound is specified

uCapDP - the IDataProvider that returns the integer upper bound for the capacity of each edge or null if no bound is specified

cost0DP - the IDataProvider that returns a double value (cost) of each edge

supplyDP - the IDataProvider that returns the supply/demand of each node; supply is denoted by a positive value, demand by a negative value

flowEM - the IEdgeMap that will be filled during the execution with an integer flow for each edge

dualsNM - the INodeMap 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, IDataProvider, IDataProvider, IDataProvider, IEdgeMap, INodeMap), minCostFlow(Graph, Node, Node, IDataProvider, IDataProvider, IEdgeMap, INodeMap)

minCostFlow

public static final int minCostFlow(Graph graph,
                                    IDataProvider uCapDP,
                                    IDataProvider cost0DP,
                                    IDataProvider supplyDP,
                                    IEdgeMap flowEM,
                                    INodeMap dualsNM)

Uses method minCostFlow(Graph, IDataProvider, IDataProvider, IDataProvider, IDataProvider, IEdgeMap, INodeMap) to solve a minimum cost flow problem.

Parameters:

graph - the given network

uCapDP - the IDataProvider that returns the integer capacity of each edge or null if no bound is specified

cost0DP - the IDataProvider that returns a double value (cost) for each edge

supplyDP - the IDataProvider that returns the supply/demand of each node; supply is denoted by a positive value, demand by a negative value

flowEM - the IEdgeMap that will be filled during the execution with an integer flow for each edge

dualsNM - the INodeMap 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, IDataProvider, IDataProvider, IEdgeMap, INodeMap), minCostFlow(Graph, IDataProvider, IDataProvider, IDataProvider, IDataProvider, IEdgeMap, INodeMap)

minCostFlow

public static final int minCostFlow(Graph graph,
                                    Node s,
                                    Node t,
                                    IDataProvider uCapDP,
                                    IDataProvider cost0DP,
                                    IEdgeMap flowEM,
                                    INodeMap 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 IDataProvider that returns the integer capacity of each edge or null if no bound is specified

cost0DP - the IDataProvider that returns a double value (cost) for each edge

flowEM - the IEdgeMap that will be filled during the execution with an integer flow for each edge

dualsNM - the INodeMap 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, IDataProvider, IDataProvider, IDataProvider, IDataProvider, IEdgeMap, INodeMap), minCostFlow(Graph, IDataProvider, IDataProvider, IDataProvider, IEdgeMap, INodeMap)