edu.uci.ics.jung.algorithms.flows
Class EdmondsKarpMaxFlow<V,E>

java.lang.Object
  extended by edu.uci.ics.jung.algorithms.util.IterativeProcess
      extended by edu.uci.ics.jung.algorithms.flows.EdmondsKarpMaxFlow<V,E>
All Implemented Interfaces:
IterativeContext

public class EdmondsKarpMaxFlow<V,E>
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, adapted to jung2 by Tom Nelson
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<V,E> directedGraph, V source, V sink,  edgeCapacityTransformer, Map<E,Number> edgeFlowMap,  edgeFactory)
          Constructs a new instance of the algorithm solver for a given graph, source, and sink.
 
Method Summary
protected  void finalizeIterations()
          Perform eventual clean-up operations (must be implement by subclass when needed).
 DirectedGraph<V,E> getFlowGraph()
          Retrieves the flow graph used to compute the max flow
 int getMaxFlow()
          Returns the max flow value
 Set<E> getMinCutEdges()
          Retrieve the min-cut edge set
 Set<V> getNodesInSinkPartition()
          Retrieves the nodes lying on the side of the partition (partitioned using the min-cut) of the sink node
 Set<V> 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.
 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, getStatus, 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(DirectedGraph<V,E> directedGraph,
                          V source,
                          V sink,
                           edgeCapacityTransformer,
                          Map<E,Number> edgeFlowMap,
                           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 max flow value

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

getNodesInSinkPartition

public Set<V> 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<V> 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<E> getMinCutEdges()
Retrieve the min-cut edge set

Returns:
set of edges in the min cut set

getFlowGraph

public DirectedGraph<V,E> 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


Copyright © 2008 null. All Rights Reserved.