```{-# LANGUAGE TemplateHaskell #-}
{-# OPTIONS_GHC -fno-warn-orphans #-}

{-| Unittests for Ganeti.Htools.Graph

-}

{-

This program is free software; you can redistribute it and/or modify
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
02110-1301, USA.

-}

module Test.Ganeti.HTools.Graph (testHTools_Graph) where

import Test.QuickCheck
import Test.HUnit

import Test.Ganeti.TestHelper
import Test.Ganeti.TestCommon

import Ganeti.HTools.Graph

import qualified Data.Graph as Graph
import qualified Data.IntMap as IntMap

{-# ANN module "HLint: ignore Use camelCase" #-}

data TestableGraph = TestableGraph Graph.Graph deriving (Show)
data TestableClique = TestableClique Graph.Graph deriving (Show)

-- | Generate node bounds and edges for an undirected graph.
-- A graph is undirected if for every (a, b) edge there is a
-- corresponding (b, a) one.
undirEdges :: Gen (Graph.Bounds, [Graph.Edge])
undirEdges = sized undirEdges'
where
undirEdges' 0 = return ((0, 0), [])
undirEdges' n = do
maxv <- choose (1, n)
edges <- listOf1 \$ do
i <- choose (0, maxv)
j <- choose (0, maxv) `suchThat` (/= i)
return [(i, j), (j, i)]
return ((0, maxv), concat edges)

-- | Generate node bounds and edges for a clique.
-- In a clique all nodes are directly connected to each other.
cliqueEdges :: Gen (Graph.Bounds, [Graph.Edge])
cliqueEdges = sized cliqueEdges'
where
cliqueEdges' 0 = return ((0, 0), [])
cliqueEdges' n = do
maxv <- choose (0, n)
let edges = [(x, y) | x <- [0..maxv], y <- [0..maxv], x /= y]
return ((0, maxv), edges)

instance Arbitrary TestableGraph where
arbitrary = do
(mybounds, myedges) <- undirEdges
return . TestableGraph \$ Graph.buildG mybounds myedges

instance Arbitrary TestableClique where
arbitrary = do
(mybounds, myedges) <- cliqueEdges
return . TestableClique \$ Graph.buildG mybounds myedges

-- | Check that the empty vertex color map is empty.
case_emptyVertColorMapNull :: Assertion
case_emptyVertColorMapNull = assertBool "" \$ IntMap.null emptyVertColorMap

-- | Check that the empty vertex color map is zero in size.
case_emptyVertColorMapEmpty :: Assertion
case_emptyVertColorMapEmpty =
assertEqual "" 0 \$ IntMap.size emptyVertColorMap

-- | Check if each two consecutive elements on a list
-- respect a given condition.
anyTwo :: (a -> a -> Bool) -> [a] -> Bool
anyTwo _ [] = True
anyTwo _ [_] = True
anyTwo op (x:y:xs) = (x `op` y) && anyTwo op (y:xs)

-- | Check order of vertices returned by verticesByDegreeAsc.
prop_verticesByDegreeAscAsc :: TestableGraph -> Bool
prop_verticesByDegreeAscAsc (TestableGraph g) = anyTwo (<=) (degrees asc)
where degrees = map (length . neighbors g)
asc = verticesByDegreeAsc g

-- | Check order of vertices returned by verticesByDegreeDesc.
prop_verticesByDegreeDescDesc :: TestableGraph -> Bool
prop_verticesByDegreeDescDesc (TestableGraph g) = anyTwo (>=) (degrees desc)
where degrees = map (length . neighbors g)
desc = verticesByDegreeDesc g

-- | Check that our generated graphs are colorable
prop_isColorableTestableGraph :: TestableGraph -> Bool
prop_isColorableTestableGraph (TestableGraph g) = isColorable g

-- | Check that our generated graphs are colorable
prop_isColorableTestableClique :: TestableClique -> Bool
prop_isColorableTestableClique (TestableClique g) = isColorable g

-- | Check that the given algorithm colors a clique with the same number of
-- colors as the vertices number.
prop_colorClique :: (Graph.Graph -> VertColorMap) -> TestableClique -> Property
prop_colorClique alg (TestableClique g) = numvertices ==? numcolors
where numcolors = (IntMap.size . colorVertMap) \$ alg g
numvertices = length (Graph.vertices g)

-- | Specific check for the LF algorithm.
prop_colorLFClique :: TestableClique -> Property
prop_colorLFClique = prop_colorClique colorLF

-- | Specific check for the Dsatur algorithm.
prop_colorDsaturClique :: TestableClique -> Property
prop_colorDsaturClique = prop_colorClique colorDsatur

-- | Specific check for the Dcolor algorithm.
prop_colorDcolorClique :: TestableClique -> Property
prop_colorDcolorClique = prop_colorClique colorDcolor

-- Check that all nodes are colored.
prop_colorAllNodes :: (Graph.Graph -> VertColorMap)
-> TestableGraph
-> Property
prop_colorAllNodes alg (TestableGraph g) = numvertices ==? numcolored
where numcolored = IntMap.fold ((+) . length) 0 vcMap
vcMap = colorVertMap \$ alg g
numvertices = length (Graph.vertices g)

-- | Specific check for the LF algorithm.
prop_colorLFAllNodes :: TestableGraph -> Property
prop_colorLFAllNodes = prop_colorAllNodes colorLF

-- | Specific check for the Dsatur algorithm.
prop_colorDsaturAllNodes :: TestableGraph -> Property
prop_colorDsaturAllNodes = prop_colorAllNodes colorDsatur

-- | Specific check for the Dcolor algorithm.
prop_colorDcolorAllNodes :: TestableGraph -> Property
prop_colorDcolorAllNodes = prop_colorAllNodes colorDcolor

-- | Check that no two vertices sharing the same edge have the same color.
prop_colorProper :: (Graph.Graph -> VertColorMap) -> TestableGraph -> Bool
prop_colorProper alg (TestableGraph g) = all isEdgeOk \$ Graph.edges g
where isEdgeOk :: Graph.Edge -> Bool
isEdgeOk (v1, v2) = color v1 /= color v2
color v = cMap IntMap.! v
cMap = alg g

-- | Specific check for the LF algorithm.
prop_colorLFProper :: TestableGraph -> Bool
prop_colorLFProper = prop_colorProper colorLF

-- | Specific check for the Dsatur algorithm.
prop_colorDsaturProper :: TestableGraph -> Bool
prop_colorDsaturProper = prop_colorProper colorDsatur

-- | Specific check for the Dcolor algorithm.
prop_colorDcolorProper :: TestableGraph -> Bool
prop_colorDcolorProper = prop_colorProper colorDcolor

-- | List of tests for the Graph module.
testSuite "HTools/Graph"
[ 'case_emptyVertColorMapNull
, 'case_emptyVertColorMapEmpty
, 'prop_verticesByDegreeAscAsc
, 'prop_verticesByDegreeDescDesc
, 'prop_colorLFClique
, 'prop_colorDsaturClique
, 'prop_colorDcolorClique
, 'prop_colorLFAllNodes
, 'prop_colorDsaturAllNodes
, 'prop_colorDcolorAllNodes
, 'prop_colorLFProper
, 'prop_colorDsaturProper
, 'prop_colorDcolorProper
, 'prop_isColorableTestableGraph
, 'prop_isColorableTestableClique
]
```