Class 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."
    • Constructor Detail

      • EdmondsKarpMaxFlow

        public EdmondsKarpMaxFlow​(edu.uci.ics.jung.graph.DirectedGraph<V,​E> directedGraph,
                                  V source,
                                  V sink,
                                  org.apache.commons.collections4.Transformer<E,​java.lang.Number> edgeCapacityTransformer,
                                  java.util.Map<E,​java.lang.Number> edgeFlowMap,
                                  org.apache.commons.collections4.Factory<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 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()
      • getMaxFlow

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

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

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

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

        public edu.uci.ics.jung.graph.DirectedGraph<V,​E> getFlowGraph()
        Returns the graph for which the maximum flow is calculated.