clojure - 如何使用 test.check 生成随机图？

问题描述

为了生成测试，我正在尝试以邻接列表形式生成随机图。一个示例图是：

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

（邻接表作为集合实现。）

我的第一个想法是这样的：

(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}是必需的，因为tcgen/elements不适用于空集。）

但是，这会产生生成图表的风险，例如

{:a #{:a :b}}

where:b是为的邻接列表随机选择的:a，但不是为图本身选择的。所以:a有一个不存在的邻居。

另一种选择是

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

它遍历所有顶点并为每个顶点显式生成一个随机邻接列表。这保证了所有顶点都将出现在图中，但缺点是 test.check 看不到正在生成的邻接列表。所以我担心这会破坏缩小的逻辑。

有没有避免这两个陷阱的解决方案？

标签： clojuretest.check

这是另一种方法：

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

这引入了第二个生成器，它为每个顶点生成一组边，然后将顶点和边压缩到一个地图中。

在您的第二个示例中使用generate的是引入不受整个生成器大小限制的随机性。从generate文档字符串：

请注意，此函数是一个开发助手，并不意味着用于构建其他生成器。

但是您可以使用generate从生成器中采样不同尺寸：

(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 #{}}

clojure - 如何使用 test.check 生成随机图？

问题描述

解决方案

推荐阅读