Jump to content

File:Higman Sims Graph.svg

Page contents not supported in other languages.
This is a file from the Wikimedia Commons
From Wikipedia, the free encyclopedia

Original file (SVG file, nominally 800 × 800 pixels, file size: 62 KB)

Summary

Description
English: Higman Sims Graph drawing, based on the construction of Paul R. Hafner: "On the Graphs of Hoffman-Singleton and Higman-Sims", The Electronic Journal of combinatorics 11 (2004).
Source Own work
Author Claudio Rocchini

Source Code

The dirty C++ source code (contains also some auto-checks):

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

Licensing

I, the copyright holder of this work, hereby publish it under the following licenses:
GNU head Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation; with no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts. A copy of the license is included in the section entitled GNU Free Documentation License.
w:en:Creative Commons
attribution
This file is licensed under the Creative Commons Attribution 3.0 Unported license.
You are free:
  • to share – to copy, distribute and transmit the work
  • to remix – to adapt the work
Under the following conditions:
  • attribution – You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
You may select the license of your choice.

Captions

Add a one-line explanation of what this file represents

Items portrayed in this file

depicts

image/svg+xml

File history

Click on a date/time to view the file as it appeared at that time.

Date/TimeThumbnailDimensionsUserComment
current12:23, 19 June 2008Thumbnail for version as of 12:23, 19 June 2008800 × 800 (62 KB)Rocchini{{Information |Description={{en|1=Higman Sims Graph drawing, based on the construction of Paul R. Hafner: "On the Graphs of Hoffman-Singleton and Higman-Sims", The Electronic Journal of combinatorics 11 (2004). }} |Source=Opera creata dall'uploader (ow

Global file usage

The following other wikis use this file: