cliques.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 <stdlib.h>
#include "assoc.h"
#include "cliques.h"

Array<Array<Array<int> *> *> *Cliques::theCliqs = NULL;

void Cliques::get_cliq(int *cliq, int cliqsz){
   int i,j;
   qsort(&cliq[1], cliqsz, sizeof(int), cmpint);
   Array<int> *cls = new Array<int>(cliqsz);
   for (i=1; i <= cliqsz; i++) cls->add(cliq[i]);
   //cout << "MAIN CLIQ " << *cls << endl;

   for (i=1; i <= cliqsz-1; i++){
      cls->reset();
      for (j=i+1; j <= cliqsz; j++){
         cls->add(cliq[j]);
      }
      //cout << "\t" << cliq[i] << " "<<*cls << endl;
      add_uniq(cliq[i], cls);
   }
   delete cls;
}

void Cliques::add_uniq(int it, Array<int> *cls)
{
   char found = false;
   if ((*theCliqs)[it] == NULL) 
      (*theCliqs)[it] = new Array<Array<int> *>;
   else{
      for (int i=0; i < (*theCliqs)[it]->size(); i++)
         if (cls->compare((*(*theCliqs)[it])[i]) == 0){
            found = true;
            break;
         }
   }
   if (!found){
      Array<int> *ncls = new Array<int>(cls->size());
      ncls->copy(cls);
      (*theCliqs)[it]->add(ncls);
   }
}

int Cliques::cmpsize(const void *c1, const void *c2)
{
   Array<int> *a1 = *(Array<int> **)c1;
   Array<int> *a2 = *(Array<int> **)c2;

   
   if (a1->size() < a2->size()) return 1;
   else if (a1->size() > a2->size()) return -1;

   for(int i=0; i < a1->size(); i++){
      if ((*a1)[i] > (*a2)[i]) return -1;
      else if ((*a1)[i] < (*a2)[i]) return 1;
   }
   return 0;
}

void Cliques::collapse()
{
   int i,j,k;
   Array<int> *bvec = new Array<int>;
   for (i = 0; i < theCliqs->size(); i++){
      if ((*theCliqs)[i] != NULL && (*theCliqs)[i]->size() > 1){
         qsort((*theCliqs)[i]->array(),(*theCliqs)[i]->size(), 
               sizeof(Array<int> *), cmpsize);
         //cout << i << ": ";
         //cout << *(*theCliqs)[i] << endl << flush;
         if ((*theCliqs)[i]->size() > bvec->totsize())
            bvec->Realloc((*theCliqs)[i]->size());
         for (j=0; j < (*theCliqs)[i]->size(); j++) (*bvec)[j] = 1;
         for (j=1; j < (*theCliqs)[i]->size(); j++){
            //cout << "CUR " << *(*(*theCliqs)[i])[j] << endl;
            for (k=0; k < j; k++){
               int res = (*(*theCliqs)[i])[j]->subset((*(*theCliqs)[i])[k]);
               //cout << " " << *(*(*theCliqs)[i])[k] << " -- " << res << endl;
               if (res == 1){
                  (*bvec)[j] = 0;
                  break;
               }
            }
         }
         for (j=1; j < (*theCliqs)[i]->size(); j++){
            if ((*bvec)[j] == 0){
               delete (*(*theCliqs)[i])[j];
               (*(*theCliqs)[i])[j] = NULL;
            }
         }
         //cout << i << ": ";
         //cout << *(*theCliqs)[i] << endl << flush;
      }
   }
   delete bvec;
   //print();   
}

void Cliques::print()
{
   for (int i = 0; i < theCliqs->size(); i++){
      if ((*theCliqs)[i] != NULL){
         cout << i << ": ";
         cout << *(*theCliqs)[i] << endl;
      }
   }
}

@