## Tuesday, December 1, 2015

### Finding the Maxflow-Mincut using Ford-Fulkerson Algorithm (BFS) - Java

Running time of the FF algorithm depends on the method used for finding the augmenting paths. Here we are using BFS for this purpose.

Maxflow and Mincut problems are duals. If we find solution to one, we easily find solution to the other one.

Graph used :

Code:

```import java.util.Arrays;
import java.util.ArrayList;
import java.util.Queue;

class FlowEdge {
final int v, w;
final double capacity;
double flow;

FlowEdge(int v, int w, double capacity){
this.v = v;
this.w = w;
this.capacity = capacity;
}

int from(){ return v;}
int to(){ return w;}
int other(int v){
return (v==this.v)?w:this.v;
}
double capacity(){return capacity;}
double flow(){return flow;}
double residualCapacityTo(int v){
if(v==this.w)return capacity-flow;
else return flow;
}
if(v==this.w)flow+=delta;
else         flow-=delta;
}

@Override
public String toString(){return "["+v+", "+w+" ("+capacity+")]";}
}

class FlowNetwork {
private final int V;
private int E;
private ArrayList<ArrayList<FlowEdge>> graph;

FlowNetwork(int V){
this.V = V;
graph = new ArrayList<>(V);
}
int v = e.from();
int w = e.to();
E++;
}

return graph.get(v);
}

Iterable<FlowEdge> edges(){
ArrayList<FlowEdge> al = new ArrayList<>(V);
for(int i=0;i<V;++i){
}
return al;
}

int V(){return V;};
int E(){return E;};
}

public class FordFulkerson {
private boolean[] marked;
private FlowEdge[] edgeTo;
private double value;

public FordFulkerson(FlowNetwork G, int s, int t){
value = 0;
while(hasAugmentingPath(G, s, t)){
double bottle = Double.POSITIVE_INFINITY;
System.out.println("Considering Augmenting Path : "+ Arrays.toString(edgeTo));

for(int v = t;v != s;v=edgeTo[v].other(v)){
bottle = Math.min(bottle, edgeTo[v].residualCapacityTo(v));
}
for(int v = t;v!=s;v = edgeTo[v].other(v))

value += bottle;
}
}

public final boolean hasAugmentingPath(FlowNetwork G, int s, int t){
edgeTo = new FlowEdge[G.V()];
marked = new boolean[G.V()];

marked[s] = true;
while(!q.isEmpty()){

int v = q.poll();
int w = e.other(v);
if(e.residualCapacityTo(w) > 0 && !marked[w]){
edgeTo[w] = e;

marked[w] = true;
}
}
}
return marked[t];
}

public double value(){
return value;
}

public boolean inCut(int v){
return marked[v];
}

public static void main(String[] args){
FlowNetwork network = new FlowNetwork(6);

FordFulkerson ff = new FordFulkerson(network, 0, 5);
System.out.println("Maxflow value = "+ff.value());

System.out.println("Mincut vertices : ");
for(int i=0;i<network.V();++i)if(ff.marked[i])System.out.print(i+" ");
}
}```

Output:

Considering Augmenting Path : [null, [0, 1 (16.0)], [0, 2 (13.0)], [1, 3 (12.0)], [2, 4 (14.0)], [3, 5 (20.0)]]
Considering Augmenting Path : [null, [0, 1 (16.0)], [0, 2 (13.0)], [4, 3 (7.0)], [2, 4 (14.0)], [4, 5 (4.0)]]
Considering Augmenting Path : [null, [0, 1 (16.0)], [0, 2 (13.0)], [4, 3 (7.0)], [2, 4 (14.0)], [3, 5 (20.0)]]
Maxflow value = 23.0
Mincut vertices :
0 1 2 4