Jump to content

File:Brouwer Haemers 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: 728 KB)

Summary

Description
English: Brouwer-Haemers graph: some random symmetric embeddings
Date
Source Own work
Author Claudio Rocchini

Licensing

I, the copyright holder of this work, hereby publish it under the following licenses:
w:en:Creative Commons
attribution share alike
This file is licensed under the Creative Commons Attribution-Share Alike 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.
  • share alike – If you remix, transform, or build upon the material, you must distribute your contributions under the same or compatible license as the original.
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.
You may select the license of your choice.

Note

Many Thanks to nauty for autos.

Source Code

The complete C++ source code! Needs Nauty to find autos.

/************************************************************************
 * making of Brouwer_Haemers_Graph                                      *
 * Copyright (C) 2010                                                   *
 *   Claudio Rocchini                                                   *
 *   All rights reserved.                                               *
 * This program is free software: you can redistribute it and/or modify *
 * it under the terms of the GNU General Public License as published by *
 * the Free  Software Foundation,  either version  3 of the License, or *
 * (at your option) any later version.                                  *
 *   This program is distributed in the hope that it will be useful,    *
 *   but WITHOUT ANY WARRANTY; without even the implied  warranty of    *
 *   MERCHANTABILITY  or FITNESS  FOR A  PARTICULAR PURPOSE. See the    *
 *   GNU General Public License for more details.                       *
 * You should have  received a  copy of the GNU  General Public License *
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.*
 ************************************************************************/
 
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <vector>
#include <set>
#include <algorithm>

const double PI = 3.1415926535897932384626433832795;

typedef std::pair<int,int> edge;

class permu {
public:
	std::vector<size_t> p;
	void ident( size_t n ) {
		p.resize(n);
		for(size_t i=0;i<n;++i) p[i] = i;
	}
};
void copy( permu & dst, const permu & src ) {
	dst.p.resize(src.p.size());
	std::copy(src.p.begin(),src.p.end(),dst.p.begin());
}
void apply( permu & dst, const size_t perm[] ) {
	permu t; copy(t,dst);
	for(size_t i=0;i<dst.p.size();++i)
		dst.p[i] = t.p[perm[i]];
}
void apply( permu & dst, const int perm[] ) {
	permu t; copy(t,dst);
	for(size_t i=0;i<dst.p.size();++i)
		dst.p[i] = t.p[perm[i]];
}
bool operator== (const permu & a, const permu & b) {
	std::vector<size_t>::const_iterator i,j;
	for(i=a.p.begin(),j=b.p.begin();i!=a.p.end();++i,++j)
		if(*i!=*j) return false;
	return true;
}
bool operator< (const permu & a, const permu & b) {
	std::vector<size_t>::const_iterator i,j;
	for(i=a.p.begin(),j=b.p.begin();i!=a.p.end();++i,++j)
		if(*i!=*j) return *i < *j;
	return false;
}
size_t fix_point( const permu & pe ) {
	size_t fix = 0;
	for(size_t j=0;j<pe.p.size();++j)
		if(pe.p[j]==j) ++fix;
	return fix;
}
size_t cicle_size( const permu & pe ) {
	permu t; copy(t,pe); size_t cs = 0;
	for(;;) {
		apply(t,& pe.p.front());
		++cs;
		if(t==pe) break;
	}
	return cs;
}
size_t sub_loops( const permu & pe, std::vector< std::vector<size_t> > & loops ) {
	std::vector<bool> done(pe.p.size()); std::fill(done.begin(),done.end(),false);
	loops.clear();
	for(;;) {
		size_t i;
		for(i=0;i<pe.p.size();++i) if(!done[i]) break;
		if(i==pe.p.size()) break;
		loops.push_back( std::vector<size_t>() );
		size_t j = i;
		do {
			done[j] = true;
			loops.back().push_back(j);
			j = pe.p[j];
		} while(j!=i);
	}
	return loops.size();
}

bool is_strong_regular( const int nv, const std::vector<edge> & edges ){
	int i,j,k;
	std::vector<bool> MA(nv*nv); std::fill(MA.begin(),MA.end(),false);
	std::vector<edge>::const_iterator q;
	for(q=edges.begin();q!=edges.end();++q)
	{
		MA[(*q).first+nv*(*q).second] = true;
		MA[(*q).second+nv*(*q).first] = true;
	}
	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;
}

