Файл:Brouwer Haemers graph.svg
![Файл:Brouwer Haemers graph.svg](http://upload.wikimedia.org/wikipedia/commons/thumb/b/b1/Brouwer_Haemers_graph.svg/600px-Brouwer_Haemers_graph.svg.png)
Розмір цього попереднього перегляду PNG для вихідного SVG-файлу: 600 × 600 пікселів. Інші роздільності: 240 × 240 пікселів | 480 × 480 пікселів | 768 × 768 пікселів | 1024 × 1024 пікселів | 2048 × 2048 пікселів.
Повна роздільність (SVG-файл, номінально 800 × 800 пікселів, розмір файлу: 728 КБ)
![]() |
Відомості про цей файл містяться на Вікісховищі — централізованому сховищі вільних файлів мультимедіа для використання у проектах Фонду Вікімедіа. |
Опис файлу
ОписBrouwer Haemers graph.svg |
English: Brouwer-Haemers graph: some random symmetric embeddings |
Час створення | |
Джерело | Власна робота |
Автор | Claudio Rocchini |
Ліцензування
Я, власник авторських прав на цей твір, добровільно публікую його на умовах таких ліцензій:
![w:uk:Creative Commons](https://upload.wikimedia.org/wikipedia/commons/thumb/7/79/CC_some_rights_reserved.svg/90px-CC_some_rights_reserved.svg.png)
![зазначення авторства](https://upload.wikimedia.org/wikipedia/commons/thumb/1/11/Cc-by_new_white.svg/24px-Cc-by_new_white.svg.png)
![поширення на тих же умовах](https://upload.wikimedia.org/wikipedia/commons/thumb/d/df/Cc-sa_white.svg/24px-Cc-sa_white.svg.png)
Цей файл ліцензований на умовах ліцензії Creative Commons Attribution-Share Alike 3.0 Unported
- Ви можете вільно:
- ділитися – копіювати, поширювати і передавати твір
- модифікувати – переробляти твір
- При дотриманні таких умов:
- зазначення авторства – Ви повинні вказати авторство, надати посилання на ліцензію і вказати, чи якісь зміни було внесено до оригінального твору. Ви можете зробити це в будь-який розсудливий спосіб, але так, щоб він жодним чином не натякав на те, наче ліцензіар підтримує Вас чи Ваш спосіб використання твору.
- поширення на тих же умовах – Якщо ви змінюєте, перетворюєте або створюєте іншу похідну роботу на основі цього твору, ви можете поширювати отриманий у результаті твір тільки на умовах такої ж або сумісної ліцензії.
![]() |
Дозволяється копіювати, розповсюджувати та/або модифікувати цей документ на умовах ліцензії GNU FDL версії 1.2 або більш пізньої, виданої Фондом вільного програмного забезпечення, без незмінних розділів, без текстів, які розміщені на першій та останній обкладинці. Копія ліцензії знаходиться у розділі GNU Free Documentation License.http://www.gnu.org/copyleft/fdl.htmlGFDLGNU Free Documentation Licensetruetrue |
Ви можете обрати ліцензію на ваш розсуд.
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;
}
Підписи
Додайте однорядкове пояснення, що саме репрезентує цей файл
Об'єкти, показані на цьому файлі
зображує
Якесь значення без елемента на сайті Вікідані
29 липня 2010
image/svg+xml
94db1a7786b0af5672e86c68b2aae32759b86bcf
745 019 байт
800 піксель
800 піксель
Історія файлу
Клацніть на дату/час, щоб переглянути, як тоді виглядав файл.
Дата/час | Мініатюра | Розмір об'єкта | Користувач | Коментар | |
---|---|---|---|---|---|
поточний | 07:13, 29 липня 2010 | ![]() | 800 × 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= }} |
Використання файлу
Такі сторінки використовують цей файл:
Глобальне використання файлу
Цей файл використовують такі інші вікі:
- Використання в en.wikipedia.org
- Використання в es.wikipedia.org
- Використання в fr.wikipedia.org
- Використання в ja.wikipedia.org
- Використання в pt.wikipedia.org
- Використання в ru.wikipedia.org
- Використання в www.wikidata.org