
Search this API  
PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 
java.lang.Object y.algo.NetworkFlows
public class NetworkFlows
This class provides sophisticated algorithms for solving classical network flow problems.
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
.
Given a directed graph in which each edge has a capacity and given a source node s
and a sink node
t
, find an st
cut of minimum capacity (i.e., a set of edges of minimum capacity whose
removal would disconnect t
from s
).
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.
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 preflowpush method. 
static int 
calcMaxFlowMinCut(Graph graph,
Node source,
Node sink,
DataProvider eCapDP,
EdgeMap flowEM,
NodeMap sourceCutNM)
Solves a maximum flow problem using the preflowpush 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 

public static int minCostFlow(Graph graph, DataProvider lCapDP, DataProvider uCapDP, DataProvider cost0DP, DataProvider supplyDP, EdgeMap flowEM, NodeMap dualsNM)
This algorithm is a variant of the successive shortest path algorithm (see Ahuja,Magnanti,Orlin: Network flows,
Prentice Hall, 1993, pp.320324). It has the pseudopolynomial 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.
graph
 the given networklCapDP
 the DataProvider
that returns the integer lower bound for the capacity of each edge or
null
if no bound is specifieduCapDP
 the DataProvider
that returns the integer upper bound for the capacity of each edgecost0DP
 the DataProvider
that returns a double value (cost) of each edgesupplyDP
 the DataProvider
that returns the supply/demand of each node; supply is denoted by a
positive value, demand by a negative valueflowEM
 the EdgeMap
that will be filled during the execution with an integer flow for each edgedualsNM
 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
minCostFlow(Graph, DataProvider, DataProvider, DataProvider, EdgeMap, NodeMap)
,
minCostFlow(Graph, Node, Node, DataProvider, DataProvider, EdgeMap, NodeMap)
public static int minCostFlow(Graph graph, DataProvider uCapDP, DataProvider cost0DP, DataProvider supplyDP, EdgeMap flowEM, NodeMap dualsNM)
minCostFlow(Graph, DataProvider, DataProvider, DataProvider, DataProvider, EdgeMap, NodeMap)
to solve a minimum cost flow problem.
graph
 the given networkuCapDP
 the DataProvider
that returns the integer capacity of each edgecost0DP
 the DataProvider
that returns a double value (cost) for each edgesupplyDP
 the DataProvider
that returns the supply/demand of each node; supply is denoted by a
positive value, demand by a negative valueflowEM
 the EdgeMap
that will be filled during the execution with an integer flow for each edgedualsNM
 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
minCostFlow(Graph, Node, Node, DataProvider, DataProvider, EdgeMap, NodeMap)
,
minCostFlow(Graph, DataProvider, DataProvider, DataProvider, DataProvider, EdgeMap, NodeMap)
public static int minCostFlow(Graph graph, Node s, Node t, DataProvider uCapDP, DataProvider cost0DP, EdgeMap flowEM, NodeMap dualsNM)
graph
 the given networks
 the source node of the networkt
 the sink node of the networkuCapDP
 the DataProvider
that returns the integer capacity of each edgecost0DP
 the DataProvider
that returns a double value (cost) for each edgeflowEM
 the EdgeMap
that will be filled during the execution with an integer flow for each edgedualsNM
 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
minCostFlow(Graph, DataProvider, DataProvider, DataProvider, DataProvider, EdgeMap, NodeMap)
,
minCostFlow(Graph, DataProvider, DataProvider, DataProvider, EdgeMap, NodeMap)
public static int calcMaxFlow(Graph graph, Node source, Node sink, DataProvider eCapDP, EdgeMap flowEM)
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
.
graph
 the given networksource
 the source node of the networksink
 the sink node of the networkeCapDP
 the EdgeMap
that returns the integer capacity for each edge. Integer.MAX_VALUE
denotes infinite capacity for an edgeflowEM
 the EdgeMap
that will be filled during the execution with an integer flow for each edge
calcMaxFlowMinCut(Graph, Node, Node, DataProvider, EdgeMap, NodeMap)
public static int calcMaxFlowMinCut(Graph graph, Node source, Node sink, DataProvider eCapDP, EdgeMap flowEM, NodeMap sourceCutNM)
graph
 the given networksource
 the source node of the networksink
 the sink node of the networkeCapDP
 the EdgeMap
that returns the integer capacity for each edge. Integer.MAX_VALUE
denotes infinite capacity for an edgeflowEM
 the EdgeMap
that will be filled during the execution with an integer flow for each edgesourceCutNM
 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
calcMaxFlow(Graph, Node, Node, DataProvider, EdgeMap)

© Copyright 20002022, yWorks GmbH. All rights reserved. 

PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 