Si bien esto puede parecer una tarea, te aseguro que no es así. Sin embargo, se deriva de una tarea que hice.Generando un gráfico cúbico aleatorio con probabilidad uniforme (o menos)
Llamemos a un gráfico no dirigido sin bordes propios "cúbico" si cada vértice tiene un grado exactamente tres. Dado un número entero positivo N, me gustaría generar un gráfico cúbico aleatorio en N vértices. Me gustaría que tuviera una probabilidad uniforme, es decir, si hay M gráficos cúbicos en N vértices, la probabilidad de generar cada uno es 1/M. Una condición más débil que todavía está bien es que cada gráfico cúbico tiene una probabilidad distinta de cero.
I feel hay una manera rápida e inteligente de hacer esto, pero hasta ahora no he tenido éxito.
soy una mala codificador, por favor tengan con este código horrible:
PRE:/2, los nodos es par, las constantes se seleccionan de tal manera bordes = (3 * nodos) que las obras de hash (BIG_PRIME es más grande que los bordes, SMALL_PRIME es más grande que los nodos, LOAD_FACTOR es pequeño).
void random_cubic_graph() {
int i, j, k, count;
int *degree;
char guard;
count = 0;
degree = (int*) calloc(nodes, sizeof(int));
while (count < edges) {
/* Try a new edge at random */
guard = 0;
i = rand() % nodes;
j = rand() % nodes;
/* Checks if it is a self-edge */
if (i == j)
guard = 1;
/* Checks that the degrees are 3 or less */
if (degree[i] > 2 || degree[j] > 2)
guard = 1;
/* Checks that the edge was not already selected with an hash */
k = 0;
while(A[(j + k*BIG_PRIME) % (LOAD_FACTOR*edges)] != 0) {
if (A[(j + k*BIG_PRIME) % (LOAD_FACTOR*edges)] % SMALL_PRIME == j)
if ((A[(j + k*BIG_PRIME) % (LOAD_FACTOR*edges)] - j)/SMALL_PRIME == i)
guard = 1;
k++;
}
if (guard == 0)
A[(j + k*BIG_PRIME) % (LOAD_FACTOR*edges)] = hash(i,j);
k = 0;
while(A[(i + k*BIG_PRIME) % (LOAD_FACTOR*edges)] != 0) {
if (A[(i + k*BIG_PRIME) % (LOAD_FACTOR*edges)] % SMALL_PRIME == i)
if ((A[(i + k*BIG_PRIME) % (LOAD_FACTOR*edges)] - i)/SMALL_PRIME == j)
guard = 1;
k++;
}
if (guard == 0)
A[(i + k*BIG_PRIME) % (LOAD_FACTOR*edges)] = hash(j,i);
/* If all checks were passed, increment the count, print the edge, increment the degrees. */
if (guard == 0) {
count++;
printf("%d\t%d\n", i, j);
degree[i]++;
degree[j]++;
}
}
El problema es que su borde final que debe seleccionarse puede ser un borde propio. Eso sucede cuando los vértices N - 1 ya tienen el grado 3, solo 1 tiene el grado 1. Por lo tanto, es posible que el algoritmo no termine. Además, no estoy del todo convencido de que la probabilidad sea uniforme.
Probablemente haya mucho que mejorar en mi código, pero ¿puede sugerirme un mejor algoritmo para implementar?
Sugiero no usar el lenguaje C para algoritmos de gráficos cuando eres solo un principiante. –
Entonces, ¿estás representando tu gráfica como una matriz cuadrada? Por cierto, ¿qué es este negocio small_prime, big_prime y load_factor? Me parece que ha copiado la solución de otra persona y está intentando darle sentido. –
No hay matriz cuadrada: A es un vector de longitud LOAD_FACTOR * bordes que contiene los bordes. Vamos a pretender que hay una función blackbox is_edge_present (int i, int j) que comprueba si el borde (i, j) ya estaba seleccionado. Ese fragmento de código hace eso, y si el borde no se seleccionó, lo selecciona para futuras búsquedas. ¿No es un poco grosero asumir que he copiado? Yo escribí esa. Es intrincado y desordenado, pero es por eso que hay una etiqueta para principiantes. –