main.cpp

拿C编写的boolmfilter算法测试程序

/*
 *	main.cpp
 */
#include <iostream.h>
#include "stdlib.h"
#include "stdio.h"
#include "math.h"

#define ZERO39 "\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0" 

typedef struct  {
	int Node;
	int parentNode;
	char mask1[40];
	char mask2[40];
	int flag;
} CONNECTION;


char nameTbl[41][20] ={
	{"node0"},
	{"node1"},
	{"node2"},
	{"node3"},
	{"node4"},
	{"node5"},
	{"node6"},
	{"node7"},
	{"node8"},
	{"node9"},
	{"node10"},
	{"node11"},
	{"node12"},
	{"node13"},
	{"node14"},
	{"node15"},
	{"node16"},
	{"Dr. Lucy"},
	{"Kevin"},
	{"Cowling"},
	{"Attila"},
	{"Andrea"},
	{"Keshav"},
	{"Mr. Brain"},
	{"Davies"},
	{"Margaret"},
	{"Rae"},
	{"Prof. Excell"},
	{"Veena"},
	{"Harrison"},
	{"Hedges"},
	{"Mr. Karim"},
	{"Harel"},
	{"Gonde"},
	{"Morris"},
	{"Mark"},
	{"Goodliff"},
	{"Godfrey"},
	{"Castro"},
	{"Forbes"},
	{"Dr. Fretwell"}
};

CONNECTION connections[40]={
	{1,0,ZERO39,ZERO39,0},
	{2,1,ZERO39,ZERO39,0},
	{3,2,ZERO39,ZERO39,0},
	{4,3,ZERO39,ZERO39,0},
	{5,4,ZERO39,ZERO39,0},
	{6,5,ZERO39,ZERO39,0},
	{7,6,ZERO39,ZERO39,0},
	{8,7,ZERO39,ZERO39,0},
	{9,1,ZERO39,ZERO39,0},
	{10,9,ZERO39,ZERO39,0},
	{11,10,ZERO39,ZERO39,0},
	{12,11,ZERO39,ZERO39,0},
	{13,12,ZERO39,ZERO39,0},
	{14,13,ZERO39,ZERO39,0},
	{15,14,ZERO39,ZERO39,0},
	{16,15,ZERO39,ZERO39,0},
	{17,2,ZERO39,ZERO39,1},
	{18,2,ZERO39,ZERO39,1},
	{19,3,ZERO39,ZERO39,1},
	{20,3,ZERO39,ZERO39,1},
	{21,4,ZERO39,ZERO39,1},
	{22,4,ZERO39,ZERO39,1},
	{23,6,ZERO39,ZERO39,1},
	{24,6,ZERO39,ZERO39,1},
	{25,7,ZERO39,ZERO39,1},
	{26,7,ZERO39,ZERO39,1},
	{27,8,ZERO39,ZERO39,1},
	{28,8,ZERO39,ZERO39,1},
	{29,10,ZERO39,ZERO39,1},
	{30,10,ZERO39,ZERO39,1},
	{31,11,ZERO39,ZERO39,1},
	{32,11,ZERO39,ZERO39,1},
	{33,12,ZERO39,ZERO39,1},
	{34,12,ZERO39,ZERO39,1},
	{35,14,ZERO39,ZERO39,1},
	{36,14,ZERO39,ZERO39,1},
	{37,15,ZERO39,ZERO39,1},
	{38,15,ZERO39,ZERO39,1},
	{39,16,ZERO39,ZERO39,1},
	{40,16,ZERO39,ZERO39,1}
};

int coefficient[16][3]={
	{70,4,1},
	{24,6,9},
	{55,3,4},
	{49,3,5},
	{95,5,9},
	{44,9,3},
	{82,3,5},
	{39,2,1},
	{39,3,3},
	{49,4,6},
	{23,8,3},
	{43,4,9},
	{21,2,8},
	{39,3,8},
	{85,7,7},
	{32,5,9}
};

int hash(char* name,int coeff[3])  //hash function,ASCII码的值乘以一个系数的和莫320(40*8)
{
	int i = 0;
	long value = 0;
	
	while(name[i] != '\0')
	{
		value += name[i]*coeff[i%3];
		i++;
	}
	
	value = (unsigned int)value%320;
	return value;
}

int setMaskBit(char* mask,int num)//设置v向量，向量的大小为320，mask为某结点的v向量，num为0到319之间的数，将向量中的第num位设为1
{
	int maskByte,maskBit;
	char maskChar;

	if(num<0 || num>319)
		return 0;

	maskByte = num/8;
	maskBit = num%8;
	maskChar = 0x01<<(7-maskBit);

	mask[maskByte] |= maskChar;
	
	return 1;
}

