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