ファイル:Brouwer Haemers graph.svg
この SVG ファイルのこの PNG プレビューのサイズ: 600 × 600 ピクセル. その他の解像度: 240 × 240 ピクセル | 480 × 480 ピクセル | 768 × 768 ピクセル | 1,024 × 1,024 ピクセル | 2,048 × 2,048 ピクセル。
元のファイル (SVG ファイル、800 × 800 ピクセル、ファイルサイズ: 728キロバイト)
|
ウィキメディア・コモンズのファイルページにある説明を、以下に表示します。
|
概要
| 解説 |
English: Brouwer-Haemers graph: some random symmetric embeddings |
| 日付 | |
| 原典 | 投稿者自身による著作物 |
| 作者 | Claudio Rocchini |
ライセンス
この作品の著作権者である私は、この作品を以下のライセンスで提供します。
このファイルはクリエイティブ・コモンズ 表示-継承 3.0 非移植ライセンスのもとに利用を許諾されています。
- あなたは以下の条件に従う場合に限り、自由に
- 共有 – 本作品を複製、頒布、展示、実演できます。
- 再構成 – 二次的著作物を作成できます。
- あなたの従うべき条件は以下の通りです。
- 表示 – あなたは適切なクレジットを表示し、ライセンスへのリンクを提供し、変更があったらその旨を示さなければなりません。これらは合理的であればどのような方法で行っても構いませんが、許諾者があなたやあなたの利用行為を支持していると示唆するような方法は除きます。
- 継承 – もしあなたがこの作品をリミックスしたり、改変したり、加工した場合には、あなたはあなたの貢献部分を元の作品とこれと同一または互換性があるライセンスの下に頒布しなければなりません。
|
この文書は、フリーソフトウェア財団発行のGNUフリー文書利用許諾書 (GNU Free Documentation License) 1.2またはそれ以降のバージョンの規約に基づき、複製や再配布、改変が許可されます。不可変更部分、表紙、背表紙はありません。このライセンスの複製は、GNUフリー文書利用許諾書という章に含まれています。 |
あなたは上記のライセンスから、どれか一つ以上を選択できます。
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;
}
ファイルの履歴
過去の版のファイルを表示するには、その版の日時をクリックしてください。
| 日付と時刻 | サムネイル | 寸法 | 利用者 | コメント | |
|---|---|---|---|---|---|
| 現在の版 | 2010年7月29日 (木) 07:13 | | 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 での使用状況
- pt.wikipedia.org での使用状況
- ru.wikipedia.org での使用状況
- uk.wikipedia.org での使用状況
- www.wikidata.org での使用状況
