-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | matroid (combinatorial pre-geometries) library
--   
--   This library provides typeclasses, instances, and algorithms for
--   working with matroids.
@package matroid
@version 0.0.0


-- | This module provides internal helpers for the matroid package which
--   fall into the <tt>general</tt> category.
module Data.Matroid.Internal.Helpers

-- | little helper that either chooses the implementation of a typeclass
--   member from the record, or uses the default implementation
defaultsTo :: (a0 -> Maybe a1) -> a0 -> a1 -> a1


-- | This module provides default implementations for the members of the
--   Matroid typeclass.
module Data.Matroid.Typeclass.Defaults

-- | returns the rank of the set, wrt. to the given basis filter
rk :: (Set a -> Set a) -> Set a -> Int

-- | tests whether a given set is independent
indep :: (Set a -> Int) -> Set a -> Bool

-- | obtains an independent subset with maximal cardinality
basis :: Ord a => (Set a -> Bool) -> Set a -> Set a

-- | computes the closure of a given set
cl :: Ord a => (Set a -> Int) -> Set a -> Set a -> Set a

-- | returns the loops in the matroid
loops :: (Set a -> Set a) -> Set a

-- | rank function of the dual matroid
coRk :: Ord a => (Set a -> Int) -> Set a -> Set a -> Int

-- | returns the coloops in the matroid
coloops :: Ord a => (Set a -> Int) -> Set a -> Set a


-- | This module provides implementations of common operations on matroids
--   and an abstract matroid data type.
module Data.Matroid.Ops

-- | abstract matroid data type with elements of a given type
--   
--   Its purpose is to hide the underlying type from the type system. The
--   records resemble the typeclass Matroid, where everything except for
--   the groundset has been placed inside the Maybe-Monad. A value of
--   Nothing indicates that the default implementation of the typeclass
--   should be used.
data AMatroid a
WMatroid :: Set a -> Maybe String -> Maybe (Set a -> Int) -> Maybe (Set a -> Bool) -> Maybe (Set a -> Set a) -> Maybe (Set a -> Set a) -> Maybe (AMatroid a) -> Maybe (AMatroid a) -> Maybe (Set a -> AMatroid a) -> Maybe (Set a -> AMatroid a) -> Maybe (Set a) -> Maybe (Set a -> Int) -> Maybe (Set a) -> AMatroid a
[w_groundset] :: AMatroid a -> Set a
[w_showName] :: AMatroid a -> Maybe String
[w_rk] :: AMatroid a -> Maybe (Set a -> Int)
[w_indep] :: AMatroid a -> Maybe (Set a -> Bool)
[w_basis] :: AMatroid a -> Maybe (Set a -> Set a)
[w_cl] :: AMatroid a -> Maybe (Set a -> Set a)
[w_abstract] :: AMatroid a -> Maybe (AMatroid a)
[w_dual] :: AMatroid a -> Maybe (AMatroid a)
[w_restriction] :: AMatroid a -> Maybe (Set a -> AMatroid a)
[w_contraction] :: AMatroid a -> Maybe (Set a -> AMatroid a)
[w_loops] :: AMatroid a -> Maybe (Set a)
[w_coRk] :: AMatroid a -> Maybe (Set a -> Int)
[w_coloops] :: AMatroid a -> Maybe (Set a)

-- | defaults for WMatroid
wrappedMatroid :: AMatroid a

-- | returns the restriction of a given matroid
--   
--   Note that this routine implements the correct routines provided that
--   the prerequisite members in the input matroid are defined. Routines
--   which have missing prerequisite members in the input matroid will be
--   left to Nothing. Data.Matroid.Typeclass.wrapUp fills all AMatroid
--   record members.
a_restriction :: (Show a, Ord a) => AMatroid a -> Set a -> AMatroid a

