Packagecom.yworks.yfiles.algo
Classpublic class NetworkFlows
InheritanceNetworkFlows Inheritance YObject Inheritance Object

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


Public Methods
 MethodDefined By
  
NetworkFlows(init:Boolean = true)
NetworkFlows
  
calcMaxFlow(graph:Graph, source:Node, sink:Node, eCapDP:DataProvider, flowEM:EdgeMap):int
[static] Solves a maximum flow problem using the preflow-push method.
NetworkFlows
  
calcMaxFlowMinCut(graph:Graph, source:Node, sink:Node, eCapDP:DataProvider, flowEM:EdgeMap, sourceCutNM:NodeMap):int
[static] Like calcMaxFlow() this method solves a maximum flow problem.
NetworkFlows
 Inherited
equals(o:Object):Boolean
YObject
  
getClass():Class
[override]
NetworkFlows
 Inherited
hashCode():int
YObject
  
minCostFlow(graph:Graph, uCapDP:DataProvider, cost0DP:DataProvider, supplyDP:DataProvider, flowEM:EdgeMap, dualsNM:NodeMap):int
[static] Solves a min-cost flow optimization problem.
NetworkFlows
  
minCostFlow2(graph:Graph, lCapDP:DataProvider, uCapDP:DataProvider, cost0DP:DataProvider, supplyDP:DataProvider, flowEM:EdgeMap, dualsNM:NodeMap):int
[static] Solves a minimum cost flow problem with a capacity scaling algorithm.
NetworkFlows
  
minCostFlowSourceSink(graph:Graph, s:Node, t:Node, uCapDP:DataProvider, cost0DP:DataProvider, flowEM:EdgeMap, dualsNM:NodeMap):int
[static] Solves a min-cost max-flow optimization problem.
NetworkFlows
  
newNetworkFlows():NetworkFlows
[static]
NetworkFlows
Protected Methods
 MethodDefined By
  
initNetworkFlows():void
NetworkFlows
Constructor Detail
NetworkFlows()Constructor
public function NetworkFlows(init:Boolean = true)



Parameters
init:Boolean (default = true)
Method Detail
calcMaxFlow()method
public static function calcMaxFlow(graph:Graph, source:Node, sink:Node, eCapDP:DataProvider, flowEM:EdgeMap):int

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:Graph — the network.
 
source:Node — the source of the network.
 
sink:Node — the sink of the network.
 
eCapDP:DataProvider — the capacity of the arcs. Infinite capacity is denoted by Integer.MAX_VALUE
 
flowEM:EdgeMap — here the resulting flow is stored.

Returns
int — the maximum flow value.
calcMaxFlowMinCut()method 
public static function calcMaxFlowMinCut(graph:Graph, source:Node, sink:Node, eCapDP:DataProvider, flowEM:EdgeMap, sourceCutNM:NodeMap):int

Like calcMaxFlow() 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

graph:Graph
 
source:Node
 
sink:Node
 
eCapDP:DataProvider
 
flowEM:EdgeMap
 
sourceCutNM:NodeMap — 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
int — 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.

See also

calcMaxFlow()
getClass()method 
override public function getClass():Class

Returns
Class
initNetworkFlows()method 
protected final function initNetworkFlows():void

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

Solves a min-cost flow optimization problem.

Parameters

graph:Graph — the network.
 
uCapDP:DataProvider — the capacity of the arcs. Infinite capacity is denoted by Integer.MAX_VALUE
 
cost0DP:DataProvider — the costs of the arcs.
 
supplyDP:DataProvider — the supply/demand of the nodes. Supply is denoted by a positive value, demand by a negative value.
 
flowEM:EdgeMap — here the resulting flow is stored.
 
dualsNM:NodeMap — here the resulting dual values are stored. Dual values are also referred as potentials.

Returns
int — the cost of the flow.
minCostFlow2()method 
public static function minCostFlow2(graph:Graph, lCapDP:DataProvider, uCapDP:DataProvider, cost0DP:DataProvider, supplyDP:DataProvider, flowEM:EdgeMap, dualsNM:NodeMap):int

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:Graph — the network.
 
lCapDP:DataProvider — the lower bound on the arc flow. May be null.
 
uCapDP:DataProvider — the capacity of the arcs. Infinite capacity is denoted by Integer.MAX_VALUE
 
cost0DP:DataProvider — the costs of the arcs.
 
supplyDP:DataProvider — the supply/demand of the nodes. Supply is denoted by a positive value, demand by a negative value.
 
flowEM:EdgeMap — here the resulting flow is stored.
 
dualsNM:NodeMap — here the resulting dual values are stored. Dual values are also referred as potentials. May be null.

Returns
int — the cost of the flow.
minCostFlowSourceSink()method 
public static function minCostFlowSourceSink(graph:Graph, s:Node, t:Node, uCapDP:DataProvider, cost0DP:DataProvider, flowEM:EdgeMap, dualsNM:NodeMap):int

Solves a min-cost max-flow optimization problem.

Parameters

graph:Graph — the network.
 
s:Node — source of the network.
 
t:Node — sink of the network.
 
uCapDP:DataProvider — the capacity of the arcs. Infinite capacity is denoted by Integer.MAX_VALUE
 
cost0DP:DataProvider — the costs of the arcs.
 
flowEM:EdgeMap — here the resulting flow is stored.
 
dualsNM:NodeMap — here the resulting dual values are stored. Dual values are also referred as potentials.

Returns
int — the cost of the flow.
newNetworkFlows()method 
public static function newNetworkFlows():NetworkFlows

Returns
NetworkFlows




Wed Oct 7 2015, 04:43 PM +02:00