Monday 28 November 2011

MPI code urgent

MPI code urgent

I have this code for parallel implement an Apriori algorithm. This code is written in VC++. I want to change it to C code. Could you please please someone help me with this. I tried many times, and I am frustrated.

#include "stdio.h"
#include <fstream>
#include <iostream>
#include "stdlib.h"
#include "string.h"
#include <iomanip>
#include <time.h>
#include "mpi.h"

struct tItem
{
int tag;
char itemset[15];
int count;
struct tItem *next;
};

#define LEN sizeof(struct tItem);

int GetColNum(char fileName1[]); //¶ÁÈ¡Ô´Êý¾ÝµÄÁÐÊý
int GetRecordNum(char fileName2[]); //¶ÁÈ¡Ô´Êý¾ÝµÄÐÐÊý
int Index(char *List, char c, int ListLength);
void GetSourceFile(char fileName[],int recordNum,int colNum); //»ñÈ¡Ô´Êý¾Ý
void FindFrequence1itemsets(char **fullSet1,double sup);
void Gen_association_rules(tItem *kf, tItem *p, double minCon); //Éú³É¹ØÁª¹æÔò
void SetminSup(); //ÉèÖÃ×îСֵ֧³Ö¶È
void SetminCon(); //ÉèÖÃ×îСÖÃÐŶÈ
struct tItem *Find_candidate_1itemsets(char **fullSet2, double sup2,int recordNum,int colNum); //Éú³ÉƵ·±1Ï
struct tItem *apriori_gen(tItem *freq); //Éú³ÉºòÑ¡Ï
struct tItem *Gen_candidate_itemset(tItem *cp,tItem *cp1,tItem *cp2); //Éú³ÉºóÑ¡Ïî
struct tItem *Gen_frequence(tItem *frequence, int recordNum, int colNum, int minNum, char **fullSet); //Éú³ÉƵ·±Ï
struct tItem *Gen_frequence1(tItem *frequence, int recordNum, int colNum, int minNum, char **fullSet);
struct tItem *Compute_candidateItem_Num(tItem *c,int recordNum, int colNum, char **fullSet); //¼ÆËãºòÑ¡ÏÖÐÿһÏîµÄ×îС֧³ÖÊý
struct tItem *Gen_kFrequence_subsets(tItem *f); //Éú³ÉƵ·±kÏÿÏîµÄ×Ó¼¯µÄ¼¯ºÏ
struct tItem *SubSet(char *List, int m, char *Buffer, int flag, tItem *fis, int ListLength); //Éú³ÉƵ·±¼¯ÖÐÿһÏîµÄ×Ó¼¯
struct tItem *AddToSubset(char *Buffer, int flag, tItem *fis); //½«Ò»¸ö×Ó¼¯¼ÓÈëÁ´±í
struct tItem *Combine_candidate_itemsets(tItem *lc, char rItemset, int rCount); //ºÏ²¢¾Ö²¿ºòÑ¡1Ï³ÉΪ×ܵĺòÑ¡1Ï
struct tItem *Combine_candidate_k_itemsets(tItem *lc,tItem *r);
bool Has_infrequence_subset(tItem *pp, tItem *f); //ÅжϺòÑ¡kÏµÄ×Ó¼¯ÊÇ·ñÔÚƵ·±k-1ÏÖÐ
bool Is_before_equal(tItem *pp1, tItem *pp2); //ÅжÏÁ½¸öÏîÄ¿¼¯µÄÇ°k-1ÏîÊÇ·ñÏàͬ
static void masterprocess(int rankNum);
static void slaveprocess(int rankNum);

char **fullSet;
int colNum=0;
int recordNum=0;
double minSup=0.37;
double minCon=0.50;

int main(int argc,char *argv[])
{
int rank,size;

MPI_Init(&argc,&argv);
MPI_Comm_rank(MPI_COMM_WORLD,&rank);
MPI_Comm_size(MPI_COMM_WORLD,&size);

if(rank==0)
{
//printf("#%d#\n",size);
masterprocess(size);
}
else
{
slaveprocess(size);
}

MPI_Finalize();
return(0);
}

void SetminSup()
{
cout<<"Please input the minSup: ";
cin>>minSup;
}

void SetminCon()
{
cout<<"Please input the minCon: ";
cin>>minCon;
}

int GetColNum(char fileName1[]) //¶ÁÈ¡Ô´Êý¾ÝµÄÁÐÊý
{
ifstream file(fileName1);

char ch;
//int colNum=0;
while(ch!='\n')
{
if(ch==',')
{
colNum++;
ch=file.get();
}
ch=file.get();
}
//colNum++;
file.close();
return colNum;
}


int GetRecordNum(char fileName2[]) //¶ÁÈ¡Ô´Êý¾ÝµÄÐÐÊý
{
ifstream file(fileName2);

char ch=NULL;
//int recordNum=0;

while(!file.eof())
{
if(ch=='\n')
{
recordNum++;
ch=file.get();
}
ch=file.get();
}

file.close();
return recordNum;
}

void GetSourceFile(char fileName[],int rNum,int cNum) //»ñÈ¡Ô´Êý¾Ý¶ÁÈëÊý×éfullSet[][]ÖÐ
{
ifstream file(fileName);

char ch;
//char **fullSet;
int item=0;
int i=0,j=0;
int temp1='A';
int temp2='a';

/*b=(int**)malloc(row*sizeof(int*));
for(i=0;i<row;i++)
{
b[i]=(int*)malloc(col*sizeof(int));
}*/

fullSet=(char**)malloc(rNum*sizeof(char*));
for(int m=0;m<rNum;m++)
{
fullSet[m]=(char*)malloc(cNum*sizeof(char));
}

while(i<rNum)
{
while(j<colNum)
{
if(ch==',')
{
item++;
ch=file.get();
if(ch=='T')
{
fullSet[i][j]=(char)(item+temp1);
//printf("%c",fullSet[i][j]);
}
if(ch=='F')
{
fullSet[i][j]=(char)(item+temp2);
//printf("%c",fullSet[i][j]);
}
j++;
}
ch=file.get();
}
//printf("\n");
j=0;
ch=file.get();
item=0;
i++;
}
file.close();
}

