package ramsey;

import java.util.*;

/**
 * An undirected graph.
 */
public class Graph implements java.io.Serializable {
    Hashtable vertices;

    static boolean debug=false;

    public Graph() {
        vertices = new Hashtable();
    }

    public Graph(Object[] vertices) {
        this();
        for (int i=0; i<vertices.length; i++)
            addVertex(vertices[i]);
    }

    public void addVertex(Object v) {
        if (vertices.containsKey(v))
            throw new ElementAllreadyExistsException(v,this);
        vertices.put(v,new Hashtable());
    }

    public void connect(Object v1, Object v2) {
        if (!vertices.containsKey(v1))
            throw new ElementNotFoundException(v1,this);
        if (!vertices.containsKey(v2))
            throw new ElementNotFoundException(v2,this);
        if (v1==v2)
            return;
        ((Hashtable)vertices.get(v1)).put(v2,v2);
        ((Hashtable)vertices.get(v2)).put(v1,v1);
    }

    public void dissconnect(Object v1, Object v2) {
        if (!vertices.containsKey(v1))
            throw new ElementNotFoundException(v1,this);
        if (!vertices.containsKey(v2))
            throw new ElementNotFoundException(v2,this);
        if (v1==v2)
            return;
        ((Hashtable)vertices.get(v1)).remove(v2);
        ((Hashtable)vertices.get(v2)).remove(v1);
    }

    public void addVertex(Object v, Object[] list) {
        addVertex(v);
        for (int i=0; i<list.length; i++)
            connect(v,list[i]);
    }

    public void addVertex(Object v, Enumeration neighboors) {
        addVertex(v);
        while(neighboors.hasMoreElements())
            connect(v,neighboors.nextElement());
    }

    public boolean isConnected(Object v1, Object v2) {
        if (!vertices.containsKey(v1))
            throw new ElementNotFoundException(v1,this);
        if (!vertices.containsKey(v2))
            throw new ElementNotFoundException(v2,this);
        Hashtable neighboors = (Hashtable) vertices.get(v1); // the neighboors of v1
        return (neighboors.containsKey(v2));
    }

    /**
     * Returns the list of neighboors of the vertex v in the graph.
     */
    public Enumeration getNeighboors(Object v) {
        if (!vertices.containsKey(v))
            throw new ElementNotFoundException(v,this);
        return ((Hashtable)vertices.get(v)).elements();
    }

    public Object[] getNeighboorsArray(Object v) {
        if (!vertices.containsKey(v))
            throw new ElementNotFoundException(v,this);
        Object[] neighboors = new Object[degree(v)];
        int i=0;
        for (Enumeration e=getNeighboors(v); e.hasMoreElements(); i++)
            neighboors[i]=e.nextElement();
        return neighboors;
    }

    public Object[] getStrangersArray(Object v) {
        if (!vertices.containsKey(v))
            throw new ElementNotFoundException(v,this);
        Object[] strangers = new Object[size()-degree(v)-1];
        int i=0;
        Hashtable neighboors = (Hashtable) vertices.get(v);
        for (Enumeration e=vertices.keys(); e.hasMoreElements();) {
            Object v1 = e.nextElement();
            if (!v.equals(v1) && !neighboors.containsKey(v1))
                strangers[i++]=v1;
        }
        return strangers;
    }

    /**
     * Returns the degree (number of neighboors) of the vertex v in the graph.
     */
    public int degree(Object v) {
        if (!vertices.containsKey(v))
            throw new ElementNotFoundException(v,this);
        return ((Hashtable)vertices.get(v)).size();
    }

    /**
     * Return the size of the graph (number of vertices).
     */
    public int size() {
        return vertices.size();
    }

    /**
     * Returns the list of vertices in the graph.
     */
    public Enumeration getVertices() {
        return vertices.keys();
    }

