为了生成测试,我正在尝试以邻接列表形式生成随机图。一个示例图是:
{: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 看不到正在生成的邻接列表。所以我担心这会破坏缩小的逻辑。
有没有避免这两个陷阱的解决方案?