-- | returns the restriction of a given matroid, named
--   
--   Note that this routine implements the correct routines provided that
--   the prerequisite members in the input matroid are defined. Routines
--   which have missing prerequisite members in the input matroid will be
--   left to Nothing. Data.Matroid.Typeclass.wrapUp fills all AMatroid
--   record members.
a_namedRestriction :: Ord a => String -> AMatroid a -> Set a -> AMatroid a

-- | returns the contraction of a given matroid
--   
--   Note that this routine implements the correct routines provided that
--   the prerequisite members in the input matroid are defined. Routines
--   which have missing prerequisite members in the input matroid will be
--   left to Nothing. Data.Matroid.Typeclass.wrapUp fills all AMatroid
--   record members.
a_contraction :: (Show a, Ord a) => AMatroid a -> Set a -> AMatroid a

-- | returns the contraction of a given matroid, named
--   
--   Note that this routine implements the correct routines provided that
--   the prerequisite members in the input matroid are defined. Routines
--   which have missing prerequisite members in the input matroid will be
--   left to Nothing. Data.Matroid.Typeclass.wrapUp fills all AMatroid
--   record members.
a_namedContraction :: Ord a => String -> AMatroid a -> Set a -> AMatroid a

-- | returns the contraction of a given matroid
--   
--   Note that this routine implements the correct routines provided that
--   the prerequisite members in the input matroid are defined. Routines
--   which have missing prerequisite members in the input matroid will be
--   left to Nothing. Data.Matroid.Typeclass.wrapUp fills all AMatroid
--   record members.
a_dual :: (Show a, Ord a) => AMatroid a -> AMatroid a

-- | returns the contraction of a given matroid, named
--   
--   Note that this routine implements the correct routines provided that
--   the prerequisite members in the input matroid are defined. Routines
--   which have missing prerequisite members in the input matroid will be
--   left to Nothing. Data.Matroid.Typeclass.wrapUp fills all AMatroid
--   record members.
a_namedDual :: Ord a => String -> AMatroid a -> AMatroid a
instance GHC.Show.Show a => GHC.Show.Show (Data.Matroid.Ops.AMatroid a)


-- | This module provides the Matroid typeclass.
module Data.Matroid.Typeclass

-- | Typeclass that provides the full matroid interface.
--   
--   The type parameter <tt>a</tt> is the type of the elements of the
--   matroid, it is most commonly used in a <tt>Set a</tt> 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.
class (Ord a, Show a) => Matroid m a

-- | The ground set of the matroid, its elements are usually called edges.
--   This set is finite.
groundset :: Matroid m a => m a -> Set a

-- | name of the matroid, may be used for show
showName :: Matroid m a => m a -> String

-- | returns the rank of the set
rk :: Matroid m a => m a -> Set a -> Int

-- | tests whether a given set is independent
indep :: Matroid m a => m a -> Set a -> Bool

-- | obtains an independent subset with maximal cardinality
basis :: Matroid m a => m a -> Set a -> Set a

-- | computes the closure of a given set
cl :: Matroid m a => m a -> Set a -> Set a

-- | returns this matroid as abstract matroid object
abstract :: Matroid m a => m a -> AMatroid a

-- | returns the dual of this matroid as abstract matroid object
dual :: Matroid m a => m a -> AMatroid a

-- | returns the restricted matroid M|X as result of the unary matroid
--   operation *|X
restriction :: Matroid m a => m a -> Set a -> AMatroid a

-- | returns the contracted matroid M.X as a result of the unary matroid
--   operation *.X
contraction :: Matroid m a => m a -> Set a -> AMatroid a

-- | returns the loops in the matroid
loops :: Matroid m a => m a -> Set a

-- | rank function of the dual matroid
coRk :: Matroid m a => m a -> Set a -> Int

-- | returns the coloops in the matroid
coloops :: Matroid m a => m a -> Set a

-- | takes an object of a type that implements the Matroid typeclass, and
--   turns it into an AMatroid record.
wrapUp :: Matroid m a => m a -> AMatroid a
instance (GHC.Classes.Ord a, GHC.Show.Show a) => Data.Matroid.Typeclass.Matroid Data.Matroid.Ops.AMatroid a


