Bit Matrix

A. First Edition
This is just for fun and I confess I never expect to make anything from this futile search of polynomial algorithm
of clique problem. It is just for fun and help me to realize the difficulty of NP-complete problem.
B.The problem
What is clique? In a graph G(V,E), what is the biggest size of clique which is a sub graph G with each vertex in it incidented with all other vertices in clique. i.e. clique = {G(V,E) ,  k}

Sub = {C(V', E')} with

1) C(V', E') and v in V' => v in V and e in E'  => e in E

2) v1,v2 in V' => (v1,v2) in E'

And for all c in Sub such that |c|<=k

In English, it says that for a graph G, to find out if exists a completed sub-graph of G with size of k.

C.The idea of program
กก

This is a rather straight forward, simple, trivial copy of bitset template. However, it makes a good tool for

future study of relations, graphs, etc.

D.The major functions
กก
E.Further improvement
F.File listing
1. bitmatrix.h
2. main.cpp
กก
file name: bitmatrix.h
#include <bitset>
#include <string.h>

typedef unsigned long ulong;
using namespace std;


template<int size>
class BitMatrix
{
private:
	bitset<size> matrix[size];
	bool degreeArray[size];
	ulong values[size];
	void update(int row);
	bool degree(int row, int deg);
	bool first(int deg);
	bool second(int deg);

public:
	BitMatrix();
	void set(int row, int col, bool val=true);
	void assign(int row, ulong seq);
	BitMatrix<size>* power(int row);
	void showPower(int times);
	void showPower(int row, int times);
	void randomSet();
	bool clique(int deg);
	void swap(int row1, int row2);
	void arrange();

	void display();
};


template<int size>
void BitMatrix<size>::arrange()
{
	int front, back;
	front=back=0;
	while (true)
	{
		//find first false one
		while (degreeArray[back])
		{
			back++;
			if (back>=size)
			{
				return;
			}
		}

		//find first true one
		front=back;
		while (!degreeArray[front])
		{
			front++;
			if (front>=size)
			{
				return;
			}
		}
		swap(front, back);
		printf("swap %d and %d \n", front, back);
		degreeArray[front]=false;
		degreeArray[back]=true;
	}
}

template<int size>
void BitMatrix<size>::swap(int row1, int row2)
{
	bool hold;
	for (int i=0; i<size; i++)
	{
		//exchange row
		hold=matrix[row1][i];
		matrix[row1][i]=matrix[row2][i];
		matrix[row2][i]=hold;
		//exchange col
		hold=matrix[i][row1];
		matrix[i][row1]=matrix[i][row2];
		matrix[i][row2]=hold;
	}
}


template<int size>
bool BitMatrix<size>::first(int deg)
{
	int total=0;
	for (int i=0; i<size; i++)
	{
		if (matrix[i].count()>=deg)
		{
			total++;
			degreeArray[i]=true;
		}
		else
		{
			degreeArray[i]=false;
		}
	}
	return total>=deg;
}

template<int size>
bool BitMatrix<size>::second(int deg)
{
	int total=0;
	int sub;
	for (int i=0; i<size; i++)
	{
		//if it is the possible candidate
		if (degreeArray[i])
		{
			sub=0;
			//begin testify the candidate
			for (int j=0; j<size; j++)
			{
				if (matrix[i][j])
				{
					if (matrix[j].count()>=deg)
					{
						sub++;
					}
				}
			}
			//count the number of qualified candidates
			if (sub>=deg)
			{
				total++;
				//printf("row[%d] is ok\n", i);
			}
			else
			{
				degreeArray[i]=false;
			}
		}
	}
	return total>=deg;
}


template<int size>
bool BitMatrix<size>::clique(int deg)
{
	if (first(deg))
	{
		if (second(deg))
		{
			return true;
		}
	}
	return false;
}

template<int size>
bool BitMatrix<size>::degree(int row, int deg)
{
	int result=0;
	if (matrix[row].count()<deg)
	{
		return false;
	}
	for (int i=0; i<size; i++)
	{
		if (matrix[row][i])
		{
			if (matrix[i].count()>=deg)
			{
				result++;
			}
		}
	}
	return result>=deg-1;
}

		


template<int size>
void BitMatrix<size>::showPower(int row, int times)
{
	BitMatrix<size>* result=this;
	for (int i=0; i<times; i++)
	{
		result=result->power(row);
		printf("show power of row #%d of times %d\n", row, i);
		result->display();

	}
}



