public class Clique {
    
    private int[] V;  // set of nodes
    private boolean[][] E; // edges as adjacence matrix

    public Clique(int[] V, boolean[][] E) {
	// initialize members
	this.V = V;
	this.E = E;  
    }
    
    /**
     * returns for a given set of nodes V and an 
     * adjacence matrix E if the graph contains
     * a k-clique?
     */ 
    public boolean kClique(int k) {
	int[] s = firstKSubSet(k, V);
	while (s != null) {
	    int c = 0;
	    for (int i = 0; i < k - 1; ++i) {
		for (int j = i; j <= k-1; ++j) {
		    if (E[V[s[i]]-1][V[s[j]]-1]) {
			++c;
		    }
		}
		if (c == (((k*(k-1))/2)))
		    return true;

	    }
	    s = nextKSubSet(s, k, V);
        }
	return false;
    }

    /**
     * move to the next subset of vertices of the set of vertices in S 
     * @param s - the old set of vertices
     * @param k - the size of the clique
     * @param S - the set of available vertices
     * @return the next subset of vertices 
     */
    private int[] nextKSubSet(int[] s, int k, int[] S) {
	int n = S.length - 1;
        int i = 0;
        while (i < k && (s[k-i-1] == (n-i))) {
            if (i == k-1)
                return null;
            ++i;
        }
        s[k-i-1] = s[k-i-1]+1;
        for (int j = k - i + 1; j <= k-1; ++j) {
            s[j-1] = s[j-2] + 1;
        }
        return s;
    }

    /**
     * select an initial set of vertices from S
     * @param k - the number of vertices to choose
     * @param S - the current set of vertices
     * @return the initial set of vertices
     */
    private int[] firstKSubSet(int k, int[] S) {
	if (k > S.length)
            return null;
        int[] s = new int[k];
        for (int i=0; i <= k-1; ++i) {
            s[i] = i;
        }
        return s;

    }


    private static void usage() {
	System.err.println("usage: java Clique <int>");
    }

    public static void main(String[] args) {

	if (args.length != 1) {
	    usage();
	    System.exit(-1);
	}
	    
	int[] V1 = { 1, 2, 3, 4, };
	int[] V2 = { 1, 2, 3, 4, 5, 6};

        boolean[][] E1 = {{ false, true, true, true },
                          { true, false, true, true },
                          { true, true, false, true },
                          { true, true, true, false } };

        boolean[][] E2 = {{ false, true, false, false, true, true },
                          { true, false, false, false, true, true },
                          { false, false, false, false, false, false },
                          { false, false, false, false, false, false },
                          { true, true, false, false, false, true },
                          { true, true, false, false, true, false }};

	
	Clique q1 = new Clique(V1, E1);
	Clique q2 = new Clique(V2, E2);

	try {
		int k = Integer.parseInt(args[0]);
		System.out.println("is " +k +"-Clique: " +q1.kClique(k));
		System.out.println("is " +k +"-Clique: " +q2.kClique(k));
	} catch (NumberFormatException e) {
		usage();
		System.exit(-2);
	}

   } 
    
}