1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
|
module Futhark.Optimise.MemoryBlockMerging.GreedyColoringTests
( tests,
)
where
import Control.Arrow ((***))
import Data.Function ((&))
import Data.Map qualified as M
import Data.Set qualified as S
import Futhark.Optimise.MemoryBlockMerging.GreedyColoring qualified as GreedyColoring
import Test.Tasty
import Test.Tasty.HUnit
tests :: TestTree
tests =
testGroup
"GreedyColoringTests"
[psumTest, allIntersect, emptyGraph, noIntersections, differentSpaces]
psumTest :: TestTree
psumTest =
testCase "psumTest"
$ assertEqual
"Color simple 1-2-3 using two colors"
( [(0, "shared"), (1, "shared")] :: [(Int, String)],
[(1 :: Int, 0), (2, 1), (3, 0)]
)
$ (M.toList *** M.toList)
$ GreedyColoring.colorGraph
(M.fromList [(1, "shared"), (2, "shared"), (3, "shared")])
$ S.fromList [(1, 2), (2, 3)]
allIntersect :: TestTree
allIntersect =
testCase "allIntersect"
$ assertEqual
"Color a graph where all values intersect"
( [(0, "shared"), (1, "shared"), (2, "shared")] :: [(Int, String)],
[(1 :: Int, 2), (2, 1), (3, 0)]
)
$ (M.toList *** M.toList)
$ GreedyColoring.colorGraph
(M.fromList [(1, "shared"), (2, "shared"), (3, "shared")])
$ S.fromList [(1, 2), (2, 3), (1, 3)]
emptyGraph :: TestTree
emptyGraph =
testCase "emptyGraph"
$ assertEqual
"Color an empty graph"
([] :: [(Int, Char)], [] :: [(Int, Int)])
$ (M.toList *** M.toList)
$ GreedyColoring.colorGraph M.empty
$ S.fromList []
noIntersections :: TestTree
noIntersections =
GreedyColoring.colorGraph
(M.fromList [(1, "shared"), (2, "shared"), (3, "shared")])
(S.fromList [])
& M.toList *** M.toList
& assertEqual
"Color nodes with no intersections"
( [(0, "shared")] :: [(Int, String)],
[(1, 0), (2, 0), (3, 0)] :: [(Int, Int)]
)
& testCase "noIntersections"
differentSpaces :: TestTree
differentSpaces =
GreedyColoring.colorGraph
(M.fromList [(1, "a"), (2, "b"), (3, "c")])
(S.fromList [])
& M.toList *** M.toList
& assertEqual
"Color nodes with no intersections but in different spaces"
( [(0, "c"), (1, "b"), (2, "a")] :: [(Int, String)],
[(1, 2), (2, 1), (3, 0)] :: [(Int, Int)]
)
& testCase "differentSpaces"
|
