title: How can I generate random graphs with test.check?
body: <p>I'm trying to generate a random graph in adjacency list form for the purposes of generative testing. An example graph would be:</p>
  
  <pre><code>{:a #{:a :b}, :b #{:a :b}}
  </code></pre>
  
  <p>(Adjacency lists are implemented as sets.)</p>
  
  <p>My first idea was this:</p>
  
  <pre><code>(def vertex-gen (tcgen/fmap (comp keyword str) tcgen/char-alpha-numeric))
  
  (def random-graph-gen-1
    (tcgen/let [vertices (tcgen/set vertex-gen {:min-elements 1})]
               (tcgen/map (tcgen/elements vertices)
                          (tcgen/set (tcgen/elements vertices)))))
  </code></pre>
  
  <p>(<code>{min-elements 1}</code> is required because <code>tcgen/elements</code> doesn't work on empty sets.)</p>
  
  <p>However, this runs the risk of generating graphs such as</p>
  
  <pre><code>{:a #{:a :b}}
  </code></pre>
  
  <p>where <code>:b</code> is randomly selected for <code>:a</code>'s adjacency list, but not selected for the graph itself. So <code>:a</code> has a neighbor that doesn't exist.</p>
  
  <p>Another option is</p>
  
  <pre><code>(def random-graph-gen-2
    (tcgen/let [vertices (tcgen/set vertex-gen)]
               (-&gt;&gt; vertices
                    (map #(-&gt;&gt; vertices
                               (tcgen/elements)
                               (tcgen/set)
                               (tcgen/generate)
                               (vector %)))
                    (into {}))))
  </code></pre>
  
  <p>which iterates through all the vertices and explicitly generates a random adjacency list for each vertex. This guarantees that all vertices will appear in the graph but has the downside that test.check doesn't see the adjacency lists being generated. So I'm worried that this will screw up the shrinking logic.</p>
  
  <p>Is there a solution that avoids both these pitfalls?</p>