length.cpp

可以求的网络的最短路径,直径,介数

// Length.cpp : implementation file
//

#include "stdafx.h"
#include "Length.h"
#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif

/////////////////////////////////////////////////////////////////////////////
// CLength

IMPLEMENT_DYNCREATE(CLength, CDocument)

CLength::CLength()
{
	int i;
	for(i=0;i<MAX;i++) vex_GShu[i]=0;
	a_length=total_length=0;
	length_number=0;
	max=520000;
	array=(int**)malloc(sizeof(int*)*(MAX));
}

BOOL CLength::OnNewDocument()
{
	if (!CDocument::OnNewDocument())
		return FALSE;
	return TRUE;
}

CLength::~CLength()
{
}


BEGIN_MESSAGE_MAP(CLength, CDocument)
	//{{AFX_MSG_MAP(CLength)
		// NOTE - the ClassWizard will add and remove mapping macros here.
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CLength diagnostics

#ifdef _DEBUG
void CLength::AssertValid() const
{
	CDocument::AssertValid();
}

void CLength::Dump(CDumpContext& dc) const
{
	CDocument::Dump(dc);
}
#endif //_DEBUG

/////////////////////////////////////////////////////////////////////////////
// CLength serialization

void CLength::Serialize(CArchive& ar)
{
	if (ar.IsStoring())
	{
		// TODO: add storing code here
	}
	else
	{
		// TODO: add loading code here
	}
}

/////////////////////////////////////////////////////////////////////////////
// CLength commands

void CLength::readdata()
{
	CString file_name;
	CStdioFile file1,file2;
	vector<int > vec;
	char s1[100],s2[100];
	int count,flag,stata,temp1,temp2,i,j,k;
	CFileDialog My_filedlg(TRUE,"txt","*.txt");
	My_filedlg.DoModal();
	file_name=My_filedlg.GetPathName();
	if (file1.Open(file_name,CFile::modeRead|CFile::typeText)==0)
	{
		AfxMessageBox("打开文件1:"+file_name+"失败!");
		return ;
	}
	My_filedlg.DoModal();
	file_name=My_filedlg.GetPathName();
	if (file2.Open(file_name,CFile::modeRead|CFile::typeText)==0)
	{
		AfxMessageBox("打开文件2:失败!");
		return ;
	}
	flag=stata=0;
	file1.ReadString(s1,100);
	file2.ReadString(s2,100);
	temp1=atoi(s1);
	temp2=atoi(s2);
    vec.push_back(temp2);
	count=1;
    for(i=1;i<max;i++)
	{
		file1.ReadString(s1,100);
		file2.ReadString(s2,100);
		temp1=atoi(s1);
		temp2=atoi(s2);
		/*if(i==156)
			j=0;*/
		if(stata==temp1)
		{
			flag=1;
			for(j=0;j<count;j++)
				if (temp2==vec[j]) 
					flag=0;
				if(flag)
				{
					vec.push_back(temp2);//加到数组后面
					count++;
				}
		}
		else
		{
			//换行处理
			array[stata]=(int*)malloc(sizeof(int)*(count+1));
			array[stata][0]=count;
			for(j=0;j<count;j++)
			{
				array[stata][j+1]=vec.back();
				vec.pop_back();
				k=vec.size();
			}
			
			while ((stata+1)!=temp1)
			{
				stata++;
				array[stata]=(int*)malloc(sizeof(int)*1);
				array[stata][0]=0;
			}
			stata=temp1;
			vec.push_back(temp2);
			count=1;
			//vec.clear();
		}
		j=0;
	}
	array[stata]=(int*)malloc(sizeof(int)*(count+1));
	array[stata][0]=count;
	for(j=0;j<count;j++)
	{
		array[stata][j+1]=vec.back();
		vec.pop_back();
		k=vec.size();
		}
	file1.Close();
	file2.Close();
}

