-----------------------------------------------------------------------------
-- |
-- Module      :  ToySolver.Graph.MaxCut
-- Copyright   :  (c) Masahiro Sakai 2018
-- License     :  BSD-style
--
-- Maintainer  :  masahiro.sakai@gmail.com
-- Stability   :  provisional
-- Portability :  portable
--
-----------------------------------------------------------------------------
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