my dumpling.cpp

一种基于网络节点距离（节点间RTT值）

#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);
}