    /**
     * Returns a newly build complete graph on the given vertices.
     */
    public static Graph createCompleteGraph(Object[] vertices) {
        Graph g = new Graph(vertices);
        for (int i=0; i<vertices.length; i++)
            for (int j=0; j<vertices.length; j++)
                g.connect(vertices[i],vertices[j]);
        return g;
    }

    /**
     * Returns the subgraph of this given graph determined by the given vertex
     * and its neighboors.
     */
    public Graph subGraph(Object v) {
        Object[] subset = new Object[degree(v)+1];
        subset[0]=v;
        int i=1;
        for (Enumeration e=getNeighboors(v); e.hasMoreElements(); i++)
            subset[i]=e.nextElement();
        return subGraph(subset);
    }

    /**
     * Returns the subgraph of this graph determined by the given list of vertices.
     */
    public Graph subGraph(Object[] subset) {
        Graph g=new Graph();
        for (int i=0; i<subset.length; i++) {
            if (!vertices.containsKey(subset[i]))
                throw new ElementNotFoundException(subset[i],this);
            g.addVertex(subset[i]);
        }
        for (int i=0; i<subset.length; i++) {
            Enumeration neighboors = getNeighboors(subset[i]);
            while(neighboors.hasMoreElements()) {
                Object neighboor = neighboors.nextElement();
                if (g.vertices.containsKey(neighboor))
                    g.connect(subset[i],neighboor);
            }
        }
        return g;
    }

    public Graph complementryGraph() {
        Graph g = new Graph();
        for (Enumeration e=vertices.keys(); e.hasMoreElements();)
            g.vertices.put(e.nextElement(),new Hashtable());
        for (Enumeration e=vertices.keys(); e.hasMoreElements();) {
            Object v = e.nextElement();
            Hashtable original = (Hashtable) vertices.get(v);
            Hashtable complement = new Hashtable();
            for (Enumeration e1=vertices.keys(); e1.hasMoreElements();) {
                Object v1 = e1.nextElement();
                if (!v1.equals(v) && !original.containsKey(v1))
                    complement.put(v1,v1);
            }
            g.vertices.put(v,complement);
        }
        return g;
    }

    /**
     * true if this graph has a clique of size n.
     */
    public boolean hasClique(int n) {
        if (debug) System.out.println("try to find "+n+" clique in "+this);
        if (size()<n) {
            if (debug) System.out.println("size<"+n+" no clique");
            return false;
        }
        if (n==1) {
            if (debug) System.out.println(this+((size()>0)? "has" : "has no") + " 1 clique");
            return size()>0;
        }
        // check for a vertex whose neighboors contains an n-1 clique
        for (Enumeration e=vertices.keys(); e.hasMoreElements(); ) {
            Object v = e.nextElement();
            Graph g = subGraph(getNeighboorsArray(v));
            if (g.hasClique(n-1)) {
                if (debug) System.out.println(this+" has "+n+" clique");
                return true;
            }
        }
        if (debug) System.out.println("has no "+n+" clique");
        return false;
    }

    /**
     * true if this graph has anti-clique of size n.
     */
    public boolean hasAntiClique(int n) {
        if (debug) System.out.println("try to find "+n+"-anticlique in "+this);
        if (debug) System.out.println("equals for finding "+n+"-clique in complementry graph");
        return complementryGraph().hasClique(n);
    }

    /**
     * Returns a description of the graph.
     */
    public String toString() {
        String s="(";
        for (Enumeration e=getVertices(); e.hasMoreElements(); ) {
            Object v = e.nextElement();
            s+=v+"(";
            for (Enumeration e1=getNeighboors(v); e1.hasMoreElements();) {
                s+=e1.nextElement();
                if (e1.hasMoreElements())
                    s+=",";
            }
            s+=")";
            if (e.hasMoreElements())
                s+=",";
        }
        s+=")";
        return s;
    }

    public void remove(Object v) {
        if (!vertices.containsKey(v))
            throw new ElementNotFoundException(v,this);
        for (Enumeration e=getNeighboors(v); e.hasMoreElements();)
            dissconnect(v,e.nextElement());
        vertices.remove(v);
    }
}