void out_nauty( int n, const std::vector<std::pair<int,int> > & edges, const char * filename) {
	std::vector< std::vector<int> > vv;
	vv.resize(n);
	std::vector<std::pair<int,int> >::const_iterator i;
	for(i=edges.begin();i!=edges.end();++i)
		if((*i).first < (*i).second) vv[(*i).first].push_back( (*i).second );
		else                         vv[(*i).second].push_back( (*i).first );
	std::vector< std::vector<int> >::iterator j;
	for(j=vv.begin();j!=vv.end();++j) std::sort(j->begin(),j->end());
	FILE * fo = fopen(filename,"w");
	fprintf(fo, "n=%d\n" "g\n" ,n );
	for(j=vv.begin();j!=vv.end();++j) {
		if(j!=vv.begin()) fprintf(fo,";\n");
		std::vector<int>::iterator k;
		for(k=j->begin();k!=j->end();++k) {
			if(k!=j->begin()) fprintf(fo," ");
			fprintf(fo,"%d",*k);
		}
	}
	fprintf(fo, ".\n" "p\n" "x\n" "o\n" "q\n" );
	fclose(fo);
}

void load_nauty( int NV, const char * filename, std::vector< std::vector<int> > & auto_base ) {
	const int BSIZE = 1024;
	static char buff[1024];
	auto_base.clear();
	FILE * fp = fopen(filename,"r");
	auto_base.push_back( std::vector<int>() );
	while(fgets(buff,BSIZE,fp)) {
		if(strstr(buff,"grpsize"))
			break;
		else if(strstr(buff,"level")) {
			auto_base.push_back( std::vector<int>() );
		}
		else {
			const char * sep = " \n\r\t";
			char * p = strtok(buff,sep);
			while(p) {
				if(auto_base.back().size()==size_t(NV)) 
					auto_base.push_back( std::vector<int>() );
				auto_base.back().push_back(atoi(p));
				p = strtok(0,sep);
			}
		}
	}
	fclose(fp);
	auto_base.pop_back();
}

bool analyze_sym( int NV, permu & p, std::vector<int> & out_perm ) {
	if(fix_point(p)!=0) return false;
	size_t cs = cicle_size(p);
	if(cs<4 || NV%cs!=0) return false;
	std::vector< std::vector<size_t> > loops;
	size_t nsl = sub_loops(p,loops);
	if(size_t(NV)==cs*loops.size() && cs>3)	{ // TODO 3?? 
		printf("GOOD! %u %u\n",cs,nsl);
		std::vector< std::vector<size_t> >::iterator q;
		size_t iq;
		for(iq=0,q=loops.begin();q!=loops.end();++iq,++q)
		{
			std::vector<size_t>::iterator w;
			size_t iw;
			for(iw=0,w=q->begin();w!=q->end();++iw,++w)
				out_perm[ iq + loops.size()*iw ] = *w;
		}
		return true;
	}
	return false;
}

void find_symmetric( int NV, const std::vector< std::vector<int> > & auto_base,
	                 std::vector<int> & out_perm, bool all = false ) {
	std::set<permu> perms;
	std::vector<permu> active;
	out_perm.resize(NV);
	permu cu;
	cu.ident(NV);
	perms.insert(cu);
	active.push_back(cu);
	while(!active.empty()) {
		std::vector<permu>::iterator i;
		std::pair< std::set<permu>::iterator, bool > r;
		std::vector<permu> old_active;
		std::swap(old_active,active);
		for(i=old_active.begin();i!=old_active.end();++i) {
			for(size_t j=0;j<auto_base.size();++j) {
				copy(cu,*i);
				apply(cu,&auto_base[j].front());
				r = perms.insert(cu);
				if(r.second) {
					if(analyze_sym(NV,cu,out_perm)) {
						if(!all) return;
					}
					active.push_back(cu);
				}
			}
		}
	}
	printf("%u autos\n",perms.size());
}

void random_perm( size_t n, size_t m, int per[] ) {
	size_t i,j;
	std::vector<size_t> shu(m);
	for(i=0;i<m;++i) shu[i] = i; std::random_shuffle(shu.begin(),shu.end());
	std::vector<size_t> fas(m);
	for(i=0;i<m;++i) fas[i] = std::rand()%n;
	std::vector<size_t> o_per(n*m); std::copy(per,per+(n*m),o_per.begin());
	for(i=0;i<m;++i) for(j=0;j<n;++j)
		per[i+j*m] = o_per[ shu[i] + ((j+fas[i])%n) * m];
}

