ToySolver.Combinatorial.HittingSet.InterestingSets

• D. Gunopulos, H. Mannila, R. Khardon, and H. Toivonen, Data mining, hypergraph transversals, and machine learning (extended abstract), in Proceedings of the Sixteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, ser. PODS '97. 1997, pp. 209-216. http://almaden.ibm.com/cs/projects/iis/hdb/Publications/papers/pods97_trans.pdf

Problem definition

class Monad m => IsProblem prob m | prob -> m where

A problem is essentially a pair of an IntSet (universe) and a monotone pure function IntSet -> Bool (isInteresting), but we generalize a bit for potentialial optimization opportunity.

For simple cases you can just use SimpleProblem instance.

Minimal complete definition

universe, (isInteresting | isInteresting')

Methods

universe :: prob -> IntSet

isInteresting :: prob -> IntSet -> m Bool

Interesting sets are lower closed subsets of universe, i.e. if xs is interesting then ys ⊆ xs is also interesting.

isInteresting' :: prob -> IntSet -> m InterestingOrUninterestingSet

If xs is interesting it returns InterestingSet ys where ys is an interesting superset of xs. If xs is uninteresting it returns UninterestingSet ys where ys is an uninteresting subset of xs.

grow :: prob -> IntSet -> m IntSet

grow xs computes maximal interesting set ys that is a superset of xs.

shrink :: prob -> IntSet -> m IntSet

shrink xs computes minimal uninteresting set ys that is a subset of xs.

maximalInterestingSet :: prob -> IntSet -> m (Maybe IntSet)

If xs is an interesting set maximalInterestingSet prob xs returns Just ys such that ys is a maximal interesting superset of xs, otherwise it returns Nothing.

minimalUninterestingSet :: prob -> IntSet -> m (Maybe IntSet)

If xs is an uninteresting set minimalUninterestingSet prob xs returns Just ys such that ys is a minimal uninteresting subset of xs, otherwise it returns Nothing.

minimalUninterestingSetOrMaximalInterestingSet :: prob -> IntSet -> m InterestingOrUninterestingSet

If xs is an uninteresting set minimalUninterestingSetOrMaximalInterestingSet prob xs returns Left ys such that ys is a minimal uninteresting subset of xs. If xs is an interesting set minimalUninterestingSetOrMaximalInterestingSet prob xs returns Right ys such that ys is a maximal interesting superset of xs

Instances

Monad m => IsProblem (SimpleProblem m) m

Defined in ToySolver.Combinatorial.HittingSet.InterestingSets

Methods

universe :: SimpleProblem m -> IntSet

isInteresting :: SimpleProblem m -> IntSet -> m Bool

isInteresting' :: SimpleProblem m -> IntSet -> m InterestingOrUninterestingSet

grow :: SimpleProblem m -> IntSet -> m IntSet

shrink :: SimpleProblem m -> IntSet -> m IntSet

maximalInterestingSet :: SimpleProblem m -> IntSet -> m (Maybe IntSet)

minimalUninterestingSet :: SimpleProblem m -> IntSet -> m (Maybe IntSet)

minimalUninterestingSetOrMaximalInterestingSet :: SimpleProblem m -> IntSet -> m InterestingOrUninterestingSet

data InterestingOrUninterestingSet

Constructors

UninterestingSet IntSet

InterestingSet IntSet

Instances

Eq InterestingOrUninterestingSet

Defined in ToySolver.Combinatorial.HittingSet.InterestingSets

Methods

(==) :: InterestingOrUninterestingSet -> InterestingOrUninterestingSet -> Bool

(/=) :: InterestingOrUninterestingSet -> InterestingOrUninterestingSet -> Bool

Ord InterestingOrUninterestingSet

Defined in ToySolver.Combinatorial.HittingSet.InterestingSets

Methods

compare :: InterestingOrUninterestingSet -> InterestingOrUninterestingSet -> Ordering

(<) :: InterestingOrUninterestingSet -> InterestingOrUninterestingSet -> Bool

(<=) :: InterestingOrUninterestingSet -> InterestingOrUninterestingSet -> Bool

(>) :: InterestingOrUninterestingSet -> InterestingOrUninterestingSet -> Bool

(>=) :: InterestingOrUninterestingSet -> InterestingOrUninterestingSet -> Bool

max :: InterestingOrUninterestingSet -> InterestingOrUninterestingSet -> InterestingOrUninterestingSet

min :: InterestingOrUninterestingSet -> InterestingOrUninterestingSet -> InterestingOrUninterestingSet

Read InterestingOrUninterestingSet

Defined in ToySolver.Combinatorial.HittingSet.InterestingSets

Methods

readsPrec :: Int -> ReadS InterestingOrUninterestingSet

readList :: ReadS [InterestingOrUninterestingSet]

readPrec :: ReadPrec InterestingOrUninterestingSet

readListPrec :: ReadPrec [InterestingOrUninterestingSet]

Show InterestingOrUninterestingSet

Defined in ToySolver.Combinatorial.HittingSet.InterestingSets

Methods

showsPrec :: Int -> InterestingOrUninterestingSet -> ShowS

show :: InterestingOrUninterestingSet -> String

showList :: [InterestingOrUninterestingSet] -> ShowS

defaultGrow :: IsProblem prob m => prob -> IntSet -> m IntSet

Default implementation of grow using isInteresting'.

defaultShrink :: IsProblem prob m => prob -> IntSet -> m IntSet

Default implementation of shrink using isInteresting'.

defaultMaximalInterestingSet :: IsProblem prob m => prob -> IntSet -> m (Maybe IntSet)

Default implementation of maximalUninterestingSet using isInteresting' and grow.

defaultMinimalUninterestingSet :: IsProblem prob m => prob -> IntSet -> m (Maybe IntSet)

Default implementation of minimalUninterestingSet using isInteresting' and shrink.

defaultMinimalUninterestingSetOrMaximalInterestingSet :: IsProblem prob m => prob -> IntSet -> m InterestingOrUninterestingSet

Default implementation of minimalUninterestingSetOrMaximalInterestingSet using isInteresting', shrink grow.

data SimpleProblem (m :: * -> *)

Constructors

SimpleProblem IntSet (IntSet -> Bool)

Instances

Monad m => IsProblem (SimpleProblem m) m

Defined in ToySolver.Combinatorial.HittingSet.InterestingSets

Methods

universe :: SimpleProblem m -> IntSet

isInteresting :: SimpleProblem m -> IntSet -> m Bool

isInteresting' :: SimpleProblem m -> IntSet -> m InterestingOrUninterestingSet

grow :: SimpleProblem m -> IntSet -> m IntSet

shrink :: SimpleProblem m -> IntSet -> m IntSet

maximalInterestingSet :: SimpleProblem m -> IntSet -> m (Maybe IntSet)

minimalUninterestingSet :: SimpleProblem m -> IntSet -> m (Maybe IntSet)

minimalUninterestingSetOrMaximalInterestingSet :: SimpleProblem m -> IntSet -> m InterestingOrUninterestingSet

Options for maximal interesting sets enumeration

data Options m

Constructors

Options

Fields

• optMinimalHittingSets :: Set IntSet -> m (Set IntSet)
• optMaximalInterestingSets :: Set IntSet
• optMinimalUninterestingSets :: Set IntSet
• optOnMaximalInterestingSetFound :: IntSet -> m ()
• optOnMinimalUninterestingSetFound :: IntSet -> m ()

Instances

Monad m => Default (Options m)

Defined in ToySolver.Combinatorial.HittingSet.InterestingSets

Methods

def :: Options m

Datatype for monotone CNF/DNF dualization

data ImplicateOrImplicant

Constructors

Implicate IntSet

Implicant IntSet

Instances

Eq ImplicateOrImplicant

Defined in ToySolver.Combinatorial.HittingSet.InterestingSets

Methods

(==) :: ImplicateOrImplicant -> ImplicateOrImplicant -> Bool

(/=) :: ImplicateOrImplicant -> ImplicateOrImplicant -> Bool

Ord ImplicateOrImplicant

Defined in ToySolver.Combinatorial.HittingSet.InterestingSets

Methods

compare :: ImplicateOrImplicant -> ImplicateOrImplicant -> Ordering

(<) :: ImplicateOrImplicant -> ImplicateOrImplicant -> Bool

(<=) :: ImplicateOrImplicant -> ImplicateOrImplicant -> Bool

(>) :: ImplicateOrImplicant -> ImplicateOrImplicant -> Bool

(>=) :: ImplicateOrImplicant -> ImplicateOrImplicant -> Bool

max :: ImplicateOrImplicant -> ImplicateOrImplicant -> ImplicateOrImplicant

min :: ImplicateOrImplicant -> ImplicateOrImplicant -> ImplicateOrImplicant

Read ImplicateOrImplicant

Defined in ToySolver.Combinatorial.HittingSet.InterestingSets

Methods

readsPrec :: Int -> ReadS ImplicateOrImplicant

readList :: ReadS [ImplicateOrImplicant]

readPrec :: ReadPrec ImplicateOrImplicant

readListPrec :: ReadPrec [ImplicateOrImplicant]

Show ImplicateOrImplicant

Defined in ToySolver.Combinatorial.HittingSet.InterestingSets

Methods

showsPrec :: Int -> ImplicateOrImplicant -> ShowS

show :: ImplicateOrImplicant -> String

showList :: [ImplicateOrImplicant] -> ShowS