Package edu.uci.ics.jung.algorithms.flows

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

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