ism核心代码.cpp

用C语言编写的ISM算法

void Cub(int p,int m,int w[N][N])//求矩阵S的p次方，结果放入矩阵w中
{
	int i,j,k,q,v[N][N];
	for(i=0;i<m;i++)
		for(j=0;j<m;j++)
			{
			    w[i][j]=S[i][j];
				v[i][j]=S[i][j];
		}
	for(q=1;q<p;q++)
	{
		for(i=0;i<m;i++)
			for(j=0;j<m;j++)
				for(k=0,w[i][j]=0;k<m;k++)
					w[i][j]+=v[i][k]*S[k][j];
		for(i=0;i<m;i++)
			for(j=0;j<m;j++)
				v[i][j]=w[i][j];
	}
}

int Comp(int m,int p[N][N],int q[N][N])//比较两个矩阵是否相等
{
	int flag=1,i,j;
	for(i=0;i<m;i++)
		for(j=0;j<m;j++)
		{
			if(p[i][j]>1)
				p[i][j]=1;
			if(q[i][j]>1)
				q[i][j]=1;
		}
	for(i=0;i<m;i++)
	  if(flag==1)
	  {
		  for(j=0;j<m;j++)
	
			if(p[i][j]!=q[i][j])
			{
				flag=0; break;
			}
	  }
	  else break;
		return flag;
}

void CompM(int m)//求可达矩阵M
{
	int i,j,k=1,s,t;
  do
	{
		Cub(k,m,s1);
		Cub(k+1,m,s2);
		Cub(k+2,m,s3);
		k++;
		s=Comp(m,s1,s2);
		t=Comp(m,s2,s3);
	}
		while(!(s==0&&t==1));
	for(i=0;i<m;i++)
		for(j=0;j<m;j++)
			M[i][j]=s2[i][j];
}



void CompAs(int m)//求先行集合As
{
    int i,j,k;
	for(i=0;i<m;i++)
	   {
	     for(j=0,k=0;j<m;j++)
			if(M[j][i]==1)
			{
				As[i][j]=j+1; k++;
			}
		}
}

void PrinM(int m,int c[N][N])//将矩阵c打印输出
{
	int i,j;
	for(i=0;i<m;i++)
	{
		for(j=0;j<m;j++)
			printf("%5d",c[i][j]);
		printf("\n");
	}
}



	
void JJ(int m,int a[N][N],int b[N][N],int c[N][N])//求矩阵a和b的交集放入矩阵c中
{
	int i,j;
	for(i=0;i<m;i++)
		for(j=0;j<m;j++)
			if(a[i][j]==b[i][j])
				c[i][j]=a[i][j];
}

void CJR(int m,int a[N][N],int d[N][N],int c[N][N])//求层级关系，n代表层数
{
	int i,j,n,b,f;
	Ini(m,c);
    for(n=0;Equ(m,a,In)==0;n++)
		{ 
			for(i=0,b=0;i<m;i++)
			 if((LineC(a,i,m)==0)) 	
			{
				for(j=0;j<m;j++)
				  if(a[i][j]!=d[i][j])
					  break;
				  if(j==m)  { c[n][b]=i+1;   b++;}
             }
			for(f=0;f<b;f++)
				for(i=0;i<m;i++)
					if((i+1)==c[n][f])
						for(j=0;j<m;j++)
						{
							a[j][i]=0;
                            d[j][i]=0;
						}
   }
	printf("\n最后求得的层级关系如下:\n");
   for(i=0;i<n;i++)
   {
	   for(j=0;c[i][j]!=0;j++)
		   printf("%5d",c[i][j]);
	   printf("\n");
   }
}



void Zo(int m,int b)
{
	int i,j,n,f,Zo[N][N],Rs1[N][N],RsEqAs1[N][N];
    Ini(m,Zo);
	for(i=0;i<b;i++)
	   {
		   n=Bo[i]-1;
	     for(j=0;j<m;j++)
			 Zo[n][j]=Rs[n][j];
	   }
		 printf("进行比较前的区域情况：\n");
		 PrinM(m,Zo);
	   for(i=0;i<m;i++)
		   for(j=i+1;j<m;j++)
			   if(LineC(Zo,i,m)==0&&LineC(Zo,j,m)==0)
				   for(f=0;f<m;f++)
					   if(Zo[i][f]==Zo[j][f])
					   {
						   for(n=0;n<m;n++)
							   if(Zo[i][n]==0)
								   Zo[i][n]=Zo[j][n];
						   for(n=0;n<m;n++)
							   Zo[j][n]=0;
						   break;
					   }
	    printf("进行比较后的区域情况：\n");
		 PrinM(m,Zo);
     for(i=0;i<m;i++)
		   if(LineC(Zo,i,m)==0) 
		   {
			   Ini(m,Rs1);
			   Ini(m,RsEqAs1);
		     for(j=0;j<m;j++)
				 if(Zo[i][j]!=0)
				 {
					 f=Zo[i][j]-1;
					 for(b=0;b<m;b++)
					 {
						 Rs1[f][b]=Rs[f][b];
					     RsEqAs1[f][b]=RsEqAs[f][b];
					 }
				 }
			CJR(m,Rs1,RsEqAs1,CJ);
		   }
}	


void main()
{
	int b,m;
	printf("请输入矩阵的行数（最多不超过100）：\n");
	scanf("%d",&m);
	InA(m);//从键盘输入邻接矩阵A
	printf("邻接矩阵A为:\n");
	PrinM(m,A);//在屏幕上输出矩阵A
	IniI(m);//求单位矩阵I
	printf("单位矩阵I为:\n");
	PrinM(m,I);//在屏幕上输出单位矩阵I
	CompS(m);//求矩阵A和I的和S
	printf("A+I的和S为:\n");
	PrinM(m,S);//在屏幕上输出矩阵S
	CompM(m);//求可达矩阵M
	printf("求得可达矩阵M为:\n");
	PrinM(m,M);//在屏幕上输出可达矩阵M
	Ini(m,Rs);//初始化可达集合矩阵Rs,先行集合矩阵As,可达集合和先行集合的交集RsEqAs,先行集合和交集的交集AEs
	Ini(m,As);
	Ini(m,RsEqAs);
	Ini(m,AEs);
	CompRs(m);//求可达集合Rs
	printf("可达集合的矩阵为:\n");    
	PrinM(m,Rs);
    CompAs(m);//求先行集合As
	printf("先行集合为:\n");
	PrinM(m,As);
    JJ(m,Rs,As,RsEqAs);//求可达集合与先行集合的交集
    printf("可达集合与先行集合的交集为:\n");
	PrinM(m,RsEqAs);
	Ini(m,CJ);
	Ini(m,In);
	printf("最底层元素为:\n");
    b=SeB(m);//寻找最底层元素
   if(b==1)    CJR(m,Rs,RsEqAs,CJ);
   else     Zo(m,b);
}