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

Question

我正试图以邻接列表的形式生成一个随机图，用于生成测试。一个示例图是：

{: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}}

其中: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看不到正在生成的邻接列表。所以我担心这会破坏正在缩小的逻辑。

有没有一个解决方案可以避免这两个陷阱？

Answer 1

这里有另一种方法：

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