static void masterprocess(int rankNum)
{

char inputFileName[]="c:\\shujuku.txt";
char *buffer;
int colNum,recordNum,blockNum,bound,i,j,m,k;
int rank,destRank,tag;
double starttime,endtime;

MPI_Status status;
MPI_Comm_rank(MPI_COMM_WORLD,&rank);
starttime=MPI_Wtime();

//SetminSup();
//SetminCon();

//printf("#%d#\n",rankNum);

colNum=GetColNum(inputFileName);
recordNum=GetRecordNum(inputFileName);

//system("pause");
printf("recordNum= %d", recordNum);
printf("\n");
printf("colNum= %d",colNum);
printf("\n");

GetSourceFile(inputFileName,recordNum,colNum);

//system("pause");

/*for(i=0;i<recordNum;i++)
{
for(j=0;j<colNum;j++)
{
printf(" %c ",fullSet[i][j]);
}
printf("\n");
}*/

blockNum=recordNum/(rankNum-1);
bound=blockNum*(rankNum-1);
//printf("%d\n",blockNum);

m=0;
k=1;
destRank=1;
tag=1;
buffer=(char*)malloc(colNum*sizeof(char*));
while(m!=recordNum)
{
if(m==(k*blockNum-1)&&(m!=bound-1))
{
MPI_Send(&colNum,1,MPI_INT,destRank,100,MPI_COMM_W ORLD);
MPI_Send(&recordNum,1,MPI_INT,destRank,101,MPI_COM M_WORLD);
MPI_Send(&blockNum,1,MPI_INT,destRank,tag,MPI_COMM _WORLD);
//printf("%d\n",blockNum);
for(i=((k-1)*blockNum);i<k*blockNum;i++)
{
for(j=0;j<colNum;j++)
{
buffer[j]=fullSet[i][j];
printf("%c ",buffer[j]);
}
MPI_Send(buffer,colNum,MPI_CHAR,destRank,tag,MPI_C OMM_WORLD);
printf("\n");
}
printf("\n");
destRank++;
tag++;
k++;
}
else if(m==bound-1)
{
blockNum=recordNum-m-1+blockNum;
MPI_Send(&colNum,1,MPI_INT,destRank,100,MPI_COMM_W ORLD);
MPI_Send(&recordNum,1,MPI_INT,destRank,101,MPI_COM M_WORLD);
MPI_Send(&blockNum,1,MPI_INT,destRank,tag,MPI_COMM _WORLD);
//MPI_Send(&flag,1,MPI_INT,destRank,102,MPI_COMM_WOR LD);
//printf("%d\n",blockNum);
for(i=bound-blockNum;i<recordNum;i++)
{
for(j=0;j<colNum;j++)
{
buffer[j]=fullSet[i][j];
printf("%c ",buffer[j]);
}
MPI_Send(buffer,colNum,MPI_CHAR,destRank,tag,MPI_C OMM_WORLD);
printf("\n");
}
printf("\n");
}

m++;
}


/*int s,rItemNum;
tItem *r;
r=(struct tItem*)malloc(sizeof(struct tItem));

s=0;
MPI_Recv(&rItemNum,1,MPI_INT,1,1000,MPI_COMM_WORLD ,&status);
while(s<rItemNum)
{
for(j=0;j<=5;j++)
{
MPI_Recv(&r->itemset[j],1,MPI_CHAR,1,1001,MPI_COMM_WORLD,&status);
}
MPI_Recv(&r->count,1,MPI_INT,1,1002,MPI_COMM_WORLD,&status);
MPI_Recv(&r->tag,1,MPI_INT,0,1003,MPI_COMM_WORLD,&status);
s++;
}*/

endtime=MPI_Wtime();
printf("The master process tooks %f seconds.\n",endtime-starttime);
printf("\n");
}

