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

Question

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)

Answer 1

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

DAG：如果您的节点承认某种顺序，并且对于每条边 (u,v) 您有 u < v 那么该图是无环的。此排序可以是任何排序，因此您可以对图中的节点集进行任意排序。

Forest：如果你的图没有边，这属性是微不足道的满足。最初，您可以添加源为任何节点的任何边。如果添加边，请从剩余的可用节点中删除该边的源。

我想最大的问题是如何将其转化为代码。 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

对于每个节点，这将计算比该节点 "greater" 的（非空）节点集。这里的 "greater" 只是表示按照列表中元素的顺序引起的任意排序。这为您提供了 DAG 属性.

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

然后你得到那个列表的一个随机子列表（它让你得到森林属性），并且对于那个随机子列表中的每个元素，你创建一个从 "largest" 节点指向的边设置为 "smaller"。

    return $ Graph ns (Set.fromList es)

那就大功告成了！像这样测试：

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

Answer 2

构造图的一种自然方式是归纳法，一次添加一个节点。然后确保所需的属性保持变得非常容易：

如果对于每个添加的节点，其边缘仅指向现有节点（而不是另一个方向），我们确保 DAG 属性。
如果从一个节点至多有一条边，我们确保森林属性。（由于您没有提供 adj 函数，因此不清楚 "forest" 是否意味着最多有一条边从来自节点或到一个节点。）

所以生成这样一个图的过程如下：

生成随机节点列表。
通过将它们一个一个地相加来构建一个图表。对于每个节点，要么向已添加的节点之一添加随机边，要么不添加边（随机决定）。

这里的主要因素是决定是否添加边缘。通过调整此参数，您可以在森林中获得更多或更少的树木。一种选择是为此使用 frequency。

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

Arbitrary instance for generating unbiased graphs for quickcheck

haskell

testing

graph

geometry

quickcheck