import java.util.*; class CliquerPP extends Cliquer { int shallowestSelection; // the lowest indexed vertex that has been selected CliquerPP (int n,int[][]A,int[] degree,int[] weight,int style) { super(n,A,degree,weight,style); } void search(){ cpuTime = System.currentTimeMillis(); nodes = 0; c = new long[n+1]; // note, 1 extra element such that c[n] = 0 adjacent = new int[n][n]; orderVertices(); for (int i=0;i P = new ArrayList(n); ArrayList C = new ArrayList(n); long pWeight = 0; // weight in candidate set P for (int i=0;i=0;i--) c[i] = Math.max(Math.max(c[i],c[i+1]),weight[i]); expand(C,P,0,pWeight); } ArrayList copy(ArrayList L){ ArrayList copy = new ArrayList(L.size()); for (int i : L) copy.add(i); return copy; } void expand(ArrayList C,ArrayList P,long cWeight,long pWeight){ if (trace) System.out.println("C: "+ C +" P: "+ P + " cWeight: "+ cWeight); if (timeLimit > 0 && System.currentTimeMillis() - cpuTime >= timeLimit) return; nodes++; if (P.isEmpty() && cWeight > maxWeight){ saveSolution(C,cWeight); for (int i=0;i<=shallowestSelection;i++) c[i] = Math.max(maxWeight,c[i]); if (trace){for (int i=0;i newP = copy(P); newP.remove((Integer) v); expand(C,newP,cWeight,pWeight - weight[v]); // reject v newP.clear(); long newPweight = 0; for (int w : P) if (adjacent[v][w] == 1){ newP.add(w); newPweight = newPweight + weight[w]; } ArrayList newC = copy(C); newC.add(v); shallowestSelection = Math.min(shallowestSelection,v); expand(newC,newP,cWeight + weight[v],newPweight); // accept v } }