title: How to generate random graphs?
body: <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>