EdmondsKarpMaxFlow

java.lang.Object
- edu.uci.ics.jung.algorithms.util.IterativeProcess
- - edu.uci.ics.jung.algorithms.flows.EdmondsKarpMaxFlow<V,E>

All Implemented Interfaces:

IterativeContext
```
public class EdmondsKarpMaxFlow<V,E>
extends IterativeProcess
```
Implements the Edmonds-Karp maximum flow algorithm for solving the maximum flow problem. After the algorithm is executed, the input Map is populated with a Number for each edge that indicates the flow along that edge.
An example of using this algorithm is as follows:
```
 EdmondsKarpMaxFlow ek = new EdmondsKarpMaxFlow(graph, source, sink, edge_capacities, edge_flows, 
 edge_factory);
 ek.evaluate(); // This instructs the class to compute the max flow
 
```
See Also:
"Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein.", "Network Flows by Ahuja, Magnanti, and Orlin.", "Theoretical improvements in algorithmic efficiency for network flow problems by Edmonds and Karp, 1972."

Constructor Summary

Constructors
Constructor and Description
`EdmondsKarpMaxFlow(edu.uci.ics.jung.graph.DirectedGraph<V,E> directedGraph, V source, V sink, org.apache.commons.collections4.Transformer<E,java.lang.Number> edgeCapacityTransformer, java.util.Map<E,java.lang.Number> edgeFlowMap, org.apache.commons.collections4.Factory<E> edgeFactory)` Constructs a new instance of the algorithm solver for a given graph, source, and sink.

Method Summary

Methods
Modifier and Type	Method and Description
`protected void`	`finalizeIterations()` Perform eventual clean-up operations (must be implement by subclass when needed).
`edu.uci.ics.jung.graph.DirectedGraph<V,E>`	`getFlowGraph()` Returns the graph for which the maximum flow is calculated.
`int`	`getMaxFlow()` Returns the value of the maximum flow from the source to the sink.
`java.util.Set<E>`	`getMinCutEdges()` Returns the edges in the minimum cut.
`java.util.Set<V>`	`getNodesInSinkPartition()` Returns the nodes which share the same partition (as defined by the min-cut edges) as the sink node.
`java.util.Set<V>`	`getNodesInSourcePartition()` Returns the nodes which share the same partition (as defined by the min-cut edges) as the source node.
`protected boolean`	`hasAugmentingPath()`
`protected void`	`initializeIterations()` Initializes internal parameters to start the iterative process.
`void`	`step()` Evaluate the result of the current iteration.

Methods inherited from class edu.uci.ics.jung.algorithms.util.IterativeProcess
done, evaluate, getDesiredPrecision, getIterations, getMaximumIterations, getPrecision, hasConverged, relativePrecision, reset, setDesiredPrecision, setMaximumIterations, setPrecision

Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

- Constructor Detail
  - EdmondsKarpMaxFlow
```
public EdmondsKarpMaxFlow(edu.uci.ics.jung.graph.DirectedGraph<V,E> directedGraph,
                  V source,
                  V sink,
                  org.apache.commons.collections4.Transformer<E,java.lang.Number> edgeCapacityTransformer,
                  java.util.Map<E,java.lang.Number> edgeFlowMap,
                  org.apache.commons.collections4.Factory<E> edgeFactory)
```
    Constructs a new instance of the algorithm solver for a given graph, source, and sink. Source and sink vertices must be elements of the specified graph, and must be distinct.
    
    Parameters:
    directedGraph - the flow graph
    source - the source vertex
    sink - the sink vertex
    edgeCapacityTransformer - the transformer that gets the capacity for each edge.
    edgeFlowMap - the map where the solver will place the value of the flow for each edge
    edgeFactory - used to create new edge instances for backEdges
- Method Detail
  - hasAugmentingPath
```
protected boolean hasAugmentingPath()
```
  - step
```
public void step()
```
    Description copied from class: IterativeProcess
    
    Evaluate the result of the current iteration.
    
    Specified by:
    
    step in interface IterativeContext
    
    Specified by:
    
    step in class IterativeProcess
  - getMaxFlow
```
public int getMaxFlow()
```
    Returns the value of the maximum flow from the source to the sink.
  - getNodesInSinkPartition
```
public java.util.Set<V> getNodesInSinkPartition()
```
    Returns the nodes which share the same partition (as defined by the min-cut edges) as the sink node.
  - getNodesInSourcePartition
```
public java.util.Set<V> getNodesInSourcePartition()
```
    Returns the nodes which share the same partition (as defined by the min-cut edges) as the source node.
  - getMinCutEdges
```
public java.util.Set<E> getMinCutEdges()
```
    Returns the edges in the minimum cut.
  - getFlowGraph
```
public edu.uci.ics.jung.graph.DirectedGraph<V,E> getFlowGraph()
```
    Returns the graph for which the maximum flow is calculated.
  - initializeIterations
```
protected void initializeIterations()
```
    Description copied from class: IterativeProcess
    
    Initializes internal parameters to start the iterative process.
    
    Overrides:
    
    initializeIterations in class IterativeProcess
  - finalizeIterations
```
protected void finalizeIterations()
```
    Description copied from class: IterativeProcess
    
    Perform eventual clean-up operations (must be implement by subclass when needed).
    
    Overrides:
    
    finalizeIterations in class IterativeProcess

Class EdmondsKarpMaxFlow<V,E>

Constructor Summary

Method Summary

Methods inherited from class edu.uci.ics.jung.algorithms.util.IterativeProcess

Methods inherited from class java.lang.Object

Constructor Detail

EdmondsKarpMaxFlow

Method Detail

hasAugmentingPath

step

getMaxFlow

getNodesInSinkPartition

getNodesInSourcePartition

getMinCutEdges

getFlowGraph

initializeIterations

finalizeIterations