content: {-# LANGUAGE ViewPatterns #-}
  -----------------------------------------------------------------------------
  -- |
  -- Module     : Algebra.Graph.Test.Acyclic.AdjacencyMap
  -- Copyright  : (c) Andrey Mokhov 2016-2025
  -- License    : MIT (see the file LICENSE)
  -- Maintainer : andrey.mokhov@gmail.com
  -- Stability  : experimental
  --
  -- Testsuite for "Algebra.Graph.Acyclic.AdjacencyMap".
  -----------------------------------------------------------------------------
  module Algebra.Graph.Test.Acyclic.AdjacencyMap (testAcyclicAdjacencyMap) where
  
  import Algebra.Graph.Acyclic.AdjacencyMap
  import Algebra.Graph.Test hiding (shrink)
  
  import Data.Bifunctor
  import Data.Tuple
  
  import qualified Algebra.Graph.AdjacencyMap           as AM
  import qualified Algebra.Graph.AdjacencyMap.Algorithm as AM
  import qualified Algebra.Graph.NonEmpty.AdjacencyMap  as NonEmpty
  import qualified Data.Set                             as Set
  import qualified GHC.Exts                             as Exts
  
  type AAI = AdjacencyMap Int
  type AI  = AM.AdjacencyMap Int
  
  -- TODO: Switch to using generic tests.
  testAcyclicAdjacencyMap :: IO ()
  testAcyclicAdjacencyMap = do
      putStrLn "\n============ Acyclic.AdjacencyMap.Show ============"
      test "show empty                == \"empty\"" $
            show (empty :: AAI)       == "empty"
  
      test "show (shrink 1)           == \"vertex 1\"" $
            show (shrink 1 :: AAI)    == "vertex 1"
  
      test "show (shrink $ 1 + 2)     == \"vertices [1,2]\"" $
            show (shrink $ 1 + 2 :: AAI) == "vertices [1,2]"
  
      test "show (shrink $ 1 * 2)     == \"(fromJust . toAcyclic) (edge 1 2)\"" $
            show (shrink $ 1 * 2 :: AAI) == "(fromJust . toAcyclic) (edge 1 2)"
  
      test "show (shrink $ 1 * 2 * 3) == \"(fromJust . toAcyclic) (edges [(1,2),(1,3),(2,3)])\"" $
            show (shrink $ 1 * 2 * 3 :: AAI) == "(fromJust . toAcyclic) (edges [(1,2),(1,3),(2,3)])"
  
      test "show (shrink $ 1 * 2 + 3) == \"(fromJust . toAcyclic) (overlay (vertex 3) (edge 1 2))\"" $
            show (shrink $ 1 * 2 + 3 :: AAI) == "(fromJust . toAcyclic) (overlay (vertex 3) (edge 1 2))"
  
      putStrLn "\n============ Acyclic.AdjacencyMap.fromAcyclic ============"
      test "fromAcyclic empty                == empty" $
            fromAcyclic (empty :: AAI)       == AM.empty
  
      test "fromAcyclic . vertex             == vertex" $ \(x :: Int) ->
           (fromAcyclic . vertex) x          == AM.vertex x
  
      test "fromAcyclic (shrink $ 1 * 3 * 2) == star 1 [2,3]" $
            fromAcyclic (shrink $ 1 * 3 + 2) == 1 * 3 + (2 :: AI)
  
      test "vertexCount . fromAcyclic        == vertexCount" $ \(x :: AAI) ->
           (AM.vertexCount . fromAcyclic) x  == vertexCount x
  
      test "edgeCount   . fromAcyclic        == edgeCount" $ \(x :: AAI) ->
           (AM.edgeCount . fromAcyclic) x    == edgeCount x
  
      test "isAcyclic   . fromAcyclic        == const True" $ \(x :: AAI) ->
           (AM.isAcyclic . fromAcyclic) x    == const True x
  
      putStrLn "\n============ Acyclic.AdjacencyMap.empty ============"
      test "isEmpty     empty == True" $
            isEmpty     (empty :: AAI) == True
  
      test "hasVertex x empty == False" $ \x ->
            hasVertex x (empty :: AAI) == False
  
      test "vertexCount empty == 0" $
            vertexCount (empty :: AAI) == 0
  
      test "edgeCount   empty == 0" $
            edgeCount   (empty :: AAI) == 0
  
      putStrLn "\n============ Acyclic.AdjacencyMap.vertex ============"
      test "isEmpty     (vertex x) == False" $ \(x :: Int) ->
            isEmpty     (vertex x) == False
  
      test "hasVertex x (vertex y) == (x == y)" $ \(x :: Int) y ->
            hasVertex x (vertex y) == (x == y)
  
      test "vertexCount (vertex x) == 1" $ \(x :: Int) ->
            vertexCount (vertex x) == 1
  
      test "edgeCount   (vertex x) == 0" $ \(x :: Int) ->
            edgeCount   (vertex x) == 0
  
      putStrLn "\n============ Acyclic.AdjacencyMap.vertices ============"
      test "vertices []            == empty" $
            vertices []            == (empty :: AAI)
  
      test "vertices [x]           == vertex x" $ \(x :: Int) ->
            vertices [x]           == vertex x
  
      test "hasVertex x . vertices == elem x" $ \(x :: Int) xs ->
           (hasVertex x . vertices) xs == elem x xs
  
      test "vertexCount . vertices == length . nub" $ \(xs :: [Int]) ->
           (vertexCount . vertices) xs == (length . nubOrd) xs
  
      test "vertexSet   . vertices == Set.fromList" $ \(xs :: [Int]) ->
           (vertexSet   . vertices) xs == Set.fromList xs
  
      putStrLn "\n============ Acyclic.AdjacencyMap.union ============"
      test "vertexSet (union x y) == <correct result>" $ \(x :: AAI) (y :: AAI) ->
            vertexSet (union x y) == Set.unions [ Set.map Left  (vertexSet x)
                                                , Set.map Right (vertexSet y) ]
  
      test "edgeSet   (union x y) == <correct result>" $ \(x :: AAI) (y :: AAI) ->
            edgeSet   (union x y) == Set.unions [ Set.map (bimap Left  Left ) (edgeSet x)
                                                , Set.map (bimap Right Right) (edgeSet y) ]
  
      putStrLn "\n============ Acyclic.AdjacencyMap.join ============"
      test "vertexSet (join x y) == <correct result>" $ \(x :: AAI) (y :: AAI) ->
            vertexSet (join x y) == Set.unions [ Set.map Left  (vertexSet x)
                                               , Set.map Right (vertexSet y) ]
  
      test "edgeSet   (join x y) == <correct result>" $ \(x :: AAI) (y :: AAI) ->
            edgeSet   (join x y) == Set.unions
              [ Set.map (bimap Left  Left ) (edgeSet x)
              , Set.map (bimap Right Right) (edgeSet y)
              , Set.map (bimap Left  Right) (Set.cartesianProduct (vertexSet x) (vertexSet y)) ]
  
      putStrLn "\n============ Acyclic.AdjacencyMap.isSubgraphOf ============"
      test "isSubgraphOf empty        x          ==  True" $ \(x :: AAI) ->
            isSubgraphOf empty        x          ==  True
  
      test "isSubgraphOf (vertex x)   empty      ==  False" $ \(x :: Int) ->
            isSubgraphOf (vertex x)   empty      ==  False
  
      test "isSubgraphOf (induce p x) x          ==  True" $ \(x :: AAI) (apply -> p) ->
            isSubgraphOf (induce p x) x          ==  True
  
      test "isSubgraphOf x (transitiveClosure x) ==  True" $ \(x :: AAI) ->
            isSubgraphOf x (transitiveClosure x) ==  True
  
      test "isSubgraphOf x y                     ==> x <= y" $ \(x :: AAI) z ->
          let connect x y = shrink $ fromAcyclic x + fromAcyclic y
              -- TODO: Make the precondition stronger
              y = connect x (vertices z) -- Make sure we hit the precondition
          in isSubgraphOf x y                    ==> x <= y
  
      putStrLn "\n============ Acyclic.AdjacencyMap.isEmpty ============"
      test "isEmpty empty                             == True" $
            isEmpty (empty :: AAI)                    == 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 1 2 $ shrink $ 1 * 2) == False" $
            isEmpty (removeEdge 1 2 $ shrink $ 1 * 2 :: AAI) == False
  
      putStrLn "\n============ Acyclic.AdjacencyMap.hasVertex ============"
      test "hasVertex x empty            == False" $ \(x :: Int) ->
            hasVertex x empty            == False
  
      test "hasVertex x (vertex y)       == (x == y)" $ \(x :: Int) y ->
            hasVertex x (vertex y)       == (x == y)
  
      test "hasVertex x . removeVertex x == const False" $ \(x :: Int) y ->
           (hasVertex x . removeVertex x) y == const False y
  
      putStrLn "\n============ Acyclic.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 1 2 (shrink $ 1 * 2) == True" $
            hasEdge 1 2 (shrink $ 1 * 2 :: AAI)    == True
  
      test "hasEdge x y . removeEdge x y == const False" $ \(x :: Int) y z ->
           (hasEdge x y . removeEdge x y) z == const False z
  
      test "hasEdge x y                  == elem (x,y) . edgeList" $ \(x :: Int) y z -> do
          (u, v) <- elements ((x, y) : edgeList z)
          return $ hasEdge u v z         == elem (u, v) (edgeList z)
  
      putStrLn "\n============ Acyclic.AdjacencyMap.vertexCount ============"
      test "vertexCount empty             ==  0" $
            vertexCount (empty :: AAI)    ==  0
  
      test "vertexCount (vertex x)        ==  1" $ \(x :: Int) ->
            vertexCount (vertex x)        ==  1
  
      test "vertexCount                   ==  length . vertexList" $ \(x :: AAI) ->
            vertexCount x                 ==  (length . vertexList) x
  
      test "vertexCount x < vertexCount y ==> x < y" $ \(x :: AAI) y ->
          if vertexCount x < vertexCount y
          then property (x < y)
          else (vertexCount x > vertexCount y ==> x > y)
  
      putStrLn "\n============ Acyclic.AdjacencyMap.edgeCount ============"
      test "edgeCount empty            == 0" $
            edgeCount (empty :: AAI)   == 0
  
      test "edgeCount (vertex x)       == 0" $ \(x :: Int) ->
            edgeCount (vertex x)       == 0
  
      test "edgeCount (shrink $ 1 * 2) == 1" $
            edgeCount (shrink $ 1 * 2 :: AAI) == 1
  
      test "edgeCount                  == length . edgeList" $ \(x :: AAI) ->
            edgeCount x                == (length . edgeList) x
  
      putStrLn "\n============ Acyclic.AdjacencyMap.vertexList ============"
      test "vertexList empty      == []" $
            vertexList (empty :: AAI) == []
  
      test "vertexList (vertex x) == [x]" $ \(x :: Int) ->
            vertexList (vertex x) == [x]
  
      test "vertexList . vertices == nub . sort" $ \(xs :: [Int]) ->
           (vertexList . vertices) xs == (nubOrd . sort) xs
  
      putStrLn "\n============ Acyclic.AdjacencyMap.edgeList ============"
      test "edgeList empty            == []" $
            edgeList (empty :: AAI)   == []
  
      test "edgeList (vertex x)       == []" $ \(x :: Int) ->
            edgeList (vertex x)       == []
  
      test "edgeList (shrink $ 2 * 1) == [(2,1)]" $
            edgeList (shrink $ 2 * 1 :: AAI) == [(2,1)]
  
      test "edgeList . transpose      == sort . map swap . edgeList" $ \(x :: AAI) ->
           (edgeList . transpose) x   == (sort . map swap . edgeList) x
  
      putStrLn "\n============ Acyclic.AdjacencyMap.adjacencyList ============"
      test "adjacencyList empty            == []" $
            adjacencyList (empty :: AAI)   == []
  
      test "adjacencyList (vertex x)       == [(x, [])]" $ \(x :: Int) ->
            adjacencyList (vertex x)       == [(x, [])]
  
      test "adjacencyList (shrink $ 1 * 2) == [(1, [2]), (2, [])]" $
            adjacencyList (shrink $ 1 * 2 :: AAI) == [(1, [2]), (2, [])]
  
      putStrLn "\n============ Acyclic.AdjacencyMap.vertexSet ============"
      test "vertexSet empty      == Set.empty" $
            vertexSet (empty :: AAI) == Set.empty
  
      test "vertexSet . vertex   == Set.singleton" $ \(x :: Int) ->
           (vertexSet . vertex) x == Set.singleton x
  
      test "vertexSet . vertices == Set.fromList" $ \(xs :: [Int]) ->
           (vertexSet . vertices) xs == Set.fromList xs
  
      putStrLn "\n============ Acyclic.AdjacencyMap.edgeSet ============"
      test "edgeSet empty            == Set.empty" $
            edgeSet (empty :: AAI)   == Set.empty
  
      test "edgeSet (vertex x)       == Set.empty" $ \(x :: Int) ->
            edgeSet (vertex x)       == Set.empty
  
      test "edgeSet (shrink $ 1 * 2) == Set.singleton (1,2)" $
            edgeSet (shrink $ 1 * 2 :: AAI) == Set.singleton (1,2)
  
      putStrLn "\n============ Acyclic.AdjacencyMap.preSet ============"
      test "preSet x empty            == Set.empty" $ \(x :: Int) ->
            preSet x empty            == Set.empty
  
      test "preSet x (vertex x)       == Set.empty" $ \(x :: Int) ->
            preSet x (vertex x)       == Set.empty
  
      test "preSet 1 (shrink $ 1 * 2) == Set.empty" $
            preSet 1 (shrink $ 1 * 2 :: AAI) == Set.empty
  
      test "preSet 2 (shrink $ 1 * 2) == Set.fromList [1]" $
            preSet 2 (shrink $ 1 * 2 :: AAI) == Set.fromList [1]
  
      test "Set.member x . preSet x   == const False" $ \(x :: Int) y ->
           (Set.member x . preSet x) y == const False y
  
      putStrLn "\n============ Acyclic.AdjacencyMap.postSet ============"
      test "postSet x empty            == Set.empty" $ \(x :: Int) ->
            postSet x empty            == Set.empty
  
      test "postSet x (vertex x)       == Set.empty" $ \(x :: Int) ->
            postSet x (vertex x)       == Set.empty
  
      test "postSet 1 (shrink $ 1 * 2) == Set.fromList [2]" $
            postSet 1 (shrink $ 1 * 2 :: AAI) == Set.fromList [2]
  
      test "postSet 2 (shrink $ 1 * 2) == Set.empty" $
            postSet 2 (shrink $ 1 * 2 :: AAI) == Set.empty
  
      test "Set.member x . postSet x   == const False" $ \(x :: Int) y ->
           (Set.member x . postSet x) y == const False y
  
      putStrLn "\n============ Acyclic.AdjacencyMap.removeVertex ============"
      test "removeVertex x (vertex x)       == empty" $ \(x :: Int) ->
            removeVertex x (vertex x)       == empty
  
      test "removeVertex 1 (vertex 2)       == vertex 2" $
            removeVertex 1 (vertex 2 :: AAI) == vertex 2
  
      test "removeVertex 1 (shrink $ 1 * 2) == vertex 2" $
            removeVertex 1 (shrink $ 1 * 2 :: AAI) == vertex 2
  
      test "removeVertex x . removeVertex x == removeVertex x" $ \(x :: Int) y ->
           (removeVertex x . removeVertex x) y == removeVertex x y
  
      putStrLn "\n============ Acyclic.AdjacencyMap.removeEdge ============"
      test "removeEdge 1 2 (shrink $ 1 * 2)     == vertices [1,2]" $
            removeEdge 1 2 (shrink $ 1 * 2 :: AAI) == vertices [1,2]
  
      test "removeEdge x y . removeEdge x y     == removeEdge x y" $ \(x :: Int) y z ->
           (removeEdge x y . removeEdge x y) z  == removeEdge x y z
  
      test "removeEdge x y . removeVertex x     == removeVertex x" $ \(x :: Int) y z ->
           (removeEdge x y . removeVertex x) z  == removeVertex x z
  
      test "removeEdge 1 2 (shrink $ 1 * 2 * 3) == shrink ((1 + 2) * 3)" $
            removeEdge 1 2 (shrink $ 1 * 2 * 3 :: AAI) == shrink ((1 + 2) * 3)
  
      putStrLn "\n============ Acyclic.AdjacencyMap.transpose ============"
      test "transpose empty       == empty" $
            transpose (empty :: AAI) == empty
  
      test "transpose (vertex x)  == vertex x" $ \(x :: Int) ->
            transpose (vertex x)  == vertex x
  
      test "transpose . transpose == id" $ size10 $ \(x :: AAI) ->
           (transpose . transpose) x == id x
  
      test "edgeList . transpose  == sort . map swap . edgeList" $ \(x :: AAI) ->
           (edgeList . transpose) x  == (sort . map swap . edgeList) x
  
      putStrLn "\n============ Acyclic.AdjacencyMap.induce ============"
      test "induce (const True ) x      == x" $ \(x :: AAI) ->
            induce (const True ) x      == x
  
      test "induce (const False) x      == empty" $ \(x :: AAI) ->
            induce (const False) x      == empty
  
      test "induce (/= x)               == removeVertex x" $ \x (y :: AAI) ->
            induce (/= x) y             == removeVertex x y
  
      test "induce p . induce q         == induce (\\x -> p x && q x)" $ \(apply -> p) (apply -> q) (y :: AAI) ->
           (induce p . induce q) y      == induce (\x -> p x && q x) y
  
      test "isSubgraphOf (induce p x) x == True" $ \(apply -> p) (x :: AAI) ->
            isSubgraphOf (induce p x) x == True
  
      putStrLn "\n============ Acyclic.AdjacencyMap.induceJust ============"
      test "induceJust (vertex Nothing) == empty" $
            induceJust (vertex Nothing) == (empty :: AAI)
  
      test "induceJust . vertex . Just  == vertex" $ \(x :: Int) ->
           (induceJust . vertex . Just) x == vertex x
  
      putStrLn "\n============ Acyclic.AdjacencyMap.box ============"
      test "edgeList (box (shrink $ 1 * 2) (shrink $ 10 * 20)) == <correct result>\n" $
            edgeList (box (shrink $ 1 * 2) (shrink $ 10 * 20)) == [ ((1,10), (1,20))
                                                                  , ((1,10), (2,10))
                                                                  , ((1,20), (2,20))
                                                                  , ((2,10), (2 :: Int,20 :: Int)) ]
  
      let gmap f = shrink . AM.gmap f . fromAcyclic
          unit = gmap $ \(a :: Int, ()      ) -> a
          comm = gmap $ \(a :: Int, b :: Int) -> (b, a)
      test "box x y               ~~ box y x" $ size10 $ \x y ->
            comm (box x y)        == box y x
  
      test "box x (vertex ())     ~~ x" $ size10 $ \x ->
       unit(box x (vertex ()))    == (x `asTypeOf` empty)
  
      test "box x empty           ~~ empty" $ size10 $ \x ->
       unit(box x empty)          == empty
  
      let assoc = gmap $ \(a :: Int, (b :: Int, c :: Int)) -> ((a, b), c)
      test "box x (box y z)       ~~ box (box x y) z" $ size10 $ \x y z ->
        assoc (box x (box y z))   == box (box x y) z
  
      test "transpose   (box x y) == box (transpose x) (transpose y)" $ size10 $ \(x :: AAI) (y :: AAI) ->
            transpose   (box x y) == box (transpose x) (transpose y)
  
      test "vertexCount (box x y) == vertexCount x * vertexCount y" $ size10 $ \(x :: AAI) (y :: AAI) ->
            vertexCount (box x y) == vertexCount x * vertexCount y
  
      test "edgeCount   (box x y) <= vertexCount x * edgeCount y + edgeCount x * vertexCount y" $ size10 $ \(x :: AAI) (y :: AAI) ->
            edgeCount   (box x y) <= vertexCount x * edgeCount y + edgeCount x * vertexCount y
  
      putStrLn "\n============ Acyclic.AdjacencyMap.transitiveClosure ============"
      test "transitiveClosure empty                    == empty" $
            transitiveClosure empty                    == (empty :: AAI)
  
      test "transitiveClosure (vertex x)               == vertex x" $ \(x :: Int) ->
            transitiveClosure (vertex x)               == vertex x
  
      test "transitiveClosure (shrink $ 1 * 2 + 2 * 3) == shrink (1 * 2 + 1 * 3 + 2 * 3)" $
            transitiveClosure (shrink $ 1 * 2 + 2 * 3  :: AAI) == shrink (1 * 2 + 1 * 3 + 2 * 3)
  
      test "transitiveClosure . transitiveClosure      == transitiveClosure" $ \(x :: AAI) ->
           (transitiveClosure . transitiveClosure) x   == transitiveClosure x
  
      putStrLn "\n============ Acyclic.AdjacencyMap.topSort ============"
      test "topSort empty                          == []" $
            topSort (empty :: AAI)                 == []
  
      test "topSort (vertex x)                     == [x]" $ \(x :: Int) ->
            topSort (vertex x)                     == [x]
  
      test "topSort (shrink $ 1 * (2 + 4) + 3 * 4) == [1, 2, 3, 4]" $
            topSort (shrink $ 1 * (2 + 4) + 3 * 4) == [1, 2, 3, 4 :: Int]
  
      test "topSort (join x y)                     == fmap Left (topSort x) ++ fmap Right (topSort y)" $ \(x :: AAI) (y :: AAI) ->
            topSort (join x y)                     == fmap Left (topSort x) ++ fmap Right (topSort y)
  
      test "Right . topSort                        == AM.topSort . fromAcyclic" $ \(x :: AAI) ->
            Right (topSort x)                      == AM.topSort (fromAcyclic x)
  
      putStrLn "\n============ Acyclic.AdjacencyMap.scc ============"
      test "           scc empty               == empty" $
                       scc (AM.empty :: AI)    == empty
  
      test "           scc (vertex x)          == vertex (NonEmpty.vertex x)" $ \(x :: Int) ->
                       scc (AM.vertex x)       == vertex (NonEmpty.vertex x)
  
      test "           scc (edge 1 1)          == vertex (NonEmpty.edge 1 1)" $
                       scc (AM.edge 1 1 :: AI) == vertex (NonEmpty.edge 1 1)
  
      test "edgeList $ scc (edge 1 2)          == [ (NonEmpty.vertex 1, NonEmpty.vertex 2) ]" $
            edgeList (scc (AM.edge 1 2 :: AI)) == [ (NonEmpty.vertex 1, NonEmpty.vertex 2) ]
  
      test "edgeList $ scc (3 * 1 * 4 * 1 * 5) == <correct result>" $
            edgeList (scc (3 * 1 * 4 * 1 * 5)) == [ (NonEmpty.vertex 3, NonEmpty.vertex (5 :: Int))
                                                  , (NonEmpty.vertex 3, NonEmpty.clique1 (Exts.fromList [1,4,1]))
                                                  , (NonEmpty.clique1 (Exts.fromList [1,4,1]), NonEmpty.vertex 5) ]
  
      putStrLn "\n============ Acyclic.AdjacencyMap.toAcyclic ============"
      test "toAcyclic (path    [1,2,3]) == Just (shrink $ 1 * 2 + 2 * 3)" $
            toAcyclic (AM.path [1,2,3]) == Just (shrink $ 1 * 2 + 2 * 3 :: AAI)
  
      test "toAcyclic (clique  [3,2,1]) == Just (transpose (shrink $ 1 * 2 * 3))" $
            toAcyclic (AM.clique [3,2,1]) == Just (transpose (shrink $ 1 * 2 * 3 :: AAI))
  
      test "toAcyclic (circuit [1,2,3]) == Nothing" $
            toAcyclic (AM.circuit [1,2,3 :: Int]) == Nothing
  
      test "toAcyclic . fromAcyclic     == Just" $ \(x :: AAI) ->
           (toAcyclic . fromAcyclic) x  == Just x
  
      putStrLn "\n============ Acyclic.AdjacencyMap.toAcyclicOrd ============"
      test "toAcyclicOrd empty       == empty" $
            toAcyclicOrd AM.empty    == (empty :: AAI)
  
      test "toAcyclicOrd . vertex    == vertex" $ \(x :: Int) ->
           (toAcyclicOrd . AM.vertex) x == vertex x
  
      test "toAcyclicOrd (1 + 2)     == shrink (1 + 2)" $
            toAcyclicOrd (1 + 2)     == (shrink $ 1 + 2 :: AAI)
  
      test "toAcyclicOrd (1 * 2)     == shrink (1 * 2)" $
            toAcyclicOrd (1 * 2)     == (shrink $ 1 * 2 :: AAI)
  
      test "toAcyclicOrd (2 * 1)     == shrink (1 + 2)" $
            toAcyclicOrd (2 * 1)     == (shrink $ 1 + 2 :: AAI)
  
      test "toAcyclicOrd (1 * 2 * 1) == shrink (1 * 2)" $
            toAcyclicOrd (1 * 2 * 1) == (shrink $ 1 * 2 :: AAI)
  
      test "toAcyclicOrd (1 * 2 * 3) == shrink (1 * 2 * 3)" $
            toAcyclicOrd (1 * 2 * 3) == (shrink $ 1 * 2 * 3 :: AAI)
  
  
      putStrLn "\n============ Acyclic.AdjacencyMap.shrink ============"
      test "shrink . AM.vertex   == vertex" $ \x ->
            (shrink . AM.vertex) x == (vertex x :: AAI)
  
      test "shrink . AM.vertices == vertices" $ \x ->
            (shrink . AM.vertices) x == (vertices x :: AAI)
  
      test "shrink . fromAcyclic == id" $ \(x :: AAI) ->
            (shrink . fromAcyclic) x == id x
  
      putStrLn "\n============ Acyclic.AdjacencyMap.consistent ============"
      test "Arbitrary"         $ \(x :: AAI)            -> consistent x
      test "empty"             $                           consistent (empty :: AAI)
      test "vertex"            $ \(x :: Int)            -> consistent (vertex x)
      test "vertices"          $ \(xs :: [Int])         -> consistent (vertices xs)
      test "union"             $ \(x :: AAI) (y :: AAI) -> consistent (union x y)
      test "join"              $ \(x :: AAI) (y :: AAI) -> consistent (join x y)
      test "transpose"         $ \(x :: AAI)            -> consistent (transpose x)
      test "box"      $ size10 $ \(x :: AAI) (y :: AAI) -> consistent (box x y)
      test "transitiveClosure" $ \(x :: AAI)            -> consistent (transitiveClosure x)
      test "scc"               $ \(x :: AI)             -> consistent (scc x)
      test "toAcyclic"         $ \(x :: AI)             -> fmap consistent (toAcyclic x) /= Just False
      test "toAcyclicOrd"      $ \(x :: AI)             -> consistent (toAcyclicOrd x)
  