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

      • source

        private V source
      • target

        private V target
      • mMaxFlow

        private int mMaxFlow
      • mSourcePartitionNodes

        private java.util.Set<V> mSourcePartitionNodes
      • mSinkPartitionNodes

        private java.util.Set<V> mSinkPartitionNodes
      • mMinCutEdges

        private java.util.Set<E> mMinCutEdges
      • residualCapacityMap

        private java.util.Map<E,​java.lang.Number> residualCapacityMap
      • parentMap

        private java.util.Map<V,​V> parentMap
      • parentCapacityMap

        private java.util.Map<V,​java.lang.Number> parentCapacityMap
      • edgeCapacityTransformer

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

        private java.util.Map<E,​java.lang.Number> edgeFlowMap
      • edgeFactory

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

      • EdmondsKarpMaxFlow

        public EdmondsKarpMaxFlow​(DirectedGraph<V,​E> directedGraph,
                                  V source,
                                  V sink,
                                  com.google.common.base.Function<E,​java.lang.Number> edgeCapacityTransformer,
                                  java.util.Map<E,​java.lang.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 Detail

      • clearParentValues

        private void clearParentValues()
      • hasAugmentingPath

        protected boolean hasAugmentingPath()
      • computeMinCut

        private void computeMinCut()
      • 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 DirectedGraph<V,​E> getFlowGraph()
        Returns:
        the graph for which the maximum flow is calculated.
      • updateResidualCapacities

        private void updateResidualCapacities()