This class provides sophisticated algorithms for solving classical network flow problems.
Inheritance Hierarchy
NetworkFlowAlgorithm
Remarks
Note: Methods of this class work with instances of Graph. To solve flow problems on IGraph instances use MaximumFlow or MinimumCostFlow instead.
Definitions
- Maximum flow problem: – Given a directed graph in which each edge has a capacity and given a source node
sand a sink nodet, find a flow of maximum value fromstot. - Minimum cut problem: – Given a directed graph in which each edge has a capacity and given a source node
sand a sink nodet, find ans-tcut of minimum capacity (i.e., a set of edges of minimum capacity whose removal would disconnecttfroms). - 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
sand a sink nodet, find a flow of maximum value fromstotthat has the minimum total cost.
Type Details
- yfiles module
- algorithms
- yfiles-umd modules
- All layout modules, view-layout-bridge
- Legacy UMD name
- yfiles.algorithms.NetworkFlows
Static Methods
calcMaxFlow
(graph: Graph, source: YNode, sink: YNode, eCapDP: IDataProvider, flowEM: IEdgeMap) : numberSolves a maximum flow problem using the preflow-push method.
Remarks
Note: This method works with instances of Graph. To solve a maximum flow problem on IGraph instances use MaximumFlow instead.
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 0x7FFFFFFF.
Parameters
options - Object
A map of options to pass to the method.
A map of options to pass to the method.
- graph - Graph
- the given network
- source - YNode
- the source node of the network
- sink - YNode
- the sink node of the network
- eCapDP - IDataProvider
- the IEdgeMap that returns the integer capacity for each edge.
0x7FFFFFFFdenotes infinite capacity for an edgeDomain Edge Values number an value representing the capacity of each edge with 0x7FFFFFFFdenoting infinite capacity for an edge - flowEM - IEdgeMap
- the IEdgeMap that will be filled during the execution with an integer flow for each edge
Domain Edge Values number an value representing the resulting flow of each edge
Returns
- ↪number
- the maximum flow value
See Also
calcMaxFlowMinCut
(graph: Graph, source: YNode, sink: YNode, eCapDP: IDataProvider, flowEM: IEdgeMap, sourceCutNM: INodeMap) : numberSolves 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.
Remarks
Note: This method works with instances of Graph. To solve a maximum flow problem on IGraph instances use MaximumFlow instead.
Parameters
options - Object
A map of options to pass to the method.
A map of options to pass to the method.
- graph - Graph
- the given network
- source - YNode
- the source node of the network
- sink - YNode
- the sink node of the network
- eCapDP - IDataProvider
- the IEdgeMap that returns the integer capacity for each edge.
0x7FFFFFFFdenotes infinite capacity for an edgeDomain Edge Values number an value representing the capacity of each edge with 0x7FFFFFFFdenoting infinite capacity for an edge - flowEM - IEdgeMap
- the IEdgeMap that will be filled during the execution with an integer flow for each edge
Domain Edge Values number an value representing the resulting flow of each edge - sourceCutNM - INodeMap
- 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
Domain YNode Values boolean trueif the node belongs to the cut set associated with the source of the network,falseotherwise
Returns
- ↪number
- the maximum flow value
See Also
minCostFlow
(graph: Graph, lCapDP: IDataProvider, uCapDP: IDataProvider, cost0DP: IDataProvider, supplyDP: IDataProvider, flowEM: IEdgeMap, dualsNM: INodeMap) : numberSolves a minimum cost flow problem with a capacity scaling algorithm.
Remarks
Note: This method works with instances of Graph. To solve a minimum-cost flow problem on IGraph instances use MinimumCostFlow instead.
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 0x7FFFFFFF.
There are no restriction for the costs. In particular, they can also be negative.
Parameters
options - Object
A map of options to pass to the method.
A map of options to pass to the method.
- graph - Graph
- the given network
- lCapDP - IDataProvider
- the IDataProvider that returns the integer lower bound for the capacity of each edge or
nullif no bound is specifiedDomain Edge Values number an value representing the lower bound of the capacity of each edge or nullif no bound is specified for an edge - uCapDP - IDataProvider
- the IDataProvider that returns the integer upper bound for the capacity of each edge
Domain Edge Values number an value representing the upper bound of the capacity of each edge - cost0DP - IDataProvider
- the IDataProvider that returns a double value (cost) of each edge
Domain Edge Values number an value representing the cost of each edge - supplyDP - IDataProvider
- the IDataProvider that returns the supply/demand of each node; supply is denoted by a positive value, demand by a negative value
Domain YNode Values number an value representing the supply/demand of each node - flowEM - IEdgeMap
- the IEdgeMap that will be filled during the execution with an integer flow for each edge
Domain Edge Values number an value representing the resulting flow of each edge - dualsNM - INodeMap
- the INodeMap that will be filled during the execution with an integer value (dual value) for each node or
nullif no such values occur; dual values are also referred as potentialsDomain YNode Values number an value representing the resulting dual value for each node or nullif no such values occur
Returns
- ↪number
- the total cost of the flow
See Also
minCostFlow
(graph: Graph, uCapDP: IDataProvider, cost0DP: IDataProvider, supplyDP: IDataProvider, flowEM: IEdgeMap, dualsNM: INodeMap) : numberUses method minCostFlow to solve a minimum cost flow problem.
Remarks
Note: This method works with instances of Graph. To solve a minimum-cost flow problem on IGraph instances use MinimumCostFlow instead.
Parameters
options - Object
A map of options to pass to the method.
A map of options to pass to the method.
- graph - Graph
- the given network
- uCapDP - IDataProvider
- the IDataProvider that returns the integer capacity of each edge
Domain Edge Values number an value representing the capacity of each edge - cost0DP - IDataProvider
- the IDataProvider that returns a double value (cost) for each edge
Domain Edge Values number an value representing the cost of each edge - supplyDP - IDataProvider
- the IDataProvider that returns the supply/demand of each node; supply is denoted by a positive value, demand by a negative value
Domain YNode Values number an value representing the supply/demand of each node - flowEM - IEdgeMap
- the IEdgeMap that will be filled during the execution with an integer flow for each edge
Domain Edge Values number an value representing the resulting flow of each edge - dualsNM - INodeMap
- the INodeMap that will be filled during the execution with an integer value (dual value) for each node or
nullif no such values occur; dual values are also referred as potentialsDomain YNode Values number an value representing the resulting dual value for each node or nullif no such values occur
Returns
- ↪number
- the total cost of the flow
See Also
minCostFlow
(graph: Graph, s: YNode, t: YNode, uCapDP: IDataProvider, cost0DP: IDataProvider, flowEM: IEdgeMap, dualsNM: INodeMap) : numberSolves a minimum cost maximum flow problem.
Remarks
Note: This method works with instances of Graph. To solve a minimum-cost flow problem on IGraph instances use MinimumCostFlow instead.
Parameters
options - Object
A map of options to pass to the method.
A map of options to pass to the method.
- graph - Graph
- the given network
- s - YNode
- the source node of the network
- t - YNode
- the sink node of the network
- uCapDP - IDataProvider
- the IDataProvider that returns the integer capacity of each edge
Domain Edge Values number an value representing the capacity of each edge - cost0DP - IDataProvider
- the IDataProvider that returns a double value (cost) for each edge
Domain Edge Values number an value representing the cost of each edge - flowEM - IEdgeMap
- the IEdgeMap that will be filled during the execution with an integer flow for each edge
Domain Edge Values number an value representing the resulting flow of each edge - dualsNM - INodeMap
- the INodeMap that will be filled during the execution with an integer value (dual value) for each node or
nullif no such values occur; dual values are also referred as potentialsDomain YNode Values number an value representing the resulting dual value for each node or nullif no such values occur
Returns
- ↪number
- the total cost of the flow