package com.data.struct;
public class EdmondsKarp {
private Node[][]graphic;
private Node s;
private Node t;
private NodeArrayQueue2 queue;
public EdmondsKarp(){
graphic=new Node[6][6];
Node node0=new Node();
node0.start=0;
node0.end=0;
graphic[0][0]=node0;
Node node1=new Node();
node1.start=1;
node1.end=1;
graphic[1][1]=node1;
Node node2=new Node();
node2.start=2;
node2.end=2;
graphic[2][2]=node2;
Node node3=new Node();
node3.start=3;
node3.end=3;
graphic[3][3]=node3;
Node node4=new Node();
node4.start=4;
node4.end=4;
graphic[4][4]=node4;
Node node5=new Node();
node5.start=5;
node5.end=5;
graphic[5][5]=node5;
Node node01=new Node();
node01.c=16;
node01.start=0;
node01.end=1;
graphic[0][1]=node01;
Node node10=new Node();
node10.start=1;
node10.end=0;
node10.reverse=true;
graphic[1][0]=node10;
Node node02=new Node();
node02.c=13;
node02.start=0;
node02.end=2;
graphic[0][2]=node02;
Node node20=new Node();
node20.start=2;
node20.end=0;
node20.reverse=true;
graphic[2][0]=node20;
Node node13=new Node();
node13.c=12;
node13.start=1;
node13.end=3;
graphic[1][3]=node13;
Node node31=new Node();
node31.start=3;
node31.end=1;
node31.reverse=true;
graphic[3][1]=node31;
Node node21=new Node();
node21.c=4;
node21.start=2;
node21.end=1;
graphic[2][1]=node21;
Node node12=new Node();
node12.start=1;
node12.end=2;
node12.reverse=true;
graphic[1][2]=node12;
Node node24=new Node();
node24.start=2;
node24.end=4;
node24.c=14;
graphic[2][4]=node24;
Node node42=new Node();
node42.start=4;
node42.end=2;
node42.reverse=true;
graphic[4][2]=node42;
Node node32=new Node();
node32.c=9;
node32.start=3;
node32.end=2;
graphic[3][2]=node32;
Node node23=new Node();
node23.start=2;
node23.end=3;
node23.reverse=true;
graphic[2][3]=node23;
Node node35=new Node();
node35.c=20;
node35.start=3;
node35.end=5;
graphic[3][5]=node35;
Node node53=new Node();
node53.start=5;
node53.end=3;
node53.reverse=true;
graphic[5][3]=node53;
Node node43=new Node();
node43.c=7;
node43.start=4;
node43.end=3;
graphic[4][3]=node43;
Node node34=new Node();
node34.start=3;
node34.end=4;
node34.reverse=true;
graphic[3][4]=node34;
Node node45=new Node();
node45.c=4;
node45.start=4;
node45.end=5;
graphic[4][5]=node45;
Node node54=new Node();
node54.start=5;
node54.end=4;
node54.reverse=true;
graphic[5][4]=node54;
s=graphic[0][0];
t=graphic[5][5];
queue = new NodeArrayQueue2((6 * (6 - 1) / 2) + 5);
}
public void edmondsKarp()throws Exception{
broadFirstSearch();
while(t.parent!=null){
Node p=t;
Node end=t;
Node start=t.parent;
int maxF=Integer.MAX_VALUE;
while(p.parent!=null){
Node edge=graphic[start.start][end.start];
if(!edge.reverse){
maxF=Math.min(maxF, edge.c-edge.f);
}else{
maxF=Math.min(maxF, edge.c-edge.fr);
}
p=end.parent;
end=p;
start=p.parent;
}
p=t;
end=t;
start=t.parent;
while(p.parent!=null){
Node edge=graphic[start.start][end.start];
if(!edge.reverse){
edge.f=edge.f+maxF;
}else{
edge.fr=edge.fr+maxF;
}
p=end.parent;
end=p;
start=p.parent;
}
t.parent=null;
broadFirstSearch();
}
}
public void broadFirstSearch() throws Exception {
for(int i=0;i<graphic.length;i++){
for(int j=0;j<graphic.length;j++){
if(graphic[i][j]!=null){
graphic[i][j].color=Node.WHITE;
graphic[i][j].parent=null;
}
}
}
s.color = Node.GRAY;
s.d = 0;
queue.enqueue(s);
while (!queue.isEmpty()) {
Node u = queue.dequeue();
Node prev = u;
for(int i=0;i<graphic.length;i++){
Node v = graphic[u.start][i];
if (v != null) {
if (graphic[v.end][v.end].color == Node.WHITE) {
if(v.c-v.f!=0&&!v.reverse){
queue.enqueue(graphic[v.end][v.end]);
graphic[v.end][v.end].parent = prev;
graphic[v.end][v.end].color = Node.GRAY;
graphic[v.end][v.end].d = prev.d + 1;
}
if(v.reverse&&v.fr-v.c<0){
queue.enqueue(graphic[v.end][v.end]);
graphic[v.end][v.end].parent = prev;
graphic[v.end][v.end].color = Node.GRAY;
graphic[v.end][v.end].d = prev.d + 1;
}
}
}
}
u.color = Node.BLACK;
}
}
public void printResult(){
int result=0;
for(int i=0;i<graphic.length;i++){
if(graphic[t.start][i]!=null){
result+=graphic[i][t.start].f;
}
}
System.out.println("max flow:"+result);
}
public void print(){
for(int i=0;i<graphic.length;i++){
for(int j=0;j<graphic.length;j++){
if(graphic[i][j]!=null){
System.out.print(graphic[i][j].c+" ");
}else{
System.out.print(" ");
}
}
System.out.println();
}
}
private class Node{
public static final int WHITE = 1;
public static final int BLACK = 2;
public static final int GRAY = 3;
private int color = WHITE;
private int c;
private int f;
private int fr;
private int start;
private int end;
private int d=Integer.MAX_VALUE;;
private Node parent;
private boolean reverse;
}
class NodeArrayQueue2 {
private Node[] data;
private int head;
private int tail;
private boolean full;
public NodeArrayQueue2(int size) {
data = new Node[size];
head = 0;
tail = 0;
}
public void enqueue(Node d) throws Exception {
if (head - tail == 0 && full || (head == 0 && (tail == 0) && full)) {
throw new Exception("full");
}
data[tail] = d;
tail = tail + 1;
if (tail == data.length) {
tail = 0;
}
if (head == tail) {
full = true;
}
}
public Node dequeue() throws Exception {
if (head == tail && !full || (head == data.length && tail == 0)) {
throw new Exception("empty");
}
full = false;
head = head + 1;
if (head == data.length) {
head = 0;
return data[data.length - 1];
} else {
return data[head - 1];
}
}
public boolean isEmpty() {
if (head == tail && !full || (head == data.length && tail == 0)) {
return true;
} else {
return false;
}
}
}
public static void main(String[] args)throws Exception {
EdmondsKarp e=new EdmondsKarp();
e.print();
e.edmondsKarp();
e.printResult();
}
}
