קובץ:Brouwer Haemers graph.svg
תוכן הדף אינו נתמך בשפות אחרות.
מראה
מתוך ויקיפדיה, האנציקלופדיה החופשית
גודל התצוגה המקדימה הזאת מסוג PNG של קובץ ה־SVG הזה: 600 × 600 פיקסלים. רזולוציות אחרות: 240 × 240 פיקסלים | 480 × 480 פיקסלים | 768 × 768 פיקסלים | 1,024 × 1,024 פיקסלים | 2,048 × 2,048 פיקסלים.
לקובץ המקורי (קובץ SVG, הגודל המקורי: 800 × 800 פיקסלים, גודל הקובץ: 728 ק"ב)
זהו קובץ שמקורו במיזם ויקישיתוף. תיאורו בדף תיאור הקובץ המקורי (בעברית) מוצג למטה. |
תוכן עניינים
תקציר
תיאורBrouwer Haemers graph.svg |
English: Brouwer-Haemers graph: some random symmetric embeddings |
תאריך יצירה | |
מקור | נוצר על־ידי מעלה היצירה |
יוצר | Claudio Rocchini |
רישיון
אני, בעל זכויות היוצרים על היצירה הזאת, מפרסם אותה בזאת תחת הרישיונות הבאים:
הקובץ הזה מתפרסם לפי תנאי רישיון קריאייטיב קומונז ייחוס-שיתוף זהה 3.0 לא מותאם.
- הנכם רשאים:
- לשתף – להעתיק, להפיץ ולהעביר את העבודה
- לערבב בין עבודות – להתאים את העבודה
- תחת התנאים הבאים:
- ייחוס – יש לתת ייחוס הולם, לתת קישור לרישיון, ולציין אם נעשו שינויים. אפשר לעשות את זה בכל צורה סבירה, אבל לא בשום צורה שמשתמע ממנה שמעניק הרישיון תומך בך או בשימוש שלך.
- שיתוף זהה – אם תיצרו רמיקס, תשנו, או תבנו על החומר, חובה עליכם להפיץ את התרומות שלך לפי תנאי רישיון זהה או תואם למקור.
מוענקת בכך הרשות להעתיק, להפיץ או לשנות את המסמך הזה, לפי תנאי הרישיון לשימוש חופשי במסמכים של גנו, גרסה 1.2 או כל גרסה מאוחרת יותר שתפורסם על־ידי המוסד לתוכנה חופשית; ללא פרקים קבועים, ללא טקסט עטיפה קדמית וללא טקסט עטיפה אחורית. עותק של הרישיון כלול בפרק שכותרתו הרישיון לשימוש חופשי במסמכים של גנו.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
745,019 בית
800 פיקסל
800 פיקסל
היסטוריית הקובץ
ניתן ללחוץ על תאריך/שעה כדי לראות את הקובץ כפי שנראה באותו זמן.
תאריך/שעה | תמונה ממוזערת | ממדים | משתמש | הערה | |
---|---|---|---|---|---|
נוכחית | 10: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
- שימוש באתר uk.wikipedia.org
- שימוש באתר www.wikidata.org