template<int size>
void BitMatrix<size>::showPower(int times)
{
	BitMatrix<size>* result;
	if (times==0)
	{
		return;
	}
	for (int i=0; i<size; i++)
	{
		result=power(i);
		
		printf("show power of times:%d, row of %d\n\n", times, i);
		result->display();
		result->showPower(times-1);
	}
}

template<int size>
void BitMatrix<size>::update(int row)
{
	values[row]=matrix[row].to_ulong();
}

//the dynamic memory is not handled yet
template<int size>
BitMatrix<size>* BitMatrix<size>::power(int row)
{
	BitMatrix<size>* result=new BitMatrix<size>;
	
	for (int i=0; i<size; i++)
	{
		result->matrix[i].reset();
		result->matrix[i]|=matrix[row];
		result->matrix[i]&=matrix[i];
		result->update(i);
	}
	return result;
}



template<int size>
void BitMatrix<size>::randomSet()
{
	bool result;
	for (int r=0; r<size; r++)
	{
		for (int c=r; c<size; c++)
		{
			if (r==c)
			{
				result=true;				
			}
			else
			{
				result=rand()%2==0;
			}
			matrix[r].set(size-c-1, result);
			matrix[c].set(size-r-1, result);
		}
		
	}
	for (int i=0; i<size; i++)
	{
		update(i);
	}
}


template<int size>
void BitMatrix<size>::assign(int row, ulong seq)
{
	bitset<size> B(seq);
	matrix[row].reset();
	matrix[row].operator|=(B);
	values[row]=seq;
}



template<int size>
BitMatrix<size>::BitMatrix<size>()
{
	for (int i=0; i<size; i++)
	{
		matrix[i].reset();
	}
}

template<int size>
void BitMatrix<size>::set(int row, int col, bool val)
{
	if (row>=size||col>=size||row<0||col<0)
	{
		printf("out of bound\n");
	}
	else
	{
		matrix[row].set(col, val);
		update(row);
	}
}



template<int size>
void BitMatrix<size>::display()
{
	for (int i=0; i<size; i++)
	{
		printf("%s     (%X)\n", matrix[i].to_string().data(), values[i]);
	}
}

	
file name: main.cpp
#include "bitmatrix.h"
#include <string.h>
#include <stdio.h>
#include <time.h>

const int MatrixSize=8;

unsigned long pos=0x00000003;

int main()
{
	srand(time(0));
	BitMatrix<MatrixSize> M;
	bitset<MatrixSize> B;
	//M.display();
	/*
	for (int r=0; r<MatrixSize; r++)
	{
		for (int c=0; c<MatrixSize; c++)
		{
			M.set(r, c, rand()%2==1);
		}
	}
	*/
	M.randomSet();
	M.display();
	//M.assign(0, pos);
	//printf("now it is \n");
	//M.display();
	//printf("%s\n", B.to_string().data());

	//B<<=pos;
	//printf("%s\n", B.to_string().data());
	//printf("begin to power\n");
	/*
	for (int i=0; i<MatrixSize; i++)
	{
		printf("power of row of %d\n", i);
		M.power(i)->display();
	}
	*/
	//M.showPower(2);
	
	for (int i=1; i<MatrixSize; i++)
	{
		if (M.clique(i))
		{
			printf("matrix has clique of size of %d\n", i);
			M.arrange();
			M.display();
		}
	}
	




	return 0;
}
	
กก




How to run?



11101001 (E9)
11100000 (E0)
11110010 (F2)
00110110 (36)
10001111 (8F)
00011110 (1E)
00111110 (3E)
10001001 (89)
matrix has clique of size of 1
11101001 (E9)
11100000 (E0)
11110010 (F2)
00110110 (36)
10001111 (8F)
00011110 (1E)
00111110 (3E)
10001001 (89)
matrix has clique of size of 2
11101001 (E9)
11100000 (E0)
11110010 (F2)
00110110 (36)
10001111 (8F)
00011110 (1E)
00111110 (3E)
10001001 (89)
matrix has clique of size of 3
11101001 (E9)
11100000 (E0)
11110010 (F2)
00110110 (36)
10001111 (8F)
00011110 (1E)
00111110 (3E)
10001001 (89)
Press any key to continue









                                                               
                      







                       back.gif (341 bytes)       

up.gif (335 bytes)                                       
next.gif (337 bytes)