closedtree.cpp

数据挖掘中的序列模式挖掘算法clospan的C++实现

	parent->max=false;
#else
	if (parent->Support == treeNode->Support) {
		parent->closed = false;
	}
#endif
	/*
	if ((treeNode->Item==1868)) {
		for (it=treeNode->Children->begin(), endit=treeNode->Children->end(); it != endit; it++) {
			printf("%d\n", (*it)->Item);
		}	
	}

	for (it=treeNode->Children->begin(), endit=treeNode->Children->end(); it != endit;) {
		if ((*it)->Parent != treeNode) {
			it=treeNode->Children->erase(it);
			endit=treeNode->Children->end();
		}
		else {
			it++;
		}
	}*/

	for (it=treeNode->Children->begin(), endit=treeNode->Children->end(); it != endit; it++) {
		if ((*it)->Parent == treeNode)
			closed_maxPruning((*it), treeNode);
	}
	//check  subpattern closed

	for (it=treeNode->Children->begin(), endit=treeNode->Children->end(); it != endit; it++) {
		if (!((*it)->ItemIsIntra && myItemIsIntra))
				pNode=parent->FindChild((*it)->Item, false);
		else
			pNode=parent->FindChild((*it)->Item, true);	

		closed_maxChecking (pNode, parent, (*it));
	}
	
}

inline bool ItemSet::IsSubsetOf( ItemSet * anItemSet )
{
	int j;
	int OtherCount=anItemSet->Count;

	if( Count> OtherCount )
		return false;

	j = 0;
	for( int i=0; i<Count; i++ )
	{
		while( ItemArray[i] != anItemSet->ItemArray[j] )
		{
			j++;
			if( (OtherCount-j) < (Count-i) ) 
				return false;
		}
	}

	return true;
}

LevelNode::LevelNode()
{
	reverseTable= NULL;
}

inline bool LevelNode::isEmpty()
{
	if ((reverseTable == NULL) || (*reverseTable).size() ==0 ) 
		return true;
	else
		return false;
}

inline void LevelNode::addCandidate(TreeNode *treeNode)
{
	NodeVector::iterator it, endit;
	if (reverseTable == NULL)
		reverseTable= new ReverseNodeHashTable;
	for(it=treeNode->Children->begin(), endit=treeNode->Children->end(); it != endit; it++) {
		(*reverseTable).insert(ReverseNodeHashTable::value_type((*it)->Item, (*it)));
	}
}

inline ReverseNodeMap LevelNode::findCandidate(int Item)
{
	return ((*reverseTable).equal_range(Item));
}

LevelNode::~LevelNode()
{
	if (reverseTable !=NULL )
		delete reverseTable;
}




TreeNode::TreeNode( int anItem, bool IsIntra, int Sup, TreeNode * aParent )
{

	Children = new NodeVector();

	Parent = aParent;
	ItemsetNumber = 0;
	Items=0;
	Item = anItem;
	ItemIsIntra = IsIntra;
	Support = Sup;
	closed=true;
	max=true;
}

TreeNode::TreeNode( TreeNode *treeNode)
{
	
	Children =treeNode->Children;

	Parent = treeNode->Parent;
	ItemsetNumber = treeNode->ItemsetNumber;
	Items= treeNode->Items;
	Item = treeNode->Item;
	ItemIsIntra = treeNode->ItemIsIntra;
	Support = treeNode->Support;
	closed=true;
	max=true;
}

inline TreeNode * TreeNode::FindChild( int anItem, bool Intra )
{
	TreeNode ** Res;
	TreeNode * tmp = new TreeNode( anItem, Intra );

	Res = (TreeNode **) bsearch( &tmp, &(*Children)[0], (*Children).size(), sizeof( TreeNode *), (int (*)(const void*, const void*))TreeNodeCompare );

	delete tmp;

	if( Res )
		return (*Res);
	else
		return NULL;
}

inline void TreeNode::DelChild( int anItem, bool Intra, NodeVector::iterator it)
{
	TreeNode *theNode=NULL;

	theNode=FindChild(anItem, Intra);
	if (theNode != NULL) {
		(*Children).erase(it);
		delete theNode;
	}
}

inline void TreeNode::DelChild( TreeNode * Child, NodeVector::iterator it)
{

	if( Children == NULL )
		return;
	(*Children).erase(it);
}

