import fi.uef.cs.tra.*;

import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Set;


public class DiGraphExample24 {

    public static void main(String[] args) {

        // defaults
        int vertices = 3;
        int edges = 6;

        if (args.length > 0)
            vertices = Integer.parseInt(args[0]);

        if (args.length > 1)
            edges = Integer.parseInt(args[1]);

        int seed = vertices+edges;

        if (args.length > 2)
            seed = Integer.parseInt(args[2]);


        DiGraphExample24 y = new DiGraphExample24();


        // create random graph
        DiGraph graph = GraphMaker.createDiGraph(vertices, edges, seed);
        System.out.println("\nGraph:");
        System.out.println(graph.toString());

        System.out.println("hasCycle: " + y.hasCycle(graph));
        System.out.println("strongly connected: " + y.stronglyConnected(graph));


        System.out.println("\nPrint by iteration");
        for (Vertex v : graph.vertices()) {
            System.out.print(v + " : " );
            for (Vertex w : v.neighbors())
                System.out.print(w + " ");
            System.out.println();
        }


        System.out.println("\nPrint all edges");
        for (Edge e : graph.edges())
            System.out.print(e + " ");
        System.out.println();

        System.out.println("\nPrint all edges by vertices");
        for (Vertex v : graph.vertices()) {
            System.out.print(v + " : " );
            for (Edge e : v.edges())
                System.out.print(e + " ");
            System.out.println();
        }

        Vertex v1 = null;
        Vertex v2 = null;
        for (Vertex v : graph.vertices()) {
            if (v1 == null)
                v1 = v;
            else if (v2 == null)
                v2 = v;
        }
        LinkedList<LinkedList<Vertex>> paths = y.allPaths(graph, v1, v2);
        System.out.println("\nAll paths");
        System.out.println(paths);

        LinkedList<LinkedList<Vertex>> comp = y.stronglyConnectedComponents(graph);
        System.out.println("\nStrongly connected components");
        System.out.println(comp);

        GraphMaker.addRandomCycle(graph, false);
        System.out.println("\nhasCycle");
        for (Vertex v : graph.vertices()) {
            System.out.print(v + " : " );
            for (Vertex w : v.neighbors())
                System.out.print(w + " ");
            System.out.println();
        }
        System.out.println("hasCycle: " + y.hasCycle(graph));
        System.out.println("strongly connected: " + y.stronglyConnected(graph));
        
        if (vertices < 20) {
            paths = y.allPaths(graph, v1, v2);
            System.out.println("\nAll paths");
            System.out.println(paths);
        }

        comp = y.stronglyConnectedComponents(graph);
        System.out.println("\nStrongly connected components");
        System.out.println(comp);

        graph = GraphMaker.createCompleteDiGraph(vertices);
        System.out.println("\nComplete graph");
        v1 = null; v2 = null;
        for (Vertex v : graph.vertices()) {
            if (v1 == null)
                v1 = v;
            else if (v2 == null)
                v2 = v;
            System.out.print(v + " : " );
            for (Vertex w : v.neighbors())
                System.out.print(w + " ");
            System.out.println();
        }
        if (vertices < 7) {
            paths = y.allPaths(graph, v1, v2);
            System.out.println("\nAll paths");
            System.out.println(paths);
        }


        graph = GraphMaker.createDAG(vertices, edges, seed);
        System.out.println("\nDAG");
        for (Vertex v : graph.vertices()) {
            System.out.print(v + " : " );
            for (Vertex w : v.neighbors())
                System.out.print(w + " ");
            System.out.println();
        }
        comp = y.stronglyConnectedComponents(graph);
        System.out.println("\nStrongly connected components");
        System.out.println(comp);
        System.out.println("hasCycle: " + y.hasCycle(graph));
        System.out.println("topoSort: " + y.topoSort(graph));


        System.out.println();
        System.out.println(GraphMaker.toMatrixString(graph));

        System.out.println("\nWeight matrix");
        float[][] M = GraphMaker.graphToMatrixWeight(graph);
        for (int i = 0; i < vertices; i++) {
            for (int j = 0; j < vertices; j++) {
                System.out.print(M[i][j] + " ");
            }
            System.out.println();
        }
        
    }


    // depth first search coloring with color col
    // original vertex colours had to be other that col
    void dfsColor(Vertex vertex, int col) {
        vertex.setColor(col);
        for (Vertex neighborVertex : vertex.neighbors())
            if (neighborVertex.getColor() != col)
                dfsColor(neighborVertex, col);

    }

    // set color of all vertices to col
    void color(AbstractGraph g, int col) {
        for (Vertex v : g.vertices())
            v.setColor(col);
    }

    // set of followers of a given vertex
    Set<Vertex> reachable(Vertex start) {
        Set<Vertex> s = new HashSet<>();
        reachable_r(s, start);
        return s;
    }

    void reachable_r(Set<Vertex> s, Vertex start) {
        for (Vertex v : start.neighbors()) {
            if (! s.contains(v)) {
                s.add(v);
                reachable_r(s, v);
            }
        }
    }


    // find whether there is a cycle in a graph or not
    // call hasCyclefs for each component
    public boolean hasCycle(DiGraph g) {
        color(g, DiGraph.WHITE);
        for (Vertex v : g.vertices())
            if (v.getColor() == DiGraph.WHITE)
                if (hasCycleDfs(v))
                    return true;
        return false;
    }

    // find whether there is a cycle in a graph or not
    // recursive part using dfs
    // vertices are gray during recursion, maked black at the end of recursion
    // if we find a gray vertex, we have found a cycle
    boolean hasCycleDfs(Vertex start) {

        start.setColor(DiGraph.GRAY);
        for (Vertex vertex : start.neighbors()) {
            if (vertex.getColor() == DiGraph.GRAY)
                return true;
            else if (vertex.getColor() == DiGraph.WHITE)
                if (hasCycleDfs(vertex))
                    return true;
        }

        start.setColor(Graph.BLACK);
        return false;
    }


    // all simple paths between two vertices
    // result as a list of list of vertices
    LinkedList<LinkedList<Vertex>> allPaths(DiGraph g, Vertex start, Vertex end) {

        color(g, DiGraph.WHITE);

        LinkedList<LinkedList<Vertex>> paths = new LinkedList<LinkedList<Vertex>>();
        LinkedList<Vertex> pino = new LinkedList<Vertex>();

        pino.add(start);

        if (start != end)
            start.setColor(Graph.BLACK);

        for (Vertex v : start.neighbors()) {
            allPaths_r(paths, pino, v, end);
        }

        start.setColor(Graph.WHITE);

        return paths;
    }

    void allPaths_r(LinkedList<LinkedList<Vertex>> paths, LinkedList<Vertex> pino,
                     Vertex start, Vertex end) {
        pino.add(start);

        if (start == end) {
            paths.add(new LinkedList<Vertex>(pino));
            pino.removeLast();
            return;
        }

        start.setColor(Graph.BLACK);

        for (Vertex v : start.neighbors()) {
            if (v.getColor() == Graph.WHITE)
                allPaths_r(paths, pino, v, end);
        }

        start.setColor(Graph.WHITE);
        pino.removeLast();
    }


    // strongly connected, brute force
    boolean stronglyConnected(DiGraph g) {
        int n = g.size();

        for (Vertex v : g.vertices()) {
            Set<Vertex> seur = reachable(v);
            seur.add(v);
            if (seur.size() != n)
                return false;
        }

        return true;
    }


    // strongly connected components as a list of list of components
    LinkedList<LinkedList<Vertex>> stronglyConnectedComponents(DiGraph g) {
        
        Vertex[] va = GraphMaker.getVertexArrayIndex(g);
        int n = va.length;

        // dfsnumber (post-order)
        int[] dfsnum = postOrderNumberingDfs(g);

        // Build transpose gt of g
        DiGraph gt = new DiGraph();
        Vertex[] vat = new Vertex[n];

        // vertices
        for (int i = 0; i < n; i++) {
            vat[i] = gt.addVertex("" + i);
            vat[i].setIndex(i);
        }

        // edges
        for (int i = 0; i < n; i++)
            for (Vertex w : va[i].neighbors())
                vat[w.getIndex()].addEdge(vat[i]);


        // dfs gt using decreasing order

        // inverse ("sorting" index) of dfsnum
        int[] dfsnum_inverse = new int[n];
        for (int i = 0; i < n; i++)
            dfsnum_inverse[dfsnum[i]] = i;

        // now dfsnum_inverse contains node indeces in order of incresing
        // dfsnumber

        color(gt, DiGraph.WHITE);

        LinkedList<LinkedList<Vertex>> components =
            new LinkedList<LinkedList<Vertex>>();

        // start dfs in decreasing order of dfsnumber
        for (int i = n-1; i >= 0; i--)
            if (vat[dfsnum_inverse[i]].getColor() == DiGraph.WHITE) {
                // new component found
                LinkedList<Vertex> comp = new LinkedList<Vertex>();
                treeDfs(vat[dfsnum_inverse[i]], va, comp);
                components.add(comp);
            }

        return components;
    }   // stronglyConnectedComponents()

    
    int[] postOrderNumberingDfs(DiGraph g) {
        int n = g.size();
        int[] f = new int[n];
        int i = 0;

        color(g, DiGraph.WHITE);

        for (Vertex v : g.vertices())
            if (v.getColor() == DiGraph.WHITE)
                i = postOrderNumberingDfs_r(f, i, v);

        return f;
    }   // postOrderNumberingDfs()
    

    int postOrderNumberingDfs_r(int[] f, int i, Vertex v) {
        v.setColor(DiGraph.BLACK);
        for (Vertex w : v.neighbors())
            if (w.getColor() == DiGraph.WHITE)
                i = postOrderNumberingDfs_r(f, i, w);
        f[v.getIndex()] = i;
        return i + 1;
    }   // postOrderNumberingDfs_r()

    
    void treeDfs(Vertex v, Vertex[] va, LinkedList<Vertex> comp) {
        v.setColor(DiGraph.BLACK);
        comp.add(va[v.getIndex()]);
        for (Vertex w : v.neighbors())
            if (w.getColor() == DiGraph.WHITE)
                 treeDfs(w, va, comp);
    }   // treeDfs()


    // \ strongly connected components


    // topological sort for vertices of DAG
    // does not check acyclicity of graph (as it is an exercise)
    LinkedList<Vertex> topoSort(DiGraph G) {
        LinkedList<Vertex> L = new LinkedList<Vertex>();

        color(G, DiGraph.WHITE);

        for (Vertex v : G.vertices())
            if (v.getColor() == DiGraph.WHITE)
                topoSort_r(v, L);

        return L;

    }

    void topoSort_r(Vertex v, LinkedList<Vertex> L) {
        v.setColor(DiGraph.BLACK);
        for (Vertex w : v.neighbors())
            if (w.getColor() == DiGraph.WHITE)
                topoSort_r(w, L);
        L.add(0, v);
    }

    // \ topo sort

    // 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
    // TODO: get vertex array, now this assumes indeces to be same
    // every time
    float fordFulkerson(DiGraph G, Vertex s, Vertex d, float[][] flow) {

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

        int si = 0, di = 5;

        Vertex[] vA = GraphMaker.getVertexArrayIndex(G);
        for (int i = 0; i < n; i++) {
            if (vA[i] == s)
                si = i;
            if (vA[i] == d)
                di = i;
        }

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

        HashMap<Edge, Edge> pairs = new HashMap<Edge, Edge>(ne*4);
        DiGraph R = makeRes(G, pairs);
        Vertex[] vAR = GraphMaker.getVertexArrayIndex(R);

        Vertex sr =  vAR[si];
        Vertex dr =  vAR[di];

        System.out.println("res");
        System.out.println(R);

        while(true) {

            System.out.println("haetaan polku");
            LinkedList<Edge> p = dfspath(R, sr, dr);
            System.out.println("polku:" + 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();

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


            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;
        }
/*
        float fl = 0;
        for (int i = 0; i < n; i++)
            fl += flow[start.getIndex()][i];
        return fl;
        */

        return tcap;
    }

    LinkedList<Edge> dfspath(DiGraph res, Vertex start, Vertex sink) {

        System.out.println("dfsparh res");
        System.out.println(res);
        color(res, DiGraph.WHITE);
        LinkedList<Edge> L = new LinkedList<Edge>();

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

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

        if (start == sink)
            return true;

        start.setColor(DiGraph.BLACK);
        for (Edge e : start.edges()) {
            if (e.getEndPoint() == start)
                continue; // bug in Vertex.edges() ?

            if (e.getEndPoint().getColor() == DiGraph.WHITE &&
                e.getWeight() > 0) {
                L.addLast(e);
                boolean found = dfsPath_r(e.getEndPoint(), sink, L);
                if (found)
                    return true;
                else
                    L.removeLast();
            }
        }

        return false;
    }



    DiGraph makeRes(DiGraph G, HashMap<Edge, Edge> pairs) {

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

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

        DiGraph C = new DiGraph();
        Vertex[] vA = new Vertex[n];
        
        for (int i = 0; i < n; i++)
            vA[i] = C.addVertex("r" + i, i);
        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 = vA[j].addEdge(vA[i], "" + j + i, 0, 0);
                    pairs.put(e1, e2);
                    pairs.put(e2, e1);
                }

        return C;
    }


    // create the same graph as in maximum flow example
    // in lectures
    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("Maximum flow");
        System.out.println(G);

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

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

        System.out.println(cap);
        System.out.println(flow);

    }








}