#include <stdio.h>#include <iostream.h>#include <vector>#include <algorithm>#include <stdlib.h>  #include <time.h>   
#include <fstream>using   namespace   std;   #define CLUSTERRADIUS 30#define ROOT 2#define NORMAL 1#define NOTINITIALED 0//int nodeStatus[1000];vector<vector<float> > nodeInfo(1000,vector<float>(0));int nodeCount = 0;int rootCount = 0;float avgDistance[1000];float x = 0.000;
void Display()//輸出每個節點的聚類信息{
	ofstream   outFile;
	outFile.open("D:\\研究生\\dumpling\\out.txt",ios::out);	//rootCount = 0;	for( int k = 0 ; k < 1000 ; k++ )		avgDistance[k] = 0;		/*for(int a = 0 ; a < nodeCount ; a++)	{		cout<<nodeInfo[a][0]<<"  ";	}*/	cout<<endl;    cout<<"*******************************************************************************"<<endl;	for(int b = 0 ; b < nodeCount ; b++)	{		cout<<b<<"           ";		for(int c = 0 ; c < nodeInfo[b].size() ; c++)
		{
			if(c == 0)
			{
				if(nodeInfo[b][c] == ROOT)
					cout<<"R"<<"           ";
				else if(nodeInfo[b][c] == NORMAL)
					cout<<"N"<<"           ";
			}
			else				cout<<nodeInfo[b][c]<<"           ";
		}		cout<<endl;	}	    cout<<"*******************************************************************************"<<endl;	for(int e = 0 ; e < nodeCount ; e++)	{		if(nodeInfo[e][0] == ROOT)		{			float sum = 0;			//rootCount++;			for(int t = 2 ; t <  nodeInfo[e].size() ; t++)				sum = sum + nodeInfo[nodeInfo[e][t]][1];						if(nodeInfo[e].size() > 2)//非孤島節點				avgDistance[e] = sum/(nodeInfo[e].size() - 2);		}			}
	cout<<"系統中共有 "<<rootCount<<" 個聚類"<<endl;	cout<<"每個聚類根節點以及聚類節點平均距離信息如下："<<endl;	cout<<"根節點ID"<<"      平均距離"<<endl;	for(int h = 0 ; h < nodeCount ; h++)	{
		//int decimal, sign;  
		char avgDst[10];
		char rID[10];
		for(int i = 0 ; i < 10 ; i++)
		{
			avgDst[i] = NULL;
			rID[i] = NULL;
		}
		gcvt(avgDistance[h],8,avgDst);
		//avgDst = _fcvt( avgDistance[h], 7, &decimal, &sign ); 
		//cout<<"*****"<<avgDst<<"*****"<<endl;
		itoa(h,rID,10);		if(nodeInfo[h].size() == 2)
		{			cout<<"   "<<h<<"          "<<avgDistance[h]<<endl;
			outFile.write(rID,sizeof(rID)); 
			outFile.write(avgDst,sizeof(avgDst));
			outFile.write("\n",1);
		}		else if(avgDistance[h] != 0)
		{
			cout<<"   "<<h<<"          "<<avgDistance[h]<<endl;
            outFile.write(rID,sizeof(rID)); 
			outFile.write(avgDst,sizeof(avgDst));
			outFile.write("\n",1);
		}	}	cout<<"*******************************************************************************"<<endl;}void main(){    FILE *file;	int ID1,ID2;	float radius;
	ofstream   rootCountFile;
	int w = 1;
	
	rootCountFile.open("D:\\研究生\\dumpling\\rootCount.txt",ios::out);
	cout<<"請輸入網絡中的節點個數:";
	cin>>nodeCount;
    for( int k = 0 ; k < nodeCount ; k++ )	{		nodeInfo[k].push_back(0);		//avgDistance[k] = 0;	}	if ((file = fopen("D:\\研究生\\dumpling\\nodetest.txt","r") ) == NULL)	{		cout<<"error"<<endl;	    fclose(file);  		return;	}     
	//outFile.write("第一次循環中每讀取一行rootCount數的變化：\n",sizeof("第一次循環中每讀取一行rootCount數的變化：\n")); 
	//第一個循環，消除未分配節點，初步聚類形成	for( long i = 0 ; i < (nodeCount*(nodeCount-1)/2 ) ; i++)	{		fscanf(file,"%d",&ID1);		fscanf(file,"%d",&ID2);		fscanf(file,"%f",&radius);		x = x + radius;			//兩個節點均未分配		if((nodeInfo[ID1][0] == NOTINITIALED)&&(nodeInfo[ID2][0] == NOTINITIALED) )		{			if(radius <= CLUSTERRADIUS)			{
				rootCount++;				nodeInfo[ID1][0] = ROOT;				nodeInfo[ID1].push_back(0);				nodeInfo[ID1].push_back(ID2);					nodeInfo[ID2][0] = NORMAL;				nodeInfo[ID2].push_back(radius);				nodeInfo[ID2].push_back(ID1);   			}						}//end of 兩個節點均未初始化			//一個為根節點，一個為未分配節點	    else if(((nodeInfo[ID1][0] == ROOT)&&(nodeInfo[ID2][0] == NOTINITIALED))				||((nodeInfo[ID2][0] == ROOT)&&(nodeInfo[ID1][0] == NOTINITIALED)))		{			int t = ID1;			if(nodeInfo[ID2][0] == ROOT)			{				ID1 = ID2;				ID2 = t;			}			if((radius <= CLUSTERRADIUS))			{				nodeInfo[ID1].push_back(ID2);					nodeInfo[ID2][0] = NORMAL;				nodeInfo[ID2].push_back(radius);				nodeInfo[ID2].push_back(ID1);			}		}			//一個為普通節點，一個為未分配節點		else if(((nodeInfo[ID1][0] == NORMAL)&&(nodeInfo[ID2][0] == NOTINITIALED))				  ||((nodeInfo[ID2][0] == NORMAL)&&(nodeInfo[ID1][0] == NOTINITIALED)))		{			int t = ID1;			if(nodeInfo[ID2][0] == NORMAL)			{				ID1 = ID2;				ID2 = t;			}			if(((radius + nodeInfo[ID1][1]) <= CLUSTERRADIUS))			{					 //cout<<"!!!!!!!!!!!!!!!!!!!!!!!!!!!!!"<<endl<<ID1<<"     "<<ID2<<endl;				nodeInfo[nodeInfo[ID1][2]].push_back(ID2);					nodeInfo[ID2][0] = NORMAL;				nodeInfo[ID2].push_back(radius + nodeInfo[ID1][1]);				nodeInfo[ID2].push_back(nodeInfo[ID1][2]);			}						}
			
		char hc[10];//記錄當前讀取節點文件的行數
		char rc[10];//記錄每讀取一行后，rootCount數的變化
		
		for(int j = 0 ; j < 10 ; j++)
		{
			rc[j] = NULL;
			hc[j] = NULL;
		}
			
		itoa(i,hc,10);
		itoa(rootCount,rc,10);
            
		if(i == 0)
		{
			rootCountFile.write(hc,sizeof(hc));
			rootCountFile.write(rc,sizeof(rc));
			rootCountFile.write("\n",1);
		}
			//cout<<hc<<"******"<<rc<<endl;
		else if(i/w == 1000)
		{
				//itoa(i/40,hc,10);
			rootCountFile.write(hc,sizeof(hc));
			rootCountFile.write(rc,sizeof(rc));
			rootCountFile.write("\n",1);
			w++;
		}	}//end of for    	//文件第一遍掃描完畢后仍有節點是未分配狀態，將其設置為根節點，為孤島	for(int m = 0; m < nodeCount ; m++)	{		if(nodeInfo[m][0] == NOTINITIALED)		{			nodeInfo[m][0] = ROOT;			nodeInfo[m].push_back(0);
			rootCount++;		}	}	cout<<endl<<"第一次循環"<<endl;    Display();    fclose(file);    if ((file = fopen("D:\\研究生\\dumpling\\nodetest.txt","r") ) == NULL)	{		cout<<"error"<<endl;	    fclose(file);  		return;	} 	    /*vector<int> randomNumber;//存放隨機整數    srand(   (unsigned)time(   NULL   )   );       for(int l = 0 ; l < nodeCount*(nodeCount-1)/4 ; l++)   	{        randomNumber.push_back(rand()%(nodeCount*(nodeCount-1)/2));        //printf(   "     %6d\n",   rand()%nodeCount   ); 	}*/	
	//outFile.write("\n第二次循環中每讀取一行rootCount數的變化：\n",sizeof("第二次循環中每讀取一行rootCount數的變化：\n")); 

	//第二個循環，優化聚類
	for( long n = 0 ; n < (nodeCount*(nodeCount-1)/2 ) ; n++)	//for( int n = 0 ; n <  (nodeCount*(nodeCount-1)/4 ); n++)	{		//for(int u = 0 ; u < randomNumber[n] ; u++)		//{		fscanf(file,"%d",&ID1);		fscanf(file,"%d",&ID2);		fscanf(file,"%f",&radius);		//}        //cout<<endl<<ID1<<"     "<<ID2<<endl;		//根節點遇到不同聚類中的普通節點		if(((nodeInfo[ID1][0] == NORMAL)&&(nodeInfo[ID2][0] == ROOT))		   ||((nodeInfo[ID2][0] == ROOT)&&(nodeInfo[ID1][0] == NORMAL)))		{//cout<<"111111111111111111111111111"<<endl<<ID1<<"     "<<ID2<<endl;			int t = ID1;			if(nodeInfo[ID2][0] == ROOT)			{				ID1 = ID2;				ID2 = t;			}			if(nodeInfo[ID2][1] > radius)			{//cout<<"222222222222222222222222"<<endl<<ID1<<"     "<<ID2<<endl;				nodeInfo[ID1].push_back(ID2);				int t = nodeInfo[ID2][2];				nodeInfo[t].erase(remove(nodeInfo[t].begin(),nodeInfo[t].end(),ID2),nodeInfo[t].end());				nodeInfo[ID2][1] = radius;				nodeInfo[ID2][2] = ID1;			}		}        //兩個普通節點相遇，無論是否屬于同一聚類		//若有跨過另一普通節點到某根的距離比現狀更近的情況		//則加入另一聚類，或者更新在本聚類到根的距離信息		/*else if((nodeStatus[ID1] == NORMAL)&&(nodeStatus[ID2] == NORMAL))		{			if(((radius + nodeInfo[ID1][0]) < nodeInfo[ID2][0]))			{cout<<"@@@@@@@@@@@@@@@@@@@@@@@@@@@@"<<endl<<ID1<<"     "<<ID2<<endl;			cout<<nodeInfo[ID1][1]<<endl;			cout<<nodeInfo[ID2][1]<<endl;				nodeInfo[nodeInfo[ID1][1]].push_back(ID2);//這步為什么沒做？？？					nodeInfo[ID2][0] = radius + nodeInfo[ID1][0];				nodeInfo[ID2][1] = nodeInfo[ID1][1];                int t = nodeInfo[ID2][1];				////這步為什么沒做？？？				nodeInfo[t].erase(remove(nodeInfo[t].begin(),nodeInfo[t].end(),ID2),nodeInfo[t].end());			}			else if(((radius + nodeInfo[ID2][0]) < nodeInfo[ID1][0]))			{cout<<"%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%"<<endl<<ID1<<"     "<<ID2<<endl;				nodeInfo[nodeInfo[ID2][1]].push_back(ID1);					nodeInfo[ID1][0] = radius + nodeInfo[ID2][0];				nodeInfo[ID1][1] = nodeInfo[ID2][1];				int t = nodeInfo[ID1][1];				nodeInfo[t].erase(remove(nodeInfo[t].begin(),nodeInfo[t].end(),ID2),nodeInfo[t].end());			}		}*/        		//兩個均為根節點		else if((nodeInfo[ID1][0] == ROOT)&&(nodeInfo[ID2][0] == ROOT))		{//cout<<"333333333333333333333333333333333"<<endl<<ID1<<"     "<<ID2<<endl;			//兩個均為孤島節點			if((nodeInfo[ID1].size() == 2)&&(nodeInfo[ID2].size() == 2)) 				if(radius < CLUSTERRADIUS)				{//cout<<"444444444444444444444444444444444"<<endl<<ID1<<"     "<<ID2<<endl;					nodeInfo[ID2][0] = NORMAL;					nodeInfo[ID2][1] = radius;					nodeInfo[ID2].push_back(ID1);
					rootCount--;				}            //有一個是孤島節點			else if((nodeInfo[ID1].size() == 2)||(nodeInfo[ID2].size() == 2))			{//cout<<"555555555555555555555555555555555555555"<<endl<<ID1<<"     "<<ID2<<endl;				int t = ID1;				if(nodeInfo[ID1].size() == 2)				{					ID1 = ID2;					ID2 = t;				}				if(radius < CLUSTERRADIUS)				{//cout<<"666666666666666666666666666666666666666"<<endl<<ID1<<"     "<<ID2<<endl;					nodeInfo[ID2][0] = NORMAL;					nodeInfo[ID2][1] = radius;					nodeInfo[ID2].push_back(ID1);
					rootCount--;				}			}			//兩個均為非孤島根節點			else if((nodeInfo[ID1].size() > 1)&&(nodeInfo[ID2].size() > 1))			{}		}

		/*for(int j = 0 ; j < 7 ; j++)
			rc[j] = NULL;
		itoa(rootCount,rc,10);
		outFile.write(rc,sizeof(rc));*/	}//end of for		cout<<endl<<"第二次循環"<<endl;    Display();
	cout<<"兩節點間平均距離為："<<(x/(nodeCount*(nodeCount-1)/2 ))<<endl;

	cout<<"各根節點包含普通節點數目信息："<<endl;
	for(int v = 0 ; v < nodeCount ; v ++)
	{
		if(nodeInfo[v][0] == ROOT)
			cout<<v<<"    "<<(nodeInfo[v].size() - 2)<<endl;
	}    fclose(file);}