Generating a random cubic graph with uniform probability (or less)

Question

While this may look like homework, I assure you it's not. It stems from some homework assignment I did, though.

Let's call an undirected graph without self-edges "cubic" if every vertex has degree exactly three. Given a positive integer N I'd like to generate a random cubic graph on N vertices. I'd like for it to have uniform probability, that is, if there are M cubic graphs on N vertices the probability of generating each one is 1/M. A weaker condition that is still fine is that every cubic graph has non-zero probability.

I feel there's a quick and smart way to do this, but so far I've been unsuccessful.

I am a bad coder, please bear with this awful code:

PRE: edges = (3*nodes)/2, nodes is even, the constants are selected in such a way that the hash works (BIG_PRIME is bigger than edges, SMALL_PRIME is bigger than nodes, LOAD_FACTOR is small).

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

}

The problem is that its final edge that has to be selected might be a self-edge. That happens when N - 1 vertices have already degree 3, only 1 has degree 1. Thus the algorithm might not terminate. Moreover, I'm not entirely convinced that the probability is uniform.

There's probably much to improve in my code, but can you suggest a better algorithm to implement?

Answer 1

Assume N is even. (Otherwise there cannot be a cubic graph on N vertices).

You can do the following:

Take 3N points and divide them into N groups of 3 points each.

Now pair up these 3N points randomly (note: 3N is even). i.e. Marry two points off randomly and form 3N/2 marriages).

If there is a pairing between group i and group j, create an edge between i and j. This gives a graph on N vertices.

If this random pairing does not create any multiple edges or loops, you have a cubic graph.

If not try again. This runs in expected linear time and generates a uniform distribution.

Note: all cubic graphs on N vertices are generated by this method (responding to Hamish's comments).

To see this:

Let G be a cubic graph on N vertices.

Let the vertices be, 1, 2, ...N.

Let the three neighbours of j be A(j), B(j) and C(j).

For each j, construct the group of ordered pairs { (j, A(j)), (j, B(j)), (j, C(j)) }.

This gives us 3N ordered pairs. We pair them up: (u,v) is paired with (v,u).

Thus any cubic graph corresponds to a pairing and vice versa...

More information on this algorithm and faster algorithms can be found here: Generating Random Regular Graphs Quickly.

Answer 2

Warning: I make a lot of intuitive-but-maybe-wrong claims in this answer. You should definitely prove them if you intend to use this idea.

Enumerating Cubic Graphs

When dealing with a random choice, a good starting point is to figure out how to enumerate over all of your possible elements. This might reveal some of the structure, and lead you to an algorithm.

Here is my strategy for enumerating cubic graphs: pick the first vertex, and iterate over all possible choices of three adjacent vertices. During those iterations, recurse on the next vertex, with the caveat that you keep track of how many edges are needed for each vertex degree to reach 3. Continue in that fashion until the lowest level is reached. Now you have your first cubic graph. Undo the recently added edges and continue to the next possibility until there are none left. There are a few implementation details you need to consider, but generally straight-forward.

Generalize Enumeration into Choice

Once you can enumerate all the elements, it is trivial to make a random choice. For example, you can scan the list once to compute its size then pick a random number in [0, size) then scan the sequence again to get the element at that offset. This is incredibly inefficient, taking at LEAST time proportional to the O(n^3) number of cubic graphs, but it works.

Sacrifice Uniform Probability for Efficiency

The obvious speed-up here is to make random edge choices at each level, instead of iterating over each possibility. Unfortunately, this will favor some graphs because of how your early choices affect the availability of later choices. Taking into account the need to track the remaining free vertices, you should be able to achieve O(n log n) time and O(n) space. Significantly better than the enumerating algorithm.

...

It's probably possible to do better. Probably a lot better. But this should get you started.

Answer 3

Another term for cubic graph is 3-regular graph or trivalent graph.

Your problem needs a little more clarification because "the number of cubic graphs" could mean the number of cubic graphs on 2n nodes that are non-isomorphic to one another or the number of (non-isomorphic) cubic graphs on 2n labelled nodes. The former is given by integer sequence A005638, and it is likely a non-trivial problem to uniformly pick a random isomorphism class of cubic graphs efficiently (i.e. not listing them all out and then picking one class). The latter is given by A002829.

There is an article on Wikipedia about random regular graphs that you should take a look at.