| Copyright | (c) Immanuel Albrecht 2020-202x |
|---|---|
| License | BSD-3 |
| Maintainer | mail@immanuel-albrecht.de |
| Stability | experimental |
| Portability | POSIX |
| Safe Haskell | Safe-Inferred |
| Language | Haskell2010 |
Data.Matroid.Typeclass
Description
This module provides the Matroid typeclass.
Synopsis
- class (Ord a, Show a) => Matroid m a where
- groundset :: m a -> Set a
- showName :: m a -> String
- rk :: m a -> Set a -> Int
- indep :: m a -> Set a -> Bool
- basis :: m a -> Set a -> Set a
- cl :: m a -> Set a -> Set a
- abstract :: m a -> AMatroid a
- dual :: m a -> AMatroid a
- restriction :: m a -> Set a -> AMatroid a
- contraction :: m a -> Set a -> AMatroid a
- loops :: m a -> Set a
- coRk :: m a -> Set a -> Int
- coloops :: m a -> Set a
- wrapUp :: Matroid m a => m a -> AMatroid a
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.
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
returns the rank of the set
tests whether a given set is independent
obtains an independent subset with maximal cardinality
computes the closure of a given set
Arguments
| :: m a | matroid |
| -> AMatroid a |
returns this matroid as abstract matroid object
Arguments
| :: m a | matroid |
| -> AMatroid a |
returns the dual of this matroid as abstract matroid object
returns the restricted matroid M|X as result of the unary matroid operation *|X
returns the contracted matroid M.X as a result of the unary matroid operation *.X
Arguments
| :: m a | the matroid |
| -> Set a |
returns the loops in the matroid
rank function of the dual matroid
Arguments
| :: m a | the matroid |
| -> Set a |
returns the coloops in the matroid