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()