matroid-0.0.0: matroid (combinatorial pre-geometries) library
Copyright(c) Immanuel Albrecht 2020-202x
LicenseBSD-3
Maintainermail@immanuel-albrecht.de
Stabilityexperimental
PortabilityPOSIX
Safe HaskellNone
LanguageHaskell2010

Test.Matroid.Suites

Description

This module contains hspec test suites that check certain matroid properties.

Synopsis

Documentation

matroidSuite Source #

Arguments

:: (Matroid m a, Show (m a)) 
=> Gen (m a)

matroid test case generator

-> SpecWith () 

all tests that any matroid should/must pass

opInvariantsSuite Source #

Arguments

:: Matroid m a 
=> Gen (m a)

matroid test case generator

-> SpecWith () 

tests the invariants associated with operations on matroids

  • rk_{M|X}(Y) = rk_M(Y)
  • coRk_{M.X}(Y) = coRk_M(Y)
  • rk_(M^*)(Y) = coRk_M(Y)
  • loop(M) = coloop(M^*)
  • coloop(M^*) = loop(M)
  • groundsets of restriction/contraction
  • restriction is the dual of contraction

rkPropertiesSuite Source #

Arguments

:: Matroid m a 
=> Gen (m a)

matroid test case generator

-> SpecWith () 

test suite for rank axioms

The following properties are verified: - rk is monotone increasing - rk(X+{x}) <= rk(X) + 1 (unit increasing) - rk(emptyset) = 0 (important special case) - rk(X) <= |X| (subcardinal) - rk(A/B) + rk(A/B) <= rk(A) + rk(B) (submodular)

indepPropertiesSuite Source #

Arguments

:: Matroid m a 
=> Gen (m a)

matroid test case generator

-> SpecWith () 

test suite for indep properties

The following properties are verified: - indep X && Ysubseteq X => indep Y (hereditary) - indep emptyset - indep X && indep Y && |Y| > |X| => exists yin Y: indep X+{y} (exchange property)

basisPropertiesSuite Source #

Arguments

:: Matroid m a 
=> Gen (m a)

matroid test case generator

-> SpecWith () 

test suite for basis properties

The following properties are verified: - basis X subseteq X - indep (basis X) - y in X(basis X) => not indep (basis X)+{y}

clPropertiesSuite Source #

Arguments

:: Matroid m a 
=> Gen (m a)

matroid test case generator

-> SpecWith () 

test suite for closure operator properties

The following properties are verified: - cl is monotone - cl(X) subseteq E - cl(cl(X)) == cl(X) (idempotence) - e in EX, yin cl(X+{e})cl(X) => e in cl(X+{y}) - rk(X) == rk(cl(X)) and cl(X) is maximal with this property

viaConsistencySuite Source #

Arguments

:: Matroid m a 
=> Gen (m a)

matroid test case generator

-> SpecWith () 

tests a given matroid implementation for equality against the default implementations

rk, indep, and cl should produce the same output when given the same input.

basis however is only required to produce a basis of the given subset, and which basis is produced really depends on how the basis is derived. Here, we are ok if b1 and b2 have cl1(b1) == cl1(b2) == cl2(b1) == cl2(b2).