Generate edges from an Arbitrary list of nodes

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}

I currently have this to generate my Graphs. However by using sample on ghci I noticed that it either doesn't generate edges or it generates a single one. Is it possible to control the number of edges generated? How would I do it?

EDIT: A Graph is considered valid when: 1-The source and target nodes of an edge exist. 2-A node can't be the source to more than one Edge.

Answer 1

An 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.

You can use choose to generate other random values than just arbitrary ones.

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}

This naive implementation isn't very efficient when generating large graphs. It could be a factor of number of nodes in the graph faster if it didn't need to scan the list for the generated values each time it uses elements