从任意节点列表生成边

Question

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 => Arbitrary (Edge v) where
    arbitrary = do s <- arbitrary
                   t <- arbitrary
                   return $ Edge {source = s, target = t}

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

我目前用它来生成我的图表。但是，通过在 ghci 上使用示例，我注意到它要么不生成边，要么生成单个边。是否可以控制生成的边数？我该怎么做？

编辑：图表在以下情况下被视为有效： 1-一条边的源节点和目标节点存在。 2-一个节点不能是多个边的源。

Answer 1

一个arbitrary value is a value in the Gen monad. You can do more in this monad than just combine arbitrary values together. You can perform any of the other Gen operations including choose:

choose :: Random a => (a, a) -> Gen a
Generates a random element in the given inclusive range.

您可以使用 choose 生成除 arbitrary 之外的其他随机值。

instance (Ord v, Arbitrary v) => Arbitrary (Graph v) where
    arbitrary = do
        nodes <- arbitrary
        let
            lNodes = toList nodes
            numNodes = length lNodes
            arbitraryEdge = do
                source <- elements lNodes
                target <- elements lNodes
                return $ Edge {
                    source = source,
                    target = target
                }
        numEdges <- choose (0, numNodes * numNodes)
        lEdges <- vectorOf numEdges arbitraryEdge
        return $ Graph {nodes = nodes, edges = fromList lEdges}

这种天真的实现在生成大图时效率不高。如果它不需要每次使用 elements

时都需要扫描列表以获取生成的值，那么它可能是图中节点数量更快的一个因素

从任意节点列表生成边

Generate edges from an Arbitrary list of nodes

haskell

testing

quickcheck