samedi 23 avril 2016

Haskell QuickCheck Graphs Software Testing Invariants

I'm using QuickCheck in Haskell for software testing and quality assurance and I require to test some function for invariant properties.

Here is the code am I testing:

import Control.Monad.State
import Data.Maybe
import Data.Set as Set

-- | The'Edge' type represents an edge between two vertex(node).
data Edge v = Edge {source :: v, target :: v}
              deriving (Show,Eq,Ord)

-- | The 'Graph' type represents an directed graph.
data Graph v = Graph {nodes :: Set v, edges :: Set (Edge v)}
               deriving Show

-- | 'Eq' instance for graphs.
instance Ord v => Eq (Graph v) where
    g == g' = nodes g == nodes g' && edges g == edges g'



-- | 'swap' swaps the origin and destination of an edge.
swap :: Edge v -> Edge v
swap e = Edge {source = target e, target = source e}

-- | Empty graph.
empty :: Graph v
empty = Graph {nodes = Set.empty, edges = Set.empty}  


-- | 'isEmpty' tests if a graph is empty.
isEmpty :: Graph v -> Bool
isEmpty g = Set.null (nodes g)


-- | 'isValid' tests if a graph is valid, in other words, if all the nodes/vertex have
-- as origin and destination one of the edges of the graph, and if there's no more than one edge equal in a pair of nodes.
isValid :: Ord v => Graph v -> Bool
isValid g = (Set.map source (edges g) `Set.union` Set.map target (edges g)) `isSubsetOf` nodes g


-- | 'isDAG' tests if a 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 type 'DAG v' is an alias for graphs that satisfy the predicate 'isDAG'.
type DAG v = Graph v


-- | 'isForest' tests if a valid DAG is a florest (a set of trees), in other words,
-- if every edge has only one adjacent.
isForest :: Ord v => DAG v -> Bool
isForest g = isDAG g && all (\v -> length (adj g v) <= 1) (nodes g)

-- | The type 'Forest'is an alias for DAGs who satisfy the predicate'isForest'.
type Forest v = DAG v


-- | 'isSubgraphOf' tests if the first graph is subgraph of the second.
isSubgraphOf :: Ord v => Graph v -> Graph v -> Bool
isSubgraphOf g g' = isSubsetOf (nodes g) (nodes g') && isSubsetOf (edges g) (edges g')


-- | 'adj' returns the list of edges adjacent to a given vertex/node.
adj :: Ord v => Graph v -> v -> Set (Edge v)
adj g v = Set.filter ((==v) . source) $ edges g


-- | 'transpose' inverts the edges of a given graph
transpose :: Ord v => Graph v -> Graph v
transpose g = Graph {nodes = nodes g, edges = Set.map swap (edges g)}


-- | `union`does the union of two graphs
union :: Ord v => Graph v -> Graph v -> Graph v
union g g' = Graph {nodes = nodes g `Set.union` nodes g', edges = edges g `Set.union` edges g'}

The functions that I require to test for are: 'isEmpty'; 'isValid'; 'isDAG'; 'isForest'; 'isSubgraphOf'; 'adj'; 'transpose'; 'union';

Here is what I have so far:

-- Example of QuickCheck propriety to  the function. isEmpty
prop_isempty :: Graph Int -> Property
prop_isempty g = not (null g) ==> Set.null (nodes g) && Set.null (edges g)

-- Example of QuickCheck propriety to test the function. isValid 
prop_isvalid :: Graph Int -> Property
prop_isvalid g = not (null g) ==> nodes g == nodes (isValid g)

-- Example of QuickCheck propriety to test the function. isDAG 
prop_isDAG :: Graph Int -> Property
prop_isDAG g = 

-- Example of QuickCheck propriety to test the function. isForest
prop_isForest :: Graph Int -> Property
prop_isForest g = 

-- Example of QuickCheck propriety to test the function. isSubgraphOf
prop_isSubgraphOf:: Graph Int -> Property
prop_isSubgraphOf = forAll (elements $ elems $ nodes g) $ \v -> adj g v `isSubsetOf` edges g

-- Example of QuickCheck propriety to test the function.o adj          
prop_adj :: Graph Int -> Property
prop_adj g = 

-- Example of QuickCheck propriety to test the function. transpose          
prop_transpose :: Graph Int -> Property
prop_transpose g = transpose (transpose g) == g

-- Example of QuickCheck propriety to test the function. union          
prop_union :: Graph Int -> Graph Int -> Property
prop_union g g' = do
                    length1 <- g
                    length2 <- g'
                    length3 <- length g + length g'
                  return $ (length1+length2) == length3

If someone well versed in QuickCheck && Graphs && Haskell could help refine/revise/re-implement these testing proprieties I would be eternally grateful!

Aucun commentaire:

Enregistrer un commentaire