Packing-Cycles.hs

module Main where

import HGraph.Directed
import qualified HGraph.Directed.Packing.Cycles as PC
import qualified HGraph.Directed.AdjacencyMap as AM
import qualified Data.Set as S

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

cycleNormalForm vs = 
  let minV = minimum vs
      (end, begin) = span (/= minV) vs
  in begin ++ end
      

tests = TestList                         
  [ TestLabel "cycle 1" $ TestCase
    ( do
      let d = digraphFromArcList AM.emptyDigraph [(0,1)]
      assertEqual "Acyclic"
        ([], 0)
        (PC.maximumI d)
      let d' = addArc (1,0) d
          (xs, k) = PC.maximumI d'
      assertEqual "cycle"
        ([[0,1]],1)
        (map cycleNormalForm xs, k)
    )
  , TestLabel "cycle 2" $ TestCase
    ( do
      let d = digraphFromArcList AM.emptyDigraph [ (0,1), (1,0)
                                                 , (0,2), (2,3), (3,0)
                                                 , (1,4), (4,5), (5,1)
                                                 ]
          (xs, k) = (PC.maximumI d)
      assertEqual "2 cycles"
        (S.fromList [[0,2,3], [1,4,5]], 2)
        (S.fromList $ map cycleNormalForm xs,k)
    )
  , TestLabel "cycle 3" $ TestCase
    ( do
      let d = digraphFromArcList AM.emptyDigraph 
                [ (0,1), (0,2)
                , (1,5), (1,6)
                , (2,7)
                , (3,0)
                , (4,5), (4,6)
                , (5,0)
                , (6,1), (6,2)
                , (7,5), (7,6)
                ]
          (xs, k) = (PC.maximumI d)
      assertEqual "2 cycles"
        (S.fromList [[0,1,5], [2,7,6]], 2)
        (S.fromList $ map cycleNormalForm xs,k)
    )
  , TestLabel "arc disjoint cycle 1" $ TestCase
    ( do
      let d = digraphFromArcList AM.emptyDigraph [ (0,1), (1,0)
                                                 , (0,2), (2,3), (3,0)
                                                 , (1,4), (4,5), (5,1)
                                                 ]
          (xs, k) = (PC.arcMaximumI d)
      assertEqual "3 cycles"
        (S.fromList [[0,1], [0,2,3], [1,4,5]], 3)
        (S.fromList $ map cycleNormalForm xs,k)
    )
  , TestLabel "arc disjoint cycles 2" $ TestCase
    ( do
      let d = digraphFromArcList AM.emptyDigraph [ (1,2)
                                                 , (2,5), (2,0)
                                                 , (3,1), (3,5)
                                                 , (5,1), (5,2)
                                                 , (0,5)
                                                 ]
          (xs, k) = (PC.arcMaximumI d)
      assertAny "2 cycles"
        [ (S.fromList [[1,2,5], [2,0,5]], 2)
        , (S.fromList [[0,5,1,2], [2,5]], 2)
        ]
        (S.fromList $ map cycleNormalForm xs, k)
    )
  , TestLabel "arc disjoint cycles 3" $ TestCase
    ( do
      let d = digraphFromArcList AM.emptyDigraph [(0,2),(2,5),(2,6),(5,0),(5,2),(5,6),(6,1),(6,2)]
          (xs, k) = (PC.arcMaximumI d)
      assertEqual "2 cycles"
        (S.fromList [[0,2,5], [2,6]], 2)
        (S.fromList $ map cycleNormalForm xs, k)
    )
  , TestLabel "arc disjoint cycles 4" $ TestCase
    ( do
      -- let d = digraphFromArcList AM.emptyDigraph [(0,1),(1,3),(1,6),(1,9),(2,0),(2,4),(3,1),(3,8),(4,6),(4,9),(5,6),(6,0),(6,3),(6,5),(7,1),(7,3),(8,1),(8,9),(9,1),(9,7)]
      let d = digraphFromArcList AM.emptyDigraph [(0,1),(1,3),(1,6),(3,1),(3,4),(5,6),(6,0),(6,3),(6,5),(7,3),(4,2),(2,7)]
          (xs, k) = (PC.arcMaximumI d)
      assertEqual "5 cycles"
        (S.fromList [[0,1,6], [1,3], [2,7,3,4], [5,6]], 4)
        (S.fromList $ map cycleNormalForm xs, k)
    )
  ]

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