{-# LANGUAGE FlexibleInstances, MultiParamTypeClasses #-}
{-|
Module      : Test.Matroid.Generators
Description : 
Copyright   : (c) Immanuel Albrecht, 2020-202x
License     : BSD-3
Maintainer  : mail@immanuel-albrecht.de
Stability   : experimental
Portability : POSIX

This module contains QuickCheck generators for testing purposes.

-}

module Test.Matroid.Generators where

import Data.Matroid
import Data.Matroid.Internal
import Test.QuickCheck


import qualified Data.Set as S


-- | a generator for uniform matroids of a reasonable size
genUniformMatroids :: Gen (UniformMatroid Int)
genUniformMatroids :: Gen (UniformMatroid Int)
genUniformMatroids = do Int
r <- (Int, Int) -> Gen Int
chooseInt (Int
0,Int
25)
                        Int
n <- (Int, Int) -> Gen Int
chooseInt (Int
r,Int
100)
                        UniformMatroid Int -> Gen (UniformMatroid Int)
forall (m :: * -> *) a. Monad m => a -> m a
return (UniformMatroid Int -> Gen (UniformMatroid Int))
-> UniformMatroid Int -> Gen (UniformMatroid Int)
forall a b. (a -> b) -> a -> b
$ Int -> Int -> UniformMatroid Int
uniform Int
n Int
r

-- | a generator for uniform matroids of small size
genSmallUniformMatroids :: Gen (UniformMatroid Int)
genSmallUniformMatroids :: Gen (UniformMatroid Int)
genSmallUniformMatroids = do Int
r <- (Int, Int) -> Gen Int
chooseInt (Int
0,Int
6)
                             Int
n <- (Int, Int) -> Gen Int
chooseInt (Int
r,Int
15)
                             UniformMatroid Int -> Gen (UniformMatroid Int)
forall (m :: * -> *) a. Monad m => a -> m a
return (UniformMatroid Int -> Gen (UniformMatroid Int))
-> UniformMatroid Int -> Gen (UniformMatroid Int)
forall a b. (a -> b) -> a -> b
$ Int -> Int -> UniformMatroid Int
uniform Int
n Int
r

                        
-- | a generator for graphic matroids of reasonable size
genGraphicMatroids :: Gen (GraphicMatroid Int (Int,Int,Int))
genGraphicMatroids :: Gen (GraphicMatroid Int (Int, Int, Int))
genGraphicMatroids =  do Int
v_ <- (Int, Int) -> Gen Int
chooseInt (Int
1,Int
8) 
                         Int
n_ <- (Int, Int) -> Gen Int
chooseInt (Int
0,Int
100) 
                         let genEdges :: Int -> a -> Gen [(a, Int, Int)]
genEdges Int
v a
n -- :: Gen [(Int,Int,Int)]
                                    | a
n a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
0 = [(a, Int, Int)] -> Gen [(a, Int, Int)]
forall (m :: * -> *) a. Monad m => a -> m a
return ([(a, Int, Int)] -> Gen [(a, Int, Int)])
-> [(a, Int, Int)] -> Gen [(a, Int, Int)]
forall a b. (a -> b) -> a -> b
$ []
                                    | Bool
otherwise = do Int
s <- (Int, Int) -> Gen Int
chooseInt (Int
1,Int
v)
                                                     Int
t <- (Int, Int) -> Gen Int
chooseInt (Int
1,Int
v) Gen Int -> (Int -> Bool) -> Gen Int
forall a. Gen a -> (a -> Bool) -> Gen a
`suchThat` (Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
s)
                                                     [(a, Int, Int)]
gs <- Int -> a -> Gen [(a, Int, Int)]
genEdges Int
v (a
na -> a -> a
forall a. Num a => a -> a -> a
-a
1)
                                                     [(a, Int, Int)] -> Gen [(a, Int, Int)]
forall (m :: * -> *) a. Monad m => a -> m a
return ([(a, Int, Int)] -> Gen [(a, Int, Int)])
-> [(a, Int, Int)] -> Gen [(a, Int, Int)]
forall a b. (a -> b) -> a -> b
$ (a
n,Int
s,Int
t) (a, Int, Int) -> [(a, Int, Int)] -> [(a, Int, Int)]
forall a. a -> [a] -> [a]
: [(a, Int, Int)]
gs
                           in do
                               [(Int, Int, Int)]
labeledEdges <- Int -> Int -> Gen [(Int, Int, Int)]
forall a. (Eq a, Num a) => Int -> a -> Gen [(a, Int, Int)]
genEdges Int
v_ Int
n_
                               let inc :: (a, a, b) -> (a, b)
inc (a
_,a
a,b
b) = (a
a,b
b)
                                in GraphicMatroid Int (Int, Int, Int)
-> Gen (GraphicMatroid Int (Int, Int, Int))
forall (m :: * -> *) a. Monad m => a -> m a
return (GraphicMatroid Int (Int, Int, Int)
 -> Gen (GraphicMatroid Int (Int, Int, Int)))
-> GraphicMatroid Int (Int, Int, Int)
-> Gen (GraphicMatroid Int (Int, Int, Int))
forall a b. (a -> b) -> a -> b
$ Set (Int, Int, Int)
-> ((Int, Int, Int) -> (Int, Int))
-> GraphicMatroid Int (Int, Int, Int)
forall a v.
(Ord a, Show a) =>
Set a -> (a -> (v, v)) -> GraphicMatroid v a
fromGraph ([(Int, Int, Int)] -> Set (Int, Int, Int)
forall a. Ord a => [a] -> Set a
S.fromList [(Int, Int, Int)]
labeledEdges) (Int, Int, Int) -> (Int, Int)
forall a a b. (a, a, b) -> (a, b)
inc

-- | a generator for graphic matroids of small size
genSmallGraphicMatroids :: Gen (GraphicMatroid Int (Int,Int,Int))
genSmallGraphicMatroids :: Gen (GraphicMatroid Int (Int, Int, Int))
genSmallGraphicMatroids =  
                      do Int
v_ <- (Int, Int) -> Gen Int
chooseInt (Int
1,Int
8) 
                         Int
n_ <- (Int, Int) -> Gen Int
chooseInt (Int
0,Int
20) 
                         let genEdges :: Int -> a -> Gen [(a, Int, Int)]
genEdges Int
v a
n -- :: Gen [(Int,Int,Int)]
                                    | a
n a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
0 = [(a, Int, Int)] -> Gen [(a, Int, Int)]
forall (m :: * -> *) a. Monad m => a -> m a
return ([(a, Int, Int)] -> Gen [(a, Int, Int)])
-> [(a, Int, Int)] -> Gen [(a, Int, Int)]
forall a b. (a -> b) -> a -> b
$ []
                                    | Bool
otherwise = do Int
s <- (Int, Int) -> Gen Int
chooseInt (Int
1,Int
v)
                                                     Int
t <- (Int, Int) -> Gen Int
chooseInt (Int
1,Int
v) Gen Int -> (Int -> Bool) -> Gen Int
forall a. Gen a -> (a -> Bool) -> Gen a
`suchThat` (Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
s)
                                                     [(a, Int, Int)]
gs <- Int -> a -> Gen [(a, Int, Int)]
genEdges Int
v (a
na -> a -> a
forall a. Num a => a -> a -> a
-a
1)
                                                     [(a, Int, Int)] -> Gen [(a, Int, Int)]
forall (m :: * -> *) a. Monad m => a -> m a
return ([(a, Int, Int)] -> Gen [(a, Int, Int)])
-> [(a, Int, Int)] -> Gen [(a, Int, Int)]
forall a b. (a -> b) -> a -> b
$ (a
n,Int
s,Int
t) (a, Int, Int) -> [(a, Int, Int)] -> [(a, Int, Int)]
forall a. a -> [a] -> [a]
: [(a, Int, Int)]
gs
                           in do
                               [(Int, Int, Int)]
labeledEdges <- Int -> Int -> Gen [(Int, Int, Int)]
forall a. (Eq a, Num a) => Int -> a -> Gen [(a, Int, Int)]
genEdges Int
v_ Int
n_
                               let inc :: (a, a, b) -> (a, b)
inc (a
_,a
a,b
b) = (a
a,b
b)
                                in GraphicMatroid Int (Int, Int, Int)
-> Gen (GraphicMatroid Int (Int, Int, Int))
forall (m :: * -> *) a. Monad m => a -> m a
return (GraphicMatroid Int (Int, Int, Int)
 -> Gen (GraphicMatroid Int (Int, Int, Int)))
-> GraphicMatroid Int (Int, Int, Int)
-> Gen (GraphicMatroid Int (Int, Int, Int))
forall a b. (a -> b) -> a -> b
$ Set (Int, Int, Int)
-> ((Int, Int, Int) -> (Int, Int))
-> GraphicMatroid Int (Int, Int, Int)
forall a v.
(Ord a, Show a) =>
Set a -> (a -> (v, v)) -> GraphicMatroid v a
fromGraph ([(Int, Int, Int)] -> Set (Int, Int, Int)
forall a. Ord a => [a] -> Set a
S.fromList [(Int, Int, Int)]
labeledEdges) (Int, Int, Int) -> (Int, Int)
forall a a b. (a, a, b) -> (a, b)
inc

                                
-- | a generator for M(K_n) matroids of reasonable size
genMKnMatroids :: Gen (GraphicMatroid Int (Int,Int))
genMKnMatroids :: Gen (GraphicMatroid Int (Int, Int))
genMKnMatroids = do Int
n <- (Int, Int) -> Gen Int
chooseInt(Int
1,Int
8)
                    GraphicMatroid Int (Int, Int)
-> Gen (GraphicMatroid Int (Int, Int))
forall (m :: * -> *) a. Monad m => a -> m a
return (GraphicMatroid Int (Int, Int)
 -> Gen (GraphicMatroid Int (Int, Int)))
-> GraphicMatroid Int (Int, Int)
-> Gen (GraphicMatroid Int (Int, Int))
forall a b. (a -> b) -> a -> b
$ Int -> GraphicMatroid Int (Int, Int)
mK Int
n
                    
                          
-- | a generator for free matroids of a reasonable size
genFreeMatroids :: Gen (FreeMatroid Int)
genFreeMatroids :: Gen (FreeMatroid Int)
genFreeMatroids = do Int
n <- (Int, Int) -> Gen Int
chooseInt (Int
0,Int
10) --(arbitrary :: Gen Int) `suchThat` (<= 30)
                     FreeMatroid Int -> Gen (FreeMatroid Int)
forall (m :: * -> *) a. Monad m => a -> m a
return (FreeMatroid Int -> Gen (FreeMatroid Int))
-> FreeMatroid Int -> Gen (FreeMatroid Int)
forall a b. (a -> b) -> a -> b
$ Set Int -> FreeMatroid Int
forall a. Ord a => Set a -> FreeMatroid a
freeOn (Set Int -> FreeMatroid Int) -> Set Int -> FreeMatroid Int
forall a b. (a -> b) -> a -> b
$ [Int] -> Set Int
forall a. Ord a => [a] -> Set a
S.fromList [Int
1..Int
n]
                       
-- | a generator for consintency matroid type based on another generator
viaRank :: Matroid m a => Gen (m a) -> Gen (RkMatroid a)
viaRank :: Gen (m a) -> Gen (RkMatroid a)
viaRank Gen (m a)
g = do
                    m a
m_ <- Gen (m a)
g
                    RkMatroid a -> Gen (RkMatroid a)
forall (m :: * -> *) a. Monad m => a -> m a
return (RkMatroid a -> Gen (RkMatroid a))
-> RkMatroid a -> Gen (RkMatroid a)
forall a b. (a -> b) -> a -> b
$ Set a -> (Set a -> Int) -> RkMatroid a
forall a. Show a => Set a -> (Set a -> Int) -> RkMatroid a
fromRk (m a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
groundset m a
m_) (m a -> Set a -> Int
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Int
rk m a
m_)
                    
-- | a generator for consintency matroid type based on another generator
viaIndep :: Matroid m a => Gen (m a) -> Gen (IndepMatroid a)
viaIndep :: Gen (m a) -> Gen (IndepMatroid a)
viaIndep Gen (m a)
g = do
                    m a
m_ <- Gen (m a)
g
                    IndepMatroid a -> Gen (IndepMatroid a)
forall (m :: * -> *) a. Monad m => a -> m a
return (IndepMatroid a -> Gen (IndepMatroid a))
-> IndepMatroid a -> Gen (IndepMatroid a)
forall a b. (a -> b) -> a -> b
$ Set a -> (Set a -> Bool) -> IndepMatroid a
forall a. Show a => Set a -> (Set a -> Bool) -> IndepMatroid a
fromIndep (m a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
groundset m a
m_) (m a -> Set a -> Bool
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Bool
indep m a
m_)

-- | a generator for consintency matroid type based on another generator
viaBasisFilter :: Matroid m a => Gen (m a) -> Gen (BasisFilterMatroid a)
viaBasisFilter :: Gen (m a) -> Gen (BasisFilterMatroid a)
viaBasisFilter Gen (m a)
g = do
                    m a
m_ <- Gen (m a)
g
                    BasisFilterMatroid a -> Gen (BasisFilterMatroid a)
forall (m :: * -> *) a. Monad m => a -> m a
return (BasisFilterMatroid a -> Gen (BasisFilterMatroid a))
-> BasisFilterMatroid a -> Gen (BasisFilterMatroid a)
forall a b. (a -> b) -> a -> b
$ Set a -> (Set a -> Set a) -> BasisFilterMatroid a
forall a.
Show a =>
Set a -> (Set a -> Set a) -> BasisFilterMatroid a
fromBasisFilter (m a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
groundset m a
m_) (m a -> Set a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Set a
basis m a
m_)

-- | a generator for matroids of the form M|X based on a generator for M
viaRestriction :: Matroid m a => Gen (m a) -> Gen (AMatroid a)
viaRestriction :: Gen (m a) -> Gen (AMatroid a)
viaRestriction Gen (m a)
g = do
                    m a
m_ <- Gen (m a)
g
                    [a]
e0 <- [a] -> Gen [a]
forall a. [a] -> Gen [a]
sublistOf ([a] -> Gen [a]) -> [a] -> Gen [a]
forall a b. (a -> b) -> a -> b
$ Set a -> [a]
forall a. Set a -> [a]
S.toList (Set a -> [a]) -> Set a -> [a]
forall a b. (a -> b) -> a -> b
$ m a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
groundset m a
m_
                    let e :: Set a
e = [a] -> Set a
forall a. Ord a => [a] -> Set a
S.fromList [a]
e0
                     in AMatroid a -> Gen (AMatroid a)
forall (m :: * -> *) a. Monad m => a -> m a
return (AMatroid a -> Gen (AMatroid a)) -> AMatroid a -> Gen (AMatroid a)
forall a b. (a -> b) -> a -> b
$ m a
m_ m a -> Set a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> AMatroid a
`restriction` Set a
e

-- | a generator for matroids of the form M.X based on a generator for M
viaContraction :: Matroid m a => Gen (m a) -> Gen (AMatroid a)
viaContraction :: Gen (m a) -> Gen (AMatroid a)
viaContraction Gen (m a)
g = do
                    m a
m_ <- Gen (m a)
g
                    [a]
e0 <- [a] -> Gen [a]
forall a. [a] -> Gen [a]
sublistOf ([a] -> Gen [a]) -> [a] -> Gen [a]
forall a b. (a -> b) -> a -> b
$ Set a -> [a]
forall a. Set a -> [a]
S.toList (Set a -> [a]) -> Set a -> [a]
forall a b. (a -> b) -> a -> b
$ m a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
groundset m a
m_
                    let e :: Set a
e = [a] -> Set a
forall a. Ord a => [a] -> Set a
S.fromList [a]
e0
                     in AMatroid a -> Gen (AMatroid a)
forall (m :: * -> *) a. Monad m => a -> m a
return (AMatroid a -> Gen (AMatroid a)) -> AMatroid a -> Gen (AMatroid a)
forall a b. (a -> b) -> a -> b
$ m a
m_ m a -> Set a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> AMatroid a
`contraction` Set a
e
                     
-- | a generator for matroids of the form M^* based on a generator for M
viaDual :: Matroid m a => Gen (m a) -> Gen (AMatroid a)
viaDual :: Gen (m a) -> Gen (AMatroid a)
viaDual Gen (m a)
g = do
                m a
m_ <- Gen (m a)
g
                AMatroid a -> Gen (AMatroid a)
forall (m :: * -> *) a. Monad m => a -> m a
return (AMatroid a -> Gen (AMatroid a)) -> AMatroid a -> Gen (AMatroid a)
forall a b. (a -> b) -> a -> b
$ m a -> AMatroid a
forall (m :: * -> *) a. Matroid m a => m a -> AMatroid a
dual m a
m_