生成具有均匀概率(或更小)的随机立方图

如果每个顶点的度数只有三个,我们来调用一个没有自边缘的无方向图.给定一个正整数N我想在N个顶点上生成一个随机立方图.我希望它具有统一的概率,也就是说,如果在N个顶点上有M个三次曲线,则生成每一个的概率为1 / M.一个较弱的条件仍然很好,每个立方图都有非零概率.

我觉得有一个快速和聪明的方式来做到这一点,但到目前为止,我一直没有成功.

我是一个坏的编码器,请承担这个可怕的代码：

PRE：edges =(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("%dt%dn",i,j);
        degree[i]++;
        degree[j]++;
    }

}

问题是它必须被选中的最后一个边缘可能是一个自我边缘.当N-1个顶点已经具有3级时,只有1个具有度数1,因此算法可能不会终止.此外,我并不完全相信概率是统一的.

我的代码可能有很多改进,但是你可以建议一个更好的算法来实现？