Test.Matroid.Suites

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

Documentation

matroidSuite

Arguments

:: (Matroid m a, Show (m a))

=> Gen (m a)

matroid test case generator

-> SpecWith ()

all tests that any matroid should/must pass

opInvariantsSuite

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

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

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

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

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

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).