Data.Matroid.Typeclass

This module provides the Matroid typeclass.

Documentation

class (Ord a, Show a) => Matroid m a where

Typeclass that provides the full matroid interface.

The type parameter a is the type of the elements of the matroid, it is most commonly used in a Set a type.

In this typeclass, we assume that every set of matroid elements passed to any of the routines is actually a subset of (groundset m). Behaviour for other sets shall be considered undefined.

In order to keep things DRY, the default implementations are fumbled through the (AMatroid a) instance definition below through wrapUp and setting the corresponding record value to Nothing.

Minimal complete definition

groundset, (rk | indep | basis)

Methods

groundset :: m a -> Set a

The ground set of the matroid, its elements are usually called edges. This set is finite.

showName :: m a -> String

name of the matroid, may be used for show

rk

Arguments

:: m a

the matroid

-> Set a

set of matroid elements

-> Int

returns the rank of the set

indep

Arguments

:: m a

the matroid

-> Set a

set of matroid elements

-> Bool

tests whether a given set is independent

basis

Arguments

:: m a

the matroid

-> Set a

set of matroid elements

-> Set a

obtains an independent subset with maximal cardinality

cl

Arguments

:: m a

the matroid

-> Set a

set of matroid elements

-> Set a

computes the closure of a given set

abstract

Arguments

:: m a

matroid

-> AMatroid a

returns this matroid as abstract matroid object

dual

Arguments

:: m a

matroid

-> AMatroid a

returns the dual of this matroid as abstract matroid object

restriction

Arguments

:: m a

the matroid

-> Set a

restricts the ground set to this set

-> AMatroid a

returns the restricted matroid M|X as result of the unary matroid operation *|X

contraction

Arguments

:: m a

the matroid

-> Set a

contracts the ground set onto this set

-> AMatroid a

returns the contracted matroid M.X as a result of the unary matroid operation *.X

loops

Arguments

:: m a

the matroid

-> Set a

returns the loops in the matroid

coRk

Arguments

:: m a

the matroid

-> Set a

set of matroid elements

-> Int

rank function of the dual matroid

coloops

Arguments

:: m a

the matroid

-> Set a

returns the coloops in the matroid

Instances

(Ord a, Show a) => Matroid AMatroid a

This instance contains the default implementations of the members of the Matroid typeclass.

Defined in Data.Matroid.Typeclass

Methods

groundset :: AMatroid a -> Set a

showName :: AMatroid a -> String

rk :: AMatroid a -> Set a -> Int

indep :: AMatroid a -> Set a -> Bool

basis :: AMatroid a -> Set a -> Set a

cl :: AMatroid a -> Set a -> Set a

abstract :: AMatroid a -> AMatroid a

dual :: AMatroid a -> AMatroid a

restriction :: AMatroid a -> Set a -> AMatroid a

contraction :: AMatroid a -> Set a -> AMatroid a

loops :: AMatroid a -> Set a

coRk :: AMatroid a -> Set a -> Int

coloops :: AMatroid a -> Set a

(Ord a, Show a) => Matroid BasisFilterMatroid a

Defined in Data.Matroid.Internal

Methods

groundset :: BasisFilterMatroid a -> Set a

showName :: BasisFilterMatroid a -> String

rk :: BasisFilterMatroid a -> Set a -> Int

indep :: BasisFilterMatroid a -> Set a -> Bool

basis :: BasisFilterMatroid a -> Set a -> Set a

cl :: BasisFilterMatroid a -> Set a -> Set a

abstract :: BasisFilterMatroid a -> AMatroid a

dual :: BasisFilterMatroid a -> AMatroid a

restriction :: BasisFilterMatroid a -> Set a -> AMatroid a

contraction :: BasisFilterMatroid a -> Set a -> AMatroid a

loops :: BasisFilterMatroid a -> Set a

coRk :: BasisFilterMatroid a -> Set a -> Int

coloops :: BasisFilterMatroid a -> Set a

(Ord a, Show a) => Matroid IndepMatroid a

Defined in Data.Matroid.Internal

Methods

groundset :: IndepMatroid a -> Set a

showName :: IndepMatroid a -> String

rk :: IndepMatroid a -> Set a -> Int

indep :: IndepMatroid a -> Set a -> Bool

basis :: IndepMatroid a -> Set a -> Set a

cl :: IndepMatroid a -> Set a -> Set a

abstract :: IndepMatroid a -> AMatroid a

dual :: IndepMatroid a -> AMatroid a

restriction :: IndepMatroid a -> Set a -> AMatroid a

contraction :: IndepMatroid a -> Set a -> AMatroid a

loops :: IndepMatroid a -> Set a

coRk :: IndepMatroid a -> Set a -> Int

coloops :: IndepMatroid a -> Set a

(Ord a, Show a) => Matroid RkMatroid a

Defined in Data.Matroid.Internal

Methods

groundset :: RkMatroid a -> Set a

showName :: RkMatroid a -> String

rk :: RkMatroid a -> Set a -> Int

indep :: RkMatroid a -> Set a -> Bool

basis :: RkMatroid a -> Set a -> Set a

cl :: RkMatroid a -> Set a -> Set a

abstract :: RkMatroid a -> AMatroid a

dual :: RkMatroid a -> AMatroid a

restriction :: RkMatroid a -> Set a -> AMatroid a

contraction :: RkMatroid a -> Set a -> AMatroid a

loops :: RkMatroid a -> Set a

coRk :: RkMatroid a -> Set a -> Int

coloops :: RkMatroid a -> Set a

(Ord a, Show a) => Matroid FreeMatroid a

Defined in Data.Matroid.Uniform

Methods

groundset :: FreeMatroid a -> Set a

showName :: FreeMatroid a -> String

rk :: FreeMatroid a -> Set a -> Int

indep :: FreeMatroid a -> Set a -> Bool

basis :: FreeMatroid a -> Set a -> Set a

cl :: FreeMatroid a -> Set a -> Set a

abstract :: FreeMatroid a -> AMatroid a

dual :: FreeMatroid a -> AMatroid a

restriction :: FreeMatroid a -> Set a -> AMatroid a

contraction :: FreeMatroid a -> Set a -> AMatroid a

loops :: FreeMatroid a -> Set a

coRk :: FreeMatroid a -> Set a -> Int

coloops :: FreeMatroid a -> Set a

(Ord a, Show a) => Matroid UniformMatroid a

Defined in Data.Matroid.Uniform

Methods

groundset :: UniformMatroid a -> Set a

showName :: UniformMatroid a -> String

rk :: UniformMatroid a -> Set a -> Int

indep :: UniformMatroid a -> Set a -> Bool

basis :: UniformMatroid a -> Set a -> Set a

cl :: UniformMatroid a -> Set a -> Set a

abstract :: UniformMatroid a -> AMatroid a

dual :: UniformMatroid a -> AMatroid a

restriction :: UniformMatroid a -> Set a -> AMatroid a

contraction :: UniformMatroid a -> Set a -> AMatroid a

loops :: UniformMatroid a -> Set a

coRk :: UniformMatroid a -> Set a -> Int

coloops :: UniformMatroid a -> Set a

(Ord a, Ord v, Show a) => Matroid (GraphicMatroid v) a

Defined in Data.Matroid.Graphic

Methods

groundset :: GraphicMatroid v a -> Set a

showName :: GraphicMatroid v a -> String

rk :: GraphicMatroid v a -> Set a -> Int

indep :: GraphicMatroid v a -> Set a -> Bool

basis :: GraphicMatroid v a -> Set a -> Set a

cl :: GraphicMatroid v a -> Set a -> Set a

abstract :: GraphicMatroid v a -> AMatroid a

dual :: GraphicMatroid v a -> AMatroid a

restriction :: GraphicMatroid v a -> Set a -> AMatroid a

contraction :: GraphicMatroid v a -> Set a -> AMatroid a

loops :: GraphicMatroid v a -> Set a

coRk :: GraphicMatroid v a -> Set a -> Int

coloops :: GraphicMatroid v a -> Set a

wrapUp :: Matroid m a => m a -> AMatroid a

takes an object of a type that implements the Matroid typeclass, and turns it into an AMatroid record.