comfort-graph-0.0.5.1: test/Test/Data/Graph/Comfort.hs

-- Do not edit! Automatically created with doctest-extract from src/Data/Graph/Comfort.hs
{-# LINE 103 "src/Data/Graph/Comfort.hs" #-}

module Test.Data.Graph.Comfort where

import Test.DocTest.Base
import qualified Test.DocTest.Driver as DocTest

{-# LINE 104 "src/Data/Graph/Comfort.hs" #-}
import     Test.Base

import     qualified Test.Data.Graph.Alternative as GraphAlt
import     qualified Data.Graph.Comfort as Graph
import     qualified Data.Map as Map
import     qualified Data.Set as Set
import     qualified Data.Char as Char
import     Data.Graph.Comfort (Graph, DirEdge(DirEdge), UndirEdge(UndirEdge))
import     Data.Tree (Forest)
import     Data.Map (Map)
import     Data.Tuple.HT (mapSnd)

import     qualified Control.Monad.Trans.Class as MT
import     qualified Control.Monad.Trans.State as MS
import     Control.Applicative (pure)
import     Data.Functor.Identity (Identity(Identity), runIdentity)

import     qualified Test.QuickCheck as QC
import     Test.QuickCheck ((==>), (===))

deleteNodeIfExists     :: Node -> MonoGraph -> MonoGraph
deleteNodeIfExists     n gr =
       maybe gr (const $ Graph.deleteNode n gr) $ Graph.lookupNode n gr

isolated     :: (Graph.Edge e, Ord n) => Graph.Graph e n el nl -> n -> Bool
isolated     gr n = Set.null (Graph.adjacentEdgeSet gr n)

nodeAction     :: (Monad m) => NodeLabel -> MS.StateT NodeLabel m NodeLabel
nodeAction     x = do y <- MS.get; MS.put x; return y

evalTraverseNode     :: NodeLabel -> MonoGraph -> MonoGraph
evalTraverseNode     nl =
       flip MS.evalState nl . Graph.traverseNode nodeAction

edgeAction     :: (Monad m) => EdgeLabel -> MS.StateT EdgeLabel m EdgeLabel
edgeAction     x = MS.modify (x+) >> MS.get

evalTraverseEdge     :: EdgeLabel -> MonoGraph -> MonoGraph
evalTraverseEdge     el =
       flip MS.evalState el . Graph.traverseEdge edgeAction

evalTraverse     :: NodeLabel -> EdgeLabel -> MonoGraph -> MonoGraph
evalTraverse     nl el =
       flip MS.evalState el . flip MS.evalStateT nl .
       Graph.traverse nodeAction (MT.lift . edgeAction)


(*-*)     :: n -> n -> UndirEdge n
(*-*)     = UndirEdge

(*->)     :: n -> n -> DirEdge n
(*->)     = DirEdge

unlabGraph     ::
       (Graph.Edge edge, Ord (edge node), Ord node) =>
       [node] -> [edge node] -> Graph edge node () ()
unlabGraph     ns es =
       let label = map (flip (,) ()) in
       Graph.fromMap
          (Map.fromList $ label $ ns ++ map Graph.from es ++ map Graph.to es)
          (Map.fromList $ label es)

addReversedEdges     ::
       (Ord node) => Graph DirEdge node el nl -> Graph DirEdge node el nl
addReversedEdges     gr =
       Graph.fromMap
          (Graph.nodeLabels gr)
          (Map.union
            (Graph.edgeLabels gr)
            (Map.mapKeys (\(Graph.DirEdge f t) -> Graph.DirEdge t f) $
               Graph.edgeLabels gr))

genShuffledGraph     ::
       (Graph.Edge e, Functor e, Ord a) =>
       Graph e a el nl -> QC.Gen (Graph e Int el nl, Map a Int)
genShuffledGraph     gr = do
       shuffledNodes <- QC.shuffle $ Graph.nodes gr
       let nodeMap = Map.fromList $ zip shuffledNodes [(0::Int)..]
       let mapNode n = nodeMap Map.! n
       return (Graph.mapKeys mapNode (fmap mapNode) gr, nodeMap)

test :: DocTest.T ()
test = do
 DocTest.printPrefix "Data.Graph.Comfort:424: "
{-# LINE 424 "src/Data/Graph/Comfort.hs" #-}
 DocTest.property(
{-# LINE 424 "src/Data/Graph/Comfort.hs" #-}
      \(TestGraph gr) -> Graph.isConsistent (Graph.reverse gr)
  )
 DocTest.printPrefix "Data.Graph.Comfort:425: "
{-# LINE 425 "src/Data/Graph/Comfort.hs" #-}
 DocTest.property(
{-# LINE 425 "src/Data/Graph/Comfort.hs" #-}
      \(TestGraph gr) -> Graph.reverse (Graph.reverse gr) === gr
  )
 DocTest.printPrefix "Data.Graph.Comfort:476: "
{-# LINE 476 "src/Data/Graph/Comfort.hs" #-}
 DocTest.property(
{-# LINE 476 "src/Data/Graph/Comfort.hs" #-}
      Graph.isEmpty (Graph.empty :: MonoGraph)
  )
 DocTest.printPrefix "Data.Graph.Comfort:477: "
{-# LINE 477 "src/Data/Graph/Comfort.hs" #-}
 DocTest.property(
{-# LINE 477 "src/Data/Graph/Comfort.hs" #-}
      Graph.isConsistent (Graph.empty :: MonoGraph)
  )
 DocTest.printPrefix "Data.Graph.Comfort:530: "
{-# LINE 530 "src/Data/Graph/Comfort.hs" #-}
 DocTest.property(
{-# LINE 530 "src/Data/Graph/Comfort.hs" #-}
      \(GraphAndEdge gr e) -> Graph.lookupEdge e gr === Map.lookup e (Graph.edgeLabels gr)
  )
 DocTest.printPrefix "Data.Graph.Comfort:548: "
{-# LINE 548 "src/Data/Graph/Comfort.hs" #-}
 DocTest.property(
{-# LINE 548 "src/Data/Graph/Comfort.hs" #-}
      \(TestGraph gr) n -> Graph.lookupNode n gr === Map.lookup n (Graph.nodeLabels gr)
  )
 DocTest.printPrefix "Data.Graph.Comfort:599: "
{-# LINE 599 "src/Data/Graph/Comfort.hs" #-}
 DocTest.property(
{-# LINE 599 "src/Data/Graph/Comfort.hs" #-}
      \(TestGraph gr) n -> Graph.isConsistent $ deleteNodeIfExists n gr
  )
 DocTest.printPrefix "Data.Graph.Comfort:600: "
{-# LINE 600 "src/Data/Graph/Comfort.hs" #-}
 DocTest.property(
{-# LINE 600 "src/Data/Graph/Comfort.hs" #-}
      \(TestGraph gr) n nl -> Graph.deleteNode n (Graph.insertNode n nl gr) === deleteNodeIfExists n gr
  )
 DocTest.printPrefix "Data.Graph.Comfort:601: "
{-# LINE 601 "src/Data/Graph/Comfort.hs" #-}
 DocTest.property(
{-# LINE 601 "src/Data/Graph/Comfort.hs" #-}
      \(TestGraph gr) -> let isolatedNodes = filter (isolated gr) $ Graph.nodes gr in not (null isolatedNodes) ==> QC.forAll (QC.elements isolatedNodes) $ \n nl -> Graph.insertNode n nl gr === Graph.insertNode n nl (Graph.deleteNode n gr)
  )
 DocTest.printPrefix "Data.Graph.Comfort:627: "
{-# LINE 627 "src/Data/Graph/Comfort.hs" #-}
 DocTest.property(
{-# LINE 627 "src/Data/Graph/Comfort.hs" #-}
      \(GraphAndEdge gr e) -> Graph.isConsistent $ Graph.deleteEdge e gr
  )
 DocTest.printPrefix "Data.Graph.Comfort:628: "
{-# LINE 628 "src/Data/Graph/Comfort.hs" #-}
 DocTest.property(
{-# LINE 628 "src/Data/Graph/Comfort.hs" #-}
      \(GraphAndEdge gr e) el -> Graph.deleteEdge e (Graph.insertEdge e el gr) === Graph.deleteEdge e gr
  )
 DocTest.printPrefix "Data.Graph.Comfort:629: "
{-# LINE 629 "src/Data/Graph/Comfort.hs" #-}
 DocTest.property(
{-# LINE 629 "src/Data/Graph/Comfort.hs" #-}
      \(GraphAndEdge gr e) el -> Graph.insertEdge e el gr === Graph.insertEdge e el (Graph.deleteEdge e gr)
  )
 DocTest.printPrefix "Data.Graph.Comfort:640: "
{-# LINE 640 "src/Data/Graph/Comfort.hs" #-}
 DocTest.property(
{-# LINE 640 "src/Data/Graph/Comfort.hs" #-}
      \(GraphAndEdge gr e) -> Graph.filterEdgeWithKey (\ei _ -> e/=ei) gr === Graph.deleteEdge e gr
  )
 DocTest.printPrefix "Data.Graph.Comfort:693: "
{-# LINE 693 "src/Data/Graph/Comfort.hs" #-}
 DocTest.property(
{-# LINE 693 "src/Data/Graph/Comfort.hs" #-}
      \(TestGraph gr) n nl -> Graph.isConsistent $ Graph.insertNode n nl gr
  )
 DocTest.printPrefix "Data.Graph.Comfort:694: "
{-# LINE 694 "src/Data/Graph/Comfort.hs" #-}
 DocTest.property(
{-# LINE 694 "src/Data/Graph/Comfort.hs" #-}
      \(TestGraph gr) n nl -> Graph.lookupNode n (Graph.insertNode n nl gr) === Just nl
  )
 DocTest.printPrefix "Data.Graph.Comfort:706: "
{-# LINE 706 "src/Data/Graph/Comfort.hs" #-}
 DocTest.property(
{-# LINE 706 "src/Data/Graph/Comfort.hs" #-}
      \(GraphAndEdge gr e) el -> Graph.isConsistent $ Graph.insertEdge e el gr
  )
 DocTest.printPrefix "Data.Graph.Comfort:707: "
{-# LINE 707 "src/Data/Graph/Comfort.hs" #-}
 DocTest.property(
{-# LINE 707 "src/Data/Graph/Comfort.hs" #-}
      \(GraphAndEdge gr e) el -> Graph.lookupEdge e (Graph.insertEdge e el gr) === Just el
  )
 DocTest.printPrefix "Data.Graph.Comfort:741: "
{-# LINE 741 "src/Data/Graph/Comfort.hs" #-}
 DocTest.property(
{-# LINE 741 "src/Data/Graph/Comfort.hs" #-}
      \(TestGraph gr) -> gr === Graph.fromMap (Graph.nodeLabels gr) (Graph.edgeLabels gr)
  )
 DocTest.printPrefix "Data.Graph.Comfort:784: "
{-# LINE 784 "src/Data/Graph/Comfort.hs" #-}
 DocTest.property(
{-# LINE 784 "src/Data/Graph/Comfort.hs" #-}
      \(TestGraph gr) -> Graph.mapNode id gr === gr
  )
 DocTest.printPrefix "Data.Graph.Comfort:797: "
{-# LINE 797 "src/Data/Graph/Comfort.hs" #-}
 DocTest.property(
{-# LINE 797 "src/Data/Graph/Comfort.hs" #-}
      \(TestGraph gr) -> Graph.mapEdge id gr === gr
  )
 DocTest.printPrefix "Data.Graph.Comfort:833: "
{-# LINE 833 "src/Data/Graph/Comfort.hs" #-}
 DocTest.property(
{-# LINE 833 "src/Data/Graph/Comfort.hs" #-}
      \(TestGraph gr) nl -> Graph.isConsistent $ evalTraverseNode nl gr
  )
 DocTest.printPrefix "Data.Graph.Comfort:834: "
{-# LINE 834 "src/Data/Graph/Comfort.hs" #-}
 DocTest.property(
{-# LINE 834 "src/Data/Graph/Comfort.hs" #-}
      \(TestGraph gr) -> runIdentity (Graph.traverseNode (Identity . Char.toUpper) gr) === Graph.mapNode Char.toUpper gr
  )
 DocTest.printPrefix "Data.Graph.Comfort:847: "
{-# LINE 847 "src/Data/Graph/Comfort.hs" #-}
 DocTest.property(
{-# LINE 847 "src/Data/Graph/Comfort.hs" #-}
      \(TestGraph gr) el -> Graph.isConsistent $ evalTraverseEdge el gr
  )
 DocTest.printPrefix "Data.Graph.Comfort:848: "
{-# LINE 848 "src/Data/Graph/Comfort.hs" #-}
 DocTest.property(
{-# LINE 848 "src/Data/Graph/Comfort.hs" #-}
      \(TestGraph gr) el -> runIdentity (Graph.traverseEdge (Identity . (el+)) gr) === Graph.mapEdge (el+) gr
  )
 DocTest.printPrefix "Data.Graph.Comfort:859: "
{-# LINE 859 "src/Data/Graph/Comfort.hs" #-}
 DocTest.property(
{-# LINE 859 "src/Data/Graph/Comfort.hs" #-}
      \(TestGraph gr) nl el -> Graph.isConsistent $ evalTraverse nl el gr
  )
 DocTest.printPrefix "Data.Graph.Comfort:860: "
{-# LINE 860 "src/Data/Graph/Comfort.hs" #-}
 DocTest.property(
{-# LINE 860 "src/Data/Graph/Comfort.hs" #-}
      \(TestGraph gr) nl el -> evalTraverse nl el gr === evalTraverseNode nl (evalTraverseEdge el gr)
  )
 DocTest.printPrefix "Data.Graph.Comfort:861: "
{-# LINE 861 "src/Data/Graph/Comfort.hs" #-}
 DocTest.property(
{-# LINE 861 "src/Data/Graph/Comfort.hs" #-}
      \(TestGraph gr) nl el -> evalTraverse nl el gr === evalTraverseEdge el (evalTraverseNode nl gr)
  )
 DocTest.printPrefix "Data.Graph.Comfort:862: "
{-# LINE 862 "src/Data/Graph/Comfort.hs" #-}
 DocTest.property(
{-# LINE 862 "src/Data/Graph/Comfort.hs" #-}
      \(TestGraph gr) nl -> flip MS.evalState nl (Graph.traverseNode nodeAction gr) === flip MS.evalState nl (Graph.traverse nodeAction pure gr)
  )
 DocTest.printPrefix "Data.Graph.Comfort:863: "
{-# LINE 863 "src/Data/Graph/Comfort.hs" #-}
 DocTest.property(
{-# LINE 863 "src/Data/Graph/Comfort.hs" #-}
      \(TestGraph gr) el -> flip MS.evalState el (Graph.traverseEdge edgeAction gr) === flip MS.evalState el (Graph.traverse pure edgeAction gr)
  )
 DocTest.printPrefix "Data.Graph.Comfort:900: "
{-# LINE 900 "src/Data/Graph/Comfort.hs" #-}
 DocTest.example(
{-# LINE 900 "src/Data/Graph/Comfort.hs" #-}
      
   Graph.depthFirstSearch $
   Graph.fromList [(0,'A'),(1,'B')]
      [(Graph.DirEdge 1 0, 23), (Graph.DirEdge 0 (1::Int), 42::Integer)]
  )
  [ExpectedLine [LineChunk "[Node {rootLabel = 0, subForest = [Node {rootLabel = 1, subForest = []}]}]"]]
 DocTest.printPrefix "Data.Graph.Comfort:907: "
{-# LINE 907 "src/Data/Graph/Comfort.hs" #-}
 DocTest.property(
{-# LINE 907 "src/Data/Graph/Comfort.hs" #-}
        
   \(TestGraph gr) ->
   Graph.depthFirstSearch gr === GraphAlt.depthFirstSearch gr
  )
 DocTest.printPrefix "Data.Graph.Comfort:944: "
{-# LINE 944 "src/Data/Graph/Comfort.hs" #-}
 DocTest.example(
{-# LINE 944 "src/Data/Graph/Comfort.hs" #-}
    mapSnd Graph.nodes $ Graph.topologicalSort $ unlabGraph [] ['a'*->'a']
  )
  [ExpectedLine [LineChunk "(\"\",\"a\")"]]
 DocTest.printPrefix "Data.Graph.Comfort:946: "
{-# LINE 946 "src/Data/Graph/Comfort.hs" #-}
 DocTest.example(
{-# LINE 946 "src/Data/Graph/Comfort.hs" #-}
    mapSnd Graph.nodes $ Graph.topologicalSort $ unlabGraph [] ['a'*->'h', 'a'*->'p', 'g'*->'r', 'p'*->'h', 'r'*->'a']
  )
  [ExpectedLine [LineChunk "(\"graph\",\"\")"]]
 DocTest.printPrefix "Data.Graph.Comfort:948: "
{-# LINE 948 "src/Data/Graph/Comfort.hs" #-}
 DocTest.example(
{-# LINE 948 "src/Data/Graph/Comfort.hs" #-}
    mapSnd Graph.nodes $ Graph.topologicalSort $ unlabGraph [] ['h'*->'a', 'a'*->'p', 'g'*->'r', 'p'*->'h', 'r'*->'a']
  )
  [ExpectedLine [LineChunk "(\"gr\",\"ahp\")"]]
 DocTest.printPrefix "Data.Graph.Comfort:971: "
{-# LINE 971 "src/Data/Graph/Comfort.hs" #-}
 DocTest.example(
{-# LINE 971 "src/Data/Graph/Comfort.hs" #-}
    map Graph.nodes $ Graph.components $ unlabGraph ['d'] ['a'*->'p', 'g'*->'r', 'p'*->'h']
  )
  [ExpectedLine [LineChunk "[\"ahp\",\"d\",\"gr\"]"]]
 DocTest.printPrefix "Data.Graph.Comfort:973: "
{-# LINE 973 "src/Data/Graph/Comfort.hs" #-}
 DocTest.example(
{-# LINE 973 "src/Data/Graph/Comfort.hs" #-}
    map Graph.nodes $ Graph.components $ unlabGraph ['d'] ['a'*-*'p', 'g'*-*'r', 'p'*-*'h']
  )
  [ExpectedLine [LineChunk "[\"ahp\",\"d\",\"gr\"]"]]
 DocTest.printPrefix "Data.Graph.Comfort:1018: "
{-# LINE 1018 "src/Data/Graph/Comfort.hs" #-}
 DocTest.example(
{-# LINE 1018 "src/Data/Graph/Comfort.hs" #-}
      
   Graph.stronglyConnectedComponents $
   Graph.fromList [(0,'A'),(1,'B')] [(Graph.DirEdge 0 (1::Int),42::Integer)]
  )
  [ExpectedLine [LineChunk "[fromList [0],fromList [1]]"]]
 DocTest.printPrefix "Data.Graph.Comfort:1024: "
{-# LINE 1024 "src/Data/Graph/Comfort.hs" #-}
 DocTest.example(
{-# LINE 1024 "src/Data/Graph/Comfort.hs" #-}
    map Set.toAscList $ Graph.stronglyConnectedComponents $ unlabGraph ['d'] ['g'*->'r', 'r'*->'a', 'a'*->'g', 'a'*->'p', 'p'*->'h', 'h'*->'p']
  )
  [ExpectedLine [LineChunk "[\"agr\",\"d\",\"hp\"]"]]
 DocTest.printPrefix "Data.Graph.Comfort:1030: "
{-# LINE 1030 "src/Data/Graph/Comfort.hs" #-}
 DocTest.property(
{-# LINE 1030 "src/Data/Graph/Comfort.hs" #-}
        
   \(TestGraph gr) ->

   Set.fromList (Graph.stronglyConnectedComponentsNE gr)
   ===
   Set.fromList (GraphAlt.stronglyConnectedComponents gr)
  )
 DocTest.printPrefix "Data.Graph.Comfort:1041: "
{-# LINE 1041 "src/Data/Graph/Comfort.hs" #-}
 DocTest.property(
{-# LINE 1041 "src/Data/Graph/Comfort.hs" #-}
        
   \forest ->
   let gr = Graph.fromForest (forest :: Forest Char) in
   all (\comp -> Set.size comp == 1) $ Graph.stronglyConnectedComponents gr
  )
 DocTest.printPrefix "Data.Graph.Comfort:1047: "
{-# LINE 1047 "src/Data/Graph/Comfort.hs" #-}
 DocTest.property(
{-# LINE 1047 "src/Data/Graph/Comfort.hs" #-}
        
   \forest -> let gr = Graph.fromForest (forest :: Forest Char) in
   QC.forAll (genShuffledGraph gr) $ \(shuffled, _nodeMap) ->

   all (\comp -> Set.size comp == 1) $
   Graph.stronglyConnectedComponents shuffled
  )
 DocTest.printPrefix "Data.Graph.Comfort:1058: "
{-# LINE 1058 "src/Data/Graph/Comfort.hs" #-}
 DocTest.property(
{-# LINE 1058 "src/Data/Graph/Comfort.hs" #-}
        
   \(TestGraph gr) ->
   QC.forAll (genShuffledGraph gr) $ \(shuffled, nodeMap) ->

   Set.fromList
      (map (Set.map (nodeMap Map.!)) $ Graph.stronglyConnectedComponents gr)
   ===
   Set.fromList (Graph.stronglyConnectedComponents shuffled)
  )
 DocTest.printPrefix "Data.Graph.Comfort:1072: "
{-# LINE 1072 "src/Data/Graph/Comfort.hs" #-}
 DocTest.property(
{-# LINE 1072 "src/Data/Graph/Comfort.hs" #-}
        
   \(TestGraph gr) ->
   Set.fromList (map Graph.nodeSet (Graph.components gr))
   ===
   Set.fromList (Graph.stronglyConnectedComponents (addReversedEdges gr))
  )