/*********************************  * Drawing the Higman-Sims Graph  * (C) 2008 Claudio Rocchini  * CC-BY 3.0  *********************************/  #include <stdio.h> #include <stdlib.h> #include <math.h>  #include <set> #include <vector> #include <map>  const double PI = 3.1415926535897932384626433832795;  static int Q( int x ) { return x*x; }  bool is_strong_regular( const int nv, bool MA[] ){ 	int i,j,k; 	 	std::vector<int> adj(nv); 	std::fill(adj.begin(),adj.end(),0); 	for(k=0;k<nv*nv;++k) if(MA[k]) { 		i = k%nv; j = k/nv; 		if(i<j) { ++adj[i]; ++adj[j]; } 	} 	for(i=1;i<nv;++i) if(adj[0]!=adj[i]) { 		printf("Error: different rank: %d, %d\n",adj[0],adj[i]); 		return false; 	} 	printf("OK rank: %d\n",adj[0]); 	 	int gni = -1; int gno = -1;		// lambda mu 	for(i=0;i<nv-1;++i) 	for(j=i+1;j<nv;++j) { 		int n = 0; 		for(k=0;k<nv;++k) if(k!=i && k!=j) 			if( MA[i*nv+k] && MA[j*nv+k] ) ++n; 		if( MA[i*nv+j] ) { 			if(gni==-1) gni = n; 			else if(gni!=n ) { 				printf("Error: different ni\n"); 				return false; 			} 		} else { 			if(gno==-1) gno = n; 			else if(gno!=n ) { 				printf("Error: different no\n"); 				return false; 			} 		} 	} 	printf("OK l:%d m:%d\n",gni,gno);  	return true; }  int main( int argc, char * argv[] ) { 	const int NV = 100; 	static int tri[100][3];		// Z4*Z5*Z5 	static bool MA[NV*NV]; static int  CO[NV*NV]; 	int i,j,k,n; 	 	n = 0; 	for(k=0;k<5;++k) 	for(j=0;j<5;++j) 	for(i=0;i<4;++i) { tri[n][0] = i; tri[n][1] = j; tri[n][2] = k; ++n; } 	printf("%d nodes\n",n);  	std::fill(MA,MA+NV*NV,false); 	std::fill(CO,CO+NV*NV,0    ); 	for(i=0;i<n;++i) 	for(j=0;j<n;++j) if(i!=j) { 		int * ti = tri[i]; 		int * tj = tri[j];  		int t = 0;  		if(ti[0]==0 && tj[0]==0 && ti[1]==tj[1] && ( (ti[2]-tj[2]+5)%5==1 || (ti[2]-tj[2]+5)%5==4 ) ) t |= 0x0001; 		if(ti[0]==1 && tj[0]==1 && ti[1]==tj[1] && ( (ti[2]-tj[2]+5)%5==2 || (ti[2]-tj[2]+5)%5==3 ) ) t |= 0x0002; 		if(ti[0]==2 && tj[0]==2 && ti[1]==tj[1] && ( (ti[2]-tj[2]+5)%5==1 || (ti[2]-tj[2]+5)%5==4 ) ) t |= 0x0004; 		if(ti[0]==3 && tj[0]==3 && ti[1]==tj[1] && ( (ti[2]-tj[2]+5)%5==2 || (ti[2]-tj[2]+5)%5==3 ) ) t |= 0x0008; 		if(ti[0]==0 && tj[0]==1 &&(     ti[1]*tj[1] +tj[2]+5000)%5==ti[2] ) t |= 0x0010;							 		if(ti[0]==1 && tj[0]==2 && (2*Q(ti[1]-tj[1])+tj[2]+5000)%5==ti[2] ) t |= 0x0020;							 		if(ti[0]==3 && tj[0]==0 && (  Q(tj[1]-ti[1])+ti[2]+5000)%5==tj[2] ) t |= 0x0080;							 		if(ti[0]==2 && tj[0]==3 && (2*Q(ti[1])+3*(ti[1]*tj[1])-Q(tj[1])+tj[2]+5000)%5==ti[2] ) t |= 0x0040;		 		if(ti[0]==0 && tj[0]==2 && ( (3*Q(ti[1])+ti[1]*tj[1]+tj[2] +1 +5000)%5==ti[2] || 								   (3*Q(ti[1])+ti[1]*tj[1]+tj[2] -1 +5000)%5==ti[2] ) )  t |= 	0x0100; 		if(ti[0]==1 && tj[0]==3 && ( (  Q(ti[1])-ti[1]*tj[1]+tj[2] +2 +5000)%5==ti[2] ||  								   (  Q(ti[1])-ti[1]*tj[1]+tj[2] -2 +5000)%5==ti[2] ) )  t |=  0x0200; 		if(t) { 			MA[i+NV*j] =     MA[j+NV*i] = true; 			CO[i+NV*j] |= t; CO[j+NV*i] |= t; 		} 	}  	std::map<int,int> stats; 	for(i=0;i<NV*NV;++i) if(CO[i]) ++stats[CO[i]]; 	std::map<int,int>::iterator ii; 	int ne = 0; 	for(ii=stats.begin();ii!=stats.end();++ii) 	{ 		printf("color %04X: %d\n",(*ii).first,(*ii).second/2); 		ne += (*ii).second/2; 	} 	printf("TOTAL: %d arcs\n",ne);  	is_strong_regular(100,MA);		// check!  	for(int v=0;v<2;++v){ 		const double SX = 800; 		const double SY = v==0 ? 800 : 400; 		const double B  = 16; 		const double R  = v==0 ? 3 : 1;  		char filename[256]; 		sprintf(filename,"c:\\temp\\higman_Sims%d.svg",v+1); 		FILE * fp = fopen(filename,"w");  		fprintf(fp, 			"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n" 			"<svg\n" 			"xmlns:svg=\"http://www.w3.org/2000/svg\"\n" 			"xmlns=\"http://www.w3.org/2000/svg\"\n" 			"version=\"1.0\"\n" 			"width=\"%g\"\n" 			"height=\"%g\"\n" 			"id=\"HigmanSimsGraph\">\n" 			,SX,SY 		);  		static double xx[NV]; 		static double yy[NV]; 		int i,j;  		for(i=0;i<NV;++i){ 			const double a = 2*PI*i/NV; 			const double r = v==0 ? (SX-2*B)/2: (SX-2*B)/11; 			xx[i] = r*cos(a); 			yy[i] = r*sin(a); 		}  		const char * colors[10] = { 			"0d0d80", 			"80590d", 			"590d80", 			"800d0d", 			"0d5980", 			"0d8059", 			"59800d", 			"0d800d", 			"800d59", 			"808080", 		};  		int tote = 0; 		for(k=10;k>0;--k){ 			fprintf(fp, 				"<g id=\"edge_layer%d\" style=\"stroke:#%s;stroke-width:%g;stroke-opacity:1.0;\">\n" 				,k 				,colors[k-1] 				,v==0 ? 0.75 : 0.5 			);	 			double ox = v==0 ? SX/2 : SX/2+(SX/5)*((k-1)%5-2); 			double oy = v==0 ? SY/2 : SY/4+(SY/2)*((k-1)/5);  			for(i=0;i<NV-1;++i) 			for(j=i+1;j<NV;++j) 				if(MA[i+NV*j] && CO[i+NV*j]==(1<<(k-1))){ 					fprintf(fp, 						"<line x1=\"%5.1lf\" y1=\"%5.1lf\" x2=\"%5.1lf\" y2=\"%5.1lf\"/>\n" 						,ox+xx[i],oy+yy[i] 						,ox+xx[j],oy+yy[j] 					); 					++tote; 				} 			fprintf(fp, "</g>\n");  			if(v==1 || k==1){ 				fprintf(fp, 					"<g id=\"node_layer\" style=\"fill:#000000;stroke:#000000;stroke-width:1;stroke-opacity:1.0;\">\n"	 				);	 				for(i=0;i<NV;++i) 					fprintf(fp,"<circle cx=\"%5.1lf\" cy=\"%5.1lf\" r=\"%5.1lf\" />\n" 						,ox+xx[i],oy+yy[i],R 					); 				fprintf(fp, "</g>\n" ); 			} 		} 		if(v==0) printf("tot edges: %d\n",tote); 		fprintf(fp, "</svg>\n" ); 		fclose(fp); 	}  	return 0; }