gbk.cc,v

charm是基于垂直数据集挖掘关联规则的一个著名算法

head	1.1;
access;
symbols;
locks
	zaki:1.1; strict;
comment	@// @;


1.1
date	2001.06.12.16.41.58;	author zaki;	state Exp;
branches;
next	;


desc
@Charm with Hashing.
@


1.1
log
@Initial revision
@
text
@#include <iostream.h>
#include <limits.h>

#include "gbk.h"

int GBK_threshold=2;
int GBKCliq::maxcliqpos = 0;
int *GBKCliq::maxcliq = NULL;

GBKCliq::GBKCliq(CLIQFUNC cf)
{
   int *ALL = new int[F2Graph->size()+1];
   maxcliq = new int[F2Graph->size()+1];
   
   for (int c=1; c <= F2Graph->size(); c++) ALL[c]=c-1;
   maxcliqpos=0;
   extend(ALL, 0, F2Graph->size(), cf);
   
   delete [] ALL;
   delete [] maxcliq;
}

void GBKCliq::extend(int *old, int ne, int ce, CLIQFUNC cf)
{
   int nod, fixp;
   int newne, newce, i, j, count, pos, p, s, sel, minnod;
   int *newary = new int [ce+1];

   if (sort_ascend) minnod = -1;
   else minnod = INT_MAX;
   i=0;
   nod=0;
   boolean nodflg;
   if (sort_ascend) nodflg = (minnod < GBK_threshold);
   else nodflg = (minnod > GBK_threshold);

   for (i=i+1; i <= ce && nodflg; i++){
      p = old[i];
      count =0;
      j=ne;
      for (j=j+1; j <= ce &&
              ((sort_ascend && count > minnod) ||
               (!sort_ascend && count < minnod)); j++){
         if (!connected(p, old[j]))
         {
            count++;
            pos=j;
         }
      }
      if ((sort_ascend && count > minnod) ||
          (!sort_ascend && count < minnod)){
         fixp = p;
         minnod = count;
         if (i <= ne) s = pos;
         else{
            s=i;
            nod=1;
         }
      }
      if (sort_ascend) nodflg = (minnod < GBK_threshold);
      else nodflg = (minnod > GBK_threshold);
   }

   for(nod=minnod+nod; nod >= 1; nod--){
      p = old[s];
      old[s] = old[ne+1];
      sel = old[ne+1] = p;
      
      newne = i = 0;
      for (i=i+1; i <= ne; i++){
         if (connected(sel, old[i])){
            newne++;
            newary[newne] = old[i];
         }
      }
      newce = newne;
      i = ne+1;
      for (i=i+1; i <= ce; i++){
         if (connected(sel, old[i])){
            newce++;
            newary[newce] = old[i];
         }
      }
      
      maxcliqpos++;
      maxcliq[maxcliqpos] = sel;
      if (newce == 0){
         if (maxcliqpos > 1){
            //cout << "CLIQ ";
            //for (i=1; i <= maxcliqpos; i++)
            //   cout << (*F2Graph)[maxcliq[i]]->item() << " ";
            //cout << endl;
            if (cf) cf(maxcliq, maxcliqpos);
         }
      }
      else if (newne < newce){
         extend(newary, newne, newce, cf);
      }
      maxcliqpos--;
      ne++;
      if (nod > 1){
         s = ne;
         look : s++;
         if (connected(fixp, old[s])) goto look;
      }
   }
   
   delete newary;
}

@