Math.SetCover.Exact.Priority

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.

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)

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 Tree label set

Constructors

Leaf

Branch set [(label, Tree label set)]

Instances

(Eq set, Eq label) => Eq (Tree label set)

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

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

data SetId

Instances

Enum SetId

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

queueIntSet :: MethodsIntSet