{-# LANGUAGE FlexibleInstances, MultiParamTypeClasses #-}

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

This module provides implementations of the greedy algorithm for
optimization on matroids.

-}

module Data.Matroid.Algorithms.Greedy where

import Data.Matroid.Typeclass

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


{- |  Obtains an independent set of the given matroid
      that is optimal wrt. some optimization problem.
      
      This version uses a ranking of the benefits of the elements of the groundset
      and the indep function in order to obtain an optimal result.
-}
greedy :: Matroid m a => 
      (m a) {- ^ matroid to optimize on -} 
   -> [a]   {- ^ elements of the groundset of the matroid, ordered from the best (most revenue, least cost, ...) element to the worst yet still improving element -}
   -> Set a
greedy :: m a -> [a] -> Set a
greedy = Set a -> m a -> [a] -> Set a
forall (m :: * -> *) a. Matroid m a => Set a -> m a -> [a] -> Set a
greedyStep Set a
forall a. Set a
S.empty
  where greedyStep :: Set a -> m a -> [a] -> Set a
greedyStep Set a
x0 m a
m (a
r:[a]
rs) -- r gives the most revenue wrt. the elements not in x0
          | m a -> Set a -> Bool
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Bool
indep m a
m Set a
x0r = Set a -> m a -> [a] -> Set a
greedyStep Set a
x0r m a
m [a]
rs  -- we may add r to x0 and stay independent, do it
          | Bool
otherwise   = Set a -> m a -> [a] -> Set a
greedyStep Set a
x0  m a
m [a]
rs  -- we cannot add r to x0, do not add it and continue
            where x0r :: Set a
x0r = a -> Set a -> Set a
forall a. Ord a => a -> Set a -> Set a
S.insert a
r Set a
x0 
        greedyStep Set a
x0 m a
_ [a]
_ = Set a
x0 -- no more profitable elements in the queue

{- |  Obtains an independent set of the given matroid
      that is optimal wrt. some optimization problem.
      
      This version uses a choice function that selects the best
      element from a list of allowed choices, or Nothing to stop
      the process.
-}
greedy1 :: Matroid m a =>
      (m a) {- ^ matroid to optimize on -} 
   -> (Set a -> Maybe a) {- ^ picks the best element from the set, or nothing if adding an element would result in a worse outcome -}
   -> Set a
greedy1 :: m a -> (Set a -> Maybe a) -> Set a
greedy1 m a
m Set a -> Maybe a
choice = Set a -> Set a -> Set a
greedyStep Set a
forall a. Set a
S.empty (Set a -> Set a) -> Set a -> Set a
forall a b. (a -> b) -> a -> b
$ m a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
loops m a
m
  where e :: Set a
e = m a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a
groundset m a
m
        greedyStep :: Set a -> Set a -> Set a
greedyStep Set a
x0 Set a
clx0
          | Maybe a
chosen Maybe a -> Maybe a -> Bool
forall a. Eq a => a -> a -> Bool
== Maybe a
forall a. Maybe a
Nothing = Set a
x0     -- cannot add any further element
          | Bool
otherwise = Set a -> Set a -> Set a
greedyStep Set a
x0c Set a
clx0c -- add the best choice;
            where chosen :: Maybe a
chosen = Set a -> Maybe a
choice (Set a -> Set a -> Set a
forall a. Ord a => Set a -> Set a -> Set a
S.difference Set a
e Set a
clx0)
                  Just a
c = Maybe a
chosen
                  x0c :: Set a
x0c = a -> Set a -> Set a
forall a. Ord a => a -> Set a -> Set a
S.insert a
c Set a
x0
                  clx0c :: Set a
clx0c = m a -> Set a -> Set a
forall (m :: * -> *) a. Matroid m a => m a -> Set a -> Set a
cl m a
m (Set a -> Set a) -> Set a -> Set a
forall a b. (a -> b) -> a -> b
$ a -> Set a -> Set a
forall a. Ord a => a -> Set a -> Set a
S.insert a
c Set a
clx0