## Wednesday, December 2, 2015

### Maximum Bipartite Matching using Ford Fulkerson Algorithm (using DFS) - Java

Maximum Bipartite Matching is an application of the Ford Fulkerson Algorithm.

1. Create a single source vertex for all vertices in one group-A.
2. Create a single sink vertex for all vertices in the other group-B.

3. Source vertex -> (group-A) vertices edges capacity = 1
4. (group-B) vertices -> sink edges capacity = 1
5. (group-A) vertices -> (group-B) edges capacity = 1

Example Graph used (Algorithms-Part II - coursera.com) -

Source:

```import java.util.ArrayList;
```public class MaximumBipartiteMatching {
class Edge{
int from, to;
double capacity, flow;

Edge(int f, int t, double capacity){
from = f;
to = t;
this.capacity = capacity;
}

int other(int vertex){
}

double capacity(){ return capacity; }

double flow(){ return flow; }

double residualCapacityTo(int vertex){
if(vertex==from)return flow; else return (capacity-flow);
}

void increaseFlowTo(int vertex, double delta){
if(vertex==from)flow = flow-delta;
else flow = flow+delta;
}

@Override
public String toString(){
return from+" - "+to;
}
}

ArrayList<ArrayList<Edge>> graph;
private int V;
private Edge[] edgeTo;
private boolean[] marked;
private double flow;

MaximumBipartiteMatching(int V){
this.V = V;
graph = new ArrayList<>(V);
}

public void addEdge(int from, int to, double capacity){
Edge e = new Edge(from, to, capacity);
}

public void fordFulkerson(int s, int t){
edgeTo = new Edge[V];
while(augmentingPathExists(s, t)){
double maxIncrease = 1;

System.out.print(" Matched Vertices -> "+(1+edgeTo[t].other(t))+" ");
for(int i=t;i!=s;i=edgeTo[i].other(i)){
if(edgeTo[i].other(i)==s)System.out.print((i+1)+"\n");
maxIncrease = Math.min(maxIncrease, edgeTo[i].residualCapacityTo(i));
}

for(int i=t;i!=s;i=edgeTo[i].other(i)){
edgeTo[i].increaseFlowTo(i, maxIncrease);
}
flow+=maxIncrease;
}
System.out.println("Max flow = "+flow);
}

public boolean augmentingPathExists(int s, int t){
marked = new boolean[V];
marked[s] = true;
quit = false;
System.out.print("Augmenting Path : ");
dfs(s, t);
return marked[t];
}

boolean quit;
public void dfs(int v, int sink){
if(v==sink)quit = true;

for(Edge e:graph.get(v)){
if(quit)return;
int other = e.other(v);
if(!marked[other] && e.residualCapacityTo(other)>0){
System.out.print((1+other)+" ");
edgeTo[other] = e;
marked[other] = true;
dfs(other, sink);
}
}
}

public static void main(String[] args){
int v = 10;
MaximumBipartiteMatching m = new MaximumBipartiteMatching(v+2);
int source = v, sink = v+1;

for(int i=0;i<v/2;++i){
}
m.fordFulkerson(source, sink);
}
}```

Output:

Augmenting Path : 1 6 12  Matched Vertices -> 6 1
Augmenting Path : 2 6 1 7 12  Matched Vertices -> 7 2
Augmenting Path : 3 6 2 7 1 9 12  Matched Vertices -> 9 3
Augmenting Path : 4 7 2 6 3 8 12  Matched Vertices -> 8 4
Augmenting Path : 5 7 4 10 12  Matched Vertices -> 10 5
Augmenting Path : Max flow = 5.0