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

Data.Matroid.Typeclass

Description

This module provides the Matroid typeclass.

Synopsis

Documentation

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

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 Source #

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

showName :: m a -> String Source #

name of the matroid, may be used for show

rk Source #

Arguments

:: m a

the matroid

-> Set a

set of matroid elements

-> Int 

returns the rank of the set

indep Source #

Arguments

:: m a

the matroid

-> Set a

set of matroid elements

-> Bool 

tests whether a given set is independent

basis Source #

Arguments

:: m a

the matroid

-> Set a

set of matroid elements

-> Set a 

obtains an independent subset with maximal cardinality

cl Source #

Arguments

:: m a

the matroid

-> Set a

set of matroid elements

-> Set a 

computes the closure of a given set

abstract Source #

Arguments

:: m a

matroid

-> AMatroid a 

returns this matroid as abstract matroid object

dual Source #

Arguments

:: m a

matroid

-> AMatroid a 

returns the dual of this matroid as abstract matroid object

restriction Source #

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 Source #

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 Source #

Arguments

:: m a

the matroid

-> Set a 

returns the loops in the matroid

coRk Source #

Arguments

:: m a

the matroid

-> Set a

set of matroid elements

-> Int 

rank function of the dual matroid

coloops Source #

Arguments

:: m a

the matroid

-> Set a 

returns the coloops in the matroid

Instances

Instances details
(Ord a, Show a) => Matroid AMatroid a Source #

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

Instance details

Defined in Data.Matroid.Typeclass

(Ord a, Show a) => Matroid BasisFilterMatroid a Source # 
Instance details

Defined in Data.Matroid.Internal

(Ord a, Show a) => Matroid IndepMatroid a Source # 
Instance details

Defined in Data.Matroid.Internal

(Ord a, Show a) => Matroid RkMatroid a Source # 
Instance details

Defined in Data.Matroid.Internal

(Ord a, Show a) => Matroid FreeMatroid a Source # 
Instance details

Defined in Data.Matroid.Uniform

(Ord a, Show a) => Matroid UniformMatroid a Source # 
Instance details

Defined in Data.Matroid.Uniform

(Ord a, Ord v, Show a) => Matroid (GraphicMatroid v) a Source # 
Instance details

Defined in Data.Matroid.Graphic

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

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