{-# LANGUAGE FlexibleInstances, MultiParamTypeClasses #-}

{-|
Module      : Data.Matroid.Algorithms.Enumerate
Description : 
Copyright   : (c) Immanuel Albrecht, 2020-202x
License     : BSD-3
Maintainer  : mail@immanuel-albrecht.de
Stability   : experimental
Portability : POSIX

This module provides implementations of algorithms that
enumerate things from matroids.

-}

module Data.Matroid.Algorithms.Enumerate where

import Data.Matroid.Typeclass

import Data.Set (Set)
import qualified Data.Set as S

{- | enumerates all bases of a matroid 
-}
enumerateBases :: Matroid m a => m a {- ^ matroid -} -> [Set a]
enumerateBases :: m a -> [Set a]
enumerateBases m a
m = [a] -> Set a -> [Set a]
dfs (Set a -> [a]
forall a. Set a -> [a]
S.toList (Set a -> [a]) -> Set a -> [a]
forall a b. (a -> b) -> a -> b
$ m a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
groundset m a
m) Set a
forall a. Set a
S.empty
            where dfs :: [a] -> Set a -> [Set a]
dfs [a]
es Set a
x
                    | Bool -> Bool
not (Bool -> Bool) -> Bool -> Bool
forall a b. (a -> b) -> a -> b
$ m a -> Set a -> Bool
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Bool
indep m a
m Set a
x = []
                    | Set a -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length Set a
x Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
rankM = [Set a
x]
                    | (a
e:[a]
ex) <- [a]
es = [a] -> Set a -> [Set a]
dfs [a]
ex ( a -> Set a -> Set a
forall a. Ord a => a -> Set a -> Set a
S.insert a
e Set a
x) [Set a] -> [Set a] -> [Set a]
forall a. [a] -> [a] -> [a]
++ [a] -> Set a -> [Set a]
dfs [a]
ex Set a
x
                    | Bool
otherwise = [] 
                  rankM :: Int
rankM = m a -> Set a -> Int
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Int
rk m a
m (Set a -> Int) -> Set a -> Int
forall a b. (a -> b) -> a -> b
$ m a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
groundset m a
m