static void slaveprocess(int rankNum)
{

int rowNum,recordNum,colNum,tag,stag,rank,destRank,m,i ,j;
char **fSet,*buffer;
double minSup=0.45;
double minCon=0.50;
double starttime,endtime;

MPI_Status status;
MPI_Comm_rank(MPI_COMM_WORLD,&rank);
starttime=MPI_Wtime();

MPI_Recv(&colNum,1,MPI_INT,0,100,MPI_COMM_WORLD,&s tatus);
MPI_Recv(&recordNum,1,MPI_INT,0,101,MPI_COMM_WORLD ,&status);
//printf("%d\n",recordNum);
//printf("%d\n",colNum);

tag=rank;
MPI_Recv(&rowNum,1,MPI_INT,0,tag,MPI_COMM_WORLD,&s tatus);
printf("\n");
printf("\n");
printf("The block in rank %d has %d records.\n",rank,rowNum);
//MPI_Recv(&flag,1,MPI_INT,0,102,MPI_COMM_WORLD,&sta tus);

buffer=(char*)malloc(colNum*sizeof(char*));
fSet=(char**)malloc(rowNum*sizeof(char*));
for(m=0;m<rowNum;m++)
{
fSet[m]=(char*)malloc(colNum*sizeof(char));
}

//½ÓÊÕ½ø³Ì0·¢ËÍÀ´µÄ³õʼ¾ØÕóµÄÒ»¿é
for(i=0;i<rowNum;i++)
{
MPI_Recv(buffer,colNum,MPI_CHAR,0,tag,MPI_COMM_WOR LD,&status);
for(j=0;j<colNum;j++)
{
fSet[i][j]=buffer[j];
}
}

printf("\n");
printf("Rank %d receives part of the matrix is as follow:\n",rank);
printf("\n");
for(i=0;i<rowNum;i++)
{
for(j=0;j<colNum;j++)
{
printf("%c ",fSet[i][j]);
}
printf("\n");
}
printf("\n");

tItem *c; //¶¨Òå¾Ö²¿ºòÑ¡Ï
tItem *cr; //½ÓÊÕÆäËû½ø³Ì·¢ËÍÀ´µÄ¾Ö²¿ºòÑ¡¼¯
tItem *p;
int count=0,s,rCount,rTag;
char rItemset;


c=(struct tItem*)malloc(sizeof(struct tItem));
c=Find_candidate_1itemsets(fSet,minSup,rowNum,colN um);

destRank=1;
stag=1;

p=c;
while(p!=NULL)
{
count++;
p=p->next;
}

for(i=1;i<=rankNum-1;i++) //ÏòÆäËû½ø³Ì·¢Ë;ֲ¿ºòÑ¡1Ï
{
p=c;
if(i!=rank)
{
MPI_Send(&count,1,MPI_INT,destRank,14,MPI_COMM_WOR LD);
while(p!=NULL)
{
MPI_Send(&p->itemset[p->tag],1,MPI_CHAR,destRank,15,MPI_COMM_WORLD);
MPI_Send(&p->count,1,MPI_INT,destRank,16,MPI_COMM_WORLD);
MPI_Send(&p->tag,1,MPI_INT,destRank,17,MPI_COMM_WORLD);
p=p->next;
}
}
destRank++;
stag++;
}

int reRank=1,reTag=1,itemNum;
for(j=1;j<=rankNum-1;j++) //½ÓÊÕÆäËû½ø³Ì·¢ËÍÀ´µÄ¾Ö²¿ºòÑ¡1Ï
{
if(j!=rank)
{
s=0;
MPI_Recv(&itemNum,1,MPI_INT,reRank,14,MPI_COMM_WOR LD,&status);
while(s<itemNum)
{
MPI_Recv(&rItemset,1,MPI_CHAR,reRank,15,MPI_COMM_W ORLD,&status);
MPI_Recv(&rCount,1,MPI_INT,reRank,16,MPI_COMM_WORL D,&status);
MPI_Recv(&rTag,1,MPI_INT,reRank,17,MPI_COMM_WORLD, &status);

c=Combine_candidate_itemsets(c,rItemset,rCount);

//printf(" %c",rItemset);
//printf(" %d",rCount);
//printf(" %d",rTag);
//printf("\n");
s++;
}
printf("\n");
}
reRank++;
reTag++;
}

//Êä³öºÏ²¢ºóµÃµ½µÄÈ«²¿ºòÑ¡1Ï
p=c;
printf("Now every rank get the whole candidate itemsets as follow:\n\n");
while(p!=NULL)
{
printf(" %c",p->itemset[p->tag]);
printf(" %d",p->count);
printf(" %d",p->tag);
printf("\n");
p=p->next;
}

//ÓɺòÑ¡1ÏÉú³ÉƵ·±1Ï
tItem *pp,*fHead,*fp,*temp;
int minNum;

fp=fHead=(struct tItem*)malloc(sizeof(struct tItem));
minNum=(int)((recordNum*minSup)+1);
//printf("%d",minNum);
pp=c;

while(pp!=NULL)
{
if(pp->count>minNum)
{
fHead->count=pp->count;
fHead->tag=pp->tag;
fHead->itemset[fHead->tag]=pp->itemset[pp->tag];
fHead->next=NULL;
break;
}
pp=pp->next;
}

fp=fHead;
pp=pp->next;

while(pp!=NULL)
{
if(pp->count>minNum)
{
temp=(struct tItem*)malloc(sizeof(struct tItem));
temp->count=pp->count;
temp->next=NULL;
temp->tag=pp->tag;
temp->itemset[temp->tag]=pp->itemset[pp->tag];
fp->next=temp;
fp=temp;
//printf("%c",pp->itemset[pp->tag]);
}
pp=pp->next;
}

/*printf("\n");
printf("--------The local frequence 1_itemsets--------\n");
fp=fHead;
while(fp!=NULL)
{
printf(" %c",fp->itemset[fp->tag]);
printf(" %d",fp->count);
printf(" %d",fp->tag);
printf("\n");
fp=fp->next;
}*/

tItem *f1,*kFrequence,*kf,*fis,*kfTemp;

//kFrequence=(struct tItem*)malloc(sizeof(struct tItem));
f1=(struct tItem*)malloc(sizeof(struct tItem));
//f1=Find_frequence_1itemsets(fullSet,minSup);

f1=fHead;

//system("pause");
//printf(" %d",rowNum);
//printf(" %d*&*&*&\n",colNum);
kFrequence=Gen_frequence(f1,rowNum,colNum,minNum,f Set);//¾*¹ýÁ¬½ÓºÍ¼ôÖ¦Éú³É×îÖÕµÄƵ·±kÏ

i=2;
while(i<=5)
{
kfTemp=Gen_frequence(kFrequence,rowNum,colNum,minN um,fSet);
if(kfTemp==NULL)
{
break;
}
kFrequence=kfTemp;
i++;
}
//MPI_Barrier(MPI_COMM_WORLD);
/*printf("^^^^^^^^^^^^^^^\n");
kf=kFrequence;
while(kf!=NULL)
{
for(j=0;j<=kf->tag;j++)
{
printf(" %c",kf->itemset[j]);
}
printf(" %d",kf->count);
printf(" %d",kf->tag);
printf("\n");
kf=kf->next;
}
printf("^^^^^^^^^^^^^^^\n");*/


printf("\n");
kf=kFrequence;
printf("--------The frequence %d_itemsets--------\n",kf->tag+1);
while(kf!=NULL)
{
for(j=0;j<=kf->tag;j++)
{
printf(" %c",kf->itemset[j]);
}
printf(" %d",kf->count);
printf(" %d",kf->tag);
printf("\n");
kf=kf->next;
}
printf("\n");

/*kf=kFrequence;
int kItemNum=0;
while(kf!=NULL)
{
kItemNum++;
kf=kf->next;
}

kf=kFrequence;
if(rank==1)
{
MPI_Send(&kItemNum,1,MPI_INT,0,1000,MPI_COMM_WORLD );
while(kf!=NULL)
{
for(j=0;j<=kf->tag;j++)
{
MPI_Send(&kf->itemset[j],1,MPI_CHAR,0,1001,MPI_COMM_WORLD);
}
MPI_Send(&kf->count,1,MPI_INT,0,1002,MPI_COMM_WORLD);
MPI_Send(&kf->tag,1,MPI_INT,0,1003,MPI_COMM_WORLD);
kf=kf->next;
}
}*/

kf=kFrequence;
printf("\n\nThe subset of the frequence is:\n\n");
while(kf!=NULL)
{

fis=Gen_kFrequence_subsets(kf); //Éú³ÉƵ·±kÏÿÏîµÄ×Ó¼¯µÄ¼¯ºÏ
fis=Compute_candidateItem_Num(fis,rowNum,colNum,fS et); //¼ÆËãÿһ¸ö×Ó¼¯µÄÖ§³Ö¶È

/*p=fis;
p=p->next;
while(p!=NULL)
{
for(i=0;i<=p->tag;i++)
{
printf(" %c",p->itemset[i]);
}
printf(" %d",p->count);
printf(" %d",p->tag);
printf("\n");
p=p->next;
}*/

printf("\n\nNow we get the association rules:\n\n");
p=fis;
p=p->next;
while(p!=NULL)
{
//printf("\n");
Gen_association_rules(kf,p,minCon);
printf("\n");
p=p->next;
}

kf=kf->next;
}
endtime=MPI_Wtime();
printf("The slave process %d tooks %f seconds.\n",rank,endtime-starttime);
printf("\n");

}

