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

public class MaxFlow {
    
    static int AugmentedGraph(int caps[][], int flows[][], int aug[][], int augp[][][] ){
        int capnodes = caps.length;
        int flownodes = flows.length;
        int augnodes = aug.length;
        int augpnodes = augp.length;
        int ii, jj, kk;
        if (capnodes != flownodes 
            || capnodes==0
            || augnodes != capnodes
            || augpnodes != capnodes) return 1;
        for (ii = 0; ii < capnodes; ii++) {
            if ((caps[ii]).length != capnodes) return 1;
            if ((flows[ii]).length != capnodes) return 1;
            if ((aug[ii]).length != capnodes) return 1;
            if ((augp[ii]).length != capnodes) return 1;
            for (jj=0; jj < capnodes; jj++) {
                if ((augp[ii][jj]).length != capnodes) return 1;
            }
        }
        for (ii=0; ii < capnodes; ii++) {
            for (jj=0; jj < capnodes; jj++) {
                augp[ii][jj][0] = 0;
                aug[ii][jj] = flows[jj][ii] + caps[ii][jj]-flows[ii][jj];
                if (aug[ii][jj] > 0 ) {
                    augp[ii][jj][0] = 1;
                    augp[ii][jj][1] = jj;
                }
            }
        }
        return 0;
    }
    
    static String LofN(int n) {
        //              0   1   2   3   4   5   6   7   8   9  10  11  12  13
        //               14  15  16  17  18  19  20  21  22  23  24  25
        String stout;
        int res, nlocal=n;
        String nn[] = {"A","B","C","D","E","F","G","H","I","J","K","L","M","N",
                         "O","P","Q","R","S","T","U","V","W","X","Y","Z"};
        if (n < 0) return "?";
        stout=nn[nlocal%26];
        nlocal = nlocal/26;
        while(nlocal>0) {
            stout = nn[nlocal%26] + stout;
        }
        return stout;
    }
    
    static int PrintAdjMat(int adj[][]) {
        int ii, jj;
        for (ii = 0; ii < adj.length; ii++) {
            System.out.print(" Links from node "+LofN(ii)+": ");
            for (jj = 0; jj < adj[ii].length; jj++) {
                if (adj[ii][jj] > 0 ) {
                    System.out.print(LofN(ii)+"-"+LofN(jj)+"("+adj[ii][jj]+") ");
                }
            }
            System.out.println();
        }
        return 0;
    }
    
