Cambalache 3,14 - La vidriera irrespetuosa


Que el mundo fue y será una porquería, ya lo sé.

Cuéntame algo...

Esto es un trozo del programa geng.c, que forma parte del sistema nauty de Brendan McKay para calcular automorfismos de grafos. Consigue construir grafos libres de triángulos:


static void
makewgraph(graph *g, xword *h, int n)
/* make x-format square graph */
{
register setword w,x;
register xword hi;
register int i,j;

for (i = 0; i < n; ++i)
{
w = g[i];
x = 0;
while (w)
{
j = FIRSTBIT(w);
w ^= bit[j];
x |= g[j];
}
x &= ~bit[i];
hi = 0;
while (x)
{
j = FIRSTBIT(x);
x ^= bit[j];
hi |= xbit[j];
}
h[i] = hi;
}
}


Tengo que conseguir transformarlo en una rutina que me construya grafos sin $W_4$, o sea, ruedas de cuatro vértices como ésta:
Image Hosted by ImageShack.us

Si lo consigo, habré resuelto parte de un importante problema de Física Cuántica. ¡Qué curiosa es la vida!

2005-08-12 11:13 | Categoría: | 9 han comentado esto | Enlace permanente | Etiquetas: | Y dicen por ahí

Referencias (TrackBacks)

URL de trackback de esta historia http://zifra.blogalia.com//trackbacks/32266

Comentarios

1
De: Mitch Fecha: 2005-08-12 12:14

Me pierdo un poco con la sintaxis de C (en realidad me pierdo del todo, lo mío es el GAP y el Singular). Sería mucho pedir una descripción más de andar por casa?



2
De: Zifra Fecha: 2005-08-12 12:19

Es realmente jodío (¿se puede decir jodío en una bitácora?). Por eso me está costando tanto la adaptación.



3
De: Salva Fecha: 2005-08-12 12:19

Efectivamente, falta comentar-documentar el código. Al menos una descripción de los parámetros y funcines auxiliares.

Zifra, nos tienes hipervalorados :)



4
De: JJ Fecha: 2005-08-12 12:27

GAP? Singular? En mi vida había oido hablar de ellos...



5
De: Zifra Fecha: 2005-08-12 12:29

No hay funciones auxiliares. Bueno, FIRSTBIT hace lo que su nombre indica ¿no?, y graph es una estructura de datos representado al grafo. Más en le manual de nauty ;-)

A setword is an unsigned integer type of either 16, 32 or 64 bits, depending on the compile time parameter WORDSIZE. (By default, WORDSIZE is the largest of 32 and the size of type int.) A set (by which we always mean a subset of V = {0, 1,...,n−1}) is represented by an array of m setwords, where m is some number such that WORDSIZE × m ≥ n. The bits of a set are numbered 0, 1,...,n−1 left to right(with in each setword: high order to low order). Bits which don’t get numbers are called “unnumbered” and are assumed permanently zero. A set represents the subset { i | bit i is 1 }. A graph is represented by an array of n sets(so it has mn setwords altogether). The i-th set gives the vertices to which vertex i is adjacent, for 0 ≤ i



6
De: Zifra Fecha: 2005-08-12 12:30

Se supone que esta rutina parte de un grafo libre de cuadrados y crea otro libre de cuadrados. Lo que debo hacer es adaptarla a las ruedas.



7
De: Mitch Fecha: 2005-08-12 14:17

GAP es un sistema de algebra computacional orientado a teoría de grupos y combinatoria. Singular es otro orientado a anillos de polinómios.

Rarezas de matemáticos.



8
De: Anónima Fecha: 2005-08-12 14:38

Lo de llamar ruedas a "eso" me hace pensar en la cuadratura del círculo :D

y estamos de acuerdo ¡que curiosa es la vida! :)

PD: cachondeos a parte, dada mi inutilidad manifiesta en cuanto al fondo, solo me queda enviaros ánimo, por lo que valga.



9
De: Lola Fecha: 2005-08-19 12:11

Ah...el Gap... qué recuerdos cuando me pasaba las horas mirando grupos...



Nombre
Correo-e
URL
Dirección IP: 54.225.42.99 (c5cc341d33)
Comentario

Busca en Cambalache


Blogalia


Se comenta en Cambalache

  • Anónima en 10 de Marzo de 1991
  • Anónima en Ya nunca juego al ajedrez Años de plomo (la película)
  • Anónima en No, no es la Diada ni son las torres gemelas de Manhattan...
  • Zifra en Olvido
  • Anónimo en Olvido
  • Zifra en Quantum State-Independent Contextuality Requires 13 Rays
  • Anónima en Álgido
  • nfernefer en Álgido
  • Zifra en Álgido
  • Anónima en Álgido
  • Categorías:

    Archivos:

    <Abril 2017
    Lu Ma Mi Ju Vi Sa Do
              1 2
    3 4 5 6 7 8 9
    10 11 12 13 14 15 16
    17 18 19 20 21 22 23
    24 25 26 27 28 29 30
                 


    Lista de Enlaces

    De interés

    E-góticos

    Mis otros

    FotoFlickr


    Blogalia



    Versión para la columna lateral


    zifra. Get yours at bighugelabs.com/flickr
    2003-2006 Zifra – Powered by Blogalia – Estadísticas: Nedstat Basic - Web site estadísticas gratuito El contador para sitios web particulares