//
//  MaxFlowTest3.java
//  
//
//  Created by Herbert J. Bernstein on 2/28/11.
//  Copyright 2011 Herbert J. Bernstein. All rights reserved.
//

public class MaxFlowTest3 {
    public static void main(String args[]) {
        int caps[][] = new int[14][14];
        int flows[][] = new int[14][14];
        int aug[][] = new int[14][14];
        int augp[][][] = new int[14][14][14];
        int tdist[][] = new int[14][14];
        int cuts[][] = new int[14][14];
        int mcap;
        boolean pdist[][] = new boolean[14][14];
        int source = 0;
        int sink = 13;
        int inter;
        int ii, jj, kk;
        //             0   1   2   3   4   5   6   7   8   9  10  11  12  13
        String nn[] = {"A","B","C","D","E","F","G","H","I","J","K","L","M","N"};
        for (ii=0; ii<14; ii++) {
            for (jj=0; jj<14; jj++ ) {
                caps[ii][jj] = 0;
            }
        }
        caps[0][1] = 6;
        caps[0][2] = 4;
        caps[0][3] = 8;
        caps[1][4] = 6;
        caps[1][5] = 3;
        caps[1][6] = 2;
        caps[2][7] = 12;
        caps[2][8] = 3;
        caps[3][1] = 1;
        caps[4][8] = 3;
        caps[4][9] = 3;
        caps[5][10] = 4;
        caps[5][3] = 4;
        caps[6][9] = 3;
        caps[7][11] = 3;
        caps[8][13] = 6;
        caps[8][11] = 3;
        caps[8][2] = 2;
        caps[9][12] = 3;
        caps[10][4] = 7;
        caps[10][12] = 3;
        caps[11][13] = 6;
        caps[12][13] = 6;
        for (ii=0; ii<14; ii++) {
            for (jj=0; jj<14; jj++ ) {
                flows[ii][jj] = 0;
            }
        }
        MaxFlow.AugmentedGraph(caps,flows,aug,augp);
        int pass=0;
        while (true) {
            System.out.println("Pass: "+(pass++));
            MaxFlow.FindRecipPath(source,sink,aug,augp,pdist,tdist);
            for (ii=0; ii<14; ii++) {
                for (jj=1; jj<14; jj++) {
                    System.out.println("Minimum distance from A to " +nn[jj]+": "+tdist[0][jj]);
                    System.out.print("Hops :"+augp[0][jj][0]+": ");
                    for (kk=1;kk<augp[0][jj][0];kk++) {
                        System.out.print(nn[augp[0][jj][kk]]);
                    }
                    System.out.println();
                }
            }
            if (augp[0][13][0] == 0) break;
            inter = augp[0][13][1];
            mcap = aug[0][inter];
            for (ii=2;ii<=augp[0][13][0];ii++) {
                if (aug[inter][augp[0][13][ii]]<mcap) mcap=aug[inter][augp[0][13][ii]];
                inter = augp[0][13][ii];
            }
            inter = 0;
            System.out.println("Flow increment "+mcap);
            for (ii=1;ii<=augp[0][13][0];ii++) {
                flows[inter][augp[0][13][ii]] += mcap;
                inter = augp[0][13][ii];
            }
            MaxFlow.AugmentedGraph(caps,flows,aug,augp);
        }
        System.out.println("Flows:");
        MaxFlow.PrintAdjMat(flows);
        System.out.println("Aug:");
        MaxFlow.PrintAdjMat(aug);
        for (ii=0; ii < 14;ii++) {
            for (jj=0; jj < 14; jj++) {
                cuts[ii][jj] = 0;
                if (caps[ii][jj] > 0 ) {
                    if (aug[ii][jj] == 0) cuts[ii][jj] = caps[ii][jj];
                }
            }
        }
        System.out.println("Cuts:");
        MaxFlow.PrintAdjMat(cuts);
        return;
    }
    

}