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.
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 programThis is a rather straight forward, simple, trivial copy of bitset template. However, it makes a good tool for
future study of relations, graphs, etc.
กก
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