Mentre questo può sembrare un compito a casa, ti assicuro che non lo è. Deriva da alcuni compiti a casa che ho fatto, però.Generazione di un grafico cubico casuale con probabilità uniforme (o inferiore)
Chiamiamo un grafico non orientato senza bordi "cubici" se ogni vertice ha esattamente il grado tre. Dato un numero intero positivo N Mi piacerebbe generare un grafico cubico casuale su N vertici. Mi piacerebbe che avesse una probabilità uniforme, cioè se ci sono grafici cubici M su N vertici la probabilità di generare ciascuno è 1/M. Una condizione più debole che è ancora valida è che ogni grafico cubico ha una probabilità diversa da zero.
I feel c'è un modo rapido e intelligente per farlo, ma finora non ho avuto successo.
Io sono un cattivo codificatore, si prega di tenere con questo codice terribile:
PRE: bordi = (3 * nodi)/2, i nodi è pari, le costanti sono selezionati in modo tale che i lavori di hash (BIG_PRIME è più grande dei bordi, SMALL_PRIME è più grande dei nodi, LOAD_FACTOR è piccolo).
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]++;
}
}
Il problema è che il suo ultimo bordo che deve essere selezionato potrebbe essere un vantaggio. Ciò accade quando i vertici N-1 hanno già grado 3, solo 1 ha il grado 1. Quindi l'algoritmo potrebbe non terminare. Inoltre, non sono del tutto convinto che la probabilità sia uniforme.
Probabilmente c'è molto da migliorare nel mio codice, ma puoi suggerire un algoritmo migliore da implementare?
Io suggerisco di non usare il linguaggio C per gli algoritmi del grafico quando sei solo un principiante. –
Quindi, stai rappresentando il tuo grafico come una matrice quadrata? A proposito, cos'è questa attività small_prime, big_prime e load_factor? Mi sembra che tu abbia copiato la soluzione di qualcun altro e stia cercando di dare un senso a ciò. –
Non esiste una matrice quadrata: A è un vettore di lunghezza LOAD_FACTOR * i bordi che contengono i bordi. Facciamo finta che esista una funzione blackbox is_edge_present (int i, int j) che controlla se il bordo (i, j) era già selezionato. Quel frammento di codice lo fa, e se il bordo non è selezionato lo seleziona per ricerche future. Non è un po 'scortese presumere di averlo copiato? L'ho scritto È complicato e disordinato, ma è per questo che c'è un tag per principianti. –