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)

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 label, Eq set) => Eq (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

Instances

Enum 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