How can I generate random graphs with test.check?

I'm trying to generate a random graph in adjacency list form for the purposes of generative testing. An example graph would be:

{:a #{:a :b}, :b #{:a :b}}

(Adjacency lists are implemented as sets.)

My first idea was this:

(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)))))

({min-elements 1} is required because tcgen/elements doesn't work on empty sets.)

However, this runs the risk of generating graphs such as

{:a #{:a :b}}

where :b is randomly selected for :a's adjacency list, but not selected for the graph itself. So :a has a neighbor that doesn't exist.

Another option is

(def random-graph-gen-2
  (tcgen/let [vertices (tcgen/set vertex-gen)]
             (->> vertices
                  (map #(->> vertices
                             (tcgen/elements)
                             (tcgen/set)
                             (tcgen/generate)
                             (vector %)))
                  (into {}))))

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.

Is there a solution that avoids both these pitfalls?

Solution

Here's another way to do it:

(def graph-gen
  (gen/let [vertices (gen/set vertex-gen {:min-elements 1})
            edges (-> vertices
                      (gen/elements)
                      (gen/set)
                      (gen/vector (count vertices)))]
    (zipmap vertices edges)))

This introduces a second generator that produces a set of edges for each vertex, then zips the vertices and edges into a single map.

Using generate in your second example is introducing randomness that isn't bound by the size of the overall generator. From generate docstring:

Note that this function is a dev helper and is not meant to be used to build other generators.

But you can use generate to sample from the generator for different sizes:

(gen/generate graph-gen 2)
=> {:F #{}, :e #{}, :S #{:e}}
(gen/generate graph-gen 10)
=>
{:L #{:n :7 :8 :H},
 :n #{:L :n :7 :C :8 :b :H :V},
 :7 #{:L :7 :C :8 :9 :b},
 :C #{:L :9 :V},
 :8 #{:L :n :7 :C :8 :9 :b :V},
 :9 #{:L :b :a},
 :b #{:n :V},
 :H #{:a},
 :V #{:n :C :b :H},
 :a #{}}