A test.check generator for a DAG

gen_dag.clj

(def gen-node
  "Generates graph nodes."
  (gen/fmap str gen/uuid))


(defn gen-connecting-edges
  "Generates edges between a connecting node and some subset of the given
  nodes."
  [connecting-node nodes]
  (gen/fmap (partial map (partial vector connecting-node))
            (gen/set (gen/elements nodes) {:min-elements 1})))


(defn gen-acyclic-edges
  "Generates edges between nodes. None of the edges will form a cycle."
  [nodes]
  (gen/fmap (partial mapcat identity)
            (loop [[current & remaining] nodes gens []]
              (if (= 0 (count remaining))
                (apply gen/tuple gens)
                (recur remaining
                       (conj gens (gen-connecting-edges current remaining)))))))


(def gen-dag
  "Generates lists of edges of directed, acyclic graphs. Edges are of the form
  `[from-node to-node]`."
  (gen/let [nodes (gen/vector-distinct gen-node {:min-elements 2})
            edges (gen-acyclic-edges nodes)]
    edges))