1{-# LANGUAGE ViewPatterns #-} 2----------------------------------------------------------------------------- 3-- | 4-- Module : Algebra.Graph.Test.Labelled.AdjacencyMap 5-- Copyright : (c) Andrey Mokhov 2016-2019 6-- License : MIT (see the file LICENSE) 7-- Maintainer : andrey.mokhov@gmail.com 8-- Stability : experimental 9-- 10-- Testsuite for "Algebra.Graph.Labelled.AdjacencyMap". 11----------------------------------------------------------------------------- 12module Algebra.Graph.Test.Labelled.AdjacencyMap ( 13 -- * Testsuite 14 testLabelledAdjacencyMap 15 ) where 16 17import Data.Monoid 18 19import Algebra.Graph.Label 20import Algebra.Graph.Labelled.AdjacencyMap 21import Algebra.Graph.Test 22import Algebra.Graph.Test.API (toIntAPI, labelledAdjacencyMapAPI) 23import Algebra.Graph.Test.Generic 24import Algebra.Graph.ToGraph (reachable) 25 26import qualified Algebra.Graph.AdjacencyMap as AM 27import qualified Data.Map as Map 28import qualified Data.Set as Set 29 30tPoly :: Testsuite (AdjacencyMap Any) Ord 31tPoly = ("Labelled.AdjacencyMap.", labelledAdjacencyMapAPI) 32 33t :: TestsuiteInt (AdjacencyMap Any) 34t = fmap toIntAPI tPoly 35 36type S = Sum Int 37type D = Distance Int 38 39type LAI = AdjacencyMap Any Int 40type LAS = AdjacencyMap S Int 41type LAD = AdjacencyMap D Int 42 43testLabelledAdjacencyMap :: IO () 44testLabelledAdjacencyMap = do 45 putStrLn "\n============ Labelled.AdjacencyMap.consistent ============" 46 test "arbitraryLabelledAdjacencyMap" $ \x -> consistent (x :: LAS) 47 test "empty" $ consistent (empty :: LAS) 48 test "vertex" $ \x -> consistent (vertex x :: LAS) 49 test "edge" $ \e x y -> consistent (edge e x y :: LAS) 50 test "overlay" $ \x y -> consistent (overlay x y :: LAS) 51 test "connect" $ size10 $ \e x y -> consistent (connect e x y :: LAS) 52 test "vertices" $ \xs -> consistent (vertices xs :: LAS) 53 test "edges" $ \es -> consistent (edges es :: LAS) 54 test "overlays" $ size10 $ \xs -> consistent (overlays xs :: LAS) 55 test "fromAdjacencyMaps" $ \xs -> consistent (fromAdjacencyMaps xs :: LAS) 56 test "removeVertex" $ \x y -> consistent (removeVertex x y :: LAS) 57 test "removeEdge" $ \x y z -> consistent (removeEdge x y z :: LAS) 58 test "replaceVertex" $ \x y z -> consistent (replaceVertex x y z :: LAS) 59 test "replaceEdge" $ \e x y z -> consistent (replaceEdge e x y z :: LAS) 60 test "transpose" $ \x -> consistent (transpose x :: LAS) 61 test "gmap" $ \(apply -> f) x -> consistent (gmap f (x :: LAS) :: LAS) 62 test "emap" $ \(apply -> f) x -> consistent (emap (fmap f::S->S) x:: LAS) 63 test "induce" $ \(apply -> p) x -> consistent (induce p x :: LAS) 64 65 test "closure" $ size10 $ \x -> consistent (closure x :: LAD) 66 test "reflexiveClosure" $ size10 $ \x -> consistent (reflexiveClosure x :: LAD) 67 test "symmetricClosure" $ size10 $ \x -> consistent (symmetricClosure x :: LAD) 68 test "transitiveClosure" $ size10 $ \x -> consistent (transitiveClosure x :: LAD) 69 70 testEmpty t 71 testVertex t 72 73 putStrLn "\n============ Labelled.AdjacencyMap.edge ============" 74 test "edge e x y == connect e (vertex x) (vertex y)" $ \(e :: S) (x :: Int) y -> 75 edge e x y == connect e (vertex x) (vertex y) 76 77 test "edge zero x y == vertices [x,y]" $ \(x :: Int) y -> 78 edge (zero :: S) x y == vertices [x,y] 79 80 test "hasEdge x y (edge e x y) == (e /= mempty)" $ \(e :: S) (x :: Int) y -> 81 hasEdge x y (edge e x y) == (e /= mempty) 82 83 test "edgeLabel x y (edge e x y) == e" $ \(e :: S) (x :: Int) y -> 84 edgeLabel x y (edge e x y) == e 85 86 test "edgeCount (edge e x y) == if e == mempty then 0 else 1" $ \(e :: S) (x :: Int) y -> 87 edgeCount (edge e x y) == if e == mempty then 0 else 1 88 89 test "vertexCount (edge e 1 1) == 1" $ \(e :: S) -> 90 vertexCount (edge e 1 (1 :: Int)) == 1 91 92 test "vertexCount (edge e 1 2) == 2" $ \(e :: S) -> 93 vertexCount (edge e 1 (2 :: Int)) == 2 94 95 test "x -<e>- y == edge e x y" $ \(e :: S) (x :: Int) y -> 96 x -<e>- y == edge e x y 97 98 testOverlay t 99 100 putStrLn "" 101 test "edgeLabel x y $ overlay (edge e x y) (edge zero x y) == e" $ \(e :: S) (x :: Int) y -> 102 edgeLabel x y (overlay (edge e x y) (edge zero x y)) == e 103 104 test "edgeLabel x y $ overlay (edge e x y) (edge f x y) == e <+> f" $ \(e :: S) f (x :: Int) y -> 105 edgeLabel x y (overlay (edge e x y) (edge f x y)) == e <+> f 106 107 putStrLn "" 108 test "edgeLabel 1 3 $ transitiveClosure (overlay (edge e 1 2) (edge one 2 3)) == e" $ \(e :: D) -> 109 edgeLabel 1 3 (transitiveClosure (overlay (edge e 1 2) (edge one 2 (3 :: Int)))) == e 110 111 test "edgeLabel 1 3 $ transitiveClosure (overlay (edge e 1 2) (edge f 2 3)) == e <.> f" $ \(e :: D) f -> 112 edgeLabel 1 3 (transitiveClosure (overlay (edge e 1 2) (edge f 2 (3 :: Int))))== e <.> f 113 114 putStrLn "\n============ Labelled.AdjacencyMap.connect ============" 115 test "isEmpty (connect e x y) == isEmpty x && isEmpty y" $ size10 $ \(e :: S) (x :: LAS) y -> 116 isEmpty (connect e x y) ==(isEmpty x && isEmpty y) 117 118 test "hasVertex z (connect e x y) == hasVertex z x || hasVertex z y" $ size10 $ \(e :: S) (x :: LAS) y z -> 119 hasVertex z (connect e x y) ==(hasVertex z x || hasVertex z y) 120 121 test "vertexCount (connect e x y) >= vertexCount x" $ size10 $ \(e :: S) (x :: LAS) y -> 122 vertexCount (connect e x y) >= vertexCount x 123 124 test "vertexCount (connect e x y) <= vertexCount x + vertexCount y" $ size10 $ \(e :: S) (x :: LAS) y -> 125 vertexCount (connect e x y) <= vertexCount x + vertexCount y 126 127 test "edgeCount (connect e x y) <= vertexCount x * vertexCount y + edgeCount x + edgeCount y" $ size10 $ \(e :: S) (x :: LAS) y -> 128 edgeCount (connect e x y) <= vertexCount x * vertexCount y + edgeCount x + edgeCount y 129 130 test "vertexCount (connect e 1 2) == 2" $ \(e :: Any) -> 131 vertexCount (connect e 1 (2 :: LAI)) == 2 132 133 test "edgeCount (connect e 1 2) == if e == zero then 0 else 1" $ \(e :: Any) -> 134 edgeCount (connect e 1 (2 :: LAI)) == if e == zero then 0 else 1 135 136 testVertices t 137 138 putStrLn "\n============ Labelled.AdjacencyMap.edges ============" 139 test "edges [] == empty" $ 140 edges [] == (empty :: LAS) 141 142 test "edges [(e,x,y)] == edge e x y" $ \(e :: S) (x :: Int) y -> 143 edges [(e,x,y)] == edge e x y 144 145 test "edges == overlays . map (\\(e, x, y) -> edge e x y)" $ \(es :: [(S, Int, Int)]) -> 146 edges es ==(overlays . map (\(e, x, y) -> edge e x y)) es 147 148 testOverlays t 149 150 putStrLn "\n============ Labelled.AdjacencyMap.fromAdjacencyMaps ============" 151 test "fromAdjacencyMaps [] == empty" $ 152 fromAdjacencyMaps [] == (empty :: LAS) 153 154 test "fromAdjacencyMaps [(x, Map.empty)] == vertex x" $ \(x :: Int) -> 155 fromAdjacencyMaps [(x, Map.empty)] == (vertex x :: LAS) 156 157 test "fromAdjacencyMaps [(x, Map.singleton y e)] == if e == zero then vertices [x,y] else edge e x y" $ \(e :: S) (x :: Int) y -> 158 fromAdjacencyMaps [(x, Map.singleton y e)] == if e == zero then vertices [x,y] else edge e x y 159 160 test "overlay (fromAdjacencyMaps xs) (fromAdjacencyMaps ys) == fromAdjacencyMaps (xs ++ ys)" $ \xs ys -> 161 overlay (fromAdjacencyMaps xs) (fromAdjacencyMaps ys) == (fromAdjacencyMaps (xs ++ ys) :: LAS) 162 163 putStrLn "\n============ Labelled.AdjacencyMap.isSubgraphOf ============" 164 test "isSubgraphOf empty x == True" $ \(x :: LAS) -> 165 isSubgraphOf empty x == True 166 167 test "isSubgraphOf (vertex x) empty == False" $ \(x :: Int) -> 168 isSubgraphOf (vertex x)(empty :: LAS)== False 169 170 test "isSubgraphOf x y ==> x <= y" $ \(x :: LAD) z -> 171 let y = x + z -- Make sure we hit the precondition 172 in isSubgraphOf x y ==> x <= y 173 174 putStrLn "\n============ Labelled.AdjacencyMap.isEmpty ============" 175 test "isEmpty empty == True" $ 176 isEmpty empty == True 177 178 test "isEmpty (overlay empty empty) == True" $ 179 isEmpty (overlay empty empty :: LAS) == True 180 181 test "isEmpty (vertex x) == False" $ \(x :: Int) -> 182 isEmpty (vertex x) == False 183 184 test "isEmpty (removeVertex x $ vertex x) == True" $ \(x :: Int) -> 185 isEmpty (removeVertex x $ vertex x) == True 186 187 test "isEmpty (removeEdge x y $ edge e x y) == False" $ \(e :: S) (x :: Int) y -> 188 isEmpty (removeEdge x y $ edge e x y) == False 189 190 testHasVertex t 191 192 putStrLn "\n============ Labelled.AdjacencyMap.hasEdge ============" 193 test "hasEdge x y empty == False" $ \(x :: Int) y -> 194 hasEdge x y empty == False 195 196 test "hasEdge x y (vertex z) == False" $ \(x :: Int) y z -> 197 hasEdge x y (vertex z) == False 198 199 test "hasEdge x y (edge e x y) == (e /= zero)" $ \(e :: S) (x :: Int) y -> 200 hasEdge x y (edge e x y) == (e /= zero) 201 202 test "hasEdge x y . removeEdge x y == const False" $ \x y (z :: LAS) -> 203 (hasEdge x y . removeEdge x y) z == const False z 204 205 test "hasEdge x y == not . null . filter (\\(_,ex,ey) -> ex == x && ey == y) . edgeList" $ \x y (z :: LAS) -> do 206 (_, u, v) <- elements ((zero, x, y) : edgeList z) 207 return $ hasEdge u v z == (not . null . filter (\(_,ex,ey) -> ex == u && ey == v) . edgeList) z 208 209 putStrLn "\n============ Labelled.AdjacencyMap.edgeLabel ============" 210 test "edgeLabel x y empty == zero" $ \(x :: Int) y -> 211 edgeLabel x y empty == (zero :: S) 212 213 test "edgeLabel x y (vertex z) == zero" $ \(x :: Int) y z -> 214 edgeLabel x y (vertex z) == (zero :: S) 215 216 test "edgeLabel x y (edge e x y) == e" $ \(e :: S) (x :: Int) y -> 217 edgeLabel x y (edge e x y) == e 218 219 test "edgeLabel s t (overlay x y) == edgeLabel s t x + edgeLabel s t y" $ \(x :: LAS) y -> do 220 z <- arbitrary 221 s <- elements ([z] ++ vertexList x ++ vertexList y) 222 t <- elements ([z] ++ vertexList x ++ vertexList y) 223 return $ edgeLabel s t (overlay x y) == edgeLabel s t x + edgeLabel s t y 224 225 testVertexCount t 226 227 putStrLn "\n============ Labelled.AdjacencyMap.edgeCount ============" 228 test "edgeCount empty == 0" $ 229 edgeCount empty == 0 230 231 test "edgeCount (vertex x) == 0" $ \(x :: Int) -> 232 edgeCount (vertex x) == 0 233 234 test "edgeCount (edge e x y) == if e == zero then 0 else 1" $ \(e :: S) (x :: Int) y -> 235 edgeCount (edge e x y) == if e == zero then 0 else 1 236 237 test "edgeCount == length . edgeList" $ \(x :: LAS) -> 238 edgeCount x == (length . edgeList) x 239 240 testVertexList t 241 242 putStrLn "\n============ Labelled.AdjacencyMap.edgeList ============" 243 test "edgeList empty == []" $ 244 edgeList (empty :: LAS) == [] 245 246 test "edgeList (vertex x) == []" $ \(x :: Int) -> 247 edgeList (vertex x :: LAS) == [] 248 249 test "edgeList (edge e x y) == if e == zero then [] else [(e,x,y)]" $ \(e :: S) (x :: Int) y -> 250 edgeList (edge e x y) == if e == zero then [] else [(e,x,y)] 251 252 testVertexSet t 253 254 putStrLn "\n============ Labelled.AdjacencyMap.edgeSet ============" 255 test "edgeSet empty == Set.empty" $ 256 edgeSet (empty :: LAS) == Set.empty 257 258 test "edgeSet (vertex x) == Set.empty" $ \(x :: Int) -> 259 edgeSet (vertex x :: LAS) == Set.empty 260 261 test "edgeSet (edge e x y) == if e == zero then Set.empty else Set.singleton (e,x,y)" $ \(e :: S) (x :: Int) y -> 262 edgeSet (edge e x y) == if e == zero then Set.empty else Set.singleton (e,x,y) 263 264 putStrLn "\n============ Labelled.AdjacencyMap.preSet ============" 265 test "preSet x empty == Set.empty" $ \x -> 266 preSet x (empty :: LAS) == Set.empty 267 268 test "preSet x (vertex x) == Set.empty" $ \x -> 269 preSet x (vertex x :: LAS) == Set.empty 270 271 test "preSet 1 (edge e 1 2) == Set.empty" $ \e -> 272 preSet 1 (edge e 1 2 :: LAS) == Set.empty 273 274 test "preSet y (edge e x y) == if e == zero then Set.empty else Set.fromList [x]" $ \(e :: S) (x :: Int) y -> 275 preSet y (edge e x y) == if e == zero then Set.empty else Set.fromList [x] 276 277 putStrLn "\n============ Labelled.AdjacencyMap.postSet ============" 278 test "postSet x empty == Set.empty" $ \x -> 279 postSet x (empty :: LAS) == Set.empty 280 281 test "postSet x (vertex x) == Set.empty" $ \x -> 282 postSet x (vertex x :: LAS) == Set.empty 283 284 test "postSet x (edge e x y) == if e == zero then Set.empty else Set.fromList [y]" $ \(e :: S) (x :: Int) y -> 285 postSet x (edge e x y) == if e == zero then Set.empty else Set.fromList [y] 286 287 test "postSet 2 (edge e 1 2) == Set.empty" $ \e -> 288 postSet 2 (edge e 1 2 :: LAS) == Set.empty 289 290 putStrLn "\n============ Labelled.AdjacencyMap.skeleton ============" 291 test "hasEdge x y == hasEdge x y . skeleton" $ \x y (z :: LAS) -> 292 hasEdge x y z == (AM.hasEdge x y . skeleton) z 293 294 putStrLn "\n============ Labelled.AdjacencyMap.removeVertex ============" 295 test "removeVertex x (vertex x) == empty" $ \x -> 296 removeVertex x (vertex x) == (empty :: LAS) 297 298 test "removeVertex 1 (vertex 2) == vertex 2" $ 299 removeVertex 1 (vertex 2) == (vertex 2 :: LAS) 300 301 test "removeVertex x (edge e x x) == empty" $ \(e :: S) (x :: Int) -> 302 removeVertex x (edge e x x) == empty 303 304 test "removeVertex 1 (edge e 1 2) == vertex 2" $ \(e :: S) -> 305 removeVertex 1 (edge e 1 2) == vertex (2 :: Int) 306 307 test "removeVertex x . removeVertex x == removeVertex x" $ \x (y :: LAS) -> 308 (removeVertex x . removeVertex x) y == removeVertex x y 309 310 putStrLn "\n============ Labelled.AdjacencyMap.removeEdge ============" 311 test "removeEdge x y (edge e x y) == vertices [x,y]" $ \(e :: S) (x :: Int) y -> 312 removeEdge x y (edge e x y) == vertices [x,y] 313 314 test "removeEdge x y . removeEdge x y == removeEdge x y" $ \x y (z :: LAS) -> 315 (removeEdge x y . removeEdge x y) z == removeEdge x y z 316 317 test "removeEdge x y . removeVertex x == removeVertex x" $ \x y (z :: LAS) -> 318 (removeEdge x y . removeVertex x) z == removeVertex x z 319 320 test "removeEdge 1 1 (1 * 1 * 2 * 2) == 1 * 2 * 2" $ 321 removeEdge 1 1 (1 * 1 * 2 * 2) == (1 * 2 * 2 :: LAD) 322 323 test "removeEdge 1 2 (1 * 1 * 2 * 2) == 1 * 1 + 2 * 2" $ 324 removeEdge 1 2 (1 * 1 * 2 * 2) == (1 * 1 + 2 * 2 :: LAD) 325 326 putStrLn "\n============ Labelled.AdjacencyMap.replaceVertex ============" 327 test "replaceVertex x x == id" $ \x y -> 328 replaceVertex x x y == (y :: LAS) 329 330 test "replaceVertex x y (vertex x) == vertex y" $ \x y -> 331 replaceVertex x y (vertex x) == (vertex y :: LAS) 332 333 test "replaceVertex x y == gmap (\\v -> if v == x then y else v)" $ \x y (z :: LAS) -> 334 replaceVertex x y z == gmap (\v -> if v == x then y else v) z 335 336 putStrLn "\n============ Labelled.AdjacencyMap.replaceEdge ============" 337 test "replaceEdge e x y z == overlay (removeEdge x y z) (edge e x y)" $ \(e :: S) (x :: Int) y z -> 338 replaceEdge e x y z == overlay (removeEdge x y z) (edge e x y) 339 340 test "replaceEdge e x y (edge f x y) == edge e x y" $ \(e :: S) f (x :: Int) y -> 341 replaceEdge e x y (edge f x y) == edge e x y 342 343 test "edgeLabel x y (replaceEdge e x y z) == e" $ \(e :: S) (x :: Int) y z -> 344 edgeLabel x y (replaceEdge e x y z) == e 345 346 putStrLn "\n============ Labelled.AdjacencyMap.transpose ============" 347 test "transpose empty == empty" $ 348 transpose empty == (empty :: LAS) 349 350 test "transpose (vertex x) == vertex x" $ \x -> 351 transpose (vertex x) == (vertex x :: LAS) 352 353 test "transpose (edge e x y) == edge e y x" $ \e x y -> 354 transpose (edge e x y) == (edge e y x :: LAS) 355 356 test "transpose . transpose == id" $ size10 $ \x -> 357 (transpose . transpose) x == (x :: LAS) 358 359 putStrLn "\n============ Labelled.AdjacencyMap.gmap ============" 360 test "gmap f empty == empty" $ \(apply -> f) -> 361 gmap f (empty :: LAS) == (empty :: LAS) 362 363 test "gmap f (vertex x) == vertex (f x)" $ \(apply -> f) x -> 364 gmap f (vertex x :: LAS) == (vertex (f x) :: LAS) 365 366 test "gmap f (edge e x y) == edge e (f x) (f y)" $ \(apply -> f) e x y -> 367 gmap f (edge e x y :: LAS) == (edge e (f x) (f y) :: LAS) 368 369 test "gmap id == id" $ \x -> 370 gmap id x == (x :: LAS) 371 372 test "gmap f . gmap g == gmap (f . g)" $ \(apply -> f) (apply -> g) x -> 373 ((gmap f :: LAS -> LAS) . gmap g) (x :: LAS) == gmap (f . g) x 374 375 -- TODO: We only test homomorphisms @h@ on @Sum Int@, which all happen to be 376 -- just linear transformations: @h = (k*)@ for some @k :: Int@. These tests 377 -- are therefore rather weak and do not cover the ruch space of possible 378 -- monoid homomorphisms. How can we improve this? 379 putStrLn "\n============ Labelled.AdjacencyMap.emap ============" 380 test "emap h empty == empty" $ \(k :: S) -> 381 let h = (k*) 382 in emap h empty == (empty :: LAS) 383 384 test "emap h (vertex x) == vertex x" $ \(k :: S) x -> 385 let h = (k*) 386 in emap h (vertex x) == (vertex x :: LAS) 387 388 test "emap h (edge e x y) == edge (h e) x y" $ \(k :: S) e x y -> 389 let h = (k*) 390 in emap h (edge e x y) == (edge (h e) x y :: LAS) 391 392 test "emap h (overlay x y) == overlay (emap h x) (emap h y)" $ \(k :: S) x y -> 393 let h = (k*) 394 in emap h (overlay x y) == (overlay (emap h x) (emap h y) :: LAS) 395 396 test "emap h (connect e x y) == connect (h e) (emap h x) (emap h y)" $ \(k :: S) (e :: S) x y -> 397 let h = (k*) 398 in emap h (connect e x y) == (connect (h e) (emap h x) (emap h y) :: LAS) 399 400 test "emap id == id" $ \x -> 401 emap id x == (id x :: LAS) 402 403 test "emap g . emap h == emap (g . h)" $ \(k :: S) (l :: S) x -> 404 let h = (k*) 405 g = (l*) 406 in (emap g . emap h) x == (emap (g . h) x :: LAS) 407 408 testInduce t 409 testInduceJust tPoly 410 411 putStrLn "\n============ Labelled.AdjacencyMap.closure ============" 412 test "closure empty == empty" $ 413 closure empty == (empty :: LAD) 414 415 test "closure (vertex x) == edge one x x" $ \x -> 416 closure (vertex x) == (edge one x x :: LAD) 417 418 test "closure (edge e x x) == edge one x x" $ \e x -> 419 closure (edge e x x) == (edge one x x :: LAD) 420 421 test "closure (edge e x y) == edges [(one,x,x), (e,x,y), (one,y,y)]" $ \e x y -> 422 closure (edge e x y) == (edges [(one,x,x), (e,x,y), (one,y,y)] :: LAD) 423 424 test "closure == reflexiveClosure . transitiveClosure" $ size10 $ \x -> 425 closure (x :: LAD) == (reflexiveClosure . transitiveClosure) x 426 427 test "closure == transitiveClosure . reflexiveClosure" $ size10 $ \x -> 428 closure (x :: LAD) == (transitiveClosure . reflexiveClosure) x 429 430 test "closure . closure == closure" $ size10 $ \x -> 431 (closure . closure) x == closure (x :: LAD) 432 433 test "postSet x (closure y) == Set.fromList (reachable x y)" $ size10 $ \(x :: Int) (y :: LAD) -> 434 postSet x (closure y) == Set.fromList (reachable x y) 435 436 putStrLn "\n============ Labelled.AdjacencyMap.reflexiveClosure ============" 437 test "reflexiveClosure empty == empty" $ 438 reflexiveClosure empty == (empty :: LAD) 439 440 test "reflexiveClosure (vertex x) == edge one x x" $ \x -> 441 reflexiveClosure (vertex x) == (edge one x x :: LAD) 442 443 test "reflexiveClosure (edge e x x) == edge one x x" $ \e x -> 444 reflexiveClosure (edge e x x) == (edge one x x :: LAD) 445 446 test "reflexiveClosure (edge e x y) == edges [(one,x,x), (e,x,y), (one,y,y)]" $ \e x y -> 447 reflexiveClosure (edge e x y) == (edges [(one,x,x), (e,x,y), (one,y,y)] :: LAD) 448 449 test "reflexiveClosure . reflexiveClosure == reflexiveClosure" $ size10 $ \x -> 450 (reflexiveClosure . reflexiveClosure) x == reflexiveClosure (x :: LAD) 451 452 putStrLn "\n============ Labelled.AdjacencyMap.symmetricClosure ============" 453 test "symmetricClosure empty == empty" $ 454 symmetricClosure empty == (empty :: LAD) 455 456 test "symmetricClosure (vertex x) == vertex x" $ \x -> 457 symmetricClosure (vertex x) == (vertex x :: LAD) 458 459 test "symmetricClosure (edge e x y) == edges [(e,x,y), (e,y,x)]" $ \e x y -> 460 symmetricClosure (edge e x y) == (edges [(e,x,y), (e,y,x)] :: LAD) 461 462 test "symmetricClosure x == overlay x (transpose x)" $ \x -> 463 symmetricClosure x == (overlay x (transpose x) :: LAD) 464 465 test "symmetricClosure . symmetricClosure == symmetricClosure" $ size10 $ \x -> 466 (symmetricClosure . symmetricClosure) x == symmetricClosure (x :: LAD) 467 468 putStrLn "\n============ Labelled.AdjacencyMap.transitiveClosure ============" 469 test "transitiveClosure empty == empty" $ 470 transitiveClosure empty == (empty :: LAD) 471 472 test "transitiveClosure (vertex x) == vertex x" $ \x -> 473 transitiveClosure (vertex x) == (vertex x :: LAD) 474 475 test "transitiveClosure (edge e x y) == edge e x y" $ \e x y -> 476 transitiveClosure (edge e x y) == (edge e x y :: LAD) 477 478 test "transitiveClosure . transitiveClosure == transitiveClosure" $ size10 $ \x -> 479 (transitiveClosure . transitiveClosure) x == transitiveClosure (x :: LAD) 480