<p>The following paper proposes an algorithm that <em>uniformly</em> samples <strong>connected</strong> random graphs with prescribed degree sequence, with an efficient implementation. It is available in several libraries, like Networkit or igraph.</p>
<p><a href="https://arxiv.org/abs/cs/0502085" rel="nofollow noreferrer">Fast generation of random connected graphs with prescribed degrees.</a>
Fabien Viger, Matthieu Latapy</p>
<p>Be careful when you make simulations on random graphs: if they are not sampled uniformly, then they may have hidden properties that impact simulations; alternatively, uniformly sampled graphs may be very different from the ones your code will meet in practice...</p>
How to generate random graphs?
<p>I want to be able to generate random, undirected, and connected graphs in Java. In addition, I want to be able to control the maximum number of vertices in the graph. I am not sure what would be the best way to approach this problem, but here are a few I can think of:</p>
<p>(1) Generate a number between <code>0</code> and <code>n</code> and let that be the number of vertices. Then, somehow randomly link vertices together (maybe generate a random number per vertex and let that be the number of edges coming out of said vertex). Traverse the graph starting from an arbitrary vertex (say with Breadth-First-Search) and let our random graph <code>G</code> be all the visited nodes (this way, we make sure that <code>G</code> is connected).</p>
<p>(2) Generate a random square matrix (of <code>0</code>'s and <code>1</code>'s) with side length between <code>0</code> and <code>n</code> (somehow). This would be the adjacency matrix for our graph (the diagonal of the matrix should then either be all <code>1</code>'s or all <code>0</code>'s). Make a data structure from the graph and traverse the graph from any node to get a connected list of nodes and call that the graph <code>G</code>.</p>
<p>Any other way to generate a sufficiently random graph is welcomed. <strong>Note</strong>: I do not need a purely random graph, i.e., the graph you generate doesn't have to have any special mathematical properties (like uniformity of some sort). I simply need lots and lots of graphs for testing purposes of something else.</p>
<p>Here is the Java <code>Node</code> class I am using:</p>
<pre><code>public class Node&lt;T&gt; {
    T data;
    ArrayList&lt;Node&gt; children= new ArrayList&lt;Node&gt;();
    ...}
</code></pre>
<p>Here is the <code>Graph</code> class I am using (you can tell why I am only interested in connected graphs at the moment):</p>
<pre><code>public class Graph {
    Node mainNode;
    ArrayList&lt;Node&gt; V= new ArrayList&lt;Node&gt;();

    public Graph(Node node){
        mainNode= node;
    }
    ...}
</code></pre>
<p>As an example, this is how I make graphs for testing purposes right now:</p>
<pre><code>//The following makes a &quot;kite&quot; graph G (with &quot;a&quot; as the main node).

/*     a-b
        |/|
        c-d
*/
Node&lt;String&gt; a= new Node(&quot;a&quot;);
Node&lt;String&gt; b= new Node(&quot;b&quot;);
Node&lt;String&gt; c= new Node(&quot;c&quot;);
Node&lt;String&gt; d= new Node(&quot;d&quot;);
a.addChild(b);
a.addChild(c);
b.addChild(a);
b.addChild(c);
b.addChild(d);
c.addChild(a);
c.addChild(b);
c.addChild(d);
d.addChild(c);
d.addChild(b);
Graph G1= new Graph(a);
</code></pre>