Повна роздільність(SVG-файл, номінально 800 × 800 пікселів, розмір файлу: 728 КБ)

Wikimedia Commons logo Відомості про цей файл містяться на Вікісховищі — централізованому сховищі вільних файлів мультимедіа для використання у проектах Фонду Вікімедіа.

Опис файлу

Опис
English: Brouwer-Haemers graph: some random symmetric embeddings
Час створення
Джерело Власна робота
Автор Claudio Rocchini

Ліцензування

Я, власник авторських прав на цей твір, добровільно публікую його на умовах таких ліцензій:
w:uk:Creative Commons
зазначення авторства поширення на тих же умовах
Цей файл ліцензований на умовах ліцензії Creative Commons Attribution-Share Alike 3.0 Unported
Ви можете вільно:
  • ділитися – копіювати, поширювати і передавати твір
  • модифікувати – переробляти твір
При дотриманні таких умов:
  • зазначення авторства – Ви повинні вказати авторство, надати посилання на ліцензію і вказати, чи якісь зміни було внесено до оригінального твору. Ви можете зробити це в будь-який розсудливий спосіб, але так, щоб він жодним чином не натякав на те, наче ліцензіар підтримує Вас чи Ваш спосіб використання твору.
  • поширення на тих же умовах – Якщо ви змінюєте, перетворюєте або створюєте іншу похідну роботу на основі цього твору, ви можете поширювати отриманий у результаті твір тільки на умовах такої ж або сумісної ліцензії.
GNU head Дозволяється копіювати, розповсюджувати та/або модифікувати цей документ на умовах ліцензії GNU FDL версії 1.2 або більш пізньої, виданої Фондом вільного програмного забезпечення, без незмінних розділів, без текстів, які розміщені на першій та останній обкладинці. Копія ліцензії знаходиться у розділі GNU Free Documentation License.
Ви можете обрати ліцензію на ваш розсуд.

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

Підписи

Додайте однорядкове пояснення, що саме репрезентує цей файл

Об'єкти, показані на цьому файлі

зображує

745 019 байт

800 піксель

800 піксель

Історія файлу

Клацніть на дату/час, щоб переглянути, як тоді виглядав файл.

Дата/часМініатюраРозмір об'єктаКористувачКоментар
поточний07:13, 29 липня 2010Мініатюра для версії від 07:13, 29 липня 2010800 × 800 (728 КБ)Rocchini{{Information |Description={{en|1=Brouwer-Haemers graph: some random symmetric embeddings}} |Source={{own}} |Author=Claudio Rocchini |Date=2010-07-29 |Permission= |other_versions= }}

Такі сторінки використовують цей файл:

Глобальне використання файлу

Цей файл використовують такі інші вікі: