Ford-Fulkerson

From Progteam

(Difference between revisions)
Jump to: navigation, search
 
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;
	}	
Personal tools