Class EdmondsKarpMaxFlow<V,E>

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."
  • Field Details

    • mFlowGraph

      private DirectedGraph<V,E> mFlowGraph
    • mOriginalGraph

      private DirectedGraph<V,E> mOriginalGraph
    • source

      private V source
    • target

      private V target
    • mMaxFlow

      private int mMaxFlow
    • mSourcePartitionNodes

      private Set<V> mSourcePartitionNodes
    • mSinkPartitionNodes

      private Set<V> mSinkPartitionNodes
    • mMinCutEdges

      private Set<E> mMinCutEdges
    • residualCapacityMap

      private Map<E,Number> residualCapacityMap
    • parentMap

      private Map<V,V> parentMap
    • parentCapacityMap

      private Map<V,Number> parentCapacityMap
    • edgeCapacityTransformer

      private com.google.common.base.Function<E,Number> edgeCapacityTransformer
    • edgeFlowMap

      private Map<E,Number> edgeFlowMap
    • edgeFactory

      private com.google.common.base.Supplier<E> edgeFactory
  • Constructor Details

    • EdmondsKarpMaxFlow

      public EdmondsKarpMaxFlow(DirectedGraph<V,E> directedGraph, V source, V sink, com.google.common.base.Function<E,Number> edgeCapacityTransformer, Map<E,Number> edgeFlowMap, com.google.common.base.Supplier<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 Function 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 Details

    • clearParentValues

      private void clearParentValues()
    • 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
    • computeMinCut

      private void computeMinCut()
    • getMaxFlow

      public int getMaxFlow()
      Returns:
      the value of the maximum flow from the source to the sink.
    • getNodesInSinkPartition

      public Set<V> getNodesInSinkPartition()
      Returns:
      the nodes which share the same partition (as defined by the min-cut edges) as the sink node.
    • getNodesInSourcePartition

      public Set<V> getNodesInSourcePartition()
      Returns:
      the nodes which share the same partition (as defined by the min-cut edges) as the source node.
    • getMinCutEdges

      public Set<E> getMinCutEdges()
      Returns:
      the edges in the minimum cut.
    • getFlowGraph

      public 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
    • updateResidualCapacities

      private void updateResidualCapacities()