Bien que cela puisse ressembler à des devoirs, je vous assure que ce n'est pas le cas. Cela vient cependant de certaines tâches que j'ai faites. Appelons un graphe non orienté sans auto-arêtes "cubique" si chaque sommet a un degré exactement trois. Étant donné un entier positif N, je voudrais générer un graphe cubique aléatoire sur N sommets. Je voudrais qu'il ait une probabilité uniforme, c'est-à-dire, s'il y a M graphes cubiques sur N sommets, la probabilité de générer chacun d'eux est 1/M. Une condition plus faible qui est encore bonne est que chaque graphe cubique a une probabilité non nulle.Génération d'un graphe cubique aléatoire avec probabilité uniforme (ou moins)
I sentir il y a une manière rapide et intelligente de faire ceci, mais jusqu'ici j'ai échoué.
Je suis un mauvais codeur, s'il vous plaît garder avec ce code terrible:
PRE: arêtes = (3 * nœuds)/2, les nœuds est même, les constantes sont choisies de telle sorte que les travaux de hachage (BIG_PRIME est plus grand que les bords, SMALL_PRIME est plus grand que les nœuds, LOAD_FACTOR est petit).
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]++;
}
}
Le problème est que son dernier bord devant être sélectionné pourrait être un auto-contour. Cela se produit lorsque N - 1 sommets ont déjà le degré 3, seulement 1 a le degré 1. Ainsi, l'algorithme peut ne pas se terminer. De plus, je ne suis pas entièrement convaincu que la probabilité soit uniforme.
Il y a probablement beaucoup à améliorer dans mon code, mais pouvez-vous suggérer un meilleur algorithme à implémenter?
Je suggère de ne pas utiliser le langage C pour les algorithmes de graphes lorsque vous êtes juste un débutant. –
Alors, représentez-vous votre graphique en tant que matrice carrée? Au fait, que sont ces affaires small_prime, big_prime, et load_factor? J'ai l'impression que vous avez copié la solution de quelqu'un d'autre et que vous essayez d'en comprendre le sens. –
Il n'y a pas de matrice carrée: A est un vecteur de longueur LOAD_FACTOR * arêtes qui contient les arêtes. Imaginons simplement qu'il existe une fonction blackbox is_edge_present (int i, int j) qui vérifie si le bord (i, j) a déjà été sélectionné. Cet extrait de code fait cela, et si le bord n'a pas été sélectionné, il le sélectionne pour les recherches futures. N'est-il pas un peu impoli de supposer que j'ai copié? J'ai écrit ça. C'est alambiqué et désordonné, mais c'est pourquoi il y a une balise pour débutant. –