TestVertexCover.hs

module Main where

import HGraph.Undirected.AdjacencyMap
import HGraph.Undirected.Solvers.VertexCover

import Test.HUnit hiding (Node)
import System.Exit (exitFailure, exitSuccess)

isVc g vc = numEdges (foldr (flip removeVertex) g vc) == 0

tests = TestList                         
  [ TestLabel "No edges 1" $ TestCase
    ( do
      let g = addVertex emptyGraph 1
          vc = minimumVertexCover g
      assertEqual "Empty VC" [] vc
    )
  , TestLabel "No edges 2" $ TestCase
    ( do
      let g = foldr (flip addVertex) emptyGraph [1,2,3,4,5,6]
          vc = minimumVertexCover g
      assertEqual "Empty VC" [] vc
    )
  , TestLabel "VC 1" $ TestCase
    ( do
      let g = addEdge (foldr (flip addVertex) emptyGraph [1,2]) (1,2)
          vc = minimumVertexCover g
      assertEqual "VC = 1" 1 (length vc)
      assertBool  "Is VC" $ isVc g vc
    )
  , TestLabel "VC 2" $ TestCase
    ( do
      let g = foldr (flip addEdge)
                    (foldr (flip addVertex) emptyGraph [1,2,3,4])
                    [(1,2), (1,3), (1,4)]
          vc = minimumVertexCover g
      assertEqual "VC = 1" 1 (length vc)
      assertBool  "Is VC" $ isVc g vc
    )
  , TestLabel "VC 3" $ TestCase
    ( do
      let g = foldr (flip addEdge)
                    (foldr (flip addVertex) emptyGraph [1,2,3,4])
                    [(1,2), (1,3), (1,4), (2,3)]
          vc = minimumVertexCover g
      assertEqual "|VC|" 2 (length vc)
      assertBool  "Is VC" $ isVc g vc
    )
  , TestLabel "VC 4" $ TestCase
    ( do
      let g = foldr (flip addEdge)
                    (foldr (flip addVertex) emptyGraph [1,2,3,4,5,6])
                    ((1,6):(zip [1..5] [2..6]))
          vc = minimumVertexCover g
      assertEqual "|VC|" 3 (length vc)
      assertBool  "Is VC" $ isVc g vc
    )
  , TestLabel "VC grid" $ TestCase
    ( do
      let g = foldr (flip addEdge)
                    (foldr (flip addVertex) emptyGraph [ (x,y) | x <- [1..4], y <- [1..4]])
                    ([((4,y), (4,y+1)) | y <- [1..3]] ++
                     [((x,4), (x+1,4)) | x <- [1..3]] ++
                     concat [[ ((x,y), (x+1,y))
                             , ((x,y), (x,y+1))
                             ]
                            | x <- [1..3], y <- [1..3]
                            ]
                    )
          vc = minimumVertexCover g
      assertEqual "|VC|" 8 (length vc)
      assertBool  "Is VC" $ isVc g vc
    )
  ]

main = do 
  count <- runTestTT tests
  if errors count + failures count > 0 then exitFailure else exitSuccess