Overview | Package | Class | Use | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

## edu.uci.ics.jung.algorithms.flows
Class EdmondsKarpMaxFlow

    java.lang.Object
      edu.uci.ics.jung.algorithms.IterativeProcess
          edu.uci.ics.jung.algorithms.flows.EdmondsKarpMaxFlow

public class EdmondsKarpMaxFlow
extends IterativeProcess

Implements the EdmondsKarpMaxFlow algorithm for solving the maximum flow problem. After the algorithm is executed, each edge is labeled with a MutableDouble value that indicates the flow along that edge.

The algorithm operates on the assumption that the user has provided a UserDatum value (with copy action either SHARED or CLONE, but not REMOVE) of type Number along each edge indicating the capacity available.

An example of using this algorithm is as follows:

     EdmondsKarpMaxFlow ek = new EdmondsKarpMaxFlow(graph,sourceVertex,"CAPACITY","FLOW");
     ek.evaluate(); // This actually instructs the solver to compute the max flow

Author:
  Scott White
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
`EdmondsKarpMaxFlow(DirectedGraph directedGraph, Vertex source, Vertex sink, String edgeCapacityKey, String edgeFlowKey)` Constructs a new instance of the algorithm solver for a given graph, source, and sink.

Method Summary
`protected double` | `evaluateIteration()` Evaluate the result of the current interation.
`protected void` | `finalizeIterations()` Perform eventual clean-up operations (must be implement by subclass when needed).
`DirectedGraph` | `getFlowGraph()` Retrieves the flow graph used to compute the max flow
`int` | `getMaxFlow()` Returns the max flow value
`Set` | `getMinCutEdges()` Retrieve the min-cut edge set
`Set` | `getNodesInSinkPartition()` Retrieves the nodes lying on the side of the partition (partitioned using the min-cut) of the sink node
`Set` | `getNodesInSourcePartition()` Retrieves the nodes lying on the side of the partition (partitioned using the min-cut) of the source node
`protected boolean` | `hasAugmentingPath()`
`protected void` | `initializeIterations()` Initializes internal parameters to start the iterative process.

Methods inherited from class edu.uci.ics.jung.algorithms.IterativeProcess
`evaluate, getDesiredPrecision, getIterations, getMaximumIterations, getPrecision, hasConverged, reinitialize, relativePrecision, setDesiredPrecision, setMaximumIterations`

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

Constructor Detail

### EdmondsKarpMaxFlow

    public EdmondsKarpMaxFlow(DirectedGraph directedGraph,
                              Vertex source,
                              Vertex sink,
                              String edgeCapacityKey,
                              String edgeFlowKey)

  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
  `edgeCapacityKey` - the UserDatum key that stores the capacity for each edge.
  `edgeFlowKey` - the UserDatum key where the solver will place the value of the flow for each edge

Method Detail

### hasAugmentingPath

    protected boolean hasAugmentingPath()

### evaluateIteration

    protected double evaluateIteration()

  Description copied from class: `IterativeProcess`
  Evaluate the result of the current interation.

  Specified by:
    `evaluateIteration` in class `IterativeProcess`
  Returns:
    the estimated precision of the result.

### getMaxFlow

    public int getMaxFlow()

  Returns the max flow value

  Returns:
    int the value of the maximum flow from the source to the sink

### getNodesInSinkPartition

    public Set getNodesInSinkPartition()

  Retrieves the nodes lying on the side of the partition (partitioned using the min-cut) of the sink node

  Returns:
    the set of nodes in the sink partition class

### getNodesInSourcePartition

    public Set getNodesInSourcePartition()

  Retrieves the nodes lying on the side of the partition (partitioned using the min-cut) of the source node

  Returns:
    the set of nodes in the source partition class

### getMinCutEdges

    public Set getMinCutEdges()

  Retrieve the min-cut edge set

  Returns:
    set of edges in the min cut set

### getFlowGraph

    public DirectedGraph getFlowGraph()

  Retrieves the flow graph used to compute the max flow

  Returns:
    a copy of the flow graph

### 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`

Overview | Package | Class | Use | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD