Cambalache 3,14 - La vidriera irrespetuosa

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:

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: | Enlace permanente | Etiquetas: | Y dicen por ahí

Referencias (TrackBacks)

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

Comentarios

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?

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.

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 :)

De: JJ

Fecha: 2005-08-12 12:27

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

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 dont 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

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.

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.

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.