int checkMaskBit(char* mask,int num)//检查向量mask 的第num位是否为1
{
	int maskByte,maskBit;
	char maskChar;

	if(num<0 || num>319)
		return 0;

	maskByte = num/8;
	maskBit = num%8;
	maskChar = 0x01<<(7-maskBit);

	if(mask[maskByte]&maskChar)
		return 1;
	else
		return 0;
}

void updataMask(char* mask,char* name)//更新一全向量，哈稀函数的键值为name，选择不同的coefficient可以得到不同的哈 稀函数
{
	int hashValue;

	hashValue = hash(name,coefficient[0]);
	setMaskBit(mask,hashValue);
	hashValue = hash(name,coefficient[1]);
	setMaskBit(mask,hashValue);
	hashValue = hash(name,coefficient[2]);
	setMaskBit(mask,hashValue);
	hashValue = hash(name,coefficient[3]);
	setMaskBit(mask,hashValue);
}

int isOffspring(int ancestor,int offspring)
{
	int retValue = 0;

	if(ancestor == offspring)
	{
		retValue = 1;
		return retValue;
	}

	for(int i = 0; i < 40; i++)
	{
		if(connections[i].parentNode == ancestor)//如果某个结点的父节点为祖先结点，，则检查子结点是否为当前结点的子女
			retValue = retValue || isOffspring(connections[i].Node,offspring);
	}

	return retValue;
}

void generateMask()
{

/*	for(int i = 0; i < 40; i++)
	{
		if(connections[i].parentNode == k)
			generateMask(connections[i].Node);
	}
*/
	for(int i=0; i<40; i++)
	{
		for(int j=0; j<41; j++)
		{
			if(isOffspring(connections[i].Node,j))
				updataMask(connections[i].mask2,nameTbl[j]);
			else
				updataMask(connections[i].mask1,nameTbl[j]);//为什么要有两个mask
		}
	}
//	cout<<k<<endl;
}

int checkMask(char* mask, char* name)//检查经过哈稀映射各位置都为1
{
	int hashValue;
	int retValue = 1;

	hashValue = hash(name,coefficient[0]);
	retValue &= checkMaskBit(mask,hashValue);
	hashValue = hash(name,coefficient[1]);
	retValue &= checkMaskBit(mask,hashValue);
	hashValue = hash(name,coefficient[2]);
	retValue &= checkMaskBit(mask,hashValue);
	hashValue = hash(name,coefficient[3]);
	retValue &= checkMaskBit(mask,hashValue);	
	
	return retValue;
}

void queryPath(int srcNode,int dstNode)
{
	int nextNode;

	cout<<srcNode<<'\t';
	
	if(srcNode == dstNode)
		return;
	
	for(int i=0; i<40; i++)
	{
		if(connections[i].Node == srcNode)
			if(1 == checkMask(connections[i].mask1,nameTbl[dstNode]))
				nextNode = connections[i].parentNode;
		if(connections[i].parentNode == srcNode)
			if(1 == checkMask(connections[i].mask2,nameTbl[dstNode]))
				nextNode = connections[i].Node;
	}
	if(nextNode>-1 && nextNode<40)
		queryPath(nextNode,dstNode);
	else
		cout<<"ERROR !"<<endl;
}

void main()
{
	int currentNode;
	int targetNode;

	generateMask();
/*	for(int i = 0; i < 40; i++)
	{
		printf("mask1 of %d: ",connections[i].Node);

		for(int j=0; j<40; j++)
			printf("%2x",(unsigned char)connections[i].mask1[j]);

		printf("\n");
		printf("mask2 of %d: ",connections[i].Node);

		for(j=0; j<40; j++)
			printf("%2x",(unsigned char)connections[i].mask2[j]);
		printf("\n");
	}
*/
	cout<<"Please input the current node"<<endl;
	cin>>currentNode;
	cout<<"Please input the target node"<<endl;
	cin>>targetNode;
//	currentNode = 2;
//	targetNode = 39;

//	cout<<checkMask(connections[17].mask2,"Veena")<<endl;
	queryPath(currentNode,targetNode);

	cout<<endl;

//	cout<<hash("Morris",coefficient[0])<<endl;
//	cout<<hash("Morris",coefficient[1])<<endl;
//	cout<<hash("Morris",coefficient[2])<<endl;
//	cout<<hash("Morris",coefficient[3])<<endl;
}