struct tItem *Gen_frequence(tItem *frequence, int recordNum, int colNum, int minNum, char **fullSet) //Éú³ÉƵ·±Ï
{

tItem *candidate,*cp,*fp,*fpb,*p,*p1;
int i,j,k,m,count=0,rank,rankNum,destRank,stag;
//int i,m,n;
//char *buffer;
MPI_Status status;
MPI_Comm_rank(MPI_COMM_WORLD,&rank);
MPI_Comm_size(MPI_COMM_WORLD,&rankNum);

/*printf("$$$$$$$$$$$$$$$$$$$$$$$$$$$$$\n");
printf("##### %d\n",recordNum);
printf("##### %d\n",colNum);
printf("##### %d\n",minNum);
for(i=0;i<recordNum;i++)
{
for(j=0;j<colNum;j++)
{
printf(" %c",fullSet[i][j]);
}
printf("\n");
}
p=(struct tItem*)malloc(sizeof(struct tItem));
p=frequence;
while(p!=NULL)
{
printf(" %c",p->itemset[p->tag]);
printf(" %d",p->count);
printf(" %d",p->tag);
printf("\n");
p=p->next;
}
printf("$$$$$$$$$$$$$$$$$$$$$$$$$$$$$\n");*/


//for(k=2;frequence!=NULL;k++)
//while(candidate!=NULL)
//{
//printf("++++++++++++++++++++++++++++++++++++++++++ ++\n");

candidate=apriori_gen(frequence);

if(candidate!=NULL)
{
candidate=Compute_candidateItem_Num(candidate,reco rdNum,colNum,fullSet);

destRank=1;
stag=1;

p=candidate;
p1=candidate;
while(p!=NULL)
{
count++;
p=p->next;
}
//printf(" #%d#\n",count);

//MPI_Barrier(MPI_COMM_WORLD);

for(i=1;i<=rankNum-1;i++) //ÏòÆäËû½ø³Ì·¢Ë;ֲ¿ºòÑ¡kÏ
{
p=candidate;
if(i!=rank)
{
MPI_Send(&count,1,MPI_INT,destRank,24,MPI_COMM_WOR LD);
while(p!=NULL)
{
for(j=0;j<=p->tag;j++)
{
MPI_Send(&p->itemset[j],1,MPI_CHAR,destRank,25,MPI_COMM_WORLD);
}

MPI_Send(&p->count,1,MPI_INT,destRank,26,MPI_COMM_WORLD);
MPI_Send(&p->tag,1,MPI_INT,destRank,27,MPI_COMM_WORLD);
p=p->next;
}
}
destRank++;
stag++;
}

//MPI_Barrier(MPI_COMM_WORLD);

int reRank=1,reTag=1,itemNum;
int rCount,rTag,s;
char rItemset;
tItem *r;
r=(struct tItem*)malloc(sizeof(struct tItem));
for(j=1;j<=rankNum-1;j++) //½ÓÊÕÆäËû½ø³Ì·¢ËÍÀ´µÄ¾Ö²¿ºòÑ¡kÏ
{
if(j!=rank)
{
s=0;
MPI_Recv(&itemNum,1,MPI_INT,reRank,24,MPI_COMM_WOR LD,&status);
while(s<itemNum)
{
for(m=0;m<=p1->tag;m++)
{
MPI_Recv(&r->itemset[m],1,MPI_CHAR,reRank,25,MPI_COMM_WORLD,&status);
//printf(" %c",r->itemset[m]);
}

MPI_Recv(&r->count,1,MPI_INT,reRank,26,MPI_COMM_WORLD,&status) ;
MPI_Recv(&r->tag,1,MPI_INT,reRank,27,MPI_COMM_WORLD,&status) ;


candidate=Combine_candidate_k_itemsets(candidate,r );

//printf(" %c",rItemset);
//printf(" %d",r->count);
//printf(" %d",r->tag);
//printf("\n");
s++;
}
//printf("\n");
//printf("&&&&&&&&&&&&&&&&&&&&&\n");
}
reRank++;
reTag++;
}

//MPI_Barrier(MPI_COMM_WORLD);

/*cp=candidate;
count=0;
printf("--------The candidate %d_itemsets--------\n",cp->tag+1);
while(cp!=NULL)
{
for(j=0;j<=cp->tag;j++)
{
printf(" %c",cp->itemset[j]);
}
printf(" %d",cp->count);
printf(" %d",cp->tag);
printf("\n");
count++;
cp=cp->next;
}
printf("\n");
printf("The total number is: %d\n",count);
printf("\n");*/

//MPI_Barrier(MPI_COMM_WORLD);

frequence=candidate;
fpb=(struct tItem*)malloc(sizeof(struct tItem));
fp=(struct tItem*)malloc(sizeof(struct tItem));
fpb=frequence;
fp=fpb->next;
//int minNum=(int)((recordNum*minSup)+1);
//printf("########## %d\n",minNum);

while(fp!=NULL) //ɾ³ýºóÑ¡ÏÖÐÖ§³Ö¶ÈСÓÚ×îС֧³Ö¶ÈµÄÏîÄ¿£¬Éú³ÉƵ·± Ï
{

if(fpb->count<minNum)
{
frequence=fp;
fpb=fp;
fp=fp->next;
}


if(fp->count<minNum)
{
fp=fp->next;
fpb->next=fp;
}
else
{
fp=fp->next;
fpb=fpb->next;

}
}

/*fp=frequence;
count=0;
printf("--------The frequence %d_itemsets--------\n",fp->tag+1);
while(fp!=NULL)
{
//MPI_Barrier(MPI_COMM_WORLD);
for(j=0;j<=fp->tag;j++)
{
printf(" %c",fp->itemset[j]);
}
printf(" %d",fp->count);
printf(" %d",fp->tag);
printf("\n");
count++;
fp=fp->next;
}

printf("\n");
printf("The total number is: %d\n",count);
printf("\n");*/

//MPI_Barrier(MPI_COMM_WORLD);
}
else
{
//return (NULL);
//break;
frequence=NULL;
}
//printf("++++++++++++++++++++++++++++++++++++++++++ ++\n");
//MPI_Barrier(MPI_COMM_WORLD);
//}

return (frequence);

}

