Генерация случайного кубического графика с универсальной вероятностью (или меньше)

В то время как это может быть похожим на домашнюю работу, я уверяю Вас, что это не. Это происходит от некоторого присвоения домашней работы, которое я сделал, все же.

Давайте назовем неориентированного графа без самокраев "кубическим", если каждая вершина имеет градус точно три. Учитывая положительное целое число N я хотел бы генерировать случайный кубический график на вершинах N. Я хотел бы за него иметь универсальную вероятность, то есть, если существуют кубические графики M на вершинах N вероятность генерации, каждый 1/М. Более слабое условие, которое прекрасно все еще, состоит в том, что каждый кубический график имеет ненулевую вероятность.

Я чувствую, что существует быстрый и умный способ сделать это, но до сих пор я был неудачен.

Я - плохой кодер, терпите этот ужасный код:

ПРЕД: края = (3*nodes)/2, узлы даже, константы выбраны таким способом, которым хеш работает (BIG_PRIME больше, чем края, SMALL_PRIME больше, чем узлы, LOAD_FACTOR является маленьким).

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]++;
    }

}

Проблема состоит в том, что ее заключительный край, который должен быть выбран, мог бы быть самокраем. Это происходит, когда N - 1 вершина уже имеет градус 3, только 1 имеет градус 1. Таким образом алгоритм не мог бы завершиться. Кроме того, я не полностью убежден, что вероятность универсальна.

Существует, вероятно, очень для улучшения в моем коде, но можно предложить, чтобы лучший алгоритм реализовал?