How to generate random adjacency matrix with given number of components in graph

Question

I am building a graph package in C and a part of the work involves generating a random graph with a given number of components in the graph.

For example, if I wanted to generate a graph of 50 vertices and 5 components, then the module will take 50 and 5 as parameters and should be able to generate an adjacency matrix of the graph(for the time being I am implementing it using adjacency matrix only). I have an idea that I can generate cliques of a different number of vertices and the number of cliques is exactly equal to the number of components. Then I can merge all the adjacency matrices corresponding to cliques to form the adjacency matrix of the graph.

Implementing this in C seems to be quite complicated, and I feel this is not an optimal solution as the graph will be dense every time and I can not achieve a sparse graph using this approach. Is there anything I am missing?

Answer 1

What you need is to take advantage of disjoint set, a very efficient data structure.

Here is the simple algorithm to generate a random graph of $n$ vertices and $m$ component.

1. MakeSet of size $n$.
2. Choose two random vertices that has not been connected by an edge.
3. Union these two vertices. That means adding the edge between them. Use an implementation of the union operation that tells you if two different components are unioned.
4. Stop if the number of components become $m$. Go back to step 2 otherwise.

There are existing implementations of disjoint set in C/C++, Java, Python, or just about every popular language.

You can implement step 2 in various ways.

• You can use rejection sampling. Choose two random vertices. Repeat if the edge between them has been added.

  This method is about the simplest to implement. It is efficient when the number of components is greater than a fixed proportion of the number of vertices. It takes little time if the number of vertices is not large.

• You can also keep track of the degree of each vertex. Choose a vertex whose degree is not $n-1$. The choose an edge from that vertex.

You can vary step 3 as well. Step 3 above is aimed to produce a random graph with given number of components and the "minimal" number of edges.

• One way to get random number of edges is to continue adding some random number of random edges after step 3 as long as no two different components become unioned/connected.
• One way to get denser graphs is to not add the edge when it connects two different component with some probability $p$. The larger $p$ is, the more edges.

In the special case of one component (connected graph) and many vertices, you can also generate a random tree using Prüfer sequence, followed by adding some random edges.

As you have mentioned, you could also generate $m$ random connected graphs with given numbers of vertices, the joining them together. Each connected graph can be generated using either disjoint set or Prüfer sequence.

Note that for all above variations, the distribution of the generated graphs is probably different from each other. It is your task to choose an implementation whose randomness/biasness is what you want. Or roughly.