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