/*********************************
* 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(MAk]) {
i = k%nv; j = k/nv;
if(i<j) { ++adji]; ++adjj]; }
}
for(i=1;i<nv;++i) if(adj0!=adji]) {
printf("Error: different rank: %d, %d\n",adj0],adji]);
return false;
}
printf("OK rank: %d\n",adj0]);
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( MAi*nv+k && MAj*nv+k ) ++n;
if( MAi*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 tri100][3]; // Z4*Z5*Z5
static bool MANV*NV]; static int CONV*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) { trin][0 = i; trin][1 = j; trin][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 = trii];
int * tj = trij];
int t = 0;
if(ti0==0 && tj0==0 && ti1==tj1 && ( (ti2-tj2+5)%5==1 || (ti2-tj2+5)%5==4 ) ) t |= 0x0001;
if(ti0==1 && tj0==1 && ti1==tj1 && ( (ti2-tj2+5)%5==2 || (ti2-tj2+5)%5==3 ) ) t |= 0x0002;
if(ti0==2 && tj0==2 && ti1==tj1 && ( (ti2-tj2+5)%5==1 || (ti2-tj2+5)%5==4 ) ) t |= 0x0004;
if(ti0==3 && tj0==3 && ti1==tj1 && ( (ti2-tj2+5)%5==2 || (ti2-tj2+5)%5==3 ) ) t |= 0x0008;
if(ti0==0 && tj0==1 &&( ti1*tj1 +tj2+5000)%5==ti2 ) t |= 0x0010;
if(ti0==1 && tj0==2 && (2*Q(ti1-tj1])+tj2+5000)%5==ti2 ) t |= 0x0020;
if(ti0==3 && tj0==0 && ( Q(tj1-ti1])+ti2+5000)%5==tj2 ) t |= 0x0080;
if(ti0==2 && tj0==3 && (2*Q(ti1])+3*(ti1*tj1])-Q(tj1])+tj2+5000)%5==ti2 ) t |= 0x0040;
if(ti0==0 && tj0==2 && ( (3*Q(ti1])+ti1*tj1+tj2 +1 +5000)%5==ti2 ||
(3*Q(ti1])+ti1*tj1+tj2 -1 +5000)%5==ti2 ) ) t |= 0x0100;
if(ti0==1 && tj0==3 && ( ( Q(ti1])-ti1*tj1+tj2 +2 +5000)%5==ti2 ||
( Q(ti1])-ti1*tj1+tj2 -2 +5000)%5==ti2 ) ) t |= 0x0200;
if(t) {
MAi+NV*j = MAj+NV*i = true;
COi+NV*j |= t; COj+NV*i |= t;
}
}
std::map<int,int> stats;
for(i=0;i<NV*NV;++i) if(COi]) ++statsCOi]];
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 filename256];
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 xxNV];
static double yyNV];
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;
xxi = r*cos(a);
yyi = r*sin(a);
}
const char * colors10 = {
"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
,colorsk-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(MAi+NV*j && COi+NV*j==(1<<(k-1))){
fprintf(fp,
"<line x1=\"%5.1lf\" y1=\"%5.1lf\" x2=\"%5.1lf\" y2=\"%5.1lf\"/>\n"
,ox+xxi],oy+yyi
,ox+xxj],oy+yyj
);
++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+xxi],oy+yyi],R
);
fprintf(fp, "</g>\n" );
}
}
if(v==0) printf("tot edges: %d\n",tote);
fprintf(fp, "</svg>\n" );
fclose(fp);
}
return 0;
}