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