blob: 7f9e3e64a11e4a7fcd37f36c020c21ad4705947f (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
{-|
Module : Test.VeriFuzz.Graph.Random
Description : Random generation for DAG
Copyright : (c) 2018-2019, Yann Herklotz Grave
License : BSD-3
Maintainer : ymherklotz [at] gmail [dot] com
Stability : experimental
Portability : POSIX
Define the random generation for the directed acyclic graph.
-}
module Test.VeriFuzz.Graph.Random where
import Data.Graph.Inductive (Graph, LEdge, mkGraph)
import Data.Graph.Inductive.PatriciaTree (Gr)
import Test.QuickCheck (Arbitrary, Gen)
import qualified Test.QuickCheck as QC
-- | Gen instance to create an arbitrary edge, where the edges are limited by
-- `n` that is passed to it.
arbitraryEdge :: (Arbitrary e) => Int -> Gen (LEdge e)
arbitraryEdge n = do
x <- with $ \a -> a < n && a > 0 && a /= n-1
y <- with $ \a -> x < a && a < n && a > 0
z <- QC.arbitrary
return (x, y, z)
where
with = QC.suchThat $ QC.resize n QC.arbitrary
-- | Gen instance for a random acyclic DAG.
randomDAG :: (Arbitrary l, Arbitrary e)
=> Gen (Gr l e) -- ^ The generated graph. It uses Arbitrary to
-- generate random instances of each node
randomDAG = do
list <- QC.infiniteListOf QC.arbitrary
l <- QC.infiniteListOf $ aE
QC.sized (\n -> return . mkGraph (nodes list n) $ take (10*n) l)
where
nodes l n = zip [0..n] $ take n l
aE = QC.sized arbitraryEdge
-- | Generate a random acyclic DAG with an IO instance.
genRandomDAG :: (Arbitrary l, Arbitrary e)
=> IO (Gr l e)
genRandomDAG = QC.generate randomDAG
|
