# Ford-Fulkerson

(Difference between revisions)
 Revision as of 22:49, 19 October 2008 (view source)Hjfreyer (Talk | contribs)← Older edit Latest revision as of 02:35, 20 October 2008 (view source)Hjfreyer (Talk | contribs) Line 1: Line 1: The '''Ford Fulkerson Algorithm''' is a procedure for solving the [[Max Flow]] (and therefore, also the min-cut) problem. The '''Ford Fulkerson Algorithm''' is a procedure for solving the [[Max Flow]] (and therefore, also the min-cut) problem. + + == Implementation == + This is pretty general purpose.  Operates on an adj matrix with double values.  Also contains a pretty general BFS. +
+                                                                                      public static double maxFlow(double[][] capacity,
+                                                                                      int source, int sink) {
+                                                                                      double[][] residual = new double[capacity.length][capacity.length];
+                                                                                      double maxFlow = 0;
+
+                                                                                      for (int i = 0; i < residual.length; i++) {
+                                                                                      for (int j = 0; j < residual.length; j++) {
+                                                                                      residual[i][j] = capacity[i][j];
+                                                                                      }
+                                                                                      }
+
+                                                                                      // While there exists an augmenting path,
+                                                                                      // increment the flow along this path.
+                                                                                      int[] pred = bfs(residual, source);
+                                                                                      while (pred[sink] != -1) {
+                                                                                      // Determine the amount by which we can increment the flow.
+                                                                                      double increment = Double.POSITIVE_INFINITY;
+                                                                                      for (int u = sink; pred[u] != -2; u = pred[u]) {
+                                                                                      increment = Math.min(increment, residual[pred[u]][u]);
+                                                                                      }
+
+                                                                                      for (int u = sink; pred[u] != -2; u = pred[u]) {
+                                                                                      residual[pred[u]][u] -= increment;
+                                                                                      residual[u][pred[u]] += increment;
+                                                                                      }
+                                                                                      maxFlow += increment;
+                                                                                      pred = bfs(residual, source);
+                                                                                      }
+
+                                                                                      return maxFlow;
+                                                                                      }
+
+                                                                                      public static int[] bfs (double[][] graph, int start) {
+                                                                                      Queue q = new LinkedList();
+
+                                                                                      int[] pred = new int[graph.length];
+                                                                                      for (int i = 0; i < pred.length; i++)
+                                                                                      pred[i] = -1;
+
+                                                                                      pred[start] = -2;
+
+                                                                                      while (!q.isEmpty()) {
+                                                                                      int u = q.remove();
+
+                                                                                      for (int v = 0; v < graph.length; v++) {
+                                                                                      if (pred[v] == -1 && graph[u][v] > 0) {
+                                                                                      pred[v] = u;
+                                                                                      }
+                                                                                      }
+                                                                                      }
+
+                                                                                      return pred;
+                                                                                      }
+
+ + [[Category:Code Packet]]

## Latest revision as of 02:35, 20 October 2008

The Ford Fulkerson Algorithm is a procedure for solving the Max Flow (and therefore, also the min-cut) problem.

## Implementation

This is pretty general purpose. Operates on an adj matrix with double values. Also contains a pretty general BFS.

```        public static double maxFlow(double[][] capacity,
int source, int sink) {
double[][] residual = new double[capacity.length][capacity.length];
double maxFlow = 0;

for (int i = 0; i < residual.length; i++) {
for (int j = 0; j < residual.length; j++) {
residual[i][j] = capacity[i][j];
}
}

// While there exists an augmenting path,
// increment the flow along this path.
int[] pred = bfs(residual, source);
while (pred[sink] != -1) {
// Determine the amount by which we can increment the flow.
double increment = Double.POSITIVE_INFINITY;
for (int u = sink; pred[u] != -2; u = pred[u]) {
increment = Math.min(increment, residual[pred[u]][u]);
}

for (int u = sink; pred[u] != -2; u = pred[u]) {
residual[pred[u]][u] -= increment;
residual[u][pred[u]] += increment;
}
maxFlow += increment;
pred = bfs(residual, source);
}

return maxFlow;
}

public static int[] bfs (double[][] graph, int start) {

int[] pred = new int[graph.length];
for (int i = 0; i < pred.length; i++)
pred[i] = -1;

pred[start] = -2;

while (!q.isEmpty()) {
int u = q.remove();

for (int v = 0; v < graph.length; v++) {
if (pred[v] == -1 && graph[u][v] > 0) {