void save_svg_random_try( const char * filename, int NV, std::vector<edge> & edges, int perm[], int simm ) {
	const double SX = 800; const double SY = 800;
	const double RR = 2;   const double BO = 5;
	const int N = 4;
	std::vector<double> px(NV);
	std::vector<double> py(NV);
	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=\"rockini\">\n"
		,SX,SY
	);
	int i;
	const double R = (SX/N)/2;
	for(size_t vx=0;vx<size_t(N);++vx)
	for(size_t vy=0;vy<size_t(N);++vy){
		fprintf(fp,"<g id=\"edges\" style=\"stroke:#000000;stroke-width:0.1;stroke-opacity:1.0;\">\n");
		for(i=0;i<NV;++i) {
			const double a = 2*PI*i/NV;
			px[perm[i]] = R + (R-BO)*cos(a) + vx*(R*2);
			py[perm[i]] = R + (R-BO)*sin(a) + vy*(R*2);
		}
		for(i=0;i<int(edges.size());++i) {
			fprintf(fp,
				"<line x1=\"%5.1lf\" y1=\"%5.1lf\" x2=\"%5.1lf\" y2=\"%5.1lf\"/>\n"
				,px[edges[i].first ],py[edges[i].first ]
				,px[edges[i].second],py[edges[i].second]
			);
		}
		fprintf(fp,"</g>\n");
		fprintf(fp,"<g id=\"nodes\" style=\"stroke:#000000;stroke-width:1;stroke-opacity:1.0;fill:#FF0000\">\n");
		for(i=0;i<NV;++i)
			fprintf(fp,"<circle cx=\"%5.1lf\" cy=\"%5.1lf\" r=\"%5.1lf\"/>\n",px[i],py[i],RR);
		fprintf(fp,"</g>\n");
		random_perm(simm,NV/simm,perm);
	}
	fprintf(fp,"</svg>\n");
	fclose(fp);
}

int main() {
		// Make over GF(3): adjacent whe full quadric of difference=0
	const size_t NV = 81;
	size_t i,j,a,b;
	std::vector<edge> edges;
	for(a=0;a<NV-1;++a) {
		size_t va[4];
		j = a;
		for(i=0;i<4;++i) { va[i] = j%3; j/=3; }
		for(b=a+1;b<NV;++b) {
			size_t vb[4];
			j = b;
			for(i=0;i<4;++i) { vb[i] = j%3; j/=3; }
			size_t di[4];
			for(i=0;i<4;++i) di[i] = (va[i]+3-vb[i])%3;
			size_t x =
				di[0]*di[0] + di[0]*di[1] + di[0]*di[2] + di[0]*di[3] + di[1]*di[1] +
				di[1]*di[2] + di[1]*di[3] + di[2]*di[2] + di[2]*di[3] + di[3]*di[3] ;
			x = x%3;
			if(x==0) edges.push_back( edge(a,b) );
		}
	}
	is_strong_regular(NV,edges);
	out_nauty(NV,edges,"Brouwer_Haemers.txt");
	system("nauty < Brouwer_Haemers.txt > Brouwer_Haemers_o.txt");
	std::vector< std::vector<int> > auto_base;
	load_nauty(NV,"Brouwer_Haemers_o.txt",auto_base);
	std::vector<int> out_perm;
	find_symmetric(NV,auto_base,out_perm);
	save_svg_random_try("Brouwer_Haemers_Graph.svg",NV,edges, & out_perm.front(),9);
	return 0;
}

Captions

Add a one-line explanation of what this file represents

Items portrayed in this file

depicts

29 July 2010

image/svg+xml

94db1a7786b0af5672e86c68b2aae32759b86bcf

745,019 byte

800 pixel

800 pixel

File history

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

Date/TimeThumbnailDimensionsUserComment
current07:13, 29 July 2010Thumbnail for version as of 07:13, 29 July 2010800 × 800 (728 KB)Rocchini{{Information |Description={{en|1=Brouwer-Haemers graph: some random symmetric embeddings}} |Source={{own}} |Author=Claudio Rocchini |Date=2010-07-29 |Permission= |other_versions= }}

Global file usage

The following other wikis use this file: