import fi.uef.cs.tra.*;

import java.util.LinkedList;


public class GraphExample24 {

    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]);


        System.out.println("\nGraph1: ");
        Graph graph = GraphMaker.createGraph(vertices, edges, seed);
        System.out.println(graph.toString());
        System.out.println(GraphMaker.toString(graph, 0));

        GraphExample24 y = new GraphExample24();
        System.out.print("\nConnected: ");
        System.out.println(y.connected(graph));
        
        if (y.connected(graph)) {
            System.out.print("Articulation vertices:   ");
            System.out.println(y.cutVertices(graph));
        }

        if (y.connected(graph)) {
            System.out.print("MST:   ");
            System.out.println(y.MSTPrim(graph));
        }


        System.out.println("\nCliquegraph: ");
        graph = GraphMaker.createGraph(vertices, 0);
        GraphMaker.addCliques(graph, false, new int[] {3, 4}, seed);
        System.out.println(graph.toString());
        System.out.println(GraphMaker.toMatrixString(graph));
        System.out.println("GreedyColor: " + y.greedyColor(graph));
        System.out.println(graph.toString());


        System.out.println("\nbipartite: ");
        graph = GraphMaker.createBiPartie(vertices, vertices, edges, seed);
        System.out.println(graph.toString());
        System.out.println("GreedyColor: " + y.greedyColor(graph));
        System.out.println(graph.toString());
        // System.out.println("bipartite: " + y.isBiPartie(graph));
        // System.out.println(graph.toString());
    }

    boolean connected(Graph g) {
        // all to white
        color(g, Graph.WHITE);

        // depth first search from some vertex
        Vertex w = g.firstVertex(); // or g.vertices().getFirst();
        dfsColor(w, Graph.BLACK);

        // if some vertices were unreached -> not connected
        for (Vertex v : g.vertices())
            if (v.getColor() == Graph.WHITE)
                return false;
        return true;
    }

    int greedyColor(Graph G) {
        int n = 0;	// number of vertices

        // count vertices, & colour with 0
        for (Vertex v : G.vertices()) {
            v.setColor(0);
            n++;
        }

        int i = 0; // number of already coloured vertices
        int c = 0; // current colour

        while (i < n) {
            c++; // new colour

            for (Vertex v : G.vertices()) {
                if (v.getColor() == 0) {
                    boolean okColor = true;
                    for (Vertex w : v.neighbors()) {
                        if (w.getColor() == c) {
                            okColor = false;
                            break;
                        }
                    }

                    if (okColor) {
                        v.setColor(c);
                        i++;
                    }
                } // if (v.getColor)
            }	// for
        } // while

        return c;

    } // greedyColor()



    // depth first search using colour col
    void dfsColor(Vertex v, int col) {
        v.setColor(col);

        for (Vertex w : v.neighbors())
            if (w.getColor() != col)
                dfsColor(w, col);
    }

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




    // Finds minimum spanning tree of g
    // returns list of tree edges 
    // assumes connected graph
    LinkedList<Edge> MSTPrim(Graph g) {

        color(g, Graph.WHITE);
        LinkedList<Edge> mst = new LinkedList<Edge>();

        AssignablePriorityQueue<Edge> Q =
            new AssignablePriorityQueue<Edge>();

        int n = g.size();
        if (n == 0)
            return mst;

        Vertex v = g.firstVertex();
        v.setColor(Graph.BLACK);
        // edges to priority queue
        for (Edge e : v.edges())
            Q.add(e, e.getWeight());
 
        int i = 1;

        while (i < n) {
            if (Q.size() == 0)
                throw new RuntimeException("MSTPrim: Not connected graph");
            Edge e = Q.poll();

            Vertex v1 = e.getStartPoint();
            Vertex v2 = e.getEndPoint();

            if (v1.getColor() != Graph.BLACK ||
                v2.getColor() != Graph.BLACK) {
                if (v2.getColor() == Graph.BLACK)
                    v2 = v1; // v2 will be the white one

                mst.add(e);
                e.setColor(Graph.BLACK);
                v2.setColor(Graph.BLACK);
                i++;
                for (Edge e2 : v2.edges())
                    if (e2.getEndPoint(v2).getColor() == Graph.WHITE)
                        Q.add(e2, e2.getWeight());
            } // if
        } // while

        return mst;
    } // MSTPrim()



    // articulation points (vertices) from connected undirected graph
    LinkedList<Vertex> cutVertices(Graph g) {
        
        Vertex[] vA = GraphMaker.getVertexArrayIndex(g);
        int n = g.size();

        color(g, Graph.WHITE);
        for (Edge e : g.edges())
            e.setColor(Graph.WHITE);

        int[] dfsnumber = new int[n];
        int[] low = new int[n];
        int i = 0;
        LinkedList<Vertex> L = new LinkedList<Vertex>();
        for (Vertex v : g.vertices())
            if (v.getColor() == Graph.WHITE)
                i = numberdfs(v, dfsnumber, low, i, L, null);

        return L;
    }

    // dfs-numbering to an array
    // classify edges: tree edges black, back edges gray
    int numberdfs(Vertex v, int[] dfsnumber, int[] low, int i,
                  LinkedList<Vertex> L, Vertex parent) {

        // pre-order numbering
        v.setColor(Graph.BLACK);
        dfsnumber[v.getIndex()] = i++;

        // dfs recursion and classification of edges
        for (Edge e : v.edges()) {

            // edge already processed in other direction
            // (parent-edge, or back edge of a descendant)
            if (e.getColor() != Graph.WHITE)
                continue;

            Vertex w = e.getEndPoint(v);

            if (w.getColor() == Graph.WHITE) {
                e.setColor(Graph.BLACK);    // tree edge
                i = numberdfs(w, dfsnumber, low, i, L, v);
            } else if (w.getColor() == Graph.BLACK)
                e.setColor(Graph.GRAY); // back edge
        }

        // calculation low number (post-order)
        int min = dfsnumber[v.getIndex()];
        for (Edge e : v.edges()) {
            Vertex w = e.getEndPoint(v);
            if (w == parent)   // ignore parent
                continue;

            // children low numbers
            if (e.getColor() == Graph.BLACK) {
                int childLow = low[w.getIndex()];
                if (childLow < min)
                    min = childLow;

            // dfsnumbers of predecessors with back edge 
            } else if (e.getColor() == Graph.GRAY) {
                int predecessorDfsn = dfsnumber[w.getIndex()];
                if (predecessorDfsn < min)
                    min = predecessorDfsn;
            } // no whites at all

        }
        low[v.getIndex()] = min;

        // recognizing cut vertices
        if (v.getIndex() == 0) { // root vertex
            int childnumber = 0;
            for (Edge e : v.edges())
                if (e.getColor() == Graph.BLACK)
                    childnumber++;
            if (childnumber > 1)
                L.add(v);

        // other vertices
        } else {
            for (Edge e : v.edges())
                if (e.getColor() == Graph.BLACK) {
                    Vertex w = e.getEndPoint(v);
                    if (low[w.getIndex()] >= dfsnumber[v.getIndex()]) {
                        L.add(v);
                        break;
                    }
                } // if BLACK
        } // else
        return i;
    }

}