struct tItem *Gen_frequence1(tItem *frequence, int recordNum, int colNum, int minNum, char **fullSet) //Éú³ÉƵ·±Ï
{

tItem *candidate,*cp,*fp,*fpb,*p,*p1;
int i,j,k,m,count=0,rank,rankNum,destRank,stag;
//int i,m,n;
//char *buffer;
MPI_Status status;
MPI_Comm_rank(MPI_COMM_WORLD,&rank);
MPI_Comm_size(MPI_COMM_WORLD,&rankNum);

//printf("****************************************** *\n");

/*printf("$$$$$$$$$$$$$$$$$$$$$$$$$$$$$\n");
printf("##### %d\n",recordNum);
printf("##### %d\n",colNum);
printf("##### %d\n",minNum);
printf("##### %d\n",rank);
for(i=0;i<recordNum;i++)
{
for(j=0;j<colNum;j++)
{
printf(" %c",fullSet[i][j]);
}
printf("\n");
}
p=(struct tItem*)malloc(sizeof(struct tItem));
p=frequence;
while(p!=NULL)
{
for(j=0;j<=p->tag;j++)
{
printf(" %c",p->itemset[j]);
}
printf(" %d",p->count);
printf(" %d",p->tag);
printf("\n");
p=p->next;
}
printf("$$$$$$$$$$$$$$$$$$$$$$$$$$$$$\n");*/

//for(k=2;frequence!=NULL;k++)
//while(candidate!=NULL)
//{
printf("++++++++++++++++++++++++++++++++++++++++++ ++\n");

candidate=apriori_gen(frequence);

/*p=candidate;
int t=0;
printf("²âÊÔ½á¹û\n");
while(p!=NULL)
{
for(j=0;j<=p->tag;j++)
{
printf(" %c",p->itemset[j]);
}
printf(" %d",p->count);
printf(" %d",p->tag);
printf("\n");
t++;
p=p->next;
}
printf("Ò»¹²ÓÐ %d\n",t);
printf("½áÊø²âÊÔ\n");*/


/*if(rank==2)
{
printf("!!!!!!\n");
p=candidate;
while(p!=NULL)
{
for(j=0;j<=p->tag;j++)
{
printf(" %c",p->itemset[j]);
}
printf(" %d",p->count);
printf(" %d",p->tag);
printf("\n");
p=p->next;
}
}

printf("!!!!!!\n");*/


if(candidate!=NULL)
{
//printf("!!!!!!\n");
candidate=Compute_candidateItem_Num(candidate,reco rdNum,colNum,fullSet);

destRank=1;
stag=1;

p=candidate;
p1=candidate;
while(p!=NULL)
{
count++;
p=p->next;
}
//printf(" #%d#\n",count);
//printf("½øÐе½ÕâÀï\n");

//MPI_Barrier(MPI_COMM_WORLD);

for(i=1;i<=rankNum-1;i++) //ÏòÆäËû½ø³Ì·¢Ë;ֲ¿ºòÑ¡kÏ
{
p=candidate;
if(i!=rank)
{
MPI_Send(&count,1,MPI_INT,destRank,54,MPI_COMM_WOR LD);
//printf("### %d ###\n",count);
while(p!=NULL)
{
for(j=0;j<=p->tag;j++)
{
MPI_Send(&p->itemset[j],1,MPI_CHAR,destRank,55,MPI_COMM_WORLD);
//printf(" %c",p->itemset[j]);
}

MPI_Send(&p->count,1,MPI_INT,destRank,56,MPI_COMM_WORLD);
MPI_Send(&p->tag,1,MPI_INT,destRank,57,MPI_COMM_WORLD);
//printf(" %d",p->count);
//printf(" %d",p->tag);
//printf("\n");
p=p->next;
}
}
destRank++;
stag++;
}

//MPI_Barrier(MPI_COMM_WORLD);

int reRank=1,reTag=1,itemNum;
int rCount,rTag,s;
char rItemset;
tItem *r;
r=(struct tItem*)malloc(sizeof(struct tItem));
for(j=1;j<=rankNum-1;j++) //½ÓÊÕÆäËû½ø³Ì·¢ËÍÀ´µÄ¾Ö²¿ºòÑ¡kÏ
{
if(j!=rank)
{
s=0;
MPI_Recv(&itemNum,1,MPI_INT,reRank,54,MPI_COMM_WOR LD,&status);
while(s<itemNum)
{
for(m=0;m<=p1->tag;m++)
{
MPI_Recv(&r->itemset[m],1,MPI_CHAR,reRank,55,MPI_COMM_WORLD,&status);
//printf(" %c",r->itemset[m]);
}

MPI_Recv(&r->count,1,MPI_INT,reRank,56,MPI_COMM_WORLD,&status) ;
MPI_Recv(&r->tag,1,MPI_INT,reRank,57,MPI_COMM_WORLD,&status) ;


candidate=Combine_candidate_k_itemsets(candidate,r );

//printf(" %c",rItemset);
//printf(" %d",r->count);
//printf(" %d",r->tag);
//printf("\n");
s++;
}
//printf("\n");
printf("&&&&&&&&&&&&&&&&&&&&&\n");
}
reRank++;
reTag++;
}

//MPI_Barrier(MPI_COMM_WORLD);

cp=candidate;
count=0;
printf("--------The candidate %d_itemsets--------\n",cp->tag+1);
while(cp!=NULL)
{
for(j=0;j<=cp->tag;j++)
{
printf(" %c",cp->itemset[j]);
}
printf(" %d",cp->count);
printf(" %d",cp->tag);
printf("\n");
count++;
cp=cp->next;
}
printf("\n");
printf("The total number is: %d\n",count);
printf("\n");

//MPI_Barrier(MPI_COMM_WORLD);

frequence=candidate;
fpb=(struct tItem*)malloc(sizeof(struct tItem));
fp=(struct tItem*)malloc(sizeof(struct tItem));
fpb=frequence;
fp=fpb->next;
//int minNum=(int)((recordNum*minSup)+1);
//printf("########## %d\n",minNum);

while(fp!=NULL) //ɾ³ýºóÑ¡ÏÖÐÖ§³Ö¶ÈСÓÚ×îС֧³Ö¶ÈµÄÏîÄ¿£¬Éú³ÉƵ·± Ï
{

if(fpb->count<minNum)
{
frequence=fp;
fpb=fp;
fp=fp->next;
}


if(fp->count<minNum)
{
fp=fp->next;
fpb->next=fp;
}
else
{
fp=fp->next;
fpb=fpb->next;

}
}

fp=frequence;
count=0;
printf("--------The frequence %d_itemsets--------\n",fp->tag+1);
while(fp!=NULL)
{
//MPI_Barrier(MPI_COMM_WORLD);
for(j=0;j<=fp->tag;j++)
{
printf(" %c",fp->itemset[j]);
}
printf(" %d",fp->count);
printf(" %d",fp->tag);
printf("\n");
count++;
fp=fp->next;
}

printf("\n");
printf("The total number is: %d\n",count);
printf("\n");

//MPI_Barrier(MPI_COMM_WORLD);
}
else
{
//return (NULL);
//break;
//frequence=NULL;
}
//printf("++++++++++++++++++++++++++++++++++++++++++ ++\n");
//MPI_Barrier(MPI_COMM_WORLD);
//}

return (frequence);

}

bool Has_infrequence_subset(tItem *pp, tItem *f) //ÅжϺòÑ¡kÏµÄ×Ó¼¯ÊÇ·ñÔÚƵ·±k-1ÏÖÐ
{
tItem *p,*fp; //´¢´æ*ppÖеÄk-1Ïî×Ó¼¯
int i=0,j,m=0;
bool flag;

while(i<=pp->tag)
{

p=(struct tItem*)malloc(sizeof(struct tItem));

for(j=0;j<pp->tag;j++)
{
if(j==i)
{
j++;
}
else
{
p->itemset[j]=pp->itemset[j];
}
}

fp=f;
while(fp!=NULL)
{
while(m<=fp->tag)
{
if(p->itemset[m]==fp->itemset[m])
{
m++;
}
else
{
flag=false;
m++;
}
}

flag=true;
fp=fp->next;
}

i++;
}


return (flag);
}

struct tItem *Gen_candidate_itemset(tItem *cp,tItem *cp1,tItem *cp2) //Éú³ÉºóÑ¡Ïî
{
int i=0;

while(i<=cp1->tag)
{
cp->itemset[i]=cp1->itemset[i];
//cp->tag=cp1->tag+1;
i++;
}

cp->tag=cp1->tag+1;
cp->itemset[i]=cp2->itemset[i-1];
cp->count=0;
cp->next=NULL;

return (cp);
}

bool Is_before_equal(tItem *pp1, tItem *pp2) //ÅжÏÁ½¸öÏîÄ¿¼¯µÄÇ°k-1ÏîÊÇ·ñÏàͬ
{
int i=0;
bool flag;

while(i<pp1->tag)
{
if(pp1->itemset[i]==pp2->itemset[i])
{
flag=true;
}
else
{
flag=false;
break;
}
i++;
}

return (flag);
}

struct tItem *Compute_candidateItem_Num(tItem *c,int recordNum, int colNum, char **fullSet) //¼ÆËãºòÑ¡ÏÖÐÿһÏîµÄ×îС֧³ÖÊý
{
tItem *cp;
int i,j,m,n;
char *buffer;

cp=c;

while(cp!=NULL) //ͳ¼Æÿ¸öºòÑ¡ÏµÄ¼ÆÊý
{
for(i=0;i<recordNum;i++)
{

bool flag=true;
buffer=(char*)malloc(colNum*sizeof(char*));

for(j=0;j<colNum;j++)
{
buffer[j]=fullSet[i][j];
}

m=0;
while(m<=cp->tag)
{
bool flag1=false;
for(n=0;n<colNum;n++)
{
if(cp->itemset[m]==buffer[n])
{
flag1=true;
break;
}

flag1=false;
}

if(flag1==false)
{
flag=false;
}
m++;
}

if(flag==true)
{
cp->count++;
}
}

cp=cp->next;
}

return (c);
}

struct tItem *apriori_gen(tItem *freq) //Éú³ÉºòÑ¡Ï
{
tItem *p1,*p2,*head,*cHead,*p,*pTail;
int tag,i=0;
//bool flag;

if(freq->next!=NULL)
{

head=freq;
p1=head;
p2=head;
p2=p2->next;

p=(struct tItem*)malloc(sizeof(struct tItem));
tag=p1->tag+1;

if(tag==1)//Éú³ÉºòÑ¡2Ï
{
//printf("############\n");
while(i<=tag)
{
if(i<=tag-1)
{
//p->count=p1->count;
p->itemset[i]=p1->itemset[i];
p->tag=tag;
}
else
{
//p->count=p2->count;
p->itemset[i]=p2->itemset[i-1];
p->tag=tag;
}
i++;
}
p->count=0;
p->next=NULL;

/*printf(" %c",p->itemset[0]);
printf(" %c",p->itemset[1]);
printf(" %d",p->tag);*/

pTail=p;
cHead=p;
p2=p2->next;
//printf("#%c#",p1->itemset[p1->tag]);

while(p1!=NULL)
{
while(p2!=NULL)
{
p=(struct tItem*)malloc(sizeof(struct tItem));
tag=p1->tag+1;
i=0;

while(i<=tag)
{
if(i<=tag-1)
{
//p->count=p1->count;
p->itemset[i]=p1->itemset[i];
//printf("%c",p->itemset[i]);
p->tag=tag;
}
else
{
//p->count=p2->count;
p->itemset[i]=p2->itemset[i-1];
//printf("%c",p->itemset[i]);
p->tag=tag;
}
i++;
}
p->count=0;
p->next=NULL;

//flag=Has_infrequence_subset(cHead,freq);

//if(flag==true)
//{
pTail->next=p;
pTail=p;
//}
p2=p2->next;
}

p1=p1->next;
p2=p1->next;

if(p2==NULL)
{
break;
}
}
}
/*else if(p1->tag==3)
{
if(Is_before_equal(p1,p2))
{
//printf("½øÐе½ÕâÀï\n");
//p=(struct tItem*)malloc(sizeof(struct tItem));
//cHead=(struct tItem*)malloc(sizeof(struct tItem));
//pTail=(struct tItem*)malloc(sizeof(struct tItem));

p=Gen_candidate_itemset(p,p1,p2);
pTail=p;
cHead=p;
p2=p2->next;


while((p1!=NULL)&&(p2!=NULL))
{
//while(Is_before_equal(p1,p2))
while(p2!=NULL)
{
if(Is_before_equal(p1,p2))
{
p=(struct tItem*)malloc(sizeof(struct tItem));
tag=p1->tag+1;

p=Gen_candidate_itemset(p,p1,p2);

if(Has_infrequence_subset(p, freq))
{
pTail->next=p;
pTail=p;
}
}
//printf("½øÐе½ÕâÀï\n");
p2=p2->next;

}

p1=p1->next;
p2=p1->next;
}
}
//printf("½øÐе½ÕâÀï\n");
}*/
else//Éú³ÉºîÑ¡2ÏÒÔÉϵĺòÑ¡¼¯(±ê¼ÇcHeadʱºòÓÐÎÊÌâ)
{

/*while(p2!=NULL)
{
if(Is_before_equal(p1,p2))
{
break;
}
p2=p2->next;
}*/

if(Is_before_equal(p1,p2))
{
//p=(struct tItem*)malloc(sizeof(struct tItem));
//cHead=(struct tItem*)malloc(sizeof(struct tItem));
//pTail=(struct tItem*)malloc(sizeof(struct tItem));

p=Gen_candidate_itemset(p,p1,p2);
pTail=p;
cHead=p;
p2=p2->next;


while((p1!=NULL)&&(p2!=NULL))
{
//while(Is_before_equal(p1,p2))
while(p2!=NULL)
{
if(Is_before_equal(p1,p2))
{
p=(struct tItem*)malloc(sizeof(struct tItem));
tag=p1->tag+1;

p=Gen_candidate_itemset(p,p1,p2);

if(Has_infrequence_subset(p, freq))
{
pTail->next=p;
pTail=p;
}
}

p2=p2->next;

}

p1=p1->next;
p2=p1->next;
}
}
else
{
p1=p1->next;
p2=p2->next;
p=Gen_candidate_itemset(p,p1,p2);
pTail=p;
cHead=p;
p2=p2->next;


while((p1!=NULL)&&(p2!=NULL))
{
while(Is_before_equal(p1,p2))
{
p=(struct tItem*)malloc(sizeof(struct tItem));
tag=p1->tag+1;

p=Gen_candidate_itemset(p,p1,p2);

if(Has_infrequence_subset(p, freq))
{
pTail->next=p;
pTail=p;
}

p2=p2->next;

}

p1=p1->next;
p2=p1->next;
}
//cHead=NULL;
}
}
}
else
{
cHead=NULL;
}
/*tItem *pp;
int j,count=0;

pp=cHead;
printf("--------The candidate %d_itemsets--------\n",pp->tag+1);
while(pp!=NULL)
{
for(j=0;j<=tag;j++)
{
printf(" %c",pp->itemset[j]);
}
printf(" %d",pp->count);
printf(" %d",pp->tag);
printf("\n");
count++;
pp=pp->next;
}
printf("\n");
printf("The total number is: %d\n",count);
printf("\n");*/

return (cHead);
}

struct tItem *Combine_candidate_k_itemsets(tItem *lc,tItem *r)
{
tItem *p;
int i,j;
bool flag,flagj;

//printf("**************************\n");
p=lc;
while(p!=NULL)
{
//flag=true;
for(i=0;i<=r->tag;i++)
{
flagj=false;
for(j=0;j<=p->tag;j++)
{
if(p->itemset[j]==r->itemset[i])
{
flagj=true;
break;
}
}
if(flagj==false)
{
flag=false;
break;
}
else
{
flag=true;
}
}
if(flag==true)
{
p->count=p->count+r->count;
break;
}
p=p->next;
}

return (lc);
}

struct tItem *Combine_candidate_itemsets(tItem *lc, char rItemset, int rCount)
{
tItem *p;

p=lc;
while(p!=NULL)
{
if(p->itemset[p->tag]==rItemset)
{
p->count=p->count+rCount;
}
p=p->next;
}

return (lc);
}

