# Ford-Fulkerson

### From Progteam

(Difference between revisions)

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. | ||

+ | <pre> | ||

+ | 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<Integer> q = new LinkedList<Integer>(); | ||

+ | |||

+ | int[] pred = new int[graph.length]; | ||

+ | for (int i = 0; i < pred.length; i++) | ||

+ | pred[i] = -1; | ||

+ | |||

+ | q.add(start); | ||

+ | 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) { | ||

+ | q.add(v); | ||

+ | pred[v] = u; | ||

+ | } | ||

+ | } | ||

+ | } | ||

+ | |||

+ | return pred; | ||

+ | } | ||

+ | </pre> | ||

+ | |||

+ | [[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) { Queue<Integer> q = new LinkedList<Integer>(); int[] pred = new int[graph.length]; for (int i = 0; i < pred.length; i++) pred[i] = -1; q.add(start); 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) { q.add(v); pred[v] = u; } } } return pred; }