// Please read "readme.txt" first. #include #include #include #include #include using namespace std; int SizeOfMatrix,SizeOfMatrixUnfolding,NumberOfMatrix,Matrix[12][12],MatrixUnfolding[12][12], List[100000][12][12],ListUnfolding[100000][12][12],LengthOfList,Depth,E[12][15] ; int e[5]; FILE* f, * file, * fl, * fnew; char NameOfInput[100],NameOfOutput[100]; void copy_matrix(int M[12][12],int M1[12][12], int dim){ for(int i=1;i<=dim;i++) for(int j=1;j<=dim;j++) M1[i][j]=M[i][j]; } void read_matrices(){ int k; fscanf(file,"%d ",&NumberOfMatrix); fscanf(file,"%d ",&SizeOfMatrix); for(int i=1;i<=SizeOfMatrix;i++) for(int j=1;j<=SizeOfMatrix;j++) fscanf(file,"%d ",&Matrix[i][j]); fscanf(file,"%d ",&Depth); k=0; for(int i=1;i<=SizeOfMatrix;i++){ fscanf(file,"%d ",&e[i]); for(int j=1;j<=e[i];j++){ k++; E[i][j]=k; } } fscanf(file,"%d ",&SizeOfMatrixUnfolding); for(int i=1;i<=SizeOfMatrixUnfolding;i++) for(int j=1;j<=SizeOfMatrixUnfolding;j++) fscanf(file,"%d ",&MatrixUnfolding[i][j]); } void print_matrix(int n, int M[12][12]){ f=fopen(NameOfOutput,"a"); fprintf(f,"\n \n SizeOfMatrix=%d \n NumberOfMatrix=%d \n Matrix= " ,n,NumberOfMatrix); for(int i=1;i<=n;i++){ fprintf(f," \n "); for(int j=1;j<=n;j++) if(M[i][j]>=0) fprintf(f," %d",M[i][j]); else fprintf(f," %d",M[i][j]); } fclose(f); } void put_to_List(int ML[12][12],int MU[12][12]){ LengthOfList++; for(int i=1;i<=SizeOfMatrix;i++) for(int j=1;j<=SizeOfMatrix;j++) List[LengthOfList][i][j]=ML[i][j]; for(int i=1;i<=SizeOfMatrixUnfolding;i++) for(int j=1;j<=SizeOfMatrixUnfolding;j++) ListUnfolding[LengthOfList][i][j]=MU[i][j]; } int sgn(int a){ if(a>0) return 1; if(a==0) return 0; if(a<0) return -1; } void mutation(int M1[12][12],int dim,int k){ int M2[12][12]; copy_matrix(M1,M2,dim); for(int i=1;i<=dim;i++) for(int j=1;j<=dim;j++) M1[i][j]=-M2[i][j]*(1-abs(sgn((i-k)*(j-k))))+(M2[i][j]+sgn(M2[i][k])*max(0,M2[i][k]*M2[k][j]))*abs(sgn((i-k)*(j-k))); } int sum_g(int n,int d){ int tmp; if(d<=-1) return 0; else{ tmp=1; for(int i=1;i<=d;i++) tmp=n*tmp+1; return tmp; } } void create_list(){ int ML[12][12],MU[12][12],ML1[12][12],MU1[12][12],cmin,cmax; copy_matrix(Matrix,ML,SizeOfMatrix); copy_matrix(MatrixUnfolding,MU,SizeOfMatrixUnfolding); LengthOfList=0; put_to_List(ML,MU); for(int d=1;d<=Depth+1;d++){ cmin=sum_g(SizeOfMatrix,d-2)+1; cmax=sum_g(SizeOfMatrix,d-1); for(int c=cmin;c<=cmax;c++){ copy_matrix(List[c],ML,SizeOfMatrix); copy_matrix(ListUnfolding[c],MU,SizeOfMatrixUnfolding); for(int i=1;i<=SizeOfMatrix;i++){ copy_matrix(ML,ML1,SizeOfMatrix); copy_matrix(MU,MU1,SizeOfMatrixUnfolding); mutation(ML1,SizeOfMatrix,i); for(int j=1;j<=e[i];j++) mutation(MU1,SizeOfMatrixUnfolding,E[i][j]); put_to_List(ML1,MU1); } } } } bool is_A(int ML[12][12], int MU[12][12]){ for(int j=1;j<=SizeOfMatrix;j++) for(int k=1;k<=e[j];k++) for(int l=1;l<=e[j];l++) if(MU[E[j][k]][E[j][l]]!=0) return false; return true; } bool is_B(int ML[12][12],int MU[12][12]){ int b; for(int j=1;j<=SizeOfMatrix;j++) for(int k=1;k<=e[j];k++) for(int i=1;i<=SizeOfMatrix;i++){ b=ML[i][j]; for(int l=1;l<=e[i];l++) b=b-MU[E[i][l]][E[j][k]]; if(b!=0) return false; } return true; } bool is_C(int ML[12][12], int MU[12][12]){ for(int j=1;j<=SizeOfMatrix;j++) for(int k=1;k<=e[j];k++) for(int i=1;i<=SizeOfMatrix;i++) for(int l=1;l<=e[i];l++) if(sgn(MU[E[i][l]][E[j][k]])*sgn(ML[i][j])==-1) return false; return true; } bool is_admissible_unfolding(int ML[12][12], int MU[12][12]){ if((is_A(ML,MU))&&(is_B(ML,MU))&&(is_C(ML,MU))) return true; else return false; } void is_correct_unfolding(){ int i; for(i=1;i<=LengthOfList;i++) if(!is_admissible_unfolding(List[i],ListUnfolding[i])){ fopen(NameOfOutput,"a"); fprintf(f,"\n FAIL i=%d \n",i); fclose(f); print_matrix(SizeOfMatrix,List[i]); print_matrix(SizeOfMatrixUnfolding,ListUnfolding[i]); i=LengthOfList+10; } if(i==LengthOfList+1){ f=fopen(NameOfOutput,"a"); fprintf(f,"\n LengthOfList =%d, Depth=%d \n",LengthOfList,Depth); fprintf(f,"\n OK \n"); fclose(f); } } int main(){ printf("\nPrint input filename: "); scanf("%s", NameOfInput); file=fopen(NameOfInput,"r"); printf("\nPrint output filename: "); scanf("%s", NameOfOutput); f=fopen(NameOfOutput,"w"); fclose(f); while (!feof(file)){ read_matrices(); print_matrix(SizeOfMatrix,Matrix); create_list(); is_correct_unfolding(); } fclose(file); printf("\n Finished \n"); return 0; }