comfort-graph 0.0.4 → 0.0.4.1

raw patch · 3 files changed

+346/−208 lines, 3 filesPVP: major bump suggested

API removals or changes: PVP suggests a major version bump

API changes (from Hackage documentation)

Files

• comfort-graph.cabal +3/−3
• src/Data/Graph/Comfort.hs +79/−23
• test/Test/Data/Graph/Comfort.hs +264/−182

@@ -1,5 +1,5 @@ Name:                comfort-graph-Version:             0.0.4+Version:             0.0.4.1 Synopsis:            Graph structure with type parameters for nodes and edges Description:   This graph structure is based on "Data.Map"@@ -60,7 +60,7 @@   Makefile  Source-Repository this-  Tag:         0.0.4+  Tag:         0.0.4.1   Type:        darcs   Location:    https://hub.darcs.net/thielema/comfort-graph @@ -77,7 +77,7 @@     Data.Graph.Comfort.TotalMap   Build-Depends:     QuickCheck >=2.5 && <3,-    containers >=0.4 && <0.7,+    containers >=0.5.8 && <0.9,     transformers >=0.5 && <0.7,     semigroups >=0.1 && <1.0,     utility-ht >=0.0.10 && <0.1,

@@ -104,6 +104,7 @@ >>> import qualified Data.Set as Set >>> import qualified Data.Char as Char >>> import Data.Graph.Comfort (Graph, DirEdge(DirEdge), UndirEdge(UndirEdge))+>>> import Data.Map (Map) >>> import Data.Tuple.HT (mapSnd) >>> >>> import qualified Control.Monad.Trans.Class as MT@@ -112,7 +113,7 @@ >>> import Data.Functor.Identity (Identity(Identity), runIdentity) >>> >>> import qualified Test.QuickCheck as QC->>> import Test.QuickCheck ((==>))+>>> import Test.QuickCheck ((==>), (===)) >>> >>> deleteNodeIfExists :: Node -> MonoGraph -> MonoGraph >>> deleteNodeIfExists n gr =@@ -165,6 +166,15 @@ >>>         (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) -}  {-@@ -406,7 +416,7 @@  {- | prop> \(TestGraph gr) -> Graph.isConsistent (Graph.reverse gr)-prop> \(TestGraph gr) -> Graph.reverse (Graph.reverse gr) == gr+prop> \(TestGraph gr) -> Graph.reverse (Graph.reverse gr) === gr -} reverse ::    (Reverse e, Ord n) =>@@ -512,7 +522,7 @@ nodeLabels = fmap snd3 . graphMapWrap  {- |-prop> \(GraphAndEdge gr e) -> Graph.lookupEdge e gr == Map.lookup e (Graph.edgeLabels gr)+prop> \(GraphAndEdge gr e) -> Graph.lookupEdge e gr === Map.lookup e (Graph.edgeLabels gr) -} lookupEdge :: (Edge e, Ord n) => e n -> Graph e n el nl -> Maybe el lookupEdge e (Graph g) =@@ -530,7 +540,7 @@ isEmpty = Map.null . graphMapWrap  {- |-prop> \(TestGraph gr) n -> Graph.lookupNode n gr == Map.lookup n (Graph.nodeLabels gr)+prop> \(TestGraph gr) n -> Graph.lookupNode n gr === Map.lookup n (Graph.nodeLabels gr) -} lookupNode :: (Ord n) => n -> Graph e n el nl -> Maybe nl lookupNode n (Graph g) = fmap snd3 $ Map.lookup n g@@ -582,8 +592,8 @@ Node to be deleted must be contained in the graph.  prop> \(TestGraph gr) n -> Graph.isConsistent $ deleteNodeIfExists n gr-prop> \(TestGraph gr) n nl -> Graph.deleteNode n (Graph.insertNode n nl gr) == deleteNodeIfExists n gr-prop> \(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)+prop> \(TestGraph gr) n nl -> Graph.deleteNode n (Graph.insertNode n nl gr) === deleteNodeIfExists n gr+prop> \(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) -} deleteNode ::    (Edge e, Ord n) =>@@ -610,8 +620,8 @@  {- | prop> \(GraphAndEdge gr e) -> Graph.isConsistent $ Graph.deleteEdge e gr-prop> \(GraphAndEdge gr e) el -> Graph.deleteEdge e (Graph.insertEdge e el gr) == Graph.deleteEdge e gr-prop> \(GraphAndEdge gr e) el -> Graph.insertEdge e el gr == Graph.insertEdge e el (Graph.deleteEdge e gr)+prop> \(GraphAndEdge gr e) el -> Graph.deleteEdge e (Graph.insertEdge e el gr) === Graph.deleteEdge e gr+prop> \(GraphAndEdge gr e) el -> Graph.insertEdge e el gr === Graph.insertEdge e el (Graph.deleteEdge e gr) -} deleteEdge ::    (Edge e, Ord n) =>@@ -622,7 +632,7 @@       Map.adjust (mapFst3 $ Map.delete $ wrap e) (to e)  {- |-prop> \(GraphAndEdge gr e) -> Graph.filterEdgeWithKey (\ei _ -> e/=ei) gr == Graph.deleteEdge e gr+prop> \(GraphAndEdge gr e) -> Graph.filterEdgeWithKey (\ei _ -> e/=ei) gr === Graph.deleteEdge e gr -} filterEdgeWithKey ::    (Edge e, Ord n) =>@@ -676,7 +686,7 @@ and you should not rely on this behavior.  prop> \(TestGraph gr) n nl -> Graph.isConsistent $ Graph.insertNode n nl gr-prop> \(TestGraph gr) n nl -> Graph.lookupNode n (Graph.insertNode n nl gr) == Just nl+prop> \(TestGraph gr) n nl -> Graph.lookupNode n (Graph.insertNode n nl gr) === Just nl -} insertNode ::    (Ord n) => n -> nl -> Graph e n el nl -> Graph e n el nl@@ -689,7 +699,7 @@  {- | prop> \(GraphAndEdge gr e) el -> Graph.isConsistent $ Graph.insertEdge e el gr-prop> \(GraphAndEdge gr e) el -> Graph.lookupEdge e (Graph.insertEdge e el gr) == Just el+prop> \(GraphAndEdge gr e) el -> Graph.lookupEdge e (Graph.insertEdge e el gr) === Just el -} insertEdge ::    (Edge e, Ord n) =>@@ -723,7 +733,7 @@    fromMapWrap (Map.fromList ns) $ Map.fromList $ map (mapFst wrap) es  {- |-prop> \(TestGraph gr) -> gr == Graph.fromMap (Graph.nodeLabels gr) (Graph.edgeLabels gr)+prop> \(TestGraph gr) -> gr === Graph.fromMap (Graph.nodeLabels gr) (Graph.edgeLabels gr) -} fromMap ::    (Edge e, Ord n) =>@@ -743,7 +753,7 @@   {- |-prop> \(TestGraph gr) -> Graph.mapNode id gr == gr+prop> \(TestGraph gr) -> Graph.mapNode id gr === gr -} mapNode :: (nl0 -> nl1) -> Graph e n el nl0 -> Graph e n el nl1 mapNode f =@@ -756,7 +766,7 @@    graphMapWrap  {- |-prop> \(TestGraph gr) -> Graph.mapEdge id gr == gr+prop> \(TestGraph gr) -> Graph.mapEdge id gr === gr -} mapEdge :: (el0 -> el1) -> Graph e n el0 nl -> Graph e n el1 nl mapEdge f =@@ -793,7 +803,7 @@ Same restrictions as in 'traverse'.  prop> \(TestGraph gr) nl -> Graph.isConsistent $ evalTraverseNode nl gr-prop> \(TestGraph gr) -> runIdentity (Graph.traverseNode (Identity . Char.toUpper) gr) == Graph.mapNode Char.toUpper gr+prop> \(TestGraph gr) -> runIdentity (Graph.traverseNode (Identity . Char.toUpper) gr) === Graph.mapNode Char.toUpper gr -} traverseNode ::    (Applicative f, Edge e, Ord n) =>@@ -807,7 +817,7 @@ Same restrictions as in 'traverse'.  prop> \(TestGraph gr) el -> Graph.isConsistent $ evalTraverseEdge el gr-prop> \(TestGraph gr) el -> runIdentity (Graph.traverseEdge (Identity . (el+)) gr) == Graph.mapEdge (el+) gr+prop> \(TestGraph gr) el -> runIdentity (Graph.traverseEdge (Identity . (el+)) gr) === Graph.mapEdge (el+) gr -} traverseEdge ::    (Applicative f, Edge e, Ord n) =>@@ -819,10 +829,10 @@ Don't rely on a particular order of traversal!  prop> \(TestGraph gr) nl el -> Graph.isConsistent $ evalTraverse nl el gr-prop> \(TestGraph gr) nl el -> evalTraverse nl el gr == evalTraverseNode nl (evalTraverseEdge el gr)-prop> \(TestGraph gr) nl el -> evalTraverse nl el gr == evalTraverseEdge el (evalTraverseNode nl gr)-prop> \(TestGraph gr) nl -> flip MS.evalState nl (Graph.traverseNode nodeAction gr) == flip MS.evalState nl (Graph.traverse nodeAction pure gr)-prop> \(TestGraph gr) el -> flip MS.evalState el (Graph.traverseEdge edgeAction gr) == flip MS.evalState el (Graph.traverse pure edgeAction gr)+prop> \(TestGraph gr) nl el -> evalTraverse nl el gr === evalTraverseNode nl (evalTraverseEdge el gr)+prop> \(TestGraph gr) nl el -> evalTraverse nl el gr === evalTraverseEdge el (evalTraverseNode nl gr)+prop> \(TestGraph gr) nl -> flip MS.evalState nl (Graph.traverseNode nodeAction gr) === flip MS.evalState nl (Graph.traverse nodeAction pure gr)+prop> \(TestGraph gr) el -> flip MS.evalState el (Graph.traverseEdge edgeAction gr) === flip MS.evalState el (Graph.traverse pure edgeAction gr) -} traverse, _traverseNaive ::    (Applicative f, Edge e, Ord n) =>@@ -858,6 +868,14 @@           (a==dst || (any (go (deleteNode a gr)) $ successors gr a))    in  flip go src +{- |+>>> :{+   Graph.depthFirstSearch $+   Graph.fromList [(0,'A'),(1,'B')]+      [(Graph.DirEdge 1 0, 23), (Graph.DirEdge 0 (1::Int), 42::Integer)]+:}+[Node {rootLabel = 0, subForest = [Node {rootLabel = 1, subForest = []}]}]+-} depthFirstSearch ::    (Edge edge, Ord node) =>    Graph edge node edgeLabel nodeLabel -> Forest node@@ -876,12 +894,20 @@    gr <- MS.get    MS.put $ deleteNode n gr    fmap (Tree.Node n . catMaybes) $ Trav.for (successors gr n) $ \succ -> do-      unvisited <- MS.gets $ memberNode n+      unvisited <- MS.gets $ memberNode succ       if unvisited          then fmap Just $ depthFirstSearchFrom succ          else pure Nothing  {- |+Returns the nodes of the graph in topological order+and the remaining non-sortable graph.+The remaining graph need not be connected+and the connected components need not be strongly connected.+For 'UndirEdge's the topological ordering is the same as the one+induced by @Ord node@.+I leave the @edge@ type variable for user defined edge types, though.+ >>> mapSnd Graph.nodes $ Graph.topologicalSort $ unlabGraph [] ['a'*->'a'] ("","a") >>> mapSnd Graph.nodes $ Graph.topologicalSort $ unlabGraph [] ['a'*->'h', 'a'*->'p', 'g'*->'r', 'p'*->'h', 'r'*->'a']@@ -954,10 +980,40 @@    n : List.foldl (flip buildReverseQueue) queue ns  {- |+Kosaraju's algorithm++>>> :{+   Graph.stronglyConnectedComponents $+   Graph.fromList [(0,'A'),(1,'B')] [(Graph.DirEdge 0 (1::Int),42::Integer)]+:}+[fromList [0],fromList [1]]+ >>> map Set.toAscList $ Graph.stronglyConnectedComponents $ unlabGraph ['d'] ['g'*->'r', 'r'*->'a', 'a'*->'g', 'a'*->'p', 'p'*->'h', 'h'*->'p']-["d","hp","agr"]+["agr","d","hp"] -prop> \(TestGraph gr) -> Set.fromList (map Graph.nodeSet (Graph.components gr)) == Set.fromList (Graph.stronglyConnectedComponents (addReversedEdges gr))++Strongly connected components are invariant under reordering of nodes:++prop> :{+   \(TestGraph gr) ->+   QC.forAll (genShuffledGraph gr) $ \(shuffled, nodeMap) ->++   Set.fromList+      (map (Set.map (nodeMap Map.!)) $ Graph.stronglyConnectedComponents gr)+   ===+   Set.fromList (Graph.stronglyConnectedComponents shuffled)+:}+++Adding reverse edges+turns connected components into strongly connected components:++prop> :{+   \(TestGraph gr) ->+   Set.fromList (map Graph.nodeSet (Graph.components gr))+   ===+   Set.fromList (Graph.stronglyConnectedComponents (addReversedEdges gr))+:} -} stronglyConnectedComponents ::    (Ord node) => Graph DirEdge node edgeLabel nodeLabel -> [Set node]

