Skip to content

Instantly share code, notes, and snippets.

@nwjsmith
Created June 3, 2017 15:12
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save nwjsmith/0f4288db2f7c0be8b06e5237d6175b3d to your computer and use it in GitHub Desktop.
Save nwjsmith/0f4288db2f7c0be8b06e5237d6175b3d to your computer and use it in GitHub Desktop.
A test.check generator for a DAG
(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))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment