{-# LANGUAGE ViewPatterns #-}
-----------------------------------------------------------------------------
-- |
-- Module     : Algebra.Graph.Test.Labelled.AdjacencyMap
-- Copyright  : (c) Andrey Mokhov 2016-2022
-- License    : MIT (see the file LICENSE)
-- Maintainer : andrey.mokhov@gmail.com
-- Stability  : experimental
--
-- Testsuite for "Algebra.Graph.Labelled.AdjacencyMap".
-----------------------------------------------------------------------------
module Algebra.Graph.Test.Labelled.AdjacencyMap (
    -- * Testsuite
    testLabelledAdjacencyMap
    ) where

import Data.Monoid (Any, Sum (..))

import Algebra.Graph.Label
import Algebra.Graph.Labelled.AdjacencyMap
import Algebra.Graph.Test
import Algebra.Graph.Test.API (toIntAPI, labelledAdjacencyMapAPI)
import Algebra.Graph.Test.Generic
import Algebra.Graph.ToGraph (reachable)

import qualified Algebra.Graph.AdjacencyMap as AM
import qualified Data.Map                   as Map
import qualified Data.Set                   as Set

tPoly :: Testsuite (AdjacencyMap Any) Ord
tPoly = ("Labelled.AdjacencyMap.", labelledAdjacencyMapAPI)

t :: TestsuiteInt (AdjacencyMap Any)
t = fmap toIntAPI tPoly

type S = Sum Int
type D = Distance Int

type LAI = AdjacencyMap Any Int
type LAS = AdjacencyMap S   Int
type LAD = AdjacencyMap D   Int

testLabelledAdjacencyMap :: IO ()
testLabelledAdjacencyMap = do
    putStrLn "\n============ Labelled.AdjacencyMap.consistent ============"
    test "arbitraryLabelledAdjacencyMap" $ \x -> consistent (x           :: LAS)
    test "empty" $                      consistent (empty                :: LAS)
    test "vertex" $ \x               -> consistent (vertex x             :: LAS)
    test "edge" $ \e x y             -> consistent (edge e x y           :: LAS)
    test "overlay" $ \x y            -> consistent (overlay x y          :: LAS)
    test "connect" $ size10 $ \e x y -> consistent (connect e x y        :: LAS)
    test "vertices" $ \xs            -> consistent (vertices xs          :: LAS)
    test "edges" $ \es               -> consistent (edges es             :: LAS)
    test "overlays" $ size10 $ \xs   -> consistent (overlays xs          :: LAS)
    test "fromAdjacencyMaps" $ \xs   -> consistent (fromAdjacencyMaps xs :: LAS)
    test "removeVertex" $ \x y       -> consistent (removeVertex x y     :: LAS)
    test "removeEdge" $ \x y z       -> consistent (removeEdge x y z     :: LAS)
    test "replaceVertex" $ \x y z    -> consistent (replaceVertex x y z  :: LAS)
    test "replaceEdge" $ \e x y z    -> consistent (replaceEdge e x y z  :: LAS)
    test "transpose" $ \x            -> consistent (transpose x          :: LAS)
    test "gmap" $ \(apply -> f) x    -> consistent (gmap f (x :: LAS)    :: LAS)
    test "emap" $ \(apply -> f) x    -> consistent (emap (fmap f::S->S) x:: LAS)
    test "induce" $ \(apply -> p) x  -> consistent (induce p x           :: LAS)

    test "closure"           $ size10 $ \x -> consistent (closure           x :: LAD)
    test "reflexiveClosure"  $ size10 $ \x -> consistent (reflexiveClosure  x :: LAD)
    test "symmetricClosure"  $ size10 $ \x -> consistent (symmetricClosure  x :: LAD)
    test "transitiveClosure" $ size10 $ \x -> consistent (transitiveClosure x :: LAD)

    testEmpty  t
    testVertex t

    putStrLn "\n============ Labelled.AdjacencyMap.edge ============"
    test "edge e    x y              == connect e (vertex x) (vertex y)" $ \(e :: S) (x :: Int) y ->
          edge e    x y              == connect e (vertex x) (vertex y)

    test "edge zero x y              == vertices [x,y]" $ \(x :: Int) y ->
          edge (zero :: S) x y       == vertices [x,y]

    test "hasEdge   x y (edge e x y) == (e /= mempty)" $ \(e :: S) (x :: Int) y ->
          hasEdge   x y (edge e x y) == (e /= mempty)

    test "edgeLabel x y (edge e x y) == e" $ \(e :: S) (x :: Int) y ->
          edgeLabel x y (edge e x y) == e

    test "edgeCount     (edge e x y) == if e == mempty then 0 else 1" $ \(e :: S) (x :: Int) y ->
          edgeCount     (edge e x y) == if e == mempty then 0 else 1

    test "vertexCount   (edge e 1 1) == 1" $ \(e :: S) ->
          vertexCount   (edge e 1 (1 :: Int)) == 1

    test "vertexCount   (edge e 1 2) == 2" $ \(e :: S) ->
          vertexCount   (edge e 1 (2 :: Int)) == 2

    test "x -<e>- y                  == edge e x y" $ \(e :: S) (x :: Int) y ->
          x -<e>- y                  == edge e x y

    testOverlay t

    putStrLn ""
    test "edgeLabel x y $ overlay (edge e x y) (edge zero x y) == e" $ \(e :: S) (x :: Int) y ->
          edgeLabel x y (overlay (edge e x y) (edge zero x y)) == e

    test "edgeLabel x y $ overlay (edge e x y) (edge f    x y) == e <+> f" $ \(e :: S) f (x :: Int) y ->
          edgeLabel x y (overlay (edge e x y) (edge f    x y)) == e <+> f

    putStrLn ""
    test "edgeLabel 1 3 $ transitiveClosure (overlay (edge e 1 2) (edge one 2 3)) == e" $ \(e :: D) ->
          edgeLabel 1 3 (transitiveClosure (overlay (edge e 1 2) (edge one 2 (3 :: Int)))) == e

    test "edgeLabel 1 3 $ transitiveClosure (overlay (edge e 1 2) (edge f   2 3)) == e <.> f" $ \(e :: D) f ->
          edgeLabel 1 3 (transitiveClosure (overlay (edge e 1 2) (edge f   2 (3 :: Int))))== e <.> f

    putStrLn "\n============ Labelled.AdjacencyMap.connect ============"
    test "isEmpty     (connect e x y) == isEmpty   x   && isEmpty   y" $ size10 $ \(e :: S) (x :: LAS) y ->
          isEmpty     (connect e x y) ==(isEmpty   x   && isEmpty   y)

    test "hasVertex z (connect e x y) == hasVertex z x || hasVertex z y" $ size10 $ \(e :: S) (x :: LAS) y z ->
          hasVertex z (connect e x y) ==(hasVertex z x || hasVertex z y)

    test "vertexCount (connect e x y) >= vertexCount x" $ size10 $ \(e :: S) (x :: LAS) y ->
          vertexCount (connect e x y) >= vertexCount x

    test "vertexCount (connect e x y) <= vertexCount x + vertexCount y" $ size10 $ \(e :: S) (x :: LAS) y ->
          vertexCount (connect e x y) <= vertexCount x + vertexCount y

    test "edgeCount   (connect e x y) <= vertexCount x * vertexCount y + edgeCount x + edgeCount y" $ size10 $ \(e :: S) (x :: LAS) y ->
          edgeCount   (connect e x y) <= vertexCount x * vertexCount y + edgeCount x + edgeCount y

    test "vertexCount (connect e 1 2) == 2" $ \(e :: Any) ->
          vertexCount (connect e 1 (2 :: LAI)) == 2

    test "edgeCount   (connect e 1 2) == if e == zero then 0 else 1" $ \(e :: Any) ->
          edgeCount   (connect e 1 (2 :: LAI)) == if e == zero then 0 else 1

    testVertices t

    putStrLn "\n============ Labelled.AdjacencyMap.edges ============"
    test "edges []        == empty" $
          edges []        == (empty :: LAS)

    test "edges [(e,x,y)] == edge e x y" $ \(e :: S) (x :: Int) y ->
          edges [(e,x,y)] == edge e x y

    test "edges           == overlays . map (\\(e, x, y) -> edge e x y)" $ \(es :: [(S, Int, Int)]) ->
          edges es        ==(overlays . map (\(e, x, y) -> edge e x y)) es

    testOverlays t

    putStrLn "\n============ Labelled.AdjacencyMap.fromAdjacencyMaps ============"
    test "fromAdjacencyMaps []                                  == empty" $
          fromAdjacencyMaps []                                  == (empty :: LAS)

    test "fromAdjacencyMaps [(x, Map.empty)]                    == vertex x" $ \(x :: Int) ->
          fromAdjacencyMaps [(x, Map.empty)]                    == (vertex x :: LAS)

    test "fromAdjacencyMaps [(x, Map.singleton y e)]            == if e == zero then vertices [x,y] else edge e x y" $ \(e :: S) (x :: Int) y ->
          fromAdjacencyMaps [(x, Map.singleton y e)]            == if e == zero then vertices [x,y] else edge e x y

    test "overlay (fromAdjacencyMaps xs) (fromAdjacencyMaps ys) == fromAdjacencyMaps (xs ++ ys)" $ \xs ys ->
          overlay (fromAdjacencyMaps xs) (fromAdjacencyMaps ys) == (fromAdjacencyMaps (xs ++ ys) :: LAS)

    putStrLn "\n============ Labelled.AdjacencyMap.isSubgraphOf ============"
    test "isSubgraphOf empty      x     ==  True" $ \(x :: LAS) ->
          isSubgraphOf empty      x     ==  True

    test "isSubgraphOf (vertex x) empty ==  False" $ \(x :: Int) ->
          isSubgraphOf (vertex x)(empty :: LAS)==  False

    test "isSubgraphOf x y              ==> x <= y" $ \(x :: LAD) z ->
        let y = x + z -- Make sure we hit the precondition
        in isSubgraphOf x y             ==> x <= y

    putStrLn "\n============ Labelled.AdjacencyMap.isEmpty ============"
    test "isEmpty empty                         == True" $
          isEmpty empty                         == True

    test "isEmpty (overlay empty empty)         == True" $
          isEmpty (overlay empty empty :: LAS)  == True

    test "isEmpty (vertex x)                    == False" $ \(x :: Int) ->
          isEmpty (vertex x)                    == False

    test "isEmpty (removeVertex x $ vertex x)   == True" $ \(x :: Int) ->
          isEmpty (removeVertex x $ vertex x)   == True

    test "isEmpty (removeEdge x y $ edge e x y) == False" $ \(e :: S) (x :: Int) y ->
          isEmpty (removeEdge x y $ edge e x y) == False

    testHasVertex t

    putStrLn "\n============ Labelled.AdjacencyMap.hasEdge ============"
    test "hasEdge x y empty            == False" $ \(x :: Int) y ->
          hasEdge x y empty            == False

    test "hasEdge x y (vertex z)       == False" $ \(x :: Int) y z ->
          hasEdge x y (vertex z)       == False

    test "hasEdge x y (edge e x y)     == (e /= zero)" $ \(e :: S) (x :: Int) y ->
          hasEdge x y (edge e x y)     == (e /= zero)

    test "hasEdge x y . removeEdge x y == const False" $ \x y (z :: LAS) ->
         (hasEdge x y . removeEdge x y) z == const False z

    test "hasEdge x y                  == not . null . filter (\\(_,ex,ey) -> ex == x && ey == y) . edgeList" $ \x y (z :: LAS) -> do
        (_, u, v) <- elements ((zero, x, y) : edgeList z)
        return $ hasEdge u v z         == (not . null . filter (\(_,ex,ey) -> ex == u && ey == v) . edgeList) z

    putStrLn "\n============ Labelled.AdjacencyMap.edgeLabel ============"
    test "edgeLabel x y empty         == zero" $ \(x :: Int) y ->
          edgeLabel x y empty         == (zero :: S)

    test "edgeLabel x y (vertex z)    == zero" $ \(x :: Int) y z ->
          edgeLabel x y (vertex z)    == (zero :: S)

    test "edgeLabel x y (edge e x y)  == e" $ \(e :: S) (x :: Int) y ->
          edgeLabel x y (edge e x y)  == e

    test "edgeLabel s t (overlay x y) == edgeLabel s t x + edgeLabel s t y" $ \(x :: LAS) y -> do
        z <- arbitrary
        s <- elements ([z] ++ vertexList x ++ vertexList y)
        t <- elements ([z] ++ vertexList x ++ vertexList y)
        return $ edgeLabel s t (overlay x y) == edgeLabel s t x + edgeLabel s t y

    testVertexCount t

    putStrLn "\n============ Labelled.AdjacencyMap.edgeCount ============"
    test "edgeCount empty        == 0" $
          edgeCount empty        == 0

    test "edgeCount (vertex x)   == 0" $ \(x :: Int) ->
          edgeCount (vertex x)   == 0

    test "edgeCount (edge e x y) == if e == zero then 0 else 1" $ \(e :: S) (x :: Int) y ->
          edgeCount (edge e x y) == if e == zero then 0 else 1

    test "edgeCount              == length . edgeList" $ \(x :: LAS) ->
          edgeCount x            == (length . edgeList) x

    testVertexList t

    putStrLn "\n============ Labelled.AdjacencyMap.edgeList ============"
    test "edgeList empty        == []" $
          edgeList (empty :: LAS) == []

    test "edgeList (vertex x)   == []" $ \(x :: Int) ->
          edgeList (vertex x :: LAS) == []

    test "edgeList (edge e x y) == if e == zero then [] else [(e,x,y)]" $ \(e :: S) (x :: Int) y ->
          edgeList (edge e x y) == if e == zero then [] else [(e,x,y)]

    testVertexSet t

    putStrLn "\n============ Labelled.AdjacencyMap.edgeSet ============"
    test "edgeSet empty        == Set.empty" $
          edgeSet (empty :: LAS) == Set.empty

    test "edgeSet (vertex x)   == Set.empty" $ \(x :: Int) ->
          edgeSet (vertex x :: LAS) == Set.empty

    test "edgeSet (edge e x y) == if e == zero then Set.empty else Set.singleton (e,x,y)" $ \(e :: S) (x :: Int) y ->
          edgeSet (edge e x y) == if e == zero then Set.empty else Set.singleton (e,x,y)

    putStrLn "\n============ Labelled.AdjacencyMap.preSet ============"
    test "preSet x empty        == Set.empty" $ \x ->
          preSet x (empty :: LAS) == Set.empty

    test "preSet x (vertex x)   == Set.empty" $ \x ->
          preSet x (vertex x :: LAS) == Set.empty

    test "preSet 1 (edge e 1 2) == Set.empty" $ \e ->
          preSet 1 (edge e 1 2 :: LAS) == Set.empty

    test "preSet y (edge e x y) == if e == zero then Set.empty else Set.fromList [x]" $ \(e :: S) (x :: Int) y ->
          preSet y (edge e x y) == if e == zero then Set.empty else Set.fromList [x]

    putStrLn "\n============ Labelled.AdjacencyMap.postSet ============"
    test "postSet x empty        == Set.empty" $ \x ->
          postSet x (empty :: LAS) == Set.empty

    test "postSet x (vertex x)   == Set.empty" $ \x ->
          postSet x (vertex x :: LAS) == Set.empty

    test "postSet x (edge e x y) == if e == zero then Set.empty else Set.fromList [y]" $ \(e :: S) (x :: Int) y ->
          postSet x (edge e x y) == if e == zero then Set.empty else Set.fromList [y]

    test "postSet 2 (edge e 1 2) == Set.empty" $ \e ->
          postSet 2 (edge e 1 2 :: LAS) == Set.empty

    putStrLn "\n============ Labelled.AdjacencyMap.skeleton ============"
    test "hasEdge x y == hasEdge x y . skeleton" $ \x y (z :: LAS) ->
          hasEdge x y z == (AM.hasEdge x y . skeleton) z

    putStrLn "\n============ Labelled.AdjacencyMap.removeVertex ============"
    test "removeVertex x (vertex x)       == empty" $ \x ->
          removeVertex x (vertex x)       == (empty :: LAS)

    test "removeVertex 1 (vertex 2)       == vertex 2" $
          removeVertex 1 (vertex 2)       == (vertex 2 :: LAS)

    test "removeVertex x (edge e x x)     == empty" $ \(e :: S) (x :: Int) ->
          removeVertex x (edge e x x)     == empty

    test "removeVertex 1 (edge e 1 2)     == vertex 2" $ \(e :: S) ->
          removeVertex 1 (edge e 1 2)     == vertex (2 :: Int)

    test "removeVertex x . removeVertex x == removeVertex x" $ \x (y :: LAS) ->
         (removeVertex x . removeVertex x) y == removeVertex x y

    putStrLn "\n============ Labelled.AdjacencyMap.removeEdge ============"
    test "removeEdge x y (edge e x y)     == vertices [x,y]" $ \(e :: S) (x :: Int) y ->
          removeEdge x y (edge e x y)     == vertices [x,y]

    test "removeEdge x y . removeEdge x y == removeEdge x y" $ \x y (z :: LAS) ->
         (removeEdge x y . removeEdge x y) z == removeEdge x y z

    test "removeEdge x y . removeVertex x == removeVertex x" $ \x y (z :: LAS) ->
         (removeEdge x y . removeVertex x) z == removeVertex x z

    test "removeEdge 1 1 (1 * 1 * 2 * 2)  == 1 * 2 * 2" $
          removeEdge 1 1 (1 * 1 * 2 * 2)  == (1 * 2 * 2 :: LAD)

    test "removeEdge 1 2 (1 * 1 * 2 * 2)  == 1 * 1 + 2 * 2" $
          removeEdge 1 2 (1 * 1 * 2 * 2)  == (1 * 1 + 2 * 2 :: LAD)

    putStrLn "\n============ Labelled.AdjacencyMap.replaceVertex ============"
    test "replaceVertex x x            == id" $ \x y ->
          replaceVertex x x y          == (y :: LAS)

    test "replaceVertex x y (vertex x) == vertex y" $ \x y ->
          replaceVertex x y (vertex x) == (vertex y :: LAS)

    test "replaceVertex x y            == gmap (\\v -> if v == x then y else v)" $ \x y (z :: LAS) ->
          replaceVertex x y z          == gmap (\v -> if v == x then y else v) z

    putStrLn "\n============ Labelled.AdjacencyMap.replaceEdge ============"
    test "replaceEdge e x y z                 == overlay (removeEdge x y z) (edge e x y)" $ \(e :: S) (x :: Int) y z ->
          replaceEdge e x y z                 == overlay (removeEdge x y z) (edge e x y)

    test "replaceEdge e x y (edge f x y)      == edge e x y" $ \(e :: S) f (x :: Int) y ->
          replaceEdge e x y (edge f x y)      == edge e x y

    test "edgeLabel x y (replaceEdge e x y z) == e" $ \(e :: S) (x :: Int) y z ->
          edgeLabel x y (replaceEdge e x y z) == e

    putStrLn "\n============ Labelled.AdjacencyMap.transpose ============"
    test "transpose empty        == empty" $
          transpose empty        == (empty :: LAS)

    test "transpose (vertex x)   == vertex x" $ \x ->
          transpose (vertex x)   == (vertex x :: LAS)

    test "transpose (edge e x y) == edge e y x" $ \e x y ->
          transpose (edge e x y) == (edge e y x :: LAS)

    test "transpose . transpose  == id" $ size10 $ \x ->
         (transpose . transpose) x == (x :: LAS)

    putStrLn "\n============ Labelled.AdjacencyMap.gmap ============"
    test "gmap f empty        == empty" $ \(apply -> f) ->
          gmap f (empty :: LAS) == (empty :: LAS)

    test "gmap f (vertex x)   == vertex (f x)" $ \(apply -> f) x ->
          gmap f (vertex x :: LAS) == (vertex (f x) :: LAS)

    test "gmap f (edge e x y) == edge e (f x) (f y)" $ \(apply -> f) e x y ->
          gmap f (edge e x y :: LAS) == (edge e (f x) (f y) :: LAS)

    test "gmap id             == id" $ \x ->
          gmap id x           == (x :: LAS)

    test "gmap f . gmap g     == gmap (f . g)" $ \(apply -> f) (apply -> g) x ->
         ((gmap f :: LAS -> LAS) . gmap g) (x :: LAS)  == gmap (f . g) x

    -- TODO: We only test homomorphisms @h@ on @Sum Int@, which all happen to be
    -- just linear transformations: @h = (k*)@ for some @k :: Int@. These tests
    -- are therefore rather weak and do not cover the ruch space of possible
    -- monoid homomorphisms. How can we improve this?
    putStrLn "\n============ Labelled.AdjacencyMap.emap ============"
    test "emap h empty           == empty" $ \(k :: S) ->
        let h = (k*)
        in emap h empty          == (empty :: LAS)

    test "emap h (vertex x)      == vertex x" $ \(k :: S) x ->
        let h = (k*)
        in emap h (vertex x)     == (vertex x :: LAS)

    test "emap h (edge e x y)    == edge (h e) x y" $ \(k :: S) e x y ->
        let h = (k*)
        in emap h (edge e x y)   == (edge (h e) x y :: LAS)

    test "emap h (overlay x y)   == overlay (emap h x) (emap h y)" $ \(k :: S) x y ->
        let h = (k*)
        in emap h (overlay x y)  == (overlay (emap h x) (emap h y) :: LAS)

    test "emap h (connect e x y) == connect (h e) (emap h x) (emap h y)" $ \(k :: S) (e :: S) x y ->
        let h = (k*)
        in emap h (connect e x y) == (connect (h e) (emap h x) (emap h y) :: LAS)

    test "emap id                == id" $ \x ->
          emap id x              == (id x :: LAS)

    test "emap g . emap h        == emap (g . h)" $ \(k :: S) (l :: S) x ->
        let h = (k*)
            g = (l*)
        in (emap g . emap h) x   == (emap (g . h) x :: LAS)

    testInduce t
    testInduceJust tPoly

    putStrLn "\n============ Labelled.AdjacencyMap.closure ============"
    test "closure empty         == empty" $
          closure empty         == (empty :: LAD)

    test "closure (vertex x)    == edge one x x" $ \x ->
          closure (vertex x)    == (edge one x x :: LAD)

    test "closure (edge e x x)  == edge one x x" $ \e x ->
          closure (edge e x x)  == (edge one x x :: LAD)

    test "closure (edge e x y)  == edges [(one,x,x), (e,x,y), (one,y,y)]" $ \e x y ->
          closure (edge e x y)  == (edges [(one,x,x), (e,x,y), (one,y,y)] :: LAD)

    test "closure               == reflexiveClosure . transitiveClosure" $ size10 $ \x ->
          closure (x :: LAD)    == (reflexiveClosure . transitiveClosure) x

    test "closure               == transitiveClosure . reflexiveClosure" $ size10 $ \x ->
          closure (x :: LAD)    == (transitiveClosure . reflexiveClosure) x

    test "closure . closure     == closure" $ size10 $ \x ->
         (closure . closure) x  == closure (x :: LAD)

    test "postSet x (closure y) == Set.fromList (reachable y x)" $ size10 $ \(x :: Int) (y :: LAD) ->
          postSet x (closure y) == Set.fromList (reachable y x)

    putStrLn "\n============ Labelled.AdjacencyMap.reflexiveClosure ============"
    test "reflexiveClosure empty              == empty" $
          reflexiveClosure empty              == (empty :: LAD)

    test "reflexiveClosure (vertex x)         == edge one x x" $ \x ->
          reflexiveClosure (vertex x)         == (edge one x x :: LAD)

    test "reflexiveClosure (edge e x x)       == edge one x x" $ \e x ->
          reflexiveClosure (edge e x x)       == (edge one x x :: LAD)

    test "reflexiveClosure (edge e x y)       == edges [(one,x,x), (e,x,y), (one,y,y)]" $ \e x y ->
          reflexiveClosure (edge e x y)       == (edges [(one,x,x), (e,x,y), (one,y,y)] :: LAD)

    test "reflexiveClosure . reflexiveClosure == reflexiveClosure" $ size10 $ \x ->
         (reflexiveClosure . reflexiveClosure) x == reflexiveClosure (x :: LAD)

    putStrLn "\n============ Labelled.AdjacencyMap.symmetricClosure ============"
    test "symmetricClosure empty              == empty" $
          symmetricClosure empty              == (empty :: LAD)

    test "symmetricClosure (vertex x)         == vertex x" $ \x ->
          symmetricClosure (vertex x)         == (vertex x :: LAD)

    test "symmetricClosure (edge e x y)       == edges [(e,x,y), (e,y,x)]" $ \e x y ->
          symmetricClosure (edge e x y)       == (edges [(e,x,y), (e,y,x)] :: LAD)

    test "symmetricClosure x                  == overlay x (transpose x)" $ \x ->
          symmetricClosure x                  == (overlay x (transpose x) :: LAD)

    test "symmetricClosure . symmetricClosure == symmetricClosure" $ size10 $ \x ->
         (symmetricClosure . symmetricClosure) x == symmetricClosure (x :: LAD)

    putStrLn "\n============ Labelled.AdjacencyMap.transitiveClosure ============"
    test "transitiveClosure empty               == empty" $
          transitiveClosure empty               == (empty :: LAD)

    test "transitiveClosure (vertex x)          == vertex x" $ \x ->
          transitiveClosure (vertex x)          == (vertex x :: LAD)

    test "transitiveClosure (edge e x y)        == edge e x y" $ \e x y ->
          transitiveClosure (edge e x y)        == (edge e x y :: LAD)

    test "transitiveClosure . transitiveClosure == transitiveClosure" $ size10 $ \x ->
         (transitiveClosure . transitiveClosure) x == transitiveClosure (x :: LAD)