@@ -14,6 +14,7 @@ import     qualified Data.Set as Set import     qualified Data.Char as Char import     Data.Graph.Comfort (Graph, DirEdge(DirEdge), UndirEdge(UndirEdge))+import     Data.Map (Map) import     Data.Tuple.HT (mapSnd)  import     qualified Control.Monad.Trans.Class as MT@@ -22,7 +23,7 @@ import     Data.Functor.Identity (Identity(Identity), runIdentity)  import     qualified Test.QuickCheck as QC-import     Test.QuickCheck ((==>))+import     Test.QuickCheck ((==>), (===))  deleteNodeIfExists     :: Node -> MonoGraph -> MonoGraph deleteNodeIfExists     n gr =@@ -76,191 +77,272 @@             (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:408: "-{-# LINE 408 "src/Data/Graph/Comfort.hs" #-}- DocTest.property-{-# LINE 408 "src/Data/Graph/Comfort.hs" #-}-     (\(TestGraph gr) -> Graph.isConsistent (Graph.reverse gr))- DocTest.printPrefix "Data.Graph.Comfort:409: "-{-# LINE 409 "src/Data/Graph/Comfort.hs" #-}- DocTest.property-{-# LINE 409 "src/Data/Graph/Comfort.hs" #-}-     (\(TestGraph gr) -> Graph.reverse (Graph.reverse gr) == gr)- DocTest.printPrefix "Data.Graph.Comfort:460: "-{-# LINE 460 "src/Data/Graph/Comfort.hs" #-}- DocTest.property-{-# LINE 460 "src/Data/Graph/Comfort.hs" #-}-     (Graph.isEmpty (Graph.empty :: MonoGraph))- DocTest.printPrefix "Data.Graph.Comfort:461: "-{-# LINE 461 "src/Data/Graph/Comfort.hs" #-}- DocTest.property-{-# LINE 461 "src/Data/Graph/Comfort.hs" #-}-     (Graph.isConsistent (Graph.empty :: MonoGraph))- DocTest.printPrefix "Data.Graph.Comfort:515: "-{-# LINE 515 "src/Data/Graph/Comfort.hs" #-}- DocTest.property-{-# LINE 515 "src/Data/Graph/Comfort.hs" #-}-     (\(GraphAndEdge gr e) -> Graph.lookupEdge e gr == Map.lookup e (Graph.edgeLabels gr))- DocTest.printPrefix "Data.Graph.Comfort:533: "-{-# LINE 533 "src/Data/Graph/Comfort.hs" #-}- DocTest.property-{-# LINE 533 "src/Data/Graph/Comfort.hs" #-}-     (\(TestGraph gr) n -> Graph.lookupNode n gr == Map.lookup n (Graph.nodeLabels gr))- DocTest.printPrefix "Data.Graph.Comfort:584: "-{-# LINE 584 "src/Data/Graph/Comfort.hs" #-}- DocTest.property-{-# LINE 584 "src/Data/Graph/Comfort.hs" #-}-     (\(TestGraph gr) n -> Graph.isConsistent $ deleteNodeIfExists n gr)- DocTest.printPrefix "Data.Graph.Comfort:585: "-{-# LINE 585 "src/Data/Graph/Comfort.hs" #-}- DocTest.property-{-# LINE 585 "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:586: "-{-# LINE 586 "src/Data/Graph/Comfort.hs" #-}- DocTest.property-{-# LINE 586 "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:612: "-{-# LINE 612 "src/Data/Graph/Comfort.hs" #-}- DocTest.property-{-# LINE 612 "src/Data/Graph/Comfort.hs" #-}-     (\(GraphAndEdge gr e) -> Graph.isConsistent $ Graph.deleteEdge e gr)- DocTest.printPrefix "Data.Graph.Comfort:613: "-{-# LINE 613 "src/Data/Graph/Comfort.hs" #-}- DocTest.property-{-# LINE 613 "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:614: "-{-# LINE 614 "src/Data/Graph/Comfort.hs" #-}- DocTest.property-{-# LINE 614 "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:625: "-{-# LINE 625 "src/Data/Graph/Comfort.hs" #-}- DocTest.property-{-# LINE 625 "src/Data/Graph/Comfort.hs" #-}-     (\(GraphAndEdge gr e) -> Graph.filterEdgeWithKey (\ei _ -> e/=ei) gr == Graph.deleteEdge e gr)- DocTest.printPrefix "Data.Graph.Comfort:678: "-{-# LINE 678 "src/Data/Graph/Comfort.hs" #-}- DocTest.property-{-# LINE 678 "src/Data/Graph/Comfort.hs" #-}-     (\(TestGraph gr) n nl -> Graph.isConsistent $ Graph.insertNode n nl gr)- DocTest.printPrefix "Data.Graph.Comfort:679: "-{-# LINE 679 "src/Data/Graph/Comfort.hs" #-}- DocTest.property-{-# LINE 679 "src/Data/Graph/Comfort.hs" #-}-     (\(TestGraph gr) n nl -> Graph.lookupNode n (Graph.insertNode n nl gr) == Just nl)- DocTest.printPrefix "Data.Graph.Comfort:691: "-{-# LINE 691 "src/Data/Graph/Comfort.hs" #-}- DocTest.property-{-# LINE 691 "src/Data/Graph/Comfort.hs" #-}-     (\(GraphAndEdge gr e) el -> Graph.isConsistent $ Graph.insertEdge e el gr)- DocTest.printPrefix "Data.Graph.Comfort:692: "-{-# LINE 692 "src/Data/Graph/Comfort.hs" #-}- DocTest.property-{-# LINE 692 "src/Data/Graph/Comfort.hs" #-}-     (\(GraphAndEdge gr e) el -> Graph.lookupEdge e (Graph.insertEdge e el gr) == Just el)- DocTest.printPrefix "Data.Graph.Comfort:726: "-{-# LINE 726 "src/Data/Graph/Comfort.hs" #-}- DocTest.property-{-# LINE 726 "src/Data/Graph/Comfort.hs" #-}-     (\(TestGraph gr) -> gr == Graph.fromMap (Graph.nodeLabels gr) (Graph.edgeLabels gr))- DocTest.printPrefix "Data.Graph.Comfort:746: "-{-# LINE 746 "src/Data/Graph/Comfort.hs" #-}- DocTest.property-{-# LINE 746 "src/Data/Graph/Comfort.hs" #-}-     (\(TestGraph gr) -> Graph.mapNode id gr == gr)- DocTest.printPrefix "Data.Graph.Comfort:759: "-{-# LINE 759 "src/Data/Graph/Comfort.hs" #-}- DocTest.property-{-# LINE 759 "src/Data/Graph/Comfort.hs" #-}-     (\(TestGraph gr) -> Graph.mapEdge id gr == gr)- DocTest.printPrefix "Data.Graph.Comfort:795: "-{-# LINE 795 "src/Data/Graph/Comfort.hs" #-}- DocTest.property-{-# LINE 795 "src/Data/Graph/Comfort.hs" #-}-     (\(TestGraph gr) nl -> Graph.isConsistent $ evalTraverseNode nl gr)- DocTest.printPrefix "Data.Graph.Comfort:796: "-{-# LINE 796 "src/Data/Graph/Comfort.hs" #-}- DocTest.property-{-# LINE 796 "src/Data/Graph/Comfort.hs" #-}-     (\(TestGraph gr) -> runIdentity (Graph.traverseNode (Identity . Char.toUpper) gr) == Graph.mapNode Char.toUpper gr)- DocTest.printPrefix "Data.Graph.Comfort:809: "-{-# LINE 809 "src/Data/Graph/Comfort.hs" #-}- DocTest.property-{-# LINE 809 "src/Data/Graph/Comfort.hs" #-}-     (\(TestGraph gr) el -> Graph.isConsistent $ evalTraverseEdge el gr)- DocTest.printPrefix "Data.Graph.Comfort:810: "-{-# LINE 810 "src/Data/Graph/Comfort.hs" #-}- DocTest.property-{-# LINE 810 "src/Data/Graph/Comfort.hs" #-}-     (\(TestGraph gr) el -> runIdentity (Graph.traverseEdge (Identity . (el+)) gr) == Graph.mapEdge (el+) gr)- DocTest.printPrefix "Data.Graph.Comfort:821: "-{-# LINE 821 "src/Data/Graph/Comfort.hs" #-}- DocTest.property-{-# LINE 821 "src/Data/Graph/Comfort.hs" #-}-     (\(TestGraph gr) nl el -> Graph.isConsistent $ evalTraverse nl el gr)- DocTest.printPrefix "Data.Graph.Comfort:822: "-{-# LINE 822 "src/Data/Graph/Comfort.hs" #-}- DocTest.property-{-# LINE 822 "src/Data/Graph/Comfort.hs" #-}-     (\(TestGraph gr) nl el -> evalTraverse nl el gr == evalTraverseNode nl (evalTraverseEdge el gr))- DocTest.printPrefix "Data.Graph.Comfort:823: "-{-# LINE 823 "src/Data/Graph/Comfort.hs" #-}- DocTest.property-{-# LINE 823 "src/Data/Graph/Comfort.hs" #-}-     (\(TestGraph gr) nl el -> evalTraverse nl el gr == evalTraverseEdge el (evalTraverseNode nl gr))- DocTest.printPrefix "Data.Graph.Comfort:824: "-{-# LINE 824 "src/Data/Graph/Comfort.hs" #-}- DocTest.property-{-# LINE 824 "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:825: "-{-# LINE 825 "src/Data/Graph/Comfort.hs" #-}- DocTest.property-{-# LINE 825 "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:885: "-{-# LINE 885 "src/Data/Graph/Comfort.hs" #-}- DocTest.example-{-# LINE 885 "src/Data/Graph/Comfort.hs" #-}-   (mapSnd Graph.nodes $ Graph.topologicalSort $ unlabGraph [] ['a'*->'a'])+ DocTest.printPrefix "Data.Graph.Comfort:418: "+{-# LINE 418 "src/Data/Graph/Comfort.hs" #-}+ DocTest.property(+{-# LINE 418 "src/Data/Graph/Comfort.hs" #-}+      \(TestGraph gr) -> Graph.isConsistent (Graph.reverse gr)+  )+ DocTest.printPrefix "Data.Graph.Comfort:419: "+{-# LINE 419 "src/Data/Graph/Comfort.hs" #-}+ DocTest.property(+{-# LINE 419 "src/Data/Graph/Comfort.hs" #-}+      \(TestGraph gr) -> Graph.reverse (Graph.reverse gr) === gr+  )+ DocTest.printPrefix "Data.Graph.Comfort:470: "+{-# LINE 470 "src/Data/Graph/Comfort.hs" #-}+ DocTest.property(+{-# LINE 470 "src/Data/Graph/Comfort.hs" #-}+      Graph.isEmpty (Graph.empty :: MonoGraph)+  )+ DocTest.printPrefix "Data.Graph.Comfort:471: "+{-# LINE 471 "src/Data/Graph/Comfort.hs" #-}+ DocTest.property(+{-# LINE 471 "src/Data/Graph/Comfort.hs" #-}+      Graph.isConsistent (Graph.empty :: MonoGraph)+  )+ DocTest.printPrefix "Data.Graph.Comfort:525: "+{-# LINE 525 "src/Data/Graph/Comfort.hs" #-}+ DocTest.property(+{-# LINE 525 "src/Data/Graph/Comfort.hs" #-}+      \(GraphAndEdge gr e) -> Graph.lookupEdge e gr === Map.lookup e (Graph.edgeLabels gr)+  )+ DocTest.printPrefix "Data.Graph.Comfort:543: "+{-# LINE 543 "src/Data/Graph/Comfort.hs" #-}+ DocTest.property(+{-# LINE 543 "src/Data/Graph/Comfort.hs" #-}+      \(TestGraph gr) n -> Graph.lookupNode n gr === Map.lookup n (Graph.nodeLabels gr)+  )+ DocTest.printPrefix "Data.Graph.Comfort:594: "+{-# LINE 594 "src/Data/Graph/Comfort.hs" #-}+ DocTest.property(+{-# LINE 594 "src/Data/Graph/Comfort.hs" #-}+      \(TestGraph gr) n -> Graph.isConsistent $ deleteNodeIfExists n gr+  )+ DocTest.printPrefix "Data.Graph.Comfort:595: "+{-# LINE 595 "src/Data/Graph/Comfort.hs" #-}+ DocTest.property(+{-# LINE 595 "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:596: "+{-# LINE 596 "src/Data/Graph/Comfort.hs" #-}+ DocTest.property(+{-# LINE 596 "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:622: "+{-# LINE 622 "src/Data/Graph/Comfort.hs" #-}+ DocTest.property(+{-# LINE 622 "src/Data/Graph/Comfort.hs" #-}+      \(GraphAndEdge gr e) -> Graph.isConsistent $ Graph.deleteEdge e gr+  )+ DocTest.printPrefix "Data.Graph.Comfort:623: "+{-# LINE 623 "src/Data/Graph/Comfort.hs" #-}+ DocTest.property(+{-# LINE 623 "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:624: "+{-# LINE 624 "src/Data/Graph/Comfort.hs" #-}+ DocTest.property(+{-# LINE 624 "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:635: "+{-# LINE 635 "src/Data/Graph/Comfort.hs" #-}+ DocTest.property(+{-# LINE 635 "src/Data/Graph/Comfort.hs" #-}+      \(GraphAndEdge gr e) -> Graph.filterEdgeWithKey (\ei _ -> e/=ei) gr === Graph.deleteEdge e gr+  )+ DocTest.printPrefix "Data.Graph.Comfort:688: "+{-# LINE 688 "src/Data/Graph/Comfort.hs" #-}+ DocTest.property(+{-# LINE 688 "src/Data/Graph/Comfort.hs" #-}+      \(TestGraph gr) n nl -> Graph.isConsistent $ Graph.insertNode n nl gr+  )+ DocTest.printPrefix "Data.Graph.Comfort:689: "+{-# LINE 689 "src/Data/Graph/Comfort.hs" #-}+ DocTest.property(+{-# LINE 689 "src/Data/Graph/Comfort.hs" #-}+      \(TestGraph gr) n nl -> Graph.lookupNode n (Graph.insertNode n nl gr) === Just nl+  )+ DocTest.printPrefix "Data.Graph.Comfort:701: "+{-# LINE 701 "src/Data/Graph/Comfort.hs" #-}+ DocTest.property(+{-# LINE 701 "src/Data/Graph/Comfort.hs" #-}+      \(GraphAndEdge gr e) el -> Graph.isConsistent $ Graph.insertEdge e el gr+  )+ DocTest.printPrefix "Data.Graph.Comfort:702: "+{-# LINE 702 "src/Data/Graph/Comfort.hs" #-}+ DocTest.property(+{-# LINE 702 "src/Data/Graph/Comfort.hs" #-}+      \(GraphAndEdge gr e) el -> Graph.lookupEdge e (Graph.insertEdge e el gr) === Just el+  )+ DocTest.printPrefix "Data.Graph.Comfort:736: "+{-# LINE 736 "src/Data/Graph/Comfort.hs" #-}+ DocTest.property(+{-# LINE 736 "src/Data/Graph/Comfort.hs" #-}+      \(TestGraph gr) -> gr === Graph.fromMap (Graph.nodeLabels gr) (Graph.edgeLabels gr)+  )+ DocTest.printPrefix "Data.Graph.Comfort:756: "+{-# LINE 756 "src/Data/Graph/Comfort.hs" #-}+ DocTest.property(+{-# LINE 756 "src/Data/Graph/Comfort.hs" #-}+      \(TestGraph gr) -> Graph.mapNode id gr === gr+  )+ DocTest.printPrefix "Data.Graph.Comfort:769: "+{-# LINE 769 "src/Data/Graph/Comfort.hs" #-}+ DocTest.property(+{-# LINE 769 "src/Data/Graph/Comfort.hs" #-}+      \(TestGraph gr) -> Graph.mapEdge id gr === gr+  )+ DocTest.printPrefix "Data.Graph.Comfort:805: "+{-# LINE 805 "src/Data/Graph/Comfort.hs" #-}+ DocTest.property(+{-# LINE 805 "src/Data/Graph/Comfort.hs" #-}+      \(TestGraph gr) nl -> Graph.isConsistent $ evalTraverseNode nl gr+  )+ DocTest.printPrefix "Data.Graph.Comfort:806: "+{-# LINE 806 "src/Data/Graph/Comfort.hs" #-}+ DocTest.property(+{-# LINE 806 "src/Data/Graph/Comfort.hs" #-}+      \(TestGraph gr) -> runIdentity (Graph.traverseNode (Identity . Char.toUpper) gr) === Graph.mapNode Char.toUpper gr+  )+ DocTest.printPrefix "Data.Graph.Comfort:819: "+{-# LINE 819 "src/Data/Graph/Comfort.hs" #-}+ DocTest.property(+{-# LINE 819 "src/Data/Graph/Comfort.hs" #-}+      \(TestGraph gr) el -> Graph.isConsistent $ evalTraverseEdge el gr+  )+ DocTest.printPrefix "Data.Graph.Comfort:820: "+{-# LINE 820 "src/Data/Graph/Comfort.hs" #-}+ DocTest.property(+{-# LINE 820 "src/Data/Graph/Comfort.hs" #-}+      \(TestGraph gr) el -> runIdentity (Graph.traverseEdge (Identity . (el+)) gr) === Graph.mapEdge (el+) gr+  )+ DocTest.printPrefix "Data.Graph.Comfort:831: "+{-# LINE 831 "src/Data/Graph/Comfort.hs" #-}+ DocTest.property(+{-# LINE 831 "src/Data/Graph/Comfort.hs" #-}+      \(TestGraph gr) nl el -> Graph.isConsistent $ evalTraverse nl el gr+  )+ DocTest.printPrefix "Data.Graph.Comfort:832: "+{-# LINE 832 "src/Data/Graph/Comfort.hs" #-}+ DocTest.property(+{-# LINE 832 "src/Data/Graph/Comfort.hs" #-}+      \(TestGraph gr) nl el -> evalTraverse nl el gr === evalTraverseNode nl (evalTraverseEdge el 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 el -> evalTraverse nl el gr === evalTraverseEdge el (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) nl -> flip MS.evalState nl (Graph.traverseNode nodeAction gr) === flip MS.evalState nl (Graph.traverse nodeAction pure gr)+  )+ DocTest.printPrefix "Data.Graph.Comfort:835: "+{-# LINE 835 "src/Data/Graph/Comfort.hs" #-}+ DocTest.property(+{-# LINE 835 "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:872: "+{-# LINE 872 "src/Data/Graph/Comfort.hs" #-}+ DocTest.example(+{-# LINE 872 "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:911: "+{-# LINE 911 "src/Data/Graph/Comfort.hs" #-}+ DocTest.example(+{-# LINE 911 "src/Data/Graph/Comfort.hs" #-}+    mapSnd Graph.nodes $ Graph.topologicalSort $ unlabGraph [] ['a'*->'a']+  )   [ExpectedLine [LineChunk "(\"\",\"a\")"]]- DocTest.printPrefix "Data.Graph.Comfort:887: "-{-# LINE 887 "src/Data/Graph/Comfort.hs" #-}- DocTest.example-{-# LINE 887 "src/Data/Graph/Comfort.hs" #-}-   (mapSnd Graph.nodes $ Graph.topologicalSort $ unlabGraph [] ['a'*->'h', 'a'*->'p', 'g'*->'r', 'p'*->'h', 'r'*->'a'])+ DocTest.printPrefix "Data.Graph.Comfort:913: "+{-# LINE 913 "src/Data/Graph/Comfort.hs" #-}+ DocTest.example(+{-# LINE 913 "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:889: "-{-# LINE 889 "src/Data/Graph/Comfort.hs" #-}- DocTest.example-{-# LINE 889 "src/Data/Graph/Comfort.hs" #-}-   (mapSnd Graph.nodes $ Graph.topologicalSort $ unlabGraph [] ['h'*->'a', 'a'*->'p', 'g'*->'r', 'p'*->'h', 'r'*->'a'])+ DocTest.printPrefix "Data.Graph.Comfort:915: "+{-# LINE 915 "src/Data/Graph/Comfort.hs" #-}+ DocTest.example(+{-# LINE 915 "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:912: "-{-# LINE 912 "src/Data/Graph/Comfort.hs" #-}- DocTest.example-{-# LINE 912 "src/Data/Graph/Comfort.hs" #-}-   (map Graph.nodes $ Graph.components $ unlabGraph ['d'] ['a'*->'p', 'g'*->'r', 'p'*->'h'])+ DocTest.printPrefix "Data.Graph.Comfort:938: "+{-# LINE 938 "src/Data/Graph/Comfort.hs" #-}+ DocTest.example(+{-# LINE 938 "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:914: "-{-# LINE 914 "src/Data/Graph/Comfort.hs" #-}- DocTest.example-{-# LINE 914 "src/Data/Graph/Comfort.hs" #-}-   (map Graph.nodes $ Graph.components $ unlabGraph ['d'] ['a'*-*'p', 'g'*-*'r', 'p'*-*'h'])+ DocTest.printPrefix "Data.Graph.Comfort:940: "+{-# LINE 940 "src/Data/Graph/Comfort.hs" #-}+ DocTest.example(+{-# LINE 940 "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:960: "-{-# LINE 960 "src/Data/Graph/Comfort.hs" #-}- DocTest.property-{-# LINE 960 "src/Data/Graph/Comfort.hs" #-}-     (\(TestGraph gr) -> Set.fromList (map Graph.nodeSet (Graph.components gr)) == Set.fromList (Graph.stronglyConnectedComponents (addReversedEdges gr)))- DocTest.printPrefix "Data.Graph.Comfort:957: "-{-# LINE 957 "src/Data/Graph/Comfort.hs" #-}- DocTest.example-{-# LINE 957 "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 "[\"d\",\"hp\",\"agr\"]"]]+ DocTest.printPrefix "Data.Graph.Comfort:985: "+{-# LINE 985 "src/Data/Graph/Comfort.hs" #-}+ DocTest.example(+{-# LINE 985 "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:991: "+{-# LINE 991 "src/Data/Graph/Comfort.hs" #-}+ DocTest.example(+{-# LINE 991 "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:997: "+{-# LINE 997 "src/Data/Graph/Comfort.hs" #-}+ DocTest.property(+{-# LINE 997 "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:1011: "+{-# LINE 1011 "src/Data/Graph/Comfort.hs" #-}+ DocTest.property(+{-# LINE 1011 "src/Data/Graph/Comfort.hs" #-}+        +   \(TestGraph gr) ->+   Set.fromList (map Graph.nodeSet (Graph.components gr))+   ===+   Set.fromList (Graph.stronglyConnectedComponents (addReversedEdges gr))+  )