module ToySolver.Graph.MaxCut
( Problem (..)
, buildDSDPMaxCutGraph
, buildDSDPMaxCutGraph'
, Solution
, eval
, evalEdge
) where
import Data.Array.IArray
import Data.Array.Unboxed
import Data.ByteString.Builder
import Data.ByteString.Builder.Scientific
import qualified Data.ByteString.Lazy.Char8 as BL
import qualified Data.Foldable as F
import Data.IntMap.Strict (IntMap)
import qualified Data.IntMap.Strict as IntMap
import Data.Monoid
import Data.Scientific (Scientific)
import ToySolver.Graph.Base
type Problem a = EdgeLabeledGraph a
buildDSDPMaxCutGraph :: EdgeLabeledGraph Scientific -> Builder
buildDSDPMaxCutGraph :: EdgeLabeledGraph Scientific -> Builder
buildDSDPMaxCutGraph = forall a. (a -> Builder) -> EdgeLabeledGraph a -> Builder
buildDSDPMaxCutGraph' Scientific -> Builder
scientificBuilder
buildDSDPMaxCutGraph' :: (a -> Builder) -> EdgeLabeledGraph a -> Builder
buildDSDPMaxCutGraph' :: forall a. (a -> Builder) -> EdgeLabeledGraph a -> Builder
buildDSDPMaxCutGraph' a -> Builder
weightBuilder EdgeLabeledGraph a
prob = Builder
header forall a. Semigroup a => a -> a -> a
<> Builder
body
where
(Int
lb,Int
ub) = forall (a :: * -> * -> *) e i.
(IArray a e, Ix i) =>
a i e -> (i, i)
bounds EdgeLabeledGraph a
prob
m :: Int
m = forall (t :: * -> *) a. (Foldable t, Num a) => t a -> a
sum [forall a. IntMap a -> Int
IntMap.size IntMap a
m | IntMap a
m <- forall (a :: * -> * -> *) e i. (IArray a e, Ix i) => a i e -> [e]
elems EdgeLabeledGraph a
prob]
header :: Builder
header = Int -> Builder
intDec (Int
ubforall a. Num a => a -> a -> a
-Int
lbforall a. Num a => a -> a -> a
+Int
1) forall a. Semigroup a => a -> a -> a
<> Char -> Builder
char7 Char
' ' forall a. Semigroup a => a -> a -> a
<> Int -> Builder
intDec Int
m forall a. Semigroup a => a -> a -> a
<> Char -> Builder
char7 Char
'\n'
body :: Builder
body = forall a. Monoid a => [a] -> a
mconcat forall a b. (a -> b) -> a -> b
$ do
(Int
a,Int
b,a
w) <- forall a. EdgeLabeledGraph a -> [(Int, Int, a)]
graphToUnorderedEdges EdgeLabeledGraph a
prob
forall (m :: * -> *) a. Monad m => a -> m a
return forall a b. (a -> b) -> a -> b
$ Int -> Builder
intDec (Int
aforall a. Num a => a -> a -> a
-Int
lbforall a. Num a => a -> a -> a
+Int
1) forall a. Semigroup a => a -> a -> a
<> Char -> Builder
char7 Char
' ' forall a. Semigroup a => a -> a -> a
<> Int -> Builder
intDec (Int
bforall a. Num a => a -> a -> a
-Int
lbforall a. Num a => a -> a -> a
+Int
1) forall a. Semigroup a => a -> a -> a
<> Char -> Builder
char7 Char
' ' forall a. Semigroup a => a -> a -> a
<> a -> Builder
weightBuilder a
w forall a. Semigroup a => a -> a -> a
<> Char -> Builder
char7 Char
'\n'
type Solution = UArray Int Bool
eval :: Num a => Solution -> Problem a -> a
eval :: forall a. Num a => Solution -> Problem a -> a
eval Solution
sol Problem a
prob = forall (t :: * -> *) a. (Foldable t, Num a) => t a -> a
sum [a
w | (Int
a,Int
b,a
w) <- forall a. EdgeLabeledGraph a -> [(Int, Int, a)]
graphToUnorderedEdges Problem a
prob, Solution
sol forall (a :: * -> * -> *) e i.
(IArray a e, Ix i) =>
a i e -> i -> e
! Int
a forall a. Eq a => a -> a -> Bool
/= Solution
sol forall (a :: * -> * -> *) e i.
(IArray a e, Ix i) =>
a i e -> i -> e
! Int
b]
evalEdge :: Num a => Solution -> (Int,Int,a) -> a
evalEdge :: forall a. Num a => Solution -> (Int, Int, a) -> a
evalEdge Solution
sol (Int
a,Int
b,a
w)
| Solution
sol forall (a :: * -> * -> *) e i.
(IArray a e, Ix i) =>
a i e -> i -> e
! Int
a forall a. Eq a => a -> a -> Bool
/= Solution
sol forall (a :: * -> * -> *) e i.
(IArray a e, Ix i) =>
a i e -> i -> e
! Int
b = a
w
| Bool
otherwise = a
0