Während dies wie Hausaufgaben aussehen mag, versichere ich Ihnen, dass es nicht ist. Es stammt jedoch von einer Hausaufgabe, die ich gemacht habe.Erzeugen eines zufälligen kubischen Graphen mit gleichförmiger Wahrscheinlichkeit (oder weniger)
Nennen wir einen ungerichteten Graphen ohne Kanten "kubisch", wenn jeder Knoten Grad genau drei hat. Bei einer positiven Ganzzahl N möchte ich einen zufälligen kubischen Graphen auf N Knoten erzeugen. Ich hätte gerne, dass es eine einheitliche Wahrscheinlichkeit hat, das heißt, wenn es M kubische Graphen auf N Ecken gibt, ist die Wahrscheinlichkeit, dass jede 1/M ist. Eine schwächere Bedingung, die immer noch in Ordnung ist, ist, dass jeder kubische Graph eine Wahrscheinlichkeit ungleich Null hat.
I fühlen gibt es eine schnelle und intelligente Möglichkeit, dies zu tun, aber bisher war ich erfolglos.
Ich bin ein schlechter Coder, bitte mit diesem schrecklichen Code tragen:
PRE: Kanten = (3 * Knoten)/2, wird Knoten selbst sind die Konstanten so gewählt, dass die Hash-Werke (BIG_PRIME ist größer als Kanten, SMALL_PRIME ist größer als Knoten, LOAD_FACTOR ist klein).
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]++;
}
}
Das Problem ist, dass die endgültige Kante, die ausgewählt werden muss, eine Self-Edge sein kann. Das passiert, wenn N - 1 Vertices bereits Grad 3 haben, nur 1 Grad 1. Daher könnte der Algorithmus nicht enden. Außerdem bin ich nicht ganz davon überzeugt, dass die Wahrscheinlichkeit einheitlich ist.
Es gibt wahrscheinlich viel zu verbessern in meinem Code, aber können Sie vorschlagen, einen besseren Algorithmus zu implementieren?
Ich schlage vor, nicht C-Sprache für Graph-Algorithmen zu verwenden, wenn Sie nur ein Anfänger sind. –
Also, stellen Sie Ihren Graphen als quadratische Matrix dar? Übrigens, was ist das Geschäft mit small_prime, big_prime und load_factor? Klingt für mich so, als ob du die Lösung eines anderen kopierst und versuchst, einen Sinn daraus zu machen. –
Es gibt keine quadratische Matrix: A ist ein Vektor der Länge LOAD_FACTOR * Kanten, der die Kanten enthält. Lass uns einfach so tun, als gäbe es eine Blackbox-Funktion is_edge_present (int i, int j), die überprüft, ob die (i, j) -Front bereits ausgewählt wurde. Dieses Code-Snippet macht das, und wenn die Kante nicht ausgewählt wurde, wählt sie es für zukünftige Suchen aus. Ist es nicht ein bisschen unhöflich anzunehmen, dass ich kopiert habe? Das habe ich geschrieben. Es ist kompliziert und chaotisch, aber deshalb gibt es ein Anfänger-Tag. –