Below is the syntax highlighted version of FordFulkerson.java.
/****************************************************************************** * Compilation: javac FordFulkerson.java * Execution: java FordFulkerson V E * Dependencies: FlowNetwork.java FlowEdge.java Queue.java * Data files: https://algs4.cs.princeton.edu/65maxflow/tinyFN.txt * * Ford-Fulkerson algorithm for computing a max flow and * a min cut using shortest augmenting path rule. * ******************************************************************************/ package edu.princeton.cs.algs4; /** * The {@code FordFulkerson} class represents a data type for computing a * <em>maximum st-flow</em> and <em>minimum st-cut</em> in a flow * network. * <p> * This implementation uses the <em>Ford-Fulkerson</em> algorithm with * the <em>shortest augmenting path</em> heuristic. * The constructor takes <em>O</em>(<em>E V</em> (<em>E</em> + <em>V</em>)) * time, where <em>V</em> is the number of vertices and <em>E</em> is * the number of edges. In practice, the algorithm will run much faster. * The {@code inCut()} and {@code value()} methods take Θ(1) time. * It uses Θ(<em>V</em>) extra space (not including the network). * <p> * 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 2<sup>52</sup>. * <p> * For additional documentation, see * <a href="https://algs4.cs.princeton.edu/64maxflow">Section 6.4</a> of * <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne. * * @author Robert Sedgewick * @author Kevin Wayne */ public class FordFulkerson { private static final double FLOATING_POINT_EPSILON = 1.0E-11; private final int V; // number of vertices private boolean[] marked; // marked[v] = true iff s->v path in residual graph private FlowEdge[] edgeTo; // edgeTo[v] = last edge on shortest residual s->v path private double value; // current value of max flow /** * Compute a maximum flow and minimum cut in the network {@code G} * from vertex {@code s} to vertex {@code t}. * * @param G the flow network * @param s the source vertex * @param t the sink vertex * @throws IllegalArgumentException unless {@code 0 <= s < V} * @throws IllegalArgumentException unless {@code 0 <= t < V} * @throws IllegalArgumentException if {@code s == t} * @throws IllegalArgumentException if initial flow is infeasible */ public FordFulkerson(FlowNetwork G, int s, int t) { V = G.V(); validate(s); validate(t); if (s == t) throw new IllegalArgumentException("Source equals sink"); if (!isFeasible(G, s, t)) throw new IllegalArgumentException("Initial flow is infeasible"); // while there exists an augmenting path, use it value = excess(G, t); while (hasAugmentingPath(G, s, t)) { // compute bottleneck capacity double bottle = Double.POSITIVE_INFINITY; for (int v = t; v != s; v = edgeTo[v].other(v)) { bottle = Math.min(bottle, edgeTo[v].residualCapacityTo(v)); } // augment flow for (int v = t; v != s; v = edgeTo[v].other(v)) { edgeTo[v].addResidualFlowTo(v, bottle); } value += bottle; } // check optimality conditions assert check(G, s, t); } /** * Returns the value of the maximum flow. * * @return the value of the maximum flow */ public double value() { return value; } /** * Returns true if the specified vertex is on the {@code s} side of the mincut. * * @param v vertex * @return {@code true} if vertex {@code v} is on the {@code s} side of the mincut; * {@code false} otherwise * @throws IllegalArgumentException unless {@code 0 <= v < V} */ public boolean inCut(int v) { validate(v); return marked[v]; } // throw an IllegalArgumentException if v is outside prescribed range private void validate(int v) { if (v < 0 || v >= V) throw new IllegalArgumentException("vertex " + v + " is not between 0 and " + (V-1)); } // is there an augmenting path? // if so, upon termination edgeTo[] will contain a parent-link representation of such a path // this implementation finds a shortest augmenting path (fewest number of edges), // which performs well both in theory and in practice private boolean hasAugmentingPath(FlowNetwork G, int s, int t) { edgeTo = new FlowEdge[G.V()]; marked = new boolean[G.V()]; // breadth-first search Queue<Integer> queue = new Queue<Integer>(); queue.enqueue(s); marked[s] = true; while (!queue.isEmpty() && !marked[t]) { int v = queue.dequeue(); for (FlowEdge e : G.adj(v)) { int w = e.other(v); // if residual capacity from v to w if (e.residualCapacityTo(w) > 0) { if (!marked[w]) { edgeTo[w] = e; marked[w] = true; queue.enqueue(w); } } } } // is there an augmenting path? return marked[t]; } // return excess flow at vertex v private double excess(FlowNetwork G, int v) { double excess = 0.0; for (FlowEdge e : G.adj(v)) { if (v == e.from()) excess -= e.flow(); else excess += e.flow(); } return excess; } // return excess flow at vertex v private boolean isFeasible(FlowNetwork G, int s, int t) { // check that capacity constraints are satisfied for (int v = 0; v < G.V(); v++) { for (FlowEdge e : G.adj(v)) { if (e.flow() < -FLOATING_POINT_EPSILON || e.flow() > e.capacity() + FLOATING_POINT_EPSILON) { System.err.println("Edge does not satisfy capacity constraints: " + e); return false; } } } // check that net flow into a vertex equals zero, except at source and sink if (Math.abs(value + excess(G, s)) > FLOATING_POINT_EPSILON) { System.err.println("Excess at source = " + excess(G, s)); System.err.println("Max flow = " + value); return false; } if (Math.abs(value - excess(G, t)) > FLOATING_POINT_EPSILON) { System.err.println("Excess at sink = " + excess(G, t)); System.err.println("Max flow = " + value); return false; } for (int v = 0; v < G.V(); v++) { if (v == s || v == t) continue; else if (Math.abs(excess(G, v)) > FLOATING_POINT_EPSILON) { System.err.println("Net flow out of " + v + " doesn't equal zero"); return false; } } return true; } // check optimality conditions private boolean check(FlowNetwork G, int s, int t) { // check that flow is feasible if (!isFeasible(G, s, t)) { System.err.println("Flow is infeasible"); return false; } // check that s is on the source side of min cut and that t is not on source side if (!inCut(s)) { System.err.println("source " + s + " is not on source side of min cut"); return false; } if (inCut(t)) { System.err.println("sink " + t + " is on source side of min cut"); return false; } // check that value of min cut = value of max flow double mincutValue = 0.0; for (int v = 0; v < G.V(); v++) { for (FlowEdge e : G.adj(v)) { if ((v == e.from()) && inCut(e.from()) && !inCut(e.to())) mincutValue += e.capacity(); } } if (Math.abs(mincutValue - value) > FLOATING_POINT_EPSILON) { System.err.println("Max flow value = " + value + ", min cut value = " + mincutValue); return false; } return true; } /** * Unit tests the {@code FordFulkerson} data type. * * @param args the command-line arguments */ public static void main(String[] args) { // create flow network with V vertices and E edges int V = Integer.parseInt(args[0]); int E = Integer.parseInt(args[1]); int s = 0, t = V-1; FlowNetwork G = new FlowNetwork(V, E); StdOut.println(G); // compute maximum flow and minimum cut FordFulkerson maxflow = new FordFulkerson(G, s, t); StdOut.println("Max flow from " + s + " to " + t); for (int v = 0; v < G.V(); v++) { for (FlowEdge e : G.adj(v)) { if ((v == e.from()) && e.flow() > 0) StdOut.println(" " + e); } } // print min-cut StdOut.print("Min cut: "); for (int v = 0; v < G.V(); v++) { if (maxflow.inCut(v)) StdOut.print(v + " "); } StdOut.println(); StdOut.println("Max flow value = " + maxflow.value()); } } /****************************************************************************** * Copyright 2002-2022, Robert Sedgewick and Kevin Wayne. * * This file is part of algs4.jar, which accompanies the textbook * * Algorithms, 4th edition by Robert Sedgewick and Kevin Wayne, * Addison-Wesley Professional, 2011, ISBN 0-321-57351-X. * http://algs4.cs.princeton.edu * * * algs4.jar is free software: you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation, either version 3 of the License, or * (at your option) any later version. * * algs4.jar is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with algs4.jar. If not, see http://www.gnu.org/licenses. ******************************************************************************/