Ford-Fulkerson

From Progteam

Revision as of 02:35, 20 October 2008 by Hjfreyer (Talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

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