#include <stdio.h>

#include <math.h>

#include <stdlib.h>

#include "mpi.h"

 

#define TRUE 1

#define FALSE 0

 

int N,K;

int * AverageIndex;

double * Average;

double * AverageCopy;

double * AllData;

double ** Cluster;

int * ElementNum;

int ProcessNum;

int MyId;

int SourceId;

 

void CreateRandomArray(int n,int k,int * aveindex)

{

        int i=0,j=0;

        srand((unsigned)time(NULL));

        for(i=0;i<k;i++)

        {

                int randtheonly=TRUE;

                while(randtheonly)

                {

                        int a=rand()%n;

                        for(j=0;j<i;j++)

                        {

                                if(aveindex[j]==a)      //重复

                                {

                                        randtheonly=TRUE;

                                        break;

                                }

                        }

                        if(j==i)                        //不重复

                        {

                                aveindex[i]=a;

                                randtheonly=FALSE;

                        }

                }

        }

}

 

void AverageBackup()                                    //聚类均值数组的备份

{

        int i=0;

        for(i=0;i<K;i++)

        {

                AverageCopy[i]=Average[i];

        }

}

 

void InitAverage()

{

        int i=0;

        CreateRandomArray(N,K,AverageIndex);            //随机产生K个均值序列

        for(i=0;i<K;i++)

        {

                Average[i]=AllData[AverageIndex[i]];    //将对应数据赋值给均值数组

        }

        AverageBackup();                                        //均值备份

}

 

void InitData()                                         //数据初始化

{

        char * FileName="DataFile.txt";

        FILE * DF;

        int i=0;

        N=0;

        int DataRead;

 

        if((DF=fopen(FileName,"r"))==NULL)      //判断文件是否为空

        {

                printf("File not exist!\n");

                exit(0);

        }

        while(!feof(DF))        //统计数据个数

        {

                fscanf(DF,"%d",&DataRead);

                N=N+1;

        }

        N-=1;

        fclose(DF);

        printf("N=%d  Please enter the number of cluster: ",N);

        scanf("%d",&K);

        if(K>N)

        {

                printf("K>N is wrong!");

                exit(0);

        }

        Average=(double *)malloc(sizeof(double)*K);

        AverageIndex=(int *)malloc(sizeof(int)*K);

        AverageCopy=(double *)malloc(sizeof(double)*K);

        ElementNum=(int *)malloc(sizeof(int)*K);

        AllData=(double *)malloc(sizeof(double)*N);

        Cluster=(double **)malloc(sizeof(double)*K);

 

        i=0;

        DF=fopen(FileName,"r");

        while(!feof(DF))                //从文件读数据

        {

                fscanf(DF,"%d",&DataRead);

                if(i==N) break;

                AllData[i++]=DataRead;

        }

        fclose(DF);

        for(i=0;i<K;i++)

        {

                Cluster[i]=(double *)malloc(sizeof(double)*N);

                ElementNum[i]=0;                        //初始每个聚类的元素个数为0

        }

 

        InitAverage();                          //K个聚类的均值初始化

}

 

int GetIndex(double value,double * ave)

{

int i=0;

        int index=i;                                    //距离最小的聚类索引

        double min=fabs(value-ave[i]);          //距聚类均值最小距离

        for(i=0;i<K;i++)                                //找到距离最小的聚类索引

        {

                if(fabs(value-ave[i])<min)

                {

                        index=i;

                        min=fabs(value-ave[i]);

                }

        }

//printf("value= %f  index= %d\n",value,index+1);

        return index;

}

 

void UpdateAverage()                            //添加元素后更新聚类均值

{

        int i=0,j=0;

        double sum=0;

        for(i=0;i<K;i++)                        //计算每个聚类的均值

        {

                sum=0;

                for(j=0;j<ElementNum[i];j++)            //计算某聚类的元素值和

                {

                        sum+=Cluster[i][j];

                }

                if(ElementNum[i]>0)

                {

                        Average[i]=sum/ElementNum[i];

                }

        }

}

 

int EqualJudge(double * ave1,double * ave2)     //compare比较前后两次聚类均值是否相同

{

        int i;

        for(i=0;i<K;i++)

        {

                if(fabs(ave1[i]!=ave2[i]))

                {

                        return FALSE;

                }

        }

        return TRUE;

}

 

