Archivo:Brouwer Haemers graph.svg
Contenido de la página no disponible en otros idiomas.
Apariencia
De Wikipedia, la enciclopedia libre
Tamaño de esta previsualización PNG del archivo SVG: 600 × 600 píxeles. Otras resoluciones: 240 × 240 píxeles · 480 × 480 píxeles · 768 × 768 píxeles · 1024 × 1024 píxeles · 2048 × 2048 píxeles.
Ver la imagen en su resolución original ((Imagen SVG, nominalmente 800 × 800 pixels, tamaño de archivo: 728 kB))
Este es un archivo de Wikimedia Commons, un depósito de contenido libre hospedado por la Fundación Wikimedia. Más abajo se reproduce su página de descripción con la información sobre su origen y licencia. |
Sumario
Resumen
DescripciónBrouwer Haemers graph.svg |
English: Brouwer-Haemers graph: some random symmetric embeddings |
Fecha | |
Fuente | Trabajo propio |
Autor | Claudio Rocchini |
Licencia
Yo, titular de los derechos de autor de esta obra, la publico en los términos de las siguientes licencias:
Este archivo se encuentra bajo la licencia Creative Commons Genérica de Atribución/Compartir-Igual 3.0.
- Eres libre:
- de compartir – de copiar, distribuir y transmitir el trabajo
- de remezclar – de adaptar el trabajo
- Bajo las siguientes condiciones:
- atribución – Debes otorgar el crédito correspondiente, proporcionar un enlace a la licencia e indicar si realizaste algún cambio. Puedes hacerlo de cualquier manera razonable pero no de manera que sugiera que el licenciante te respalda a ti o al uso que hagas del trabajo.
- compartir igual – En caso de mezclar, transformar o modificar este trabajo, deberás distribuir el trabajo resultante bajo la misma licencia o una compatible como el original.
Se autoriza la copia, distribución y modificación de este documento bajo los términos de la licencia de documentación libre GNU, versión 1.2 o cualquier otra que posteriormente publique la Fundación para el Software Libre; sin secciones invariables, textos de portada, ni textos de contraportada. Se incluye una copia de la dicha licencia en la sección titulada Licencia de Documentación Libre GNU.http://www.gnu.org/copyleft/fdl.htmlGFDLGNU Free Documentation Licensetruetrue |
Puedes usar la licencia que prefieras.
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;
}
Elementos representados en este archivo
representa a
Algún valor sin elemento de Wikidata
29 jul 2010
image/svg+xml
94db1a7786b0af5672e86c68b2aae32759b86bcf
745 019 byte
800 píxel
800 píxel
Historial del archivo
Haz clic sobre una fecha y hora para ver el archivo tal como apareció en ese momento.
Fecha y hora | Miniatura | Dimensiones | Usuario | Comentario | |
---|---|---|---|---|---|
actual | 07:13 29 jul 2010 | 800 × 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= }} |
Usos del archivo
La siguiente página usa este archivo:
Uso global del archivo
Las wikis siguientes utilizan este archivo:
- Uso en en.wikipedia.org
- Uso en fr.wikipedia.org
- Uso en ja.wikipedia.org
- Uso en pt.wikipedia.org
- Uso en ru.wikipedia.org
- Uso en uk.wikipedia.org
- Uso en www.wikidata.org