用于生成快速检查的无偏图的任意实例 [英] Arbitrary instance for generating unbiased graphs for quickcheck

问题描述

 模块Main其中
 
 import Test.QuickCheck 
导入Data.Set作为集合
 
数据边缘v =边缘{source :: v，target :: v} 
 deriving（Show，Eq，Ord）
 
 data Graph v = Graph {nodes :: Set v，edges :: Set（Edge v ）} 
导出显示
 
实例任意v =>内部 - >任意（边缘v）其中
任意=尺寸辅助
其中aux n = do s < - 任意
t < - 任意`suchThat`（/ = s）
返回$ Edge {source = s，target = t} 
 
 
 instance（Ord v，Arbitrary v）=>任意（图v）其中
 arbitrary = aux`suchThat` isValid 
其中aux = do ns < - 任意
 es < - 任意
返回$ Graph {nodes = fromList ns，edges = fromList es} 
  

该实例的当前定义是生成具有极少边的图，我是否会改变它，所以它没有偏见，它满足这两个功能？ ：

- |函数'isDAG'测试图是否是非循环的。

  isDAG :: Ord v =>图表v  - > Bool 
 isDAG g = isValid g&&所有nocycle（节点g）
其中nocycle v = all（\  -   - > v`notMember`可到达ga）$ Set.map目标（adj gv）
  

- |函数'isForest'测试一个有效的DAG是否是一个florest（一组树），换句话说，
- 如果每个节点（顶点）最多有一个相邻的。

  isForest :: Ord v => DAG v  - > Bool 
 isForest g = isDAG g&& all（\v->长度（adjgv）< = 1）（节点g）
  

解决方案

首先，您必须弄清楚如何构建满足这些属性的图。
$ b $ DAG：如果你的节点承认了一些排序，并且对于每个边（u，v），你有 u < v 那么该图是非循环的。此排序可以是任何排序，因此您可以在图形中的一组节点上制作任意排序。

森林：如果你的图没有边，这个属性很平常。最初，您可以添加其源为任何节点的任何边缘。如果添加边，则从剩余的可用节点中删除该边的源。

我想最大的问题是如何将其转换为代码。 QuickCheck提供了许多组合器，尤其是。 （Ord v，Arbitrary v）=>从列表中选择，有和没有替换，各种尺寸等。

  ;任意（图v）其中
任意= do 
 ns<  -  Set.fromList< $> liftA2（++）（replicateM 10任意）任意
  

首先生成一组随机节点。

  let ns'=地图反转$ drop 2 $ inits $ Set.toList ns 
  

对于每个节点，这将计算比该节点更大的（非空）节点集。这里的更大仅仅意味着根据列表中的元素顺序引起的任意排序。这为您带来了DAG属性。

  es<  -  sublistOf ns'>> = 
 mapM（\\ \\（f：ts） - >边缘f< $>元素ts）
  

获取该列表的随机子列表（获取森林属性），并为该随机子列表中的每个元素创建一个从该集合中最大节点指向较小节点的边缘。

  return $ Graph ns（Set.fromList es）
  

然后你就完成了！测试如下：

  main = quickCheck $ forAll任意（liftA2（&&））（isDAG ::图表整数 - > ; Bool）isForest）
  

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}

This current definition of the instance is generating graphs with few edges, how do I alter it so it's less biased and it satisfies these two functions? :

-- | The function 'isDAG' tests if the graph is acyclic.

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)

-- | The function 'isForest' tests if a valid DAG is a florest (a set of trees), in other words, -- if every node(vertex) has a maximum of one adjacent.

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

解决方案

First you must figure out how to construct a graph which satisfies those properties.

DAG: If your nodes admit some ordering, and for each edge (u,v) you have u < v then the graph is acyclic. This ordering can be any ordering at all, so you can just manufacture an arbitrary ordering on the set of nodes in the graph.

Forest: If your graph has no edges, this property is trivially satisfied. Initially you can add any edge whose source is any node. If you add an edge, remove the source of that edge from the remaining available nodes.

I guess the big question is how to translate this to code. QuickCheck provides many combinators, esp. for selecting from lists, with and without replacement, of various sizes, etc.

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

First you generate a random set of nodes.

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

For each node, this computes the (non-empty) set of nodes which are "greater" than that node. Here "greater" just means according to the arbitrary ordering induced by the order of the elements in the list. This gets you the DAG property.

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

You then get a random sublist of that list (which gets you the forest property), and for each element in that random sublist, you create an edge pointing from the "largest" node in that set to one that is "smaller".

    return $ Graph ns (Set.fromList es) 

Then you're done! Test like so:

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

这篇关于用于生成快速检查的无偏图的任意实例的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！