    static int FindPath(int source, int sink,
                         int aug[][], int augp[][][], 
                         boolean pdist[][], int tdist[][]) {
        int augnodes = aug.length;
        int augpnodes = augp.length;
        int pdistnodes = pdist.length;
        int tdistnodes = tdist.length;
        int ii, jj, kk, ihop, permcount;
        int ipass;
        int tmin, dist;
        if (pdistnodes != tdistnodes 
            || pdistnodes==0
            || augnodes != pdistnodes
            || augpnodes != pdistnodes) return 1;
        for (ii = 0; ii < pdistnodes; ii++) {
            if ((pdist[ii]).length != pdistnodes) return 1;
            if ((tdist[ii]).length != pdistnodes) return 1;
            if ((aug[ii]).length != pdistnodes) return 1;
            if ((augp[ii]).length != pdistnodes) return 1;
            for (jj=0; jj < pdistnodes; jj++) {
                if ((augp[ii][jj]).length != pdistnodes) return 1;
            }
        }
        
        // Start every node off with its one-hop distance
        for (ii=0; ii < pdistnodes; ii++) {
            for (jj=0; jj < pdistnodes; jj++) {
                pdist[ii][jj] = false;
                tdist[ii][jj] = aug[ii][jj];
            }
        }
        pdist[source][source] = true;
        permcount = 1;
        
        // first find the closest node to the source
        // and mark all 1 hop nodes at that distance
        // as permanent
        
        tmin = -1;
        dist = 0;
        for (ii=0; ii < pdistnodes; ii++) {
            if (aug[source][ii] != 0 ) {
                if(tmin == -1 || aug[source][ii] < dist) {tmin = ii; dist=aug[source][ii];}
            }            
        }
        if (tmin == -1) return 1;
        for (ii=0; ii < pdistnodes; ii++) {
            if (!pdist[source][ii] && tdist[source][ii] > 0 && tdist[source][ii] <= tdist[source][tmin]) {
                pdist[source][ii] = true;
                permcount++;
            }
        }
        
        PrintAdjMat(tdist);
        PrintAdjMat(aug);
        
        // Now we run through a cases of 2 through pdistnodes-1 hops
        // marking the minimal distances at each hop as permanent
        
        for (ihop = 2; ihop < pdistnodes && permcount < pdistnodes; ihop++) {
            System.out.println("Hop: "+ihop);
            // extend each path from source by a hop,
            // provided it reduces the distance
            for (ii=0; ii < pdistnodes; ii++) {
                if (tdist[source][ii] != 0)
                for (jj = 0; jj < pdistnodes; jj++) {
                    if (aug[ii][jj] != 0 && jj != source ) {
                        if (tdist[source][jj] > tdist[source][ii]+aug[ii][jj]
                            ||tdist[source][jj]==0) {
                            System.out.print("Found path via "+ii+" to "+jj+": ");
                            for(kk = 0; kk < pdistnodes; kk++) {
                                augp[source][jj][kk] = augp[source][ii][kk];
                                System.out.print(" "+augp[source][ii][kk]);
                            }
                            augp[source][jj][0]++;
                            augp[source][jj][augp[source][jj][0]] = jj;
                            System.out.println(" "+jj);
                            tdist[source][jj] = tdist[source][ii]+aug[ii][jj];
                        }
                    }
                }
            }
            // now find the minimal non-permanent distance and make it permanent
            tmin = -1;
            dist = 0;
            for (ii=0; ii < pdistnodes; ii++) {
                if (aug[source][ii] != 0 && !pdist[source][ii] ) {
                    if(tmin == -1 || aug[source][ii] < dist) {tmin = ii; dist=aug[source][ii]; }
                }            
            }
            if (tmin == -1) return 1;
            for (ii=0; ii < pdistnodes; ii++) {
                if (!pdist[source][ii] && tdist[source][ii] > 0 && tdist[source][ii] <= tdist[source][tmin]) {
                    pdist[source][ii] = true;
                    permcount++;
                }
            } 
            
            PrintAdjMat(tdist);
        }
        
        System.out.println(" Final distances from Dijkstra's algorithm");
        PrintAdjMat(tdist);
        
        return 0;
        
    }

    
    static int FindRecipPath(int source, int sink,
                        int aug[][], int augp[][][], 
                        boolean pdist[][], int tdist[][]) {
        int augnodes = aug.length;
        int augpnodes = augp.length;
        int pdistnodes = pdist.length;
        int tdistnodes = tdist.length;
        int ii, jj, kk, ihop, permcount;
        int ipass;
        int tmin, dist;
        if (pdistnodes != tdistnodes 
            || pdistnodes==0
            || augnodes != pdistnodes
            || augpnodes != pdistnodes) return 1;
        for (ii = 0; ii < pdistnodes; ii++) {
            if ((pdist[ii]).length != pdistnodes) return 1;
            if ((tdist[ii]).length != pdistnodes) return 1;
            if ((aug[ii]).length != pdistnodes) return 1;
            if ((augp[ii]).length != pdistnodes) return 1;
            for (jj=0; jj < pdistnodes; jj++) {
                if ((augp[ii][jj]).length != pdistnodes) return 1;
            }
        }
        
        // Start every node off with its one-hop distance
        for (ii=0; ii < pdistnodes; ii++) {
            for (jj=0; jj < pdistnodes; jj++) {
                pdist[ii][jj] = false;
                tdist[ii][jj] = aug[ii][jj];
                if (aug[ii][jj] != 0) tdist[ii][jj] = 1000/aug[ii][jj];
            }
        }
        pdist[source][source] = true;
        permcount = 1;
        
        // first find the closest node to the source
        // and mark all 1 hop nodes at that distance
        // as permanent
        
        tmin = -1;
        dist = 0;
        for (ii=0; ii < pdistnodes; ii++) {
            if (aug[source][ii] != 0 ) {
                if(tmin == -1 || 1000/aug[source][ii] < dist) {tmin = ii; dist=1000/aug[source][ii]; }
            }            
        }
        if (tmin == -1) return 1;
        for (ii=0; ii < pdistnodes; ii++) {
            if (!pdist[source][ii] && tdist[source][ii] > 0 && tdist[source][ii] <= tdist[source][tmin]) {
                pdist[source][ii] = true;
                permcount++;
            }
        }
        
        PrintAdjMat(tdist);
        PrintAdjMat(aug);
        
        // Now we run through a cases of 2 through pdistnodes-1 hops
        // marking the minimal distances at each hop as permanent
        
        for (ihop = 2; ihop < pdistnodes && permcount < pdistnodes; ihop++) {
            System.out.println("Hop: "+ihop);
            // extend each path from source by a hop,
            // provided it reduces the distance
            for (ii=0; ii < pdistnodes; ii++) {
                if (tdist[source][ii] != 0)
                    for (jj = 0; jj < pdistnodes; jj++) {
                        if (aug[ii][jj] != 0 && jj != source ) {
                            if (tdist[source][jj] > tdist[source][ii]+1000/aug[ii][jj]
                                ||tdist[source][jj]==0) {
                                System.out.print("Found path via "+ii+" to "+jj+": ");
                                for(kk = 0; kk < pdistnodes; kk++) {
                                    augp[source][jj][kk] = augp[source][ii][kk];
                                    System.out.print(" "+augp[source][ii][kk]);
                                }
                                augp[source][jj][0]++;
                                augp[source][jj][augp[source][jj][0]] = jj;
                                System.out.println(" "+jj);
                                tdist[source][jj] = tdist[source][ii]+1000/aug[ii][jj];
                            }
                        }
                    }
            }
            // now find the minimal non-permanent distance and make it permanent
            tmin = -1;
            dist = 0;
            for (ii=0; ii < pdistnodes; ii++) {
                if (aug[source][ii] != 0 && !pdist[source][ii] ) {
                    if(tmin == -1 || 1000/aug[source][ii] < dist) {tmin = ii; dist=1000/aug[source][ii]; }
                }            
            }
            if (tmin == -1) return 1;
            for (ii=0; ii < pdistnodes; ii++) {
                if (!pdist[source][ii] && tdist[source][ii] > 0 && tdist[source][ii] <= tdist[source][tmin]) {
                    pdist[source][ii] = true;
                    permcount++;
                }
            } 
            
            PrintAdjMat(tdist);
        }
        
        System.out.println(" Final distances from Dijkstra's algorithm using reciprocals");
        PrintAdjMat(tdist);
        System.out.println("\n\n");

        
        return 0;
        
    }
    
}