Copyright | (c) Masahiro Sakai 2018 |
---|---|
License | BSD-style |
Maintainer | masahiro.sakai@gmail.com |
Stability | provisional |
Portability | non-portable |
Safe Haskell | None |
Language | Haskell2010 |
References:
- M. R. Garey, D. S. Johnson, and L. Stockmeyer. Some simplified NP-complete problems. In STOC ’74: Proceedings of the sixth annual ACM symposium on Theory of computing, pages 47–63, New York, NY, USA, 1974. https://dl.acm.org/citation.cfm?doid=800119.803884 https://www.sciencedirect.com/science/article/pii/0304397576900591
Synopsis
- type SATToMaxSAT2Info = ComposedTransformer SAT2KSATInfo SAT3ToMaxSAT2Info
- satToMaxSAT2 :: CNF -> ((WCNF, Integer), SATToMaxSAT2Info)
- type MaxSAT2ToSimpleMaxCutInfo = ComposedTransformer SimplifyMaxSAT2Info SimpleMaxSAT2ToSimpleMaxCutInfo
- maxSAT2ToSimpleMaxCut :: (WCNF, Integer) -> ((Problem Integer, Integer), MaxSAT2ToSimpleMaxCutInfo)
- type SATToSimpleMaxCutInfo = ComposedTransformer SATToMaxSAT2Info MaxSAT2ToSimpleMaxCutInfo
- satToSimpleMaxCut :: CNF -> ((Problem Integer, Integer), SATToSimpleMaxCutInfo)
- data SAT3ToMaxSAT2Info = SAT3ToMaxSAT2Info !Int !Int (IntMap (Lit, Lit, Lit))
- sat3ToMaxSAT2 :: CNF -> ((WCNF, Integer), SAT3ToMaxSAT2Info)
- type SimpleMaxSAT2 = (Int, Set (Int, Int), Integer)
- data SimplifyMaxSAT2Info = SimplifyMaxSAT2Info !Int !Int (IntMap (Lit, Lit))
- simplifyMaxSAT2 :: (WCNF, Integer) -> (SimpleMaxSAT2, SimplifyMaxSAT2Info)
- data SimpleMaxSAT2ToSimpleMaxCutInfo = SimpleMaxSAT2ToSimpleMaxCutInfo !Int !Int
- simpleMaxSAT2ToSimpleMaxCut :: SimpleMaxSAT2 -> ((Problem Integer, Integer), SimpleMaxSAT2ToSimpleMaxCutInfo)
SAT to Max-2-SAT conversion
satToMaxSAT2 :: CNF -> ((WCNF, Integer), SATToMaxSAT2Info) Source #
Max-2-SAT to simple Max-Cut conversion
type MaxSAT2ToSimpleMaxCutInfo = ComposedTransformer SimplifyMaxSAT2Info SimpleMaxSAT2ToSimpleMaxCutInfo Source #
maxSAT2ToSimpleMaxCut :: (WCNF, Integer) -> ((Problem Integer, Integer), MaxSAT2ToSimpleMaxCutInfo) Source #
SAT to simple Max-Cut conversion
type SATToSimpleMaxCutInfo = ComposedTransformer SATToMaxSAT2Info MaxSAT2ToSimpleMaxCutInfo Source #
satToSimpleMaxCut :: CNF -> ((Problem Integer, Integer), SATToSimpleMaxCutInfo) Source #
Low-level conversion
3-SAT to Max-2-SAT conversion
data SAT3ToMaxSAT2Info Source #
Instances
Eq SAT3ToMaxSAT2Info Source # | |
Defined in ToySolver.Converter.SAT2MaxSAT (==) :: SAT3ToMaxSAT2Info -> SAT3ToMaxSAT2Info -> Bool # (/=) :: SAT3ToMaxSAT2Info -> SAT3ToMaxSAT2Info -> Bool # | |
Read SAT3ToMaxSAT2Info Source # | |
Defined in ToySolver.Converter.SAT2MaxSAT | |
Show SAT3ToMaxSAT2Info Source # | |
Defined in ToySolver.Converter.SAT2MaxSAT showsPrec :: Int -> SAT3ToMaxSAT2Info -> ShowS # show :: SAT3ToMaxSAT2Info -> String # showList :: [SAT3ToMaxSAT2Info] -> ShowS # | |
BackwardTransformer SAT3ToMaxSAT2Info Source # | |
ForwardTransformer SAT3ToMaxSAT2Info Source # | |
Transformer SAT3ToMaxSAT2Info Source # | |
Defined in ToySolver.Converter.SAT2MaxSAT type Source SAT3ToMaxSAT2Info :: Type Source # type Target SAT3ToMaxSAT2Info :: Type Source # | |
type Source SAT3ToMaxSAT2Info Source # | |
Defined in ToySolver.Converter.SAT2MaxSAT | |
type Target SAT3ToMaxSAT2Info Source # | |
Defined in ToySolver.Converter.SAT2MaxSAT |
sat3ToMaxSAT2 :: CNF -> ((WCNF, Integer), SAT3ToMaxSAT2Info) Source #
Max-2-SAT to SimpleMaxSAT2 conversion
data SimplifyMaxSAT2Info Source #
Instances
Eq SimplifyMaxSAT2Info Source # | |
Defined in ToySolver.Converter.SAT2MaxSAT (==) :: SimplifyMaxSAT2Info -> SimplifyMaxSAT2Info -> Bool # (/=) :: SimplifyMaxSAT2Info -> SimplifyMaxSAT2Info -> Bool # | |
Read SimplifyMaxSAT2Info Source # | |
Defined in ToySolver.Converter.SAT2MaxSAT | |
Show SimplifyMaxSAT2Info Source # | |
Defined in ToySolver.Converter.SAT2MaxSAT showsPrec :: Int -> SimplifyMaxSAT2Info -> ShowS # show :: SimplifyMaxSAT2Info -> String # showList :: [SimplifyMaxSAT2Info] -> ShowS # | |
BackwardTransformer SimplifyMaxSAT2Info Source # | |
ForwardTransformer SimplifyMaxSAT2Info Source # | |
Transformer SimplifyMaxSAT2Info Source # | |
Defined in ToySolver.Converter.SAT2MaxSAT type Source SimplifyMaxSAT2Info :: Type Source # type Target SimplifyMaxSAT2Info :: Type Source # | |
type Source SimplifyMaxSAT2Info Source # | |
Defined in ToySolver.Converter.SAT2MaxSAT | |
type Target SimplifyMaxSAT2Info Source # | |
Defined in ToySolver.Converter.SAT2MaxSAT |
simplifyMaxSAT2 :: (WCNF, Integer) -> (SimpleMaxSAT2, SimplifyMaxSAT2Info) Source #
SimpleMaxSAT2 to simple Max-Cut conversion
data SimpleMaxSAT2ToSimpleMaxCutInfo Source #