Max Clique
A. First Edition
This is the programming assignment 5 of comp6661 and we are requested to find maximum clique which has the biggest size
among all maximal clique. A maximal clique is such a clique that it cannot be enlarged any more.
The input part cost me a half evening before I started watching "starcraft" competition. The max clique part cost me a whole
morning before I began to enjoy my dinner cooked by a visiting friend. Maybe I am becoming slower and slower, more and more
lazy.
Please be noted that original input data makes no need of matrix "B" which is a set of all elements behind an element. But
you will find it is useful in "greedybound". That is why I added a seemingly useless statement A[second].set(first); after
statement A[first].set(second);. If you are a programmer, you surely understand this.
And as usual I tried to show off a bit by using call back functions.
E.Further improvement
F.File listing
1. clique.cpp
file name: clique.cpp
#include <iostream> #include <fstream> //#include <vector> using namespace std; const int MaxNumber=16; class SimpleSet { protected: static int size; unsigned int data; public: SimpleSet() { data=0; } void set(int index) { unsigned int mask=1; data|=(mask<<index); } void reset(int index) { unsigned int mask=1; data^=(mask<<index); } void clear() { data=0; } bool test(int index) const { unsigned int mask=1; return (data&(mask<<index))!=0; } void intersect(const SimpleSet& other) { data&=other.data; } int count() const { int result=0; for (int i=0; i<size; i++) { if (test(i)) { result++; } } return result; } SimpleSet& operator=(const SimpleSet& other) { data=other.data; return *this; } int first() const { int result=-1; for (int i=0; i<size; i++) { if (test(i)) { result= i; break; } } return result; } int last() const { int result=-1; for (int i=size-1; i>=0; i--) { if (test(i)) { result= i; break; } } return result; } int next(int start) const { int result=-1; for (int i=start+1; i<size; i++) { if (test(i)) { result= i; break; } } return result; } SimpleSet operator&&(const SimpleSet& other) { SimpleSet result=*this; result.intersect(other); return result; } void display() { cout<<"["; for (int i=0; i<size; i++) { if (test(i)) { if (i<10) { cout<<i<<" "; } else { cout<<(char)('a'+(i-10))<<" "; } } } cout<<"]\n"; } }; int SimpleSet::size=MaxNumber; char nameList[MaxNumber]; SimpleSet A[MaxNumber]; SimpleSet B[MaxNumber]; //SimpleSet C; SimpleSet result; SimpleSet current; int currentMax=0; int nodeCount; int currentBound; int color[MaxNumber]; int colorSize; int greedyColor(const SimpleSet A[], const SimpleSet& vertex, int color[]) { int h, k=0, index=-1, i=0; SimpleSet colorClass[MaxNumber]; SimpleSet temp; while ((index=vertex.next(index))!=-1) { h=0; while (h<k&&((colorClass[h]&&A[index]&&vertex).count()!=0)) { h++; } if (h==k) { k++; colorClass[h].clear(); } colorClass[h].set(index); color[index]=h; } return k; } void display() { int i, j, count=0; cout<<"the name list is:\n"; for (i=0; i<MaxNumber; i++) { cout<<nameList[i]<<","; } cout<<"\n"; cout<<"the adjacent list is:\n"; for (i=0; i<MaxNumber; i++) { for (j=0; j<MaxNumber; j++) { if (A[i].test(j)) { cout<<"("<<nameList[i]<<","<<nameList[j]<<"),"; count++; if (count%10==0) { cout<<"\n"; } } } } } int element2Index(char ch) { if (ch<='9'&&ch>='0') { return ch-'0'; } else { if (ch>='a'&&ch<='z') { return ch-'a'+10; } else { return -1; } } } void readFromFile(char* fileName) { char buf[256]; char* ptr; ifstream in(fileName); while (!in.eof()) { in.getline(buf, 256); //first call to initialize ptr= strtok(buf, ","); //to get edge one by one while (ptr!=NULL) { int first=-1, second=-1, i=0; while (*(ptr+i)!='\0') { if (*(ptr+i)!=' ') { if (first==-1) { first=element2Index(*(ptr+i)); } else { second=element2Index(*(ptr+i)); } } i++; } if (first==-1||second==-1) { cout<<"error in reading edge\n"; exit(1); } //get the edge A[first].set(second); A[second].set(first); ptr=strtok(NULL, ","); } } } void initialize(char* fileName) { SimpleSet full; for (int i=0; i<MaxNumber; i++) { full.set(i); if (i<10) { nameList[i]='0'+i; } else { nameList[i]='a'+i-10; } for (int j=i+1; j<MaxNumber; j++) { B[i].set(j); } } readFromFile(fileName); colorSize=greedyColor(A, full, color); } int samplingBound(int size, const SimpleSet& choice) { int index=-1, i, result=0; int counter[MaxNumber]; for (i=0; i<MaxNumber; i++) { counter[i]=0; } //to count the number of color used in C while ((index=choice.next(index))!=-1) { //flag the color used in C counter[color[index]]=1; } //count color used for (i=0; i<MaxNumber; i++) { result+=counter[i]; } return size+result; } int greedyBound(int size, const SimpleSet& choice) { int result; int local[MaxNumber]; result=greedyColor(A, choice, local); return result+size; } int sizeBound(int size, const SimpleSet& choice) { return size+choice.count(); } int noBound(int size, const SimpleSet& choice) { return MaxNumber; } //pass choice as value!!!! void doMaxClique(int size, SimpleSet choice, int (*boundFunc)(int, const SimpleSet&)) { //static int currentElem; nodeCount++; int last; if (size>currentMax) { currentMax=size; result=current; } if (size==0) { for (int i=0; i<MaxNumber; i++) { choice.set(i); } } else { last=current.last(); choice.intersect(A[last]); choice.intersect(B[last]); } currentBound=boundFunc(size, choice); if (boundFunc==greedyBound&&size==1&&last==8) { cout<<"the answer for question 1 is:"<<currentBound<<endl; } if (currentBound<=currentMax) { return; } else { int index=-1; while ((index=choice.next(index))!=-1) { current.set(index); doMaxClique(size+1, choice, boundFunc); current.reset(index); } } } void maxClique(int (*boundFunc)(int, const SimpleSet&)) { SimpleSet choice; currentMax=0; nodeCount=0; doMaxClique(0, choice, boundFunc); } int main( ) { initialize("data1.txt"); display(); cout<<"using no bound:\n"; maxClique(noBound); cout<<"nodeCount="<<nodeCount<<"\n"; result.display(); cout<<"using size bound:\n"; maxClique(sizeBound); cout<<"nodeCount="<<nodeCount<<"\n"; result.display(); cout<<"using sample bound:\n"; maxClique(samplingBound); cout<<"nodeCount="<<nodeCount<<"\n"; result.display(); cout<<"using greedy bound:\n"; maxClique(greedyBound); cout<<"nodeCount="<<nodeCount<<"\n"; result.display(); return 0; }
The input data file is named "data1.txt":
0 1, 0 2, 0 7, 0 8, 0 9, 0 a, 0 e, 1 4, 1 7, 1 8, 1 9, 1 a, 1 b, 1 c, 1 e, 2 3, 2 5, 2 6, 2 7, 2 8, 2 a, 2 b, 3 4, 3 5, 3 6, 3 a, 3 f, 4 5, 4 6, 4 8, 4 9, 4 a, 4 e, 5 6, 5 8, 5 9, 5 b, 5 d, 5 e, 5 f, 6 f, 7 8, 7 a, 7 c, 7 e, 7 f, 8 b, 8 c, 8 e, 8 f, 9 d, 9 e, a c, a d, a e, b c, b e, b f, c d, e f
another input data file is named "data2.txt":
(I place it here because it takes quite some time to make it by hand.)
0 2, 0 3, 0 4, 0 5, 0 6, 0 7, 0 8, 0 9, 0 a, 0 c, 0 d, 0 e, 1 5, 1 6, 1 7, 1 8, 1 9, 1 a, 1 b, 1 c, 1 d, 1 e, 1 f, 2 5, 2 6, 2 7, 2 8, 2 a, 2 b, 2 e, 2 f, 3 4, 3 5, 3 6, 3 7, 3 8, 3 a, 3 c, 3 d, 3 e, 3 f, 4 6, 4 8, 4 9, 4 b, 4 c, 4 e, 4 f, 5 6, 5 7, 5 9, 5 a, 5 b, 5 c, 5 e, 5 f, 6 7, 6 8, 6 9, 6 a, 6 b, 6 d, 6 e, 6 f, 7 8, 7 9, 7 b, 7 c, 7 d, 7 e, 7 f, 8 9, 8 a, 8 b, 8 f, 9 b, 9 c, 9 d, 9 f, a c, a d, a e, a f, b c, b d, b e, b f, c d, c e, d f
A snapshot of running automated testing:
the name list is: 0,1,2,3,4,5,6,7,8,9,a,b,c,d,e,f, the adjacent list is: (0,1),(0,2),(0,7),(0,8),(0,9),(0,a),(0,e),(1,0),(1,4),(1,7), (1,8),(1,9),(1,a),(1,b),(1,c),(1,e),(2,0),(2,3),(2,5),(2,6), (2,7),(2,8),(2,a),(2,b),(3,2),(3,4),(3,5),(3,6),(3,a),(3,f), (4,1),(4,3),(4,5),(4,6),(4,8),(4,9),(4,a),(4,e),(5,2),(5,3), (5,4),(5,6),(5,8),(5,9),(5,b),(5,d),(5,e),(5,f),(6,2),(6,3), (6,4),(6,5),(6,f),(7,0),(7,1),(7,2),(7,8),(7,a),(7,c),(7,e), (7,f),(8,0),(8,1),(8,2),(8,4),(8,5),(8,7),(8,b),(8,c),(8,e), (8,f),(9,0),(9,1),(9,4),(9,5),(9,d),(9,e),(a,0),(a,1),(a,2), (a,3),(a,4),(a,7),(a,c),(a,d),(a,e),(b,1),(b,2),(b,5),(b,8), (b,c),(b,e),(b,f),(c,1),(c,7),(c,8),(c,a),(c,b),(c,d),(d,5), (d,9),(d,a),(d,c),(e,0),(e,1),(e,4),(e,5),(e,7),(e,8),(e,9), (e,a),(e,b),(e,f),(f,3),(f,5),(f,6),(f,7),(f,8),(f,b),(f,e), using no bound: nodeCount=184 [0 1 7 8 e ] using size bound: nodeCount=83 [0 1 7 8 e ] using sample bound: nodeCount=41 [0 1 7 8 e ] using greedy bound: the answer for question 1 is:4 nodeCount=33 [0 1 7 8 e ] Press any key to continue