void Print()

{

        int i,j;

        printf("--------------------------\n");

        for(i=0;i<K;i++)

        {

                printf("第 %d 组：中心值： %f \n",i+1,Average[i]);

                printf("聚类成员：\n");

                for(j=0;j<ElementNum[i];j++)

                {

                        printf("%f  ",Cluster[i][j]);

if(((j+1)%8)==0)         //display 8 data per line

{

printf("\n");

}

                }

                printf("\n");

        }

}

 

int main(int argc,char *argv[])

{

int LocalStart;

int Flag=1;

int TemAveIndex;

int * TemArray;

int * TemArrayAdd;

int i=0;

MPI_Status Status;

MPI_Init(&argc,&argv);

MPI_Comm_rank(MPI_COMM_WORLD,&MyId);

MPI_Comm_size(MPI_COMM_WORLD,&ProcessNum);

if(MyId==0)

{

InitData();

MPI_Bcast(&N,1,MPI_DOUBLE,0,MPI_COMM_WORLD);

MPI_Bcast(&K,1,MPI_DOUBLE,0,MPI_COMM_WORLD);

MPI_Bcast(AllData,N,MPI_DOUBLE,0,MPI_COMM_WORLD);

TemArrayAdd=(int *)malloc(sizeof(int)*(N-(N%ProcessNum)));

 

MPI_Barrier(MPI_COMM_WORLD);

}

else

{

//MPI_Barrier(MPI_COMM_WORLD);

         MPI_Bcast(&N,1,MPI_DOUBLE,0,MPI_COMM_WORLD);

MPI_Bcast(&K,1,MPI_DOUBLE,0,MPI_COMM_WORLD);

AllData=(double *)malloc(sizeof(double)*N);

Average=(double *)malloc(sizeof(double)*K);

MPI_Bcast(AllData,N,MPI_DOUBLE,0,MPI_COMM_WORLD);

MPI_Barrier(MPI_COMM_WORLD);

}

//printf("MYID is %d\n",MyId);

TemArray=(int *)malloc(sizeof(int)*(N/ProcessNum));

while(Flag)

{

if(MyId==0)

{

MPI_Barrier(MPI_COMM_WORLD);

MPI_Bcast(Average,K,MPI_DOUBLE,0,MPI_COMM_WORLD);

// for(i=0;i<K;i++) printf("%f ",Average[i]);

for(LocalStart=0;LocalStart<(N/ProcessNum);LocalStart++)

                        {

                                TemAveIndex=GetIndex(AllData[LocalStart],Average);

                                TemArrayAdd[LocalStart]=TemAveIndex;

}

//for(i=0;i<N/ProcessNum;i++) printf("%d ",TemArrayAdd[i]);

for(i=1;i<ProcessNum;i++)

{

                     MPI_Recv(TemArrayAdd+i*(N/ProcessNum),N/ProcessNum,MPI_INT,i,100,MPI_COMM_WORLD,&Status);

}

for(i=0;i<K;i++)                                //clear all the number of element of the clusters 清空所有聚类元素个数

{

ElementNum[i]=0;

}

for(i=0;i<N-(N%ProcessNum);i++)

{

//printf("%d %d       ",i,TemArrayAdd[i]);

Cluster[TemArrayAdd[i]][ElementNum[TemArrayAdd[i]]++]=AllData[i];

}

UpdateAverage();

//for(i=0;i<K;i++) printf("%f ",Average[i]);

if(EqualJudge(Average,AverageCopy))

{

Flag=0;

}

else

{

AverageBackup();

}

//printf("Flag = %d ",Flag);

}

else

{

MPI_Barrier(MPI_COMM_WORLD);

MPI_Bcast(Average,K,MPI_DOUBLE,0,MPI_COMM_WORLD);

i=0;

for(LocalStart=MyId*(N/ProcessNum);LocalStart<((MyId+1)*(N/ProcessNum));LocalStart++)

{

TemAveIndex=GetIndex(AllData[LocalStart],Average);

TemArray[i++]=TemAveIndex;

}

MPI_Send(TemArray,N/ProcessNum,MPI_INT,0,100,MPI_COMM_WORLD);

}

}

if(MyId==0)

{

Print();

}

MPI_Finalize();

//getchar();

return 0;

}