----------------------------------------------------------------------------- -- | -- Module : Data.Graph.Test.Typed -- Copyright : (c) Andrey Mokhov 2016-2022 -- License : MIT (see the file LICENSE) -- Maintainer : anfelor@posteo.de, andrey.mokhov@gmail.com -- Stability : experimental -- -- Testsuite for "Data.Graph.Typed". ----------------------------------------------------------------------------- module Data.Graph.Test.Typed ( -- * Testsuite testTyped ) where import qualified Algebra.Graph.AdjacencyMap as AM import qualified Algebra.Graph.AdjacencyIntMap as AIM import Algebra.Graph.Test import Data.Array (array) import Data.Graph.Typed import Data.Tree import Data.List (nub, sort) import qualified Data.Graph as KL import qualified Data.IntSet as IntSet type AI = AM.AdjacencyMap Int -- TODO: Improve the alignment in the testsuite to match the documentation. (%) :: (GraphKL Int -> a) -> AM.AdjacencyMap Int -> a a % g = a $ fromAdjacencyMap g testTyped :: IO () testTyped = do putStrLn "\n============ Typed ============" putStrLn "\n============ Typed.fromAdjacencyMap ============" test "toGraphKL (fromAdjacencyMap (1 * 2 + 3 * 1)) == array (0,2) [(0,[1]), (1,[]), (2,[0])]" $ toGraphKL (fromAdjacencyMap (1 * 2 + 3 * 1 :: AI)) == array (0,2) [(0,[1]), (1,[]), (2,[0])] test "toGraphKL (fromAdjacencyMap (1 * 2 + 2 * 1)) == array (0,1) [(0,[1]), (1,[0])]" $ toGraphKL (fromAdjacencyMap (1 * 2 + 2 * 1 :: AI)) == array (0,1) [(0,[1]), (1,[0])] test "map (fromVertexKL h) (vertices $ toGraphKL h) == vertexList g" $ \(g :: AI) -> let h = fromAdjacencyMap g in map (fromVertexKL h) (KL.vertices $ toGraphKL h) == AM.vertexList g test "map (\\(x, y) -> (fromVertexKL h x, fromVertexKL h y)) (edges $ toGraphKL h) == edgeList g" $ \(g :: AI) -> let h = fromAdjacencyMap g in map (\(x, y) -> (fromVertexKL h x, fromVertexKL h y)) (KL.edges $ toGraphKL h) == AM.edgeList g putStrLn "\n============ Typed.fromAdjacencyIntMap ============" test "toGraphKL (fromAdjacencyIntMap (1 * 2 + 3 * 1)) == array (0,2) [(0,[1]), (1,[]), (2,[0])]" $ toGraphKL (fromAdjacencyIntMap (1 * 2 + 3 * 1)) == array (0,2) [(0,[1]), (1,[]), (2,[0])] test "toGraphKL (fromAdjacencyIntMap (1 * 2 + 2 * 1)) == array (0,1) [(0,[1]), (1,[0])]" $ toGraphKL (fromAdjacencyIntMap (1 * 2 + 2 * 1)) == array (0,1) [(0,[1]), (1,[0])] test "map (fromVertexKL h) (vertices $ toGraphKL h) == IntSet.toAscList (vertexIntSet g)" $ \g -> let h = fromAdjacencyIntMap g in map (fromVertexKL h) (KL.vertices $ toGraphKL h) == IntSet.toAscList (AIM.vertexIntSet g) test "map (\\(x, y) -> (fromVertexKL h x, fromVertexKL h y)) (edges $ toGraphKL h) == edgeList g" $ \g -> let h = fromAdjacencyIntMap g in map (\(x, y) -> (fromVertexKL h x, fromVertexKL h y)) (KL.edges $ toGraphKL h) == AIM.edgeList g putStrLn $ "\n============ Typed.dfsForest ============" test "forest (dfsForest % edge 1 1) == vertex 1" $ AM.forest (dfsForest % AM.edge 1 1) == AM.vertex 1 test "forest (dfsForest % edge 1 2) == edge 1 2" $ AM.forest (dfsForest % AM.edge 1 2) == AM.edge 1 2 test "forest (dfsForest % edge 2 1) == vertices [1, 2]" $ AM.forest (dfsForest % AM.edge 2 1) == AM.vertices [1, 2] test "isSubgraphOf (forest $ dfsForest % x) x == True" $ \x -> AM.isSubgraphOf (AM.forest $ dfsForest % x) x == True test "dfsForest % forest (dfsForest % x) == dfsForest % x" $ \x -> dfsForest % AM.forest (dfsForest % x) == dfsForest % x test "dfsForest % vertices vs == map (\\v -> Node v []) (nub $ sort vs)" $ \vs -> dfsForest % AM.vertices vs == map (\v -> Node v []) (nub $ sort vs) test "dfsForest % (3 * (1 + 4) * (1 + 5)) == " $ dfsForest % (3 * (1 + 4) * (1 + 5)) == [ Node { rootLabel = 1 , subForest = [ Node { rootLabel = 5 , subForest = [] }]} , Node { rootLabel = 3 , subForest = [ Node { rootLabel = 4 , subForest = [] }]}] putStrLn $ "\n============ Typed.dfsForestFrom ============" test "forest (dfsForestFrom [1] % edge 1 1) == vertex 1" $ AM.forest (dfsForestFrom [1] % AM.edge 1 1) == AM.vertex 1 test "forest (dfsForestFrom [1] % edge 1 2) == edge 1 2" $ AM.forest (dfsForestFrom [1] % AM.edge 1 2) == AM.edge 1 2 test "forest (dfsForestFrom [2] % edge 1 2) == vertex 2" $ AM.forest (dfsForestFrom [2] % AM.edge 1 2) == AM.vertex 2 test "forest (dfsForestFrom [3] % edge 1 2) == empty" $ AM.forest (dfsForestFrom [3] % AM.edge 1 2) == AM.empty test "forest (dfsForestFrom [2, 1] % edge 1 2) == vertices [1, 2]" $ AM.forest (dfsForestFrom [2, 1] % AM.edge 1 2) == AM.vertices [1, 2] test "isSubgraphOf (forest $ dfsForestFrom vs % x) x == True" $ \vs x -> AM.isSubgraphOf (AM.forest (dfsForestFrom vs % x)) x == True test "dfsForestFrom (vertexList x) % x == dfsForest % x" $ \x -> dfsForestFrom (AM.vertexList x) % x == dfsForest % x test "dfsForestFrom vs % (AM.vertices vs) == map (\\v -> Node v []) (nub vs)" $ \vs -> dfsForestFrom vs % AM.vertices vs == map (\v -> Node v []) (nub vs) test "dfsForestFrom [] % x == []" $ \x -> dfsForestFrom [] % x == [] test "dfsForestFrom [1, 4] % 3 * (1 + 4) * (1 + 5) == " $ dfsForestFrom [1, 4] % (3 * (1 + 4) * (1 + 5)) == [ Node { rootLabel = 1 , subForest = [ Node { rootLabel = 5 , subForest = [] }]} , Node { rootLabel = 4 , subForest = [] }] putStrLn $ "\n============ Typed.dfs ============" test "dfs [1] % edge 1 1 == [1]" $ dfs [1] % AM.edge 1 1 == [1] test "dfs [1] % edge 1 2 == [1,2]" $ dfs [1] % AM.edge 1 2 == [1,2] test "dfs [2] % edge 1 2 == [2]" $ dfs [2] % AM.edge 1 2 == [2] test "dfs [3] % edge 1 2 == []" $ dfs [3] % AM.edge 1 2 == [] test "dfs [1, 2] % edge 1 2 == [1, 2]" $ dfs [1, 2] % AM.edge 1 2 == [1, 2] test "dfs [2, 1] % edge 1 2 == [2, 1]" $ dfs [2, 1] % AM.edge 1 2 == [2, 1] test "dfs [] % x == []" $ \x -> dfs [] % x == [] test "dfs [1, 4] % 3 * (1 + 4) * (1 + 5) == [1,5,4]" $ dfs [1, 4] % (3 * (1 + 4) * (1 + 5)) == [1,5,4] test "isSubgraphOf (vertices $ dfs vs % x) x == True" $ \vs x -> AM.isSubgraphOf (AM.vertices $ dfs vs % x) x == True putStrLn "\n============ Typed.topSort ============" test "topSort % (1 * 2 + 3 * 1) == [3,1,2]" $ topSort % (1 * 2 + 3 * 1) == ([3,1,2] :: [Int]) test "topSort % (1 * 2 + 2 * 1) == [1,2]" $ topSort % (1 * 2 + 2 * 1) == ([1,2] :: [Int])