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

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 是否为 florest（一组树），换句话说， -- 如果每个节点（顶点）最多有一个相邻节点。

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)