combinatorial algorithm

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.

    B.The problem

1. (5 marks, from final exam of 2000)
Bounding functions for maximum clique
Consider the maximum clique problem as specified by Ex. 4.9 (p. 147) of your textbook,
which is based on using Algorithm 4.19: MAXCLIQUE2(`) (p. 139) of the
textbook. Assume that your input data is the graph given in part (b) of Ex. 4.9
and consider the particular instance when MAXCLIQUE2 is called with ` = 1 and
[x0] = [8]. Assume also that GREEDYBOUND (Algorithm 4.18, p. 138) is used as
the bounding function.
What value is returned by GREEDYBOUND?
¡¡
C.The idea of program
¡¡

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.

    D.The major functions

    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