import fi.joensuu.cs.tra.*;

import java.util.HashMap;
import java.util.LinkedList;
import java.lang.RuntimeException;

public class FordFulkerson {

    public static void main(String[] args) {

        FordFulkerson y;

        if (args.length > 0)
            y = new FordFulkerson(true);
        else
            y = new FordFulkerson(false);

        y.floatExample();
    }

    boolean print = false;

    public FordFulkerson(boolean p) {
        print = p;
    }


    // vertices to given color
    void color(AbstractGraph g, int c) {
        for (Vertex v : g.vertices())
            v.setColor(c);
    }

    // maximum flow
    // Ford-Fulkerson

    // returns only max flow
    float fordFulkerson(DiGraph G, Vertex s, Vertex d) {
        float[][] flow = new float[G.size()][G.size()];
        return fordFulkerson(G, s, d, flow);
    }

    // returns also usage of edges as a matrix
    float fordFulkerson(DiGraph G, Vertex s, Vertex d, float[][] flow) {

        int n = G.size();
        float tcap = 0;

        int si = -1, di = -1;

        // make Vertex array, find indecis of s and d
        Vertex[] vA = GraphMaker.getVertexArrayIndex(G);
        for (int i = 0; i < n; i++) {
            if (vA[i] == s)
                si = i;
            if (vA[i] == d)
                di = i;
        }

        if (si < 0 || di < 0)
            throw new RuntimeException("Source or destination not found");

        // init flow
        int ne = 0;
        for (Edge e : G.edges()) {
            int i = e.getStartPoint().getIndex();
            int j = e.getStartPoint().getIndex();
            flow[i][j] = 0;
            flow[j][i] = 0;
            ne++;
        }

        // make residual graph, get map of edge pairs
        HashMap<Edge, Edge> pairs = new HashMap<Edge, Edge>(ne*4);
        DiGraph R = makeRes(G, pairs);
        Vertex[] vAR = GraphMaker.getVertexArrayIndex(R);

        // source and destination in residual graph
        Vertex sr =  vAR[si];
        Vertex dr =  vAR[di];

        while(true) {

            if (print) System.out.println("\nFind path");
            LinkedList<Edge> p = dfsPath(R, sr, dr);
            if (print) System.out.println("\nPath:" + p);

            if (p == null)
                break;

            // find capacity of the found augmenting path
            float cap = p.getFirst().getWeight();
            for (Edge e : p)
                if (e.getWeight() < cap)
                    cap = e.getWeight();

            if (print) System.out.println("cap " + cap);

            // update flow and residual graph
            for (Edge e : p) {
                Vertex v1 = e.getStartPoint();
                Vertex v2 = e.getEndPoint();

                flow[v1.getIndex()][v2.getIndex()] += cap;
                flow[v2.getIndex()][v1.getIndex()] =
                    -flow[v1.getIndex()][v2.getIndex()];

                e.setWeight(e.getWeight() - cap);
                Edge e2 = pairs.get(e);
                e2.setWeight(e2.getWeight() + cap);
            }
            tcap += cap;    // add total flow capacity
        } // while

        return tcap;
    }   // fordFulkerson()

    // finds augmenting path
    LinkedList<Edge> dfsPath(DiGraph res, Vertex start, Vertex sink) {

        if (print) System.out.println("Dfspath residual graph:");
        if (print) System.out.print(res);

        color(res, DiGraph.WHITE);
        LinkedList<Edge> L = new LinkedList<Edge>();

        // actual search
        if (dfsPath_r(start, sink, L))
            return L;
        else
            return null;
    }

    // recursive dfs
    boolean dfsPath_r(Vertex start, Vertex sink, LinkedList<Edge> L) {

        if (start == sink)
            return true;        // path found

        start.setColor(DiGraph.BLACK);
        for (Edge e : start.edges()) {

            if (e.getEndPoint().getColor() == DiGraph.WHITE &&
                e.getWeight() > 0) {    // positive residual capacity

                L.addLast(e);   // add edge to path
                boolean found = dfsPath_r(e.getEndPoint(), sink, L);
                if (found)
                    return true;
                else
                    L.removeLast(); // remove edge
            }
        }
        return false;
    }

    // make residual graph, in addition to each edge, also a reverse
    // edge (unless it already exists), returns also a map of reverse edges
    DiGraph makeRes(DiGraph G, HashMap<Edge, Edge> pairs) {

        int n = G.size();
        float[][] M = GraphMaker.graphToMatrixWeight(G);

        // graph and vertices
        DiGraph R = new DiGraph();
        Vertex[] vA = new Vertex[n];

        for (int i = 0; i < n; i++)
            vA[i] = R.addVertex("r" + i, i);

        // edges
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (M[i][j] != -1.0) {
                    Edge e1 = vA[i].addEdge(vA[j], "" + i + j, 0, M[i][j]);
                    Edge e2;
                    if (M[j][i] == -1.0)       // virtual pair
                        e2 = vA[j].addEdge(vA[i], "" + j + i, 0, 0);
                    else if (j < i)             // if pair was done already
                        e2 = vA[j].getEdge(vA[i]);
                    else
                        continue;       // real pair will be made later
                        
                    pairs.put(e1, e2);
                    pairs.put(e2, e1);
                }

        return R;
    }


    // constructs example flow graph
    void floatExample() {

        final int n = 6;

        DiGraph G = new DiGraph();

        Vertex[] vA = new Vertex[n];

        vA[0] = G.addVertex("s");
        vA[1] = G.addVertex("1");
        vA[2] = G.addVertex("2");
        vA[3] = G.addVertex("3");
        vA[4] = G.addVertex("4");
        vA[5] = G.addVertex("d");

        vA[0].addEdge(vA[1], "16", 0, 16);
        vA[0].addEdge(vA[2], "13", 0, 13);
        vA[1].addEdge(vA[2], "10", 0, 10);
        vA[1].addEdge(vA[3], "12", 0, 12);
        vA[2].addEdge(vA[4], "14", 0, 14);
        vA[2].addEdge(vA[1], " 4",  0, 4);
        vA[3].addEdge(vA[2], " 9", 0,  9);
        vA[3].addEdge(vA[5], "20", 0, 20);
        vA[4].addEdge(vA[3], " 7", 0,  7);
        vA[4].addEdge(vA[5], " 4", 0,  4);

        System.out.println("Maximal flow");
        if (print) System.out.println(G);

        float[][] flow = new float[n][n];

        float cap = fordFulkerson(G, vA[0], vA[5], flow);

        System.out.println("Capacity = " + cap);

        if (print) for (int i = 0; i < n; i++) {
            System.out.print(i + " |");
            for (int j = 0; j < n; j++) {
                System.out.print(" " + flow[i][j]);
            }
            System.out.println();
        }

    } // floatExample()


}   // class FordFulkerson