/*********************************
 * 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;
}