combinatorial algorithm

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

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.

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;
}