Хотя это может выглядеть как домашняя работа, уверяю вас, это не так.Это связано с некоторым домашним заданием, которое я сделал.
Давайте назовем неориентированный граф без самоограничений "кубическим", если каждая вершина имеет степень ровно три.Учитывая положительное целое число N, я хотел бы генерировать случайный кубический граф на N вершинах.Я бы хотел, чтобы он имел одинаковую вероятность, то есть, если на N вершинах имеется M кубических графов, вероятность генерации каждого равна 1 / M.Более слабое условие, которое все еще в порядке, состоит в том, что каждый кубический граф имеет ненулевую вероятность.
Я чувствую есть быстрый и умный способ сделать это, но до сих пор я был неудачным.
Я плохой кодер, пожалуйста, потерпите этот ужасный код:
PRE :dge = (3 * узлов) / 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. Таким образом, алгоритм может не завершиться.Более того, я не совсем уверен, что вероятность одинакова.
Возможно, в моем коде многое можно улучшить, но можете ли вы предложить лучший алгоритм для реализации?