Graph.hs

{- | Calculating the properties of graph algorithms scales very badly
because the specifications aren't optimised (naturally). Exhaustive testing
is a lot more effective than randomized testing in this case because it
avoids computations on large graphs. -}

{-# OPTIONS_GHC -Wno-orphans #-}
module Darcs.Test.Misc.Graph ( testSuite ) where

import Darcs.Prelude

import Darcs.Util.Graph
  ( Graph
  , Component
  , genGraphs
  , genComponents
  , prop_ltmis_eq_bkmis
  , prop_ltmis_maximal_independent_sets
  , prop_ltmis_all_maximal_independent_sets
  , prop_components
  )

import Test.Framework
    ( Test
    , plusTestOptions
    , testGroup
    , topt_maximum_generated_tests
    )
import Test.Framework.Providers.LeanCheck ( testProperty )
import Test.LeanCheck

testSuite :: Test
testSuite =
  {- Unfortunately, test-framework is a bit limited in that it doesn't allow
  to scale the number of tests, just to set them to a fixed value. We opt to
  set it to 0x8000 which roughly covers the graphs up to size 6 and
  completes reasonably fast. The estimate is not precise because it doesn't
  account for graphs with more than one component; however, the overall
  error is not big because the majority of graphs have only one component,
  e.g. for graphs of size 6 the average number of components is 1.22. -}
  plusTestOptions (mempty { topt_maximum_generated_tests = Just 0x8000 }) $
  testGroup "Darcs.Util.Graph"
  [ testProperty "ltmis is equivalent to bkmis" prop_ltmis_eq_bkmis
  , testProperty
      "ltmis generates only maximal independent sets"
      prop_ltmis_maximal_independent_sets
  , testProperty
      "ltmis generates all maximal independent sets"
      prop_ltmis_all_maximal_independent_sets
  , testProperty
      "components generates all connected components"
      prop_components
  ]

instance Listable Graph where
  tiers = map genGraphs [0..]

instance Listable Component where
  tiers = map genComponents [0..]