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;
    }


    // verkko (suunnattu tai suuntaamaton) annetun väriseksi
    void varita(AbstractGraph g, int c) {
        for (Vertex v : g.vertices())
            v.setColor(c);
    }

    // maksimaalinen virtaus
    // Ford-Fulkerson

    // kuorrutus, palauttaa vain virtauslukeman
    float fordFulkerson(DiGraph G, Vertex s, Vertex d) {
        float[][] flow = new float[G.size()][G.size()];
        return fordFulkerson(G, s, d, flow);
    }

    // täysi versio, palauttaa myös virtauksen kaarimatriisina
    // s lähdesolmu, d kohdesolmu, flow virtausmatriisi
    float fordFulkerson(DiGraph G, Vertex s, Vertex d, float[][] flow) {

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

        int si = -1, di = -1;

        // indeksoidaan solmut, tallennetaan lähteen ja kohteen indeksit
        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");

        // alustetaan virtausverkko
        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++;
        }

        // muodostetaan jäännösverkko ja kuvaus vastinkaarien välillä
        HashMap<Edge, Edge> pairs = new HashMap<Edge, Edge>(ne*4);
        DiGraph R = makeRes(G, pairs);
        Vertex[] vAR = GraphMaker.getVertexArrayIndex(R);

        // lähde ja kohde jäännösverkossa
        Vertex sr =  vAR[si];
        Vertex dr =  vAR[di];

        // toistetaan täydentävän plun hakua
        while(true) {

            if (print) System.out.println("\nHaetaan polku");
            // haetaan täydentävä polku
            LinkedList<Edge> p = dfsPath(R, sr, dr);
            if (print) System.out.println("\nPolku:" + p);

            if (p == null)
                break;

            // täydentävän polun kapasiteetti on minimi polkujen kapasiteetista
            float cap = p.getFirst().getWeight();
            for (Edge e : p)
                if (e.getWeight() < cap)
                    cap = e.getWeight();

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

            // lisätään täydentävä polku virtausverkkoon
            // ja vähennetään kapasiteetti jäännösverkosta
            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;    // lisätään kokonaiskapasiteettia
        } // while

        return tcap;
    }   // fordFulkerson()

    // täydentävän polun haku syvyyssuuntaisella haulla
    LinkedList<Edge> dfsPath(DiGraph res, Vertex start, Vertex sink) {

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

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

        // haun käynnistys
        if (dfsPath_r(start, sink, L))
            return L;
        else
            return null;
    }

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

        // rekursion lopetus polku löytyessä
        if (start == sink)
            return true;

        // värjäys estämään kehiä
        start.setColor(DiGraph.BLACK);
        for (Edge e : start.edges()) {

            if (e.getEndPoint().getColor() == DiGraph.WHITE &&
                e.getWeight() > 0) {    // positiuvun jäännöskapasiteetti

                // lisätään kaari polulle, kutsutaan rekursiivisesti
                L.addLast(e);
                boolean found = dfsPath_r(e.getEndPoint(), sink, L);
                if (found)
                    return true;
                else
                    L.removeLast(); // poistaan kaari jollei polkua löytynyt
            }
        }
        // palautetaan väri valkoiseksi jotta toinen haun haara voisi käyttää
        // tätäkin solmua
        start.setColor(DiGraph.WHITE);
        return false;
    }

    // jäännösverkon alustus alkuperäisestä verkosta. Vastakaarien lisäksi
    // tehdään vastakaari (paitsi jos se on jo olemassa). Palauttaa myös
    // kaariparien kuvauksen
    DiGraph makeRes(DiGraph G, HashMap<Edge, Edge> pairs) {

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

        // verkko ja solmut
        DiGraph R = new DiGraph();
        Vertex[] vA = new Vertex[n];

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

        // kaaret
        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)       // virtuaalinen pari
                        e2 = vA[j].addEdge(vA[i], "" + j + i, 0, 0);
                    else if (j < i)            // todellinen pari jo oli
                        e2 = vA[j].getEdge(vA[i]);
                    else
                        continue;       // todellinen pari lisätään myöhemmin
                        
                    pairs.put(e1, e2);
                    pairs.put(e2, e1);
                }

        return R;
    }


    // esimerkkiverkko
    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("Maksimivirta");
        if (print) System.out.println(G);

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

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

        System.out.println("Kapasiteetti = " + 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