haskell - 用于生成无偏图进行快速检查的任意实例

module Main where

import Test.QuickCheck
import Data.Set as Set

data Edge v = Edge {source :: v, target :: v}
                  deriving (Show,Eq,Ord)

data Graph v = Graph {nodes :: Set v, edges :: Set (Edge v)}
               deriving Show

instance Arbitrary v => Int-> Arbitrary (Edge v) where
    arbitrary = sized aux
        where aux n = do s <- arbitrary
                         t <- arbitrary `suchThat` (/= s)
                         return $ Edge {source = s, target = t}


instance (Ord v, Arbitrary v) => Arbitrary (Graph v) where
    arbitrary = aux `suchThat` isValid
        where aux = do ns <- arbitrary
                       es <- arbitrary
                       return $ Graph {nodes = fromList ns, edges = fromList es}

实例的当前定义正在生成几乎没有边缘的图，如何更改它以减少偏见并满足这两个功能？ ：

-|函数“ isDAG”测试图是否为非循环图。

isDAG :: Ord v => Graph v -> Bool
isDAG g = isValid g && all nocycle (nodes g)
    where nocycle v = all (\a -> v `notMember` reachable g a) $ Set.map target (adj g v)

-|函数“ isForest”测试有效的DAG是否为小花（一组树木），换句话说，
-如果每个节点（顶点）最多具有一个相邻的节点。

isForest :: Ord v => DAG v -> Bool
isForest g = isDAG g && all (\v -> length (adj g v) <= 1) (nodes g)

最佳答案

首先，您必须弄清楚如何构造满足这些属性的图。

DAG：如果您的节点允许一些排序，并且对于每个边(u,v)，您都有u < v，则该图是非循环的。此排序完全可以是任何排序，因此您可以在图形中的节点集上制造任意排序。

森林：如果图形没有边，则可以轻松满足此属性。最初，您可以添加源为任何节点的任何边。如果添加边缘，请从其余可用节点中删除该边缘的源。

我想最大的问题是如何将其转换为代码。 QuickCheck提供了许多组合器，尤其是。用于从列表中进行选择，有或没有替代品，各种尺寸等。

instance (Ord v, Arbitrary v) => Arbitrary (Graph v) where
  arbitrary = do
    ns <- Set.fromList <$> liftA2 (++) (replicateM 10 arbitrary) arbitrary

首先，您生成一组随机节点。

    let ns' = map reverse $ drop 2 $ inits $ Set.toList ns

对于每个节点，这将计算（大于）该节点“（非空）”的节点集。在这里，“更大”仅表示根据列表中元素顺序产生的任意顺序。这将为您提供DAG属性。

    es <- sublistOf ns' >>=
            mapM (\(f:ts) -> Edge f <$> elements ts)

然后，您将获得该列表的一个随机子列表（这将为您提供林属性），并为该随机子列表中的每个元素创建一个从该集合中“最大”节点指向“较小”节点的边。

    return $ Graph ns (Set.fromList es)

这样就完成了！像这样测试：

main = quickCheck $ forAll arbitrary (liftA2 (&&) (isDAG :: Graph Integer -> Bool) isForest)

关于haskell - 用于生成无偏图进行快速检查的任意实例，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/36398392/