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 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

Documentation

data Assign label set #

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) #
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 #

labeledSet :: Assign label set -> set #

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

Construction of a labeled 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 #

Constructors

State
Fields 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 SetId #

Instances

Enum SetId #
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 #

queueSet :: Ord a => Methods a #

queueBit :: C bits => Methods bits #

queueBitPQ :: C bits => Methods bits #