-- | This module provides internal helpers for the matroid package, for
--   instance data types that help converting different matroid
--   representations to Matroid . . -types.
--   
--   Although it is exported, using anything from this module that is not
--   re-exported by another module may (and eventually will) break client
--   side code. The main reason for exporting this is so anyone can inspect
--   internals using haddock; it's a little bit like an open door policy
--   for code.
module Data.Matroid.Internal

-- | matroid constructor given groundset and rank function
fromRk :: Show a => Set a -> (Set a -> Int) -> RkMatroid a

-- | named matroid constructor given groundset and rank function
namedFromRk :: String -> Set a -> (Set a -> Int) -> RkMatroid a

-- | matroid constructor given groundset and test for independence
fromIndep :: Show a => Set a -> (Set a -> Bool) -> IndepMatroid a

-- | named matroid constructor given groundset and test for independence
namedFromIndep :: String -> Set a -> (Set a -> Bool) -> IndepMatroid a

-- | matroid constructor given groundset and set-basis filter
fromBasisFilter :: Show a => Set a -> (Set a -> Set a) -> BasisFilterMatroid a

-- | named matroid constructor given groundset and set-basis filter
namedFromBasisFilter :: String -> Set a -> (Set a -> Set a) -> BasisFilterMatroid a

-- | we use this data type to combine a given rank function with the
--   default implementations from the Matroid typeclass
data RkMatroid a

-- | we use this data type to combine a given independence test with the
--   default implementations from the Matroid typeclass
data IndepMatroid a

-- | we use this data type to combine a given a basis filter with the
--   default implementations from the Matroid typeclass
data BasisFilterMatroid a
instance GHC.Show.Show a => GHC.Show.Show (Data.Matroid.Internal.BasisFilterMatroid a)
instance (GHC.Classes.Ord a, GHC.Show.Show a) => Data.Matroid.Typeclass.Matroid Data.Matroid.Internal.BasisFilterMatroid a
instance GHC.Show.Show a => GHC.Show.Show (Data.Matroid.Internal.IndepMatroid a)
instance (GHC.Classes.Ord a, GHC.Show.Show a) => Data.Matroid.Typeclass.Matroid Data.Matroid.Internal.IndepMatroid a
instance GHC.Show.Show a => GHC.Show.Show (Data.Matroid.Internal.RkMatroid a)
instance (GHC.Classes.Ord a, GHC.Show.Show a) => Data.Matroid.Typeclass.Matroid Data.Matroid.Internal.RkMatroid a


-- | This module provides implementations of graphic matroids.
module Data.Matroid.Graphic

-- | data type representing the cycle matroid (aka. polygon matroid) of a
--   (multi-)graph
data GraphicMatroid v a

-- | constructs a GraphicMatroid from a set of (abstract) edges and the
--   incident-vertex map
fromGraph :: (Ord a, Show a) => Set a -> (a -> (v, v)) -> GraphicMatroid v a

-- | constructs a named GraphicMatroid from a set of (abstract) edges and
--   the incident-vertex map
namedFromGraph :: Ord a => String -> Set a -> (a -> (v, v)) -> GraphicMatroid v a

-- | constructs an unnamed GraphicMatroid from a set of (abstract) edges
--   and the incident-vertex map
fromGraph' :: Ord a => Set a -> (a -> (v, v)) -> GraphicMatroid v a

-- | constructs the graphic matroid M(K_n) where K_n is the complete graph
--   on n vertices
mK :: Int -> GraphicMatroid Int (Int, Int)
instance (GHC.Classes.Ord v, GHC.Classes.Ord a) => GHC.Classes.Ord (Data.Matroid.Graphic.Forrest v a)
instance (GHC.Classes.Eq v, GHC.Classes.Eq a) => GHC.Classes.Eq (Data.Matroid.Graphic.Forrest v a)
instance (GHC.Show.Show v, GHC.Show.Show a) => GHC.Show.Show (Data.Matroid.Graphic.Forrest v a)
instance (GHC.Classes.Ord a, GHC.Classes.Ord v, GHC.Show.Show a) => Data.Matroid.Typeclass.Matroid (Data.Matroid.Graphic.GraphicMatroid v) a
instance GHC.Show.Show a => GHC.Show.Show (Data.Matroid.Graphic.GraphicMatroid v a)


