Class FordFulkerson


  • public class FordFulkerson
    extends Object
    The FordFulkerson class represents a data type for computing a maximum st-flow and minimum st-cut in a flow network.

    This implementation uses the Ford-Fulkerson algorithm with the shortest augmenting path heuristic. The constructor takes O(E V (E + V)) time, where V is the number of vertices and E is the number of edges. In practice, the algorithm will run much faster. The inCut() and value() methods take Θ(1) time. It uses Θ(V) extra space (not including the network).

    This correctly computes the maxflow and mincut if all arithmetic performed is without floating-point rounding error or arithmetic overflow. This is guaranteed to be the case if all edge capacities and initial flow values are integers and the value of the maxflow does not exceed 252.

    For additional documentation, see Section 6.4 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

    Author:
    Robert Sedgewick, Kevin Wayne
    • Method Detail

      • value

        public double value()
        Returns the value of the maximum flow.
        Returns:
        the value of the maximum flow
      • inCut

        public boolean inCut​(int v)
        Returns true if the specified vertex is on the s side of the mincut.
        Parameters:
        v - vertex
        Returns:
        true if vertex v is on the s side of the mincut; false otherwise
        Throws:
        IllegalArgumentException - unless 0 <= v < V
      • main

        public static void main​(String[] args)
        Unit tests the FordFulkerson data type.
        Parameters:
        args - the command-line arguments