Safe Haskell	None
Language	Haskell98

Math.SetCover.Exact.Priority

Description

This implementation uses priority queues and avoids full scans through available sets. It can be faster than Math.SetCover.Exact if there is a huge number of sets.

Synopsis

data Assign label set
label :: Assign label set -> label
labeledSet :: Assign label set -> set
assign :: label -> set -> Assign label set
partitions :: Methods queue set -> [Assign label set] -> [[label]]
search :: Methods queue set -> State queue label set -> [[label]]
step :: Methods queue set -> State queue label set -> [State queue label set]
data State queue label set = State {
- availableSubsets :: EnumMap SetId (Assign label set)
- queue :: queue
- usedSubsets :: [label]
}
initState :: Methods queue set -> [Assign label set] -> State queue label set
updateState :: Methods queue set -> Assign label set -> State queue label set -> State queue label set
data Tree label set
- = Leaf
- | Branch set [(label, Tree label set)]
decisionTree :: Methods queue set -> [Assign label set] -> Tree label set
completeTree :: Methods queue set -> State queue label set -> Tree label set
data SetId
queueMap :: Ord a => Methods queue set -> Methods a queue set
queueSet :: Ord a => Methods a
queueBit :: C bits => Methods bits
queueBitPQ :: C bits => Methods bits
queueIntSet :: MethodsIntSet

Documentation

data Assign label set Source #

Assign allows to associate a set with a label. If a particular set is chosen for a set cover, then its label is included in the output of partitions.

I have decided to separate sets and labels this way, since it is the easiest way to assign a meaning to a set. If you really want to know the sets in a partition, then you can fill the label field with the set.

Instances

Functor (Assign label) Source #
Instance details Defined in Math.SetCover.Exact Methods fmap :: (a -> b) -> Assign label a -> Assign label b # (<$) :: a -> Assign label b -> Assign label a #

label :: Assign label set -> label Source #

labeledSet :: Assign label set -> set Source #

assign :: label -> set -> Assign label set Source #

Construction of a labeled set.

partitions :: Methods queue set -> [Assign label set] -> [[label]] Source #

search :: Methods queue set -> State queue label set -> [[label]] Source #

step :: Methods queue set -> State queue label set -> [State queue label set] Source #

data State queue label set Source #

Constructors

State
Fields availableSubsets :: EnumMap SetId (Assign label set) queue :: queue usedSubsets :: [label]

initState :: Methods queue set -> [Assign label set] -> State queue label set Source #

updateState :: Methods queue set -> Assign label set -> State queue label set -> State queue label set Source #

data Tree label set Source #

Constructors

Leaf
Branch set [(label, Tree label set)]

Instances

(Eq set, Eq label) => Eq (Tree label set) Source #
Instance details Defined in Math.SetCover.Exact Methods (==) :: Tree label set -> Tree label set -> Bool # (/=) :: Tree label set -> Tree label set -> Bool #

decisionTree :: Methods queue set -> [Assign label set] -> Tree label set Source #

completeTree :: Methods queue set -> State queue label set -> Tree label set Source #

data SetId Source #

Instances

Enum SetId Source #
Instance details Defined in Math.SetCover.Queue Methods succ :: SetId -> SetId # pred :: SetId -> SetId # toEnum :: Int -> SetId # fromEnum :: SetId -> Int # enumFrom :: SetId -> [SetId] # enumFromThen :: SetId -> SetId -> [SetId] # enumFromTo :: SetId -> SetId -> [SetId] # enumFromThenTo :: SetId -> SetId -> SetId -> [SetId] #

queueMap :: Ord a => Methods queue set -> Methods a queue set Source #

queueSet :: Ord a => Methods a Source #

queueBit :: C bits => Methods bits Source #

queueBitPQ :: C bits => Methods bits Source #

queueIntSet :: MethodsIntSet Source #