001package algs64; // section 6.4 002import stdlib.*; 003import algs13.Queue; 004/* *********************************************************************** 005 * Compilation: javac FordFulkerson.java 006 * Execution: java FordFulkerson V E 007 * Dependencies: FlowNetwork.java FlowEdge.java Queue.java 008 * 009 * Ford-Fulkerson algorithm for computing a max flow and 010 * a min cut using shortest augmenthing path rule. 011 * 012 *********************************************************************/ 013 014public class FordFulkerson { 015 private boolean[] marked; // marked[v] = true iff s->v path in residual graph 016 private FlowEdge[] edgeTo; // edgeTo[v] = last edge on shortest residual s->v path 017 private double value; // current value of max flow 018 019 // max flow in flow network G from s to t 020 public FordFulkerson(FlowNetwork G, int s, int t) { 021 if (s < 0 || s >= G.V()) { 022 throw new IndexOutOfBoundsException("Source s is invalid: " + s); 023 } 024 if (t < 0 || t >= G.V()) { 025 throw new IndexOutOfBoundsException("Sink t is invalid: " + t); 026 } 027 if (s == t) { 028 throw new IllegalArgumentException("Source equals sink"); 029 } 030 value = excess(G, t); 031 if (!isFeasible(G, s, t)) { 032 throw new Error("Initial flow is infeasible"); 033 } 034 035 // while there exists an augmenting path, use it 036 while (hasAugmentingPath(G, s, t)) { 037 038 // compute bottleneck capacity 039 double bottle = Double.POSITIVE_INFINITY; 040 for (int v = t; v != s; v = edgeTo[v].other(v)) { 041 bottle = Math.min(bottle, edgeTo[v].residualCapacityTo(v)); 042 } 043 044 // augment flow 045 for (int v = t; v != s; v = edgeTo[v].other(v)) { 046 edgeTo[v].addResidualFlowTo(v, bottle); 047 } 048 049 value += bottle; 050 } 051 052 // check optimality conditions 053 assert check(G, s, t); 054 } 055 056 // return value of max flow 057 public double value() { 058 return value; 059 } 060 061 // is v in the s side of the min s-t cut? 062 public boolean inCut(int v) { 063 return marked[v]; 064 } 065 066 067 // return an augmenting path if one exists, otherwise return null 068 private boolean hasAugmentingPath(FlowNetwork G, int s, int t) { 069 edgeTo = new FlowEdge[G.V()]; 070 marked = new boolean[G.V()]; 071 072 // breadth-first search 073 Queue<Integer> q = new Queue<>(); 074 q.enqueue(s); 075 marked[s] = true; 076 while (!q.isEmpty()) { 077 int v = q.dequeue(); 078 079 for (FlowEdge e : G.adj(v)) { 080 int w = e.other(v); 081 082 // if residual capacity from v to w 083 if (e.residualCapacityTo(w) > 0) { 084 if (!marked[w]) { 085 edgeTo[w] = e; 086 marked[w] = true; 087 q.enqueue(w); 088 } 089 } 090 } 091 } 092 093 // is there an augmenting path? 094 return marked[t]; 095 } 096 097 098 099 // return excess flow at vertex v 100 private double excess(FlowNetwork G, int v) { 101 double excess = 0.0; 102 for (FlowEdge e : G.adj(v)) { 103 if (v == e.from()) excess -= e.flow(); 104 else excess += e.flow(); 105 } 106 return excess; 107 } 108 109 // return excess flow at vertex v 110 private boolean isFeasible(FlowNetwork G, int s, int t) { 111 double EPSILON = 1E-11; 112 113 // check that capacity constraints are satisfied 114 for (int v = 0; v < G.V(); v++) { 115 for (FlowEdge e : G.adj(v)) { 116 if (e.flow() < -EPSILON || e.flow() > e.capacity() + EPSILON) { 117 System.err.println("Edge does not satisfy capacity constraints: " + e); 118 return false; 119 } 120 } 121 } 122 123 // check that net flow into a vertex equals zero, except at source and sink 124 if (Math.abs(value + excess(G, s)) > EPSILON) { 125 System.err.println("Excess at source = " + excess(G, s)); 126 System.err.println("Max flow = " + value); 127 return false; 128 } 129 if (Math.abs(value - excess(G, t)) > EPSILON) { 130 System.err.println("Excess at sink = " + excess(G, t)); 131 System.err.println("Max flow = " + value); 132 return false; 133 } 134 for (int v = 0; v < G.V(); v++) { 135 if (v == s || v == t) continue; 136 else if (Math.abs(excess(G, v)) > EPSILON) { 137 System.err.println("Net flow out of " + v + " doesn't equal zero"); 138 return false; 139 } 140 } 141 return true; 142 } 143 144 145 146 // check optimality conditions 147 private boolean check(FlowNetwork G, int s, int t) { 148 149 // check that flow is feasible 150 if (!isFeasible(G, s, t)) { 151 System.err.println("Flow is infeasible"); 152 return false; 153 } 154 155 // check that s is on the source side of min cut and that t is not on source side 156 if (!inCut(s)) { 157 System.err.println("source " + s + " is not on source side of min cut"); 158 return false; 159 } 160 if (inCut(t)) { 161 System.err.println("sink " + t + " is on source side of min cut"); 162 return false; 163 } 164 165 // check that value of min cut = value of max flow 166 double mincutValue = 0.0; 167 for (int v = 0; v < G.V(); v++) { 168 for (FlowEdge e : G.adj(v)) { 169 if ((v == e.from()) && inCut(e.from()) && !inCut(e.to())) 170 mincutValue += e.capacity(); 171 } 172 } 173 174 double EPSILON = 1E-11; 175 if (Math.abs(mincutValue - value) > EPSILON) { 176 System.err.println("Max flow value = " + value + ", min cut value = " + mincutValue); 177 return false; 178 } 179 180 return true; 181 } 182 183 184 // test client that creates random network, solves max flow, and prints results 185 public static void main(String[] args) { 186 187 // create flow network with V vertices and E edges 188 int V = Integer.parseInt(args[0]); 189 int E = Integer.parseInt(args[1]); 190 int s = 0, t = V-1; 191 FlowNetwork G = new FlowNetwork(V, E); 192 StdOut.println(G); 193 194 // compute maximum flow and minimum cut 195 FordFulkerson maxflow = new FordFulkerson(G, s, t); 196 StdOut.println("Max flow from " + s + " to " + t); 197 for (int v = 0; v < G.V(); v++) { 198 for (FlowEdge e : G.adj(v)) { 199 if ((v == e.from()) && e.flow() > 0) 200 StdOut.println(" " + e); 201 } 202 } 203 204 // print min-cut 205 StdOut.print("Min cut: "); 206 for (int v = 0; v < G.V(); v++) { 207 if (maxflow.inCut(v)) StdOut.print(v + " "); 208 } 209 StdOut.println(); 210 211 StdOut.println("Max flow value = " + maxflow.value()); 212 } 213 214}