Copyright	(c) Masahiro Sakai 2018
License	BSD-style
Maintainer	masahiro.sakai@gmail.com
Stability	provisional
Portability	non-portable
Safe Haskell	None
Language	Haskell2010

ToySolver.Converter.SAT2MaxCut

Contents

SAT to MaxCut conversion
Low-level conversion
- NAE-SAT to MaxCut
- NAE-3-SAT to MaxCut

Description

http://www.cs.cornell.edu/courses/cs4820/2014sp/notes/reduction-maxcut.pdf

Synopsis

type SAT2MaxCutInfo = ComposedTransformer SAT2NAESATInfo NAESAT2MaxCutInfo
sat2maxcut :: CNF -> ((Problem Integer, Integer), SAT2MaxCutInfo)
type NAESAT2MaxCutInfo = ComposedTransformer NAESAT2NAEKSATInfo NAE3SAT2MaxCutInfo
naesat2maxcut :: NAESAT -> ((Problem Integer, Integer), NAESAT2MaxCutInfo)
data NAE3SAT2MaxCutInfo = NAE3SAT2MaxCutInfo
nae3sat2maxcut :: NAESAT -> ((Problem Integer, Integer), NAE3SAT2MaxCutInfo)

SAT to MaxCut conversion

type SAT2MaxCutInfo = ComposedTransformer SAT2NAESATInfo NAESAT2MaxCutInfo Source #

sat2maxcut :: CNF -> ((Problem Integer, Integer), SAT2MaxCutInfo) Source #

Low-level conversion

NAE-SAT to MaxCut

type NAESAT2MaxCutInfo = ComposedTransformer NAESAT2NAEKSATInfo NAE3SAT2MaxCutInfo Source #

naesat2maxcut :: NAESAT -> ((Problem Integer, Integer), NAESAT2MaxCutInfo) Source #

NAE-3-SAT to MaxCut

data NAE3SAT2MaxCutInfo Source #

Constructors

NAE3SAT2MaxCutInfo

Instances

Eq NAE3SAT2MaxCutInfo Source #
Instance details Defined in ToySolver.Converter.SAT2MaxCut Methods (==) :: NAE3SAT2MaxCutInfo -> NAE3SAT2MaxCutInfo -> Bool # (/=) :: NAE3SAT2MaxCutInfo -> NAE3SAT2MaxCutInfo -> Bool #
Read NAE3SAT2MaxCutInfo Source #
Instance details Defined in ToySolver.Converter.SAT2MaxCut Methods readsPrec :: Int -> ReadS NAE3SAT2MaxCutInfo # readList :: ReadS [NAE3SAT2MaxCutInfo] # readPrec :: ReadPrec NAE3SAT2MaxCutInfo # readListPrec :: ReadPrec [NAE3SAT2MaxCutInfo] #
Show NAE3SAT2MaxCutInfo Source #
Instance details Defined in ToySolver.Converter.SAT2MaxCut Methods showsPrec :: Int -> NAE3SAT2MaxCutInfo -> ShowS # show :: NAE3SAT2MaxCutInfo -> String # showList :: [NAE3SAT2MaxCutInfo] -> ShowS #
BackwardTransformer NAE3SAT2MaxCutInfo Source #
Instance details Defined in ToySolver.Converter.SAT2MaxCut Methods transformBackward :: NAE3SAT2MaxCutInfo -> Target NAE3SAT2MaxCutInfo -> Source NAE3SAT2MaxCutInfo Source #
ForwardTransformer NAE3SAT2MaxCutInfo Source #
Instance details Defined in ToySolver.Converter.SAT2MaxCut Methods transformForward :: NAE3SAT2MaxCutInfo -> Source NAE3SAT2MaxCutInfo -> Target NAE3SAT2MaxCutInfo Source #
Transformer NAE3SAT2MaxCutInfo Source #
Instance details Defined in ToySolver.Converter.SAT2MaxCut Associated Types type Source NAE3SAT2MaxCutInfo :: Type Source # type Target NAE3SAT2MaxCutInfo :: Type Source #
type Source NAE3SAT2MaxCutInfo Source #
Instance details Defined in ToySolver.Converter.SAT2MaxCut type Source NAE3SAT2MaxCutInfo = Model
type Target NAE3SAT2MaxCutInfo Source #
Instance details Defined in ToySolver.Converter.SAT2MaxCut type Target NAE3SAT2MaxCutInfo = Solution

nae3sat2maxcut :: NAESAT -> ((Problem Integer, Integer), NAE3SAT2MaxCutInfo) Source #