void CLength::c_length()
{
		// TODO: Add your command handler code here
	node *p,*p_start,*p_end,*head;//p用于中间交换指针,*p_start用于当前访问的节点,
	                        //*p_end用于记录最后一个找到的节点.
	int flag[MAX+1];//用于标志当前访问节点的孩子节点是否被访问过
	int i,j,count,mmm;//count用于计数
	FILE* fp;
	//===================================
	//==================================
	int x,y;
	x=y=0;
	path_node tt;//临时变量节点
	for (i=0;i<MAX;i++) //从第一个节点开始,广度搜索整个邻接表,一层一层的搜索最短路径
	{
		for (j=0;j<MAX+1;j++) flag[j]=100000;
		flag[i]=0;//最短路径是否以求得标志
		head=p_start=p_end=new node;
		tt.length=p_start->length=0;
		p_start->next=NULL;
		tt.node_id=p_start->node_id=i;
		tt.father=-1;
		vec1.push_back(tt);
		count=0;
		int temp;
		temp=array[p_start->node_id][0];
		if (temp==0){	p=p_start;
						p_start=p_start->next;
						total_length=total_length+p->length;
						if (mmm<p->length) mmm=p->length;//求直径	
						delete p;
		}
		while (p_start!=NULL&&temp!=0&&p_end!=NULL)
		{
			
			for (j=0;j<array[p_start->node_id][0];j++)//*Array[p_start->node_id]邻接表第一个元素保存该节点的出度数
				{
					//if(flag[array[p_start->node_id][j+1]]==(p_start->length+1))
				//	{
				//		tt.father=count;
				//		tt.length=p_start->length+1;
				//		tt.node_id=array[p_start->node_id][j+1];
				//		vec1.push_back(tt);
				//	}
					if (flag[array[p_start->node_id][j+1]]>(p_start->length+1))//这里
					{
						p=new node;
						tt.length=p->length=p_start->length+1;
						tt.node_id=p->node_id=array[p_start->node_id][j+1];
						tt.father=count;
						vec1.push_back(tt);
						p->next=NULL;
						p_end->next=p;
						p_end=p;
						length_number=length_number+1;
						flag[array[p_start->node_id][j+1]]=tt.length;
						p_end=p;
					}
				}
				p=p_start;
				p_start=p_start->next;
				total_length=total_length+p->length;
				if (mmm<p->length) mmm=p->length;//求直径
				delete p;
				count++;
		}
		while (p_start!=NULL)
		{
			p=p_start;
			total_length=total_length+p->length;
			p_start=p->next;
			if (mmm<p->length) mmm=p->length;//求直径
			delete p;			
		}
		betweenness();
	}
	if ((fp=fopen("平均最短路径和网络直径.txt","w"))==0)
	{
		AfxMessageBox("donot open the file");
		return;
	}
	fprintf(fp,"最短路径总和是%f,  最短路径数是%f,    网络直径是:%f\n",total_length,length_number,mmm);
	fprintf(fp,"最短路径:%f,",total_length/length_number);
	fclose(fp);
/*	if ((fp=fopen("点介数分布.txt","w"))==0)
	{
		AfxMessageBox("donot open the file");
		return;
	}
	int xxxx;
	xxxx=MAX;
	for (i=1;i<MAX+1;i++) fprintf(fp,"%d\n",vex_GShu[i]);
	fclose(fp);
	for (i=1;i<MAX;i++) free(array[i]);	
	free(array);*/
}