struct tItem *Find_candidate_1itemsets(char **fullSet2, double sup2,int recordNum,int colNum) //Éú³ÉƵ·±1Ï
{
tItem *cHead,*fHead;
tItem *p1,*pHead,*pTail,*p;
tItem *fp,*temp,*pp;
fp=fHead=(struct tItem*)malloc(sizeof(struct tItem));

int i,j,count=0;
bool flag;

p=pHead=pTail=(struct tItem*)malloc(sizeof(struct tItem));
cHead=NULL;
pHead->tag=0;
pHead->itemset[pHead->tag]=fullSet2[0][0];
pHead->count=0;
pHead->next=NULL;


int minNum=(int)((recordNum*sup2)+1);
//printf("%d",minNum);

cHead=pHead;
for(i=0;i<recordNum;i++)
{
for(j=0;j<colNum;j++)
{
p=cHead;
while(p!=NULL)
{
if(p->itemset[p->tag]==fullSet2[i][j])
{
p->count++;
flag=false;
break;
}
else
{
pTail=p;
p=p->next;
flag=true;
}
}
if(flag==true)
{
p1=(struct tItem*)malloc(sizeof(struct tItem));
p1->tag=0;
p1->itemset[p1->tag]=fullSet2[i][j];
p1->count=1;
pTail->next=p1;
p1->next=NULL;
}
}
}

printf("\n");
printf("--------The local candidate 1_itemsets--------\n");
p=cHead;
while(p!=NULL)
{
count++;
printf(" %c",p->itemset[p->tag]);
printf(" %d",p->count);
printf(" %d",p->tag);
printf("\n");
p=p->next;
}
printf("\n");
printf("In all, there are %d candidate 1_itemsets.\n",count);

/*pp=cHead;

while(pp!=NULL)
{
if(pp->count>minNum)
{
fHead->count=cHead->count;
fHead->tag=cHead->tag;
fHead->itemset[fHead->tag]=cHead->itemset[cHead->tag];
fHead->next=NULL;
break;
}
pp=pp->next;
}

fp=fHead;
pp=pp->next;

while(pp!=NULL)
{
if(pp->count>minNum)
{
temp=(struct tItem*)malloc(sizeof(struct tItem));
temp->count=pp->count;
temp->next=NULL;
temp->tag=pp->tag;
temp->itemset[temp->tag]=pp->itemset[pp->tag];
fp->next=temp;
fp=temp;
//printf("%c",pp->itemset[pp->tag]);
}
pp=pp->next;
}

printf("\n");
printf("--------The frequence 1_itemsets--------\n");
fp=fHead;
while(fp!=NULL)
{
printf(" %c",fp->itemset[fp->tag]);
printf(" %d",fp->count);
printf(" %d",fp->tag);
printf("\n");
fp=fp->next;
}

return (fHead);*/
return (cHead);
}

struct tItem *Gen_kFrequence_subsets(tItem *f) //Éú³ÉƵ·±kÏÿÏîµÄ×Ó¼¯µÄ¼¯ºÏ
{
tItem *FreItemSubset;
//tItem *p;
int ListLength=f->tag+1;
int i;
//buffer=(int*)malloc(col*sizeof(int*))
char *List,*Buffer;

List=(char*)malloc(ListLength*sizeof(char*));
Buffer=(char*)malloc(ListLength*sizeof(char*));

for(i=0;i<f->tag+1;i++)
{
List[i]=f->itemset[i];
//printf(" %c",List[i]);
}

FreItemSubset=(struct tItem*)malloc(sizeof(struct tItem));
FreItemSubset->next=NULL;
FreItemSubset=SubSet(List,0,Buffer,0,FreItemSubset ,ListLength);

/*p=FreItemSubset;
p=p->next;
while(p!=NULL)
{
for(i=0;i<=p->tag;i++)
{
printf(" %c",p->itemset[i]);
}
printf(" %d",p->count);
printf(" %d",p->tag);
printf("\n");
p=p->next;
}*/

return (FreItemSubset);
}

int Index(char *List, char c, int ListLength)
{
for(int i=0; i<=ListLength-1; i++)
{
if(c==List[i])
{
return i;
break;
}
}
return -1;
}

struct tItem *SubSet(char *List, int m, char *Buffer, int flag, tItem *fis,int ListLength)
{
//fis->next=NULL;
//printf("###\n");
if(m <= ListLength-1)
{
/*if(m==0)
{
Buffer[0]=List[0];
}*/
//Buffer[flag]=List[m];
/*if(flag==0)
{
Buffer[flag]=List[m];
}*/

for(int i=(flag==0) ? 0 : Index(List,Buffer[flag-1],ListLength)+1; i<=ListLength-1; i++)
//µ±flag==0ʱ£¬BufferÖÐûÓÐÈκÎÔªËØ£¬´Ëʱi=[0...ListLength-1]
//µ±flag>0ʱ£¬ÕÒµ½BufferÖеÄ×îºóÒ»¸öÔªËØÔÚ¼¯ºÏListÖÐ µÄλÖÃi£¬°Ñ[i....ListLength-1]
//´¦µÄÔªËØ£¬¼Óµ½BufferÔªËصÄ×îºóÃæ
{

Buffer[flag]=List[i];
fis=AddToSubset(Buffer,flag,fis);
//Output(Buffer,flag);
SubSet(List, m+1, Buffer,flag+1,fis,ListLength);
}
}

/*tItem *p;
p=fis;
while(p!=NULL)
{
for(int j=0;j<=p->tag;j++)
{
printf(" %c",p->itemset[j]);
}
printf(" %d",p->count);
printf(" %d",p->tag);
printf("\n");
p=p->next;
}*/

return (fis);
}

struct tItem *AddToSubset(char *Buffer, int flag, tItem *fis) //½«×Ó¼¯Ìí¼Óµ½Á´±íÖÐ
{

tItem *p;
int i=0;

p=(struct tItem*)malloc(sizeof(struct tItem));

p->count=0;
p->tag=flag;

while(i<=flag)
{
p->itemset[i]=Buffer[i];
i++;
}

p->next=fis->next;
fis->next=p;

return (fis);
}

void Gen_association_rules(tItem *kf, tItem *p, double minCon) //Éú³É¹ØÁª¹æÔò
{
int i=0;
int j=0;
double m;
bool flag;

//printf("@@@@ %f\n",minCon);

m=(double)(kf->count)/(double)(p->count);

if(m>=minCon)
{
printf("\n");
while(i<=p->tag)
{
if(i!=p->tag)
{
printf("%c ",p->itemset[i]);
}
else
{
printf("%c ",p->itemset[i]);
}
i++;
}

printf("=====> ");

while(j<=kf->tag)
{
if(j!=kf->tag)
{
for(i=0;i<=p->tag;i++)
{
if(kf->itemset[j]==p->itemset[i])
{
flag=false;
break;
}
else
{
flag=true;
}
}
if(flag==true)
{
printf("%c ",kf->itemset[j]);
}

}
else
{
for(i=0;i<=p->tag;i++)
{
if(kf->itemset[j]==p->itemset[i])
{
flag=false;
break;
}
else
{
flag=true;
}
}
if(flag==true)
{
printf("%c ",kf->itemset[j]);
}

}
j++;
}

//cout << setprecision<< m <<endl;
m=(double)(p->count)/(double)(kf->count);
printf(" Confidence : %f",m);

printf("\n");
}
}

URL:

Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)