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 of the input subset, which has maximal cardinality among all such subsets.

Please note that this routine returns a basis of the input subset wrt. the matroid, which is not necessarily also a basis of the matroid itself. You can obtain at least one basis of the matroid via

basis m $ groundset m

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.