void CLength::c()
{  
  int i,j,k,m,n=MAX;
  bool flage1;
                            
  struct  author *point,*point1;
  struct adjnode * pp1,*pp2;
 point=(struct author *)malloc(sizeof(struct author)*MAX);
 for(i=0;i<MAX;i++)
 {
	 (point+i)->nodenumber=i;
	 (point+i)->degree=0;
	 (point+i)->next1=NULL;
 }
for (i=0;i<MAX;i++)
{
	(point+i)->degree=array[i][0];
	if(array[i][0]==0) continue;
	pp2=(point+i)->next1;
	for (j=1;j<(array[i][0]+1);j++)
	{
		pp2=(point+i)->next1;
		pp1=(struct adjnode *)malloc(sizeof(struct adjnode));
		pp1->reader_number=array[i][j];
		(point+i)->next1=pp1;
		pp1->next=pp2;
	}
	for(j=0;j<MAX;j++)
	{
		if(i==j) continue;
		flage1=false;
		for(m=1;m<=array[i][0];m++)
			{
				if(array[i][m]==j)
				{
					flage1=true;
					break;
				}
			}
			if(flage1==true) continue;
			if(array[j][0]==0) continue;
			for(k=1;k<=array[j][0];k++)
			{
				if(array[j][k]==i)
				{
					pp2=(point+i)->next1;
					pp1=(struct adjnode *)malloc(sizeof(struct adjnode));
					pp1->reader_number=j;
					(point+i)->next1=pp1;
					pp1->next=pp2;
					(point+i)->degree=(point+i)->degree+1;
					break;
				}

			}
	}
}
///////////////////////////////////////////////////////////////////////////////////////////////////
FILE *fp;
	if((fp=fopen("无权算法簇系数.txt","w"))==NULL)  //创文本文件并在里面写每个节点的度
	{
	   AfxMessageBox("cannot open this file\n");
	   return;
	}
	int x,y,k1,k2,k3,mmm=0;
	struct adjnode *p1,*p2;
	float totalcluster=0,averagecluster=0;
	float *pcluster;      //开辟一个动态数组保存每个节点的簇系数
	pcluster=new float[n];//
    for(x=0;x<n;x++)     //节点循环
	{
	   pcluster[x]=0;
	   p1=(point+x)->next1;
	   float cdenominator=0;                 //节点i的簇系数分母
	   float cnumerator=0;                    //节点i的簇系数分子
	   int *p;                            //开辟动态数组保存
	   p=new int[(point+x)->degree];   // 保持节点x的所有邻居节点号
	   for(y=0;y<(point+x)->degree;y++)//
	       {
		       p[y]=p1->reader_number;
		       p1=p1->next;
	       }
	   int kkk;
	   kkk=(point+x)->degree;
	   if(kkk==0)
	   {
			mmm++;
			continue; 
	   }
	   else if (kkk==1)
	   {
			//pcluster[x]=0;
			continue;
	   }
	   else kkk=(kkk*(kkk-1))/2;
       cdenominator=(float)kkk;  //求de节点x的簇系数分母
	   k2=0;//
	   for( k1=0;k1<((point+x)->degree-1);k1++) //节点x的所有邻居节点循环
		{
				p2=(point+p[k1])->next1;
				while(p2!=NULL)                           //这两个循环查找
				{
					for( k3=k1+1;k3<(point+x)->degree;k3++)//k1相连 的x节点的邻居节点
					{
						if(p2->reader_number==p[k3])
						{
							k2=k2+1;        //x邻居节点的所有实际连接数
							break;
						}	
					}
			        p2=p2->next;
				}
		}  
       cnumerator=(float)k2;                       //x邻居节点的所有实际连接数就是簇系数分子
	   pcluster[x]=cnumerator/cdenominator;// 保存节点x的簇系数
	   totalcluster=totalcluster+pcluster[x];
	   delete []p;
	 }
       //averagecluster=totalcluster/(n-mmm);
	    averagecluster=totalcluster/n;
       fprintf(fp,"%f ",averagecluster);
       delete []pcluster;
	   fclose(fp);
/////////////////////////////////////////////////////////////////////////////////////////////////////////
}

void CLength::betweenness()
{
	int i;
	path_node tt;
	while (!vec1.empty())
	{
		tt=vec1.back();
		vec1.pop_back();
		i=tt.father;
		while (i!=-1)
		{
			vex_GShu[vec1[i].node_id]++;
			i=vec1[i].father;
		}
	}
	vec1.clear();
}