TreeNode * TreeNode::AddChild( int anItem, bool Intra, int Sup)
{
	TreeNode *Result = NULL;
	TreeNode *Child  = NULL;

	Result = FindChild( anItem, Intra);
	if( Result == NULL ) {
		Child= new TreeNode(anItem, Intra, Sup);
		Result = Child;
		(*Children).push_back( Child ); 
		// To keep the children vector sorted.
		inplace_merge( (*Children).begin(), (*Children).end()-1, (*Children).end(), TreeNodeLess );
		Child->Parent = this;
		if( Child->ItemIsIntra ) {
			Child->ItemsetNumber = ItemsetNumber;
			Child->Items = Items + 1;
		}
		else {
			Child->ItemsetNumber = ItemsetNumber + 1;
			Child->Items = Items + 1;
		}
	} else {
		if( Result->Support < Sup ) {
			printf("Item: %d %d %d\n", anItem, Result->Support, Sup);
			printf("ParentItem: %d %d\n", Item, Support);
			Result->Support = Sup;
		}
	}
	return Result;
}

inline TreeNode *TreeNode::AddChildWithoutChecking(int anItem, bool Intra, int Sup)
{
	TreeNode *Child;

	Child= new TreeNode(anItem, Intra, Sup);

	(*Children).push_back( Child ); 
	// To keep the children vector sorted.
	inplace_merge( (*Children).begin(), (*Children).end()-1, (*Children).end(), TreeNodeLess );
	Child->Parent = this;
	if( Child->ItemIsIntra ) {
		Child->ItemsetNumber = ItemsetNumber;
		Child->Items = Items + 1;
	}
	else {
		Child->ItemsetNumber = ItemsetNumber + 1;
		Child->Items = Items + 1;
	}
	return Child;
}

TreeNode * TreeNode::AddChild( TreeNode * Child ) 
{ 
	TreeNode * Result = NULL;

	
	Result = FindChild( Child->Item, Child->ItemIsIntra);
	if( Result == NULL ) {
		Result = Child;
		(*Children).push_back( Child ); 
		// To keep the children vector sorted.
		//inplace_merge( (*Children).begin(), (*Children).end()-1, (*Children).end(), TreeNodeLess );
		Child->Parent = this;
		if( Child->ItemIsIntra ) {
			Child->ItemsetNumber = ItemsetNumber;
			Child->Items = Items + 1;
		}
		else {
			Child->ItemsetNumber = ItemsetNumber + 1;
			Child->Items = Items + 1;
		}
	} else {
		if( Child->Support > Result->Support )
				Result->Support = Child->Support;
		delete Child;

	}
	return Result;
}

inline void TreeNode::SetProjDBSize(long size)
{
	NumOfItems = size;
}

bool TreeNode::isRoot()
{
	if (Parent == NULL )
		return true;
	else
		return false;
}
inline int TreeNode::NumOfChildren()
{
	if( Children==NULL )
		return 0;
	else
		return (*Children).size();
}

inline int TreeNode::MaxChildSupport()
{
	int maxChildSup = 0;
	NodeVector::iterator it;

	if( Children==NULL )
		return 0;

	for( it = (*Children).begin(); it != (*Children).end(); it++ )
		if( ((*it))->Support > maxChildSup )
			maxChildSup = (*it)->Support;

	return maxChildSup;
}

bool TreeNode::LastItemOfSequence()
{
	if( Children==NULL )
		return true;

	if( MaxChildSupport() < Support )
		return true;

	return false;
}


void TreeNode::Print(char *PrefixString, FILE * aFile)
{
	NodeVector::iterator it;
	char NewPrefixString[256];

	if(ItemIsIntra) {
		sprintf(NewPrefixString, "%s %d", PrefixString, Item);
	}
	else {
		sprintf(NewPrefixString, "%s)(%d", PrefixString, Item);
	}

	if( Children != NULL && NumOfChildren() > 0) {
		for( it = (*Children).begin(); it != (*Children).end(); it++ ) {
			if ((*it)->Parent == this)  // if not equal, its subtree must be totally absorbed
				(*it)->Print(NewPrefixString, aFile );
		}
	}

	
	#if defined (_ANOTHER_MAX_APPROACH)
		if (max){
				closed_maxFreq[Items] ++;
	#else 
		if (closed) {
				closed_maxFreq[Items] ++;
				//if (Items == 9 )
					//	fprintf(aFile, "HEHE: ");

	#endif 
			fprintf( aFile, "<%s)>  Num= %d Support = %d   ItemsetNumber = %d\n", NewPrefixString+2, NumOfItems, Support, ItemsetNumber );
			//fprintf( aFile, "<%s)>\n", NewPrefixString+2);
		}

}

TreeNode::~TreeNode()
{
	NodeVector::iterator it;

	if( Children )
		for( it = (*Children).begin(); it != (*Children).end(); it++)
			delete *it;

	delete Children;

}

#endif // !defined( _FIND_MAX_SEQS ) && !defined( _FIND_FREQUENT_SEQS )