-- | This module provides implementations of uniform matroids.
module Data.Matroid.Uniform

-- | data type representing a uniform matroid over a given ground set
data UniformMatroid a

-- | returns a uniform matroid on a given ground set of rank r
uniformOn :: Ord a => Set a -> Int -> UniformMatroid a

-- | returns a uniform matroid on the intergers from 1..n of rank r
uniform :: Int -> Int -> UniformMatroid Int

-- | data type that represents a free matroid over a given set (free
--   matroids are of course uniform)
data FreeMatroid a

-- | returns a free matroid on a given ground set (where every subset of
--   the groundset is independent)
freeOn :: Ord a => Set a -> FreeMatroid a
instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.Matroid.Uniform.UniformMatroid a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.Matroid.Uniform.UniformMatroid a)
instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.Matroid.Uniform.FreeMatroid a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.Matroid.Uniform.FreeMatroid a)
instance (GHC.Classes.Ord a, GHC.Show.Show a) => Data.Matroid.Typeclass.Matroid Data.Matroid.Uniform.FreeMatroid a
instance GHC.Show.Show a => GHC.Show.Show (Data.Matroid.Uniform.FreeMatroid a)
instance GHC.Show.Show a => GHC.Show.Show (Data.Matroid.Uniform.UniformMatroid a)
instance (GHC.Classes.Ord a, GHC.Show.Show a) => Data.Matroid.Typeclass.Matroid Data.Matroid.Uniform.UniformMatroid a


-- | This module provides type classes and functionalities that allow you
--   to work with matroids and related structures.
--   
--   A <a>matroid</a> is also called a combinatorial pre-geometry and is a
--   structure that abstracts (linear) dependence. Matroids occur naturally
--   in settings where the greedy algorithm works, although they usually
--   stay under the radar.
module Data.Matroid

-- | matroid constructor given groundset and rank function
fromRk :: Show a => Set a -> (Set a -> Int) -> RkMatroid a

-- | named matroid constructor given groundset and rank function
namedFromRk :: String -> Set a -> (Set a -> Int) -> RkMatroid a

-- | matroid constructor given groundset and test for independence
fromIndep :: Show a => Set a -> (Set a -> Bool) -> IndepMatroid a

-- | named matroid constructor given groundset and test for independence
namedFromIndep :: String -> Set a -> (Set a -> Bool) -> IndepMatroid a

-- | matroid constructor given groundset and set-basis filter
fromBasisFilter :: Show a => Set a -> (Set a -> Set a) -> BasisFilterMatroid a

-- | named matroid constructor given groundset and set-basis filter
namedFromBasisFilter :: String -> Set a -> (Set a -> Set a) -> BasisFilterMatroid a


-- | This module contains QuickCheck generators for testing purposes.
module Test.Matroid.Generators

-- | a generator for uniform matroids of a reasonable size
genUniformMatroids :: Gen (UniformMatroid Int)

-- | a generator for graphic matroids of reasonable size
genGraphicMatroids :: Gen (GraphicMatroid Int (Int, Int, Int))

-- | a generator for M(K_n) matroids of reasonable size
genMKnMatroids :: Gen (GraphicMatroid Int (Int, Int))

-- | a generator for free matroids of a reasonable size
genFreeMatroids :: Gen (FreeMatroid Int)

-- | a generator for consintency matroid type based on another generator
viaRank :: Matroid m a => Gen (m a) -> Gen (RkMatroid a)

-- | a generator for consintency matroid type based on another generator
viaIndep :: Matroid m a => Gen (m a) -> Gen (IndepMatroid a)

-- | a generator for consintency matroid type based on another generator
viaBasisFilter :: Matroid m a => Gen (m a) -> Gen (BasisFilterMatroid a)

-- | a generator for matroids of the form M|X based on a generator for M
viaRestriction :: Matroid m a => Gen (m a) -> Gen (AMatroid a)

-- | a generator for matroids of the form M.X based on a generator for M
viaContraction :: Matroid m a => Gen (m a) -> Gen (AMatroid a)

-- | a generator for matroids of the form M^* based on a generator for M
viaDual :: Matroid m a => Gen (m a) -> Gen (AMatroid a)


-- | This module contains helpers for the matroid unit tests.
module Test.Matroid.Helpers

-- | Tests whether a given integer valued set function is indeed monotone
--   increasing in at most unit steps
isMonotoneUnitIncreasing :: Ord a => (Set a -> Int) -> [a] -> Bool

-- | Tests whether a given boolean valued set function indeed only flips
--   from true to false once when adding elements to its argument
isMonotoneDecreasingBool :: Ord a => (Set a -> Bool) -> [a] -> Bool

-- | Tests the exchange property of the indep function of a matroid
hasIndepExchangeProperty :: Ord a => (Set a -> Bool) -> Set a -> Set a -> Bool

-- | Tests whether a given set valued set function is isotone in the set
--   lattice
isIsotoneSetMap :: Ord a => (Set a -> Set a) -> [a] -> Bool


-- | This module contains hspec test suites that check certain matroid
--   properties.
module Test.Matroid.Suites

-- | all tests that any matroid should/must pass
matroidSuite :: (Matroid m a, Show (m a)) => Gen (m a) -> SpecWith ()

-- | tests the invariants associated with operations on matroids
--   
--   <ul>
--   <li>rk_{M|X}(Y) = rk_M(Y)</li>
--   <li>coRk_{M.X}(Y) = coRk_M(Y)</li>
--   <li>rk_(M^*)(Y) = coRk_M(Y)</li>
--   <li>loop(M) = coloop(M^*)</li>
--   <li>coloop(M^*) = loop(M)</li>
--   <li>groundsets of restriction/contraction</li>
--   <li>restriction is the dual of contraction</li>
--   </ul>
opInvariantsSuite :: Matroid m a => Gen (m a) -> SpecWith ()

-- | test suite for rank axioms
--   
--   The following properties are verified: - rk is monotone increasing -
--   rk(X+{x}) &lt;= rk(X) + 1 (unit increasing) - rk(emptyset) = 0
--   (important special case) - rk(X) &lt;= |X| (subcardinal) - rk(A/B) +
--   rk(A/B) &lt;= rk(A) + rk(B) (submodular)
rkPropertiesSuite :: Matroid m a => Gen (m a) -> SpecWith ()

-- | test suite for indep properties
--   
--   The following properties are verified: - indep X &amp;&amp; Ysubseteq
--   X =&gt; indep Y (hereditary) - indep emptyset - indep X &amp;&amp;
--   indep Y &amp;&amp; |Y| &gt; |X| =&gt; exists yin Y: indep X+{y}
--   (exchange property)
indepPropertiesSuite :: Matroid m a => Gen (m a) -> SpecWith ()

-- | test suite for basis properties
--   
--   The following properties are verified: - basis X subseteq X - indep
--   (basis X) - y in X(basis X) =&gt; not indep (basis X)+{y}
basisPropertiesSuite :: Matroid m a => Gen (m a) -> 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) =&gt; e in cl(X+{y}) - rk(X) == rk(cl(X)) and cl(X) is
--   maximal with this property
clPropertiesSuite :: Matroid m a => Gen (m a) -> 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).
viaConsistencySuite :: Matroid m a => Gen (m a) -> SpecWith ()


-- | This module exports routines that may be used to write test cases for
--   user written instances of the Matroid typeclass.
--   
--   It is also used in the unit tests of the matroid library.
module Test.Matroid