comfort-graph 0.0.3.3 → 0.0.4
raw patch · 3 files changed
+343/−96 lines, 3 filesdep +doctest-libdep ~containersPVP ok
version bump matches the API change (PVP)
Dependencies added: doctest-lib
Dependency ranges changed: containers
API changes (from Hackage documentation)
+ Data.Graph.Comfort: components :: (Edge edge, Ord node) => Graph edge node edgeLabel nodeLabel -> [Graph edge node edgeLabel nodeLabel]
+ Data.Graph.Comfort: depthFirstSearch :: (Edge edge, Ord node) => Graph edge node edgeLabel nodeLabel -> Forest node
+ Data.Graph.Comfort: stronglyConnectedComponents :: Ord node => Graph DirEdge node edgeLabel nodeLabel -> [Set node]
+ Data.Graph.Comfort: topologicalSort :: (Edge edge, Ord node) => Graph edge node edgeLabel nodeLabel -> ([node], Graph edge node edgeLabel nodeLabel)
Files
- comfort-graph.cabal +4/−2
- src/Data/Graph/Comfort.hs +180/−5
- test/Test/Data/Graph/Comfort.hs +159/−89
comfort-graph.cabal view
@@ -1,5 +1,5 @@ Name: comfort-graph-Version: 0.0.3.3+Version: 0.0.4 Synopsis: Graph structure with type parameters for nodes and edges Description: This graph structure is based on "Data.Map"@@ -36,6 +36,7 @@ For examples see the @linear-circuit@ package and its tests. The @ResistorCube@ test demonstrates non-integer node types and the @Tree@ test demonstrates multigraphs.+ Another application is @cabal-sort@. . Currently the package does not contain any advanced algorithm, just the data structure and some manipulation functions.@@ -59,7 +60,7 @@ Makefile Source-Repository this- Tag: 0.0.3.3+ Tag: 0.0.4 Type: darcs Location: https://hub.darcs.net/thielema/comfort-graph @@ -96,6 +97,7 @@ Test.Data.Graph.Comfort Build-Depends: comfort-graph,+ doctest-lib >=0.1 && <0.2, doctest-exitcode-stdio >=0.0 && <0.1, QuickCheck >=2 && <3, transformers,
src/Data/Graph/Comfort.hs view
@@ -23,7 +23,11 @@ adjacentEdgeSet, adjacentEdges, isLoop, pathExists,+ depthFirstSearch,+ topologicalSort,+ components, isConsistent,+ stronglyConnectedComponents, -- * Manipulate labels mapNode, mapNodeWithKey,@@ -52,19 +56,22 @@ import qualified Data.Graph.Comfort.Map as MapU import qualified Data.Graph.Comfort.TotalMap as TMap +import qualified Control.Monad.Trans.State as MS import Control.Monad.Trans.Identity (IdentityT(IdentityT, runIdentityT))+import Control.Monad (liftM2, when, (=<<))+import Control.Applicative (Applicative, liftA2, liftA3, pure) import Data.Functor.Classes (Eq1(liftEq), Ord1(liftCompare), Show1(liftShowsPrec)) -import qualified Data.Set as Set import qualified Data.Map as Map+import qualified Data.Set as Set+import qualified Data.Tree as Tree import qualified Data.Traversable as Trav import qualified Data.Foldable as Fold-import Control.Monad (liftM2, (=<<))-import Control.Applicative (Applicative, liftA2, liftA3) import Data.Foldable (Foldable, foldMap)-import Data.Set (Set) import Data.Map (Map)+import Data.Set (Set)+import Data.Tree (Tree, Forest) import Data.Monoid (Monoid, mempty, mappend, All(All), getAll, Endo(Endo), appEndo) import Data.Semigroup (Semigroup((<>)), )@@ -72,10 +79,11 @@ import qualified Test.QuickCheck as QC +import qualified Data.List as List import Data.Functor (Functor, fmap) import Data.List (map, any, all, (++)) import Data.String (String)-import Data.Maybe (Maybe)+import Data.Maybe (Maybe(Nothing, Just), catMaybes) import Data.Bool (Bool(False), not, (&&), (||)) import Data.Eq (Eq, (==)) import Data.Ord (Ord, Ordering(LT,GT), (<), (>))@@ -95,6 +103,8 @@ >>> 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.Tuple.HT (mapSnd) >>> >>> import qualified Control.Monad.Trans.Class as MT >>> import qualified Control.Monad.Trans.State as MS@@ -129,6 +139,32 @@ >>> 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)) -} {-@@ -217,6 +253,20 @@ data DirEdge node = DirEdge node node deriving (Eq, Ord, Show) +{- |+Danger:+Do not use the data constructor 'UndirEdge'+because it does not ensure ordering of members.+Use the smart constructor 'undirEdge' instead.++'UndirEdge' is not really an undirected edge.+It is more like a directed edge with a canonical direction.+Working with 'UndirEdge' requires caution.+In @Graph UndirEdge@ 'predecessors' are all edges to lower nodes+with respect to @Ord node@,+whereas 'successors' are all edges to higher nodes.+Thus you get all connection only when merging 'predecessors' and 'successors'.+-} data UndirEdge node = UndirEdge node node deriving (Eq, Ord, Show) @@ -485,9 +535,14 @@ lookupNode :: (Ord n) => n -> Graph e n el nl -> Maybe nl lookupNode n (Graph g) = fmap snd3 $ Map.lookup n g +memberNode :: (Ord n) => n -> Graph e n el nl -> Bool+memberNode n (Graph g) = Map.member n g+ {- | Direct predecessors of a node, i.e. nodes with an outgoing edge to the queried node.++It is a checked error, if the queried node is not contained in the graph. -} predecessors :: (Edge e, Ord n) => Graph e n el nl -> n -> [n] predecessors g n =@@ -497,6 +552,8 @@ {- | Direct successors of a node, i.e. nodes with an incoming edge from the queried node.++It is a checked error, if the queried node is not contained in the graph. -} successors :: (Edge e, Ord n) => Graph e n el nl -> n -> [n] successors g n =@@ -800,6 +857,124 @@ not (isEmpty gr) && (a==dst || (any (go (deleteNode a gr)) $ successors gr a)) in flip go src++depthFirstSearch ::+ (Edge edge, Ord node) =>+ Graph edge node edgeLabel nodeLabel -> Forest node+depthFirstSearch =+ let go = do+ gr <- MS.get+ case nodes gr of+ n:_ -> liftA2 (:) (depthFirstSearchFrom n) go+ [] -> pure []+ in MS.evalState go++depthFirstSearchFrom ::+ (Edge edge, Ord node) =>+ node -> MS.State (Graph edge node edgeLabel nodeLabel) (Tree node)+depthFirstSearchFrom n = do+ 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+ if unvisited+ then fmap Just $ depthFirstSearchFrom succ+ else pure Nothing++{- |+>>> 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']+("graph","")+>>> mapSnd Graph.nodes $ Graph.topologicalSort $ unlabGraph [] ['h'*->'a', 'a'*->'p', 'g'*->'r', 'p'*->'h', 'r'*->'a']+("gr","ahp")+-}+topologicalSort ::+ (Edge edge, Ord node) =>+ Graph edge node edgeLabel nodeLabel ->+ ([node], Graph edge node edgeLabel nodeLabel)+topologicalSort gr =+ let go gr0 startNodes =+ case Set.minView startNodes of+ Nothing -> ([], gr0)+ Just (n,ns) ->+ let gr1 = deleteNode n gr0 in+ mapFst (n :) $+ go gr1 $+ Set.filter+ (List.null . predecessors gr1)+ (Set.fromList $ successors gr0 n)+ `Set.union`+ ns+ in go gr . Map.keysSet . Map.filter (Set.null . fst3) . nodeEdges $ gr++{- |+>>> map Graph.nodes $ Graph.components $ unlabGraph ['d'] ['a'*->'p', 'g'*->'r', 'p'*->'h']+["ahp","d","gr"]+>>> map Graph.nodes $ Graph.components $ unlabGraph ['d'] ['a'*-*'p', 'g'*-*'r', 'p'*-*'h']+["ahp","d","gr"]+-}+components ::+ (Edge edge, Ord node) =>+ Graph edge node edgeLabel nodeLabel ->+ [Graph edge node edgeLabel nodeLabel]+components =+ let go gr0 =+ case nodes gr0 of+ [] -> []+ n:_ ->+ let (comp, remaining) = fetchComponent gr0 n in+ comp : go remaining+ in go++fetchComponent ::+ (Edge edge, Ord node) =>+ Graph edge node edgeLabel nodeLabel -> node ->+ (Graph edge node edgeLabel nodeLabel,+ Graph edge node edgeLabel nodeLabel)+fetchComponent (Graph gr) n =+ let go comp0 gr0 set =+ if Set.null set+ then (Graph comp0, Graph gr0)+ else+ let zone = Map.restrictKeys gr0 set+ remaining = Map.withoutKeys gr0 set+ comp1 = Map.union comp0 zone+ newSet =+ Set.fromList $+ foldMap (map fromWrap . Map.keys . fst3) zone+ +++ foldMap (map toWrap . Map.keys . thd3) zone+ in go comp1 remaining newSet+ in go Map.empty gr (Set.singleton n)+++buildReverseQueue :: Tree node -> [node] -> [node]+buildReverseQueue (Tree.Node n ns) queue =+ n : List.foldl (flip buildReverseQueue) queue ns++{- |+>>> map Set.toAscList $ Graph.stronglyConnectedComponents $ unlabGraph ['d'] ['g'*->'r', 'r'*->'a', 'a'*->'g', 'a'*->'p', 'p'*->'h', 'h'*->'p']+["d","hp","agr"]++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]+stronglyConnectedComponents gr =+ let forest = depthFirstSearch gr+ queue = List.foldl (flip buildReverseQueue) [] forest+ assignComponent root n = do+ assigned <- MS.gets $ Map.member n+ when (not assigned) $ do+ MS.modify $ Map.insert n root+ Fold.mapM_ (assignComponent root) $ predecessors gr n+ transposeMap =+ Map.elems . Map.foldl (Map.unionWith Set.union) Map.empty .+ Map.mapWithKey (\n root -> Map.singleton root $ Set.singleton n)+ in transposeMap $+ MS.execState (Fold.mapM_ (\n -> assignComponent n n) queue) Map.empty+ -- * Wrap utilities
test/Test/Data/Graph/Comfort.hs view
@@ -1,17 +1,20 @@ -- Do not edit! Automatically created with doctest-extract from src/Data/Graph/Comfort.hs-{-# LINE 91 "src/Data/Graph/Comfort.hs" #-}+{-# LINE 99 "src/Data/Graph/Comfort.hs" #-} module Test.Data.Graph.Comfort where +import Test.DocTest.Base import qualified Test.DocTest.Driver as DocTest -{-# LINE 92 "src/Data/Graph/Comfort.hs" #-}+{-# LINE 100 "src/Data/Graph/Comfort.hs" #-} import Test.Base 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.Tuple.HT (mapSnd) import qualified Control.Monad.Trans.Class as MT import qualified Control.Monad.Trans.State as MS@@ -47,150 +50,217 @@ 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))+ test :: DocTest.T () test = do- DocTest.printPrefix "Data.Graph.Comfort:358: "-{-# LINE 358 "src/Data/Graph/Comfort.hs" #-}+ DocTest.printPrefix "Data.Graph.Comfort:408: "+{-# LINE 408 "src/Data/Graph/Comfort.hs" #-} DocTest.property-{-# LINE 358 "src/Data/Graph/Comfort.hs" #-}+{-# LINE 408 "src/Data/Graph/Comfort.hs" #-} (\(TestGraph gr) -> Graph.isConsistent (Graph.reverse gr))- DocTest.printPrefix "Data.Graph.Comfort:359: "-{-# LINE 359 "src/Data/Graph/Comfort.hs" #-}+ DocTest.printPrefix "Data.Graph.Comfort:409: "+{-# LINE 409 "src/Data/Graph/Comfort.hs" #-} DocTest.property-{-# LINE 359 "src/Data/Graph/Comfort.hs" #-}+{-# LINE 409 "src/Data/Graph/Comfort.hs" #-} (\(TestGraph gr) -> Graph.reverse (Graph.reverse gr) == gr)- DocTest.printPrefix "Data.Graph.Comfort:410: "-{-# LINE 410 "src/Data/Graph/Comfort.hs" #-}+ DocTest.printPrefix "Data.Graph.Comfort:460: "+{-# LINE 460 "src/Data/Graph/Comfort.hs" #-} DocTest.property-{-# LINE 410 "src/Data/Graph/Comfort.hs" #-}+{-# LINE 460 "src/Data/Graph/Comfort.hs" #-} (Graph.isEmpty (Graph.empty :: MonoGraph))- DocTest.printPrefix "Data.Graph.Comfort:411: "-{-# LINE 411 "src/Data/Graph/Comfort.hs" #-}+ DocTest.printPrefix "Data.Graph.Comfort:461: "+{-# LINE 461 "src/Data/Graph/Comfort.hs" #-} DocTest.property-{-# LINE 411 "src/Data/Graph/Comfort.hs" #-}+{-# LINE 461 "src/Data/Graph/Comfort.hs" #-} (Graph.isConsistent (Graph.empty :: MonoGraph))- DocTest.printPrefix "Data.Graph.Comfort:465: "-{-# LINE 465 "src/Data/Graph/Comfort.hs" #-}+ DocTest.printPrefix "Data.Graph.Comfort:515: "+{-# LINE 515 "src/Data/Graph/Comfort.hs" #-} DocTest.property-{-# LINE 465 "src/Data/Graph/Comfort.hs" #-}+{-# 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:483: "-{-# LINE 483 "src/Data/Graph/Comfort.hs" #-}+ DocTest.printPrefix "Data.Graph.Comfort:533: "+{-# LINE 533 "src/Data/Graph/Comfort.hs" #-} DocTest.property-{-# LINE 483 "src/Data/Graph/Comfort.hs" #-}+{-# 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:527: "-{-# LINE 527 "src/Data/Graph/Comfort.hs" #-}+ DocTest.printPrefix "Data.Graph.Comfort:584: "+{-# LINE 584 "src/Data/Graph/Comfort.hs" #-} DocTest.property-{-# LINE 527 "src/Data/Graph/Comfort.hs" #-}+{-# LINE 584 "src/Data/Graph/Comfort.hs" #-} (\(TestGraph gr) n -> Graph.isConsistent $ deleteNodeIfExists n gr)- DocTest.printPrefix "Data.Graph.Comfort:528: "-{-# LINE 528 "src/Data/Graph/Comfort.hs" #-}+ DocTest.printPrefix "Data.Graph.Comfort:585: "+{-# LINE 585 "src/Data/Graph/Comfort.hs" #-} DocTest.property-{-# LINE 528 "src/Data/Graph/Comfort.hs" #-}+{-# 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:529: "-{-# LINE 529 "src/Data/Graph/Comfort.hs" #-}+ DocTest.printPrefix "Data.Graph.Comfort:586: "+{-# LINE 586 "src/Data/Graph/Comfort.hs" #-} DocTest.property-{-# LINE 529 "src/Data/Graph/Comfort.hs" #-}+{-# 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:555: "-{-# LINE 555 "src/Data/Graph/Comfort.hs" #-}+ DocTest.printPrefix "Data.Graph.Comfort:612: "+{-# LINE 612 "src/Data/Graph/Comfort.hs" #-} DocTest.property-{-# LINE 555 "src/Data/Graph/Comfort.hs" #-}+{-# LINE 612 "src/Data/Graph/Comfort.hs" #-} (\(GraphAndEdge gr e) -> Graph.isConsistent $ Graph.deleteEdge e gr)- DocTest.printPrefix "Data.Graph.Comfort:556: "-{-# LINE 556 "src/Data/Graph/Comfort.hs" #-}+ DocTest.printPrefix "Data.Graph.Comfort:613: "+{-# LINE 613 "src/Data/Graph/Comfort.hs" #-} DocTest.property-{-# LINE 556 "src/Data/Graph/Comfort.hs" #-}+{-# 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:557: "-{-# LINE 557 "src/Data/Graph/Comfort.hs" #-}+ DocTest.printPrefix "Data.Graph.Comfort:614: "+{-# LINE 614 "src/Data/Graph/Comfort.hs" #-} DocTest.property-{-# LINE 557 "src/Data/Graph/Comfort.hs" #-}+{-# 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:568: "-{-# LINE 568 "src/Data/Graph/Comfort.hs" #-}+ DocTest.printPrefix "Data.Graph.Comfort:625: "+{-# LINE 625 "src/Data/Graph/Comfort.hs" #-} DocTest.property-{-# LINE 568 "src/Data/Graph/Comfort.hs" #-}+{-# 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:621: "-{-# LINE 621 "src/Data/Graph/Comfort.hs" #-}+ DocTest.printPrefix "Data.Graph.Comfort:678: "+{-# LINE 678 "src/Data/Graph/Comfort.hs" #-} DocTest.property-{-# LINE 621 "src/Data/Graph/Comfort.hs" #-}+{-# LINE 678 "src/Data/Graph/Comfort.hs" #-} (\(TestGraph gr) n nl -> Graph.isConsistent $ Graph.insertNode n nl gr)- DocTest.printPrefix "Data.Graph.Comfort:622: "-{-# LINE 622 "src/Data/Graph/Comfort.hs" #-}+ DocTest.printPrefix "Data.Graph.Comfort:679: "+{-# LINE 679 "src/Data/Graph/Comfort.hs" #-} DocTest.property-{-# LINE 622 "src/Data/Graph/Comfort.hs" #-}+{-# 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:634: "-{-# LINE 634 "src/Data/Graph/Comfort.hs" #-}+ DocTest.printPrefix "Data.Graph.Comfort:691: "+{-# LINE 691 "src/Data/Graph/Comfort.hs" #-} DocTest.property-{-# LINE 634 "src/Data/Graph/Comfort.hs" #-}+{-# LINE 691 "src/Data/Graph/Comfort.hs" #-} (\(GraphAndEdge gr e) el -> Graph.isConsistent $ Graph.insertEdge e el gr)- DocTest.printPrefix "Data.Graph.Comfort:635: "-{-# LINE 635 "src/Data/Graph/Comfort.hs" #-}+ DocTest.printPrefix "Data.Graph.Comfort:692: "+{-# LINE 692 "src/Data/Graph/Comfort.hs" #-} DocTest.property-{-# LINE 635 "src/Data/Graph/Comfort.hs" #-}+{-# 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:669: "-{-# LINE 669 "src/Data/Graph/Comfort.hs" #-}+ DocTest.printPrefix "Data.Graph.Comfort:726: "+{-# LINE 726 "src/Data/Graph/Comfort.hs" #-} DocTest.property-{-# LINE 669 "src/Data/Graph/Comfort.hs" #-}+{-# LINE 726 "src/Data/Graph/Comfort.hs" #-} (\(TestGraph gr) -> gr == Graph.fromMap (Graph.nodeLabels gr) (Graph.edgeLabels gr))- DocTest.printPrefix "Data.Graph.Comfort:689: "-{-# LINE 689 "src/Data/Graph/Comfort.hs" #-}+ DocTest.printPrefix "Data.Graph.Comfort:746: "+{-# LINE 746 "src/Data/Graph/Comfort.hs" #-} DocTest.property-{-# LINE 689 "src/Data/Graph/Comfort.hs" #-}+{-# LINE 746 "src/Data/Graph/Comfort.hs" #-} (\(TestGraph gr) -> Graph.mapNode id gr == gr)- DocTest.printPrefix "Data.Graph.Comfort:702: "-{-# LINE 702 "src/Data/Graph/Comfort.hs" #-}+ DocTest.printPrefix "Data.Graph.Comfort:759: "+{-# LINE 759 "src/Data/Graph/Comfort.hs" #-} DocTest.property-{-# LINE 702 "src/Data/Graph/Comfort.hs" #-}+{-# LINE 759 "src/Data/Graph/Comfort.hs" #-} (\(TestGraph gr) -> Graph.mapEdge id gr == gr)- DocTest.printPrefix "Data.Graph.Comfort:738: "-{-# LINE 738 "src/Data/Graph/Comfort.hs" #-}+ DocTest.printPrefix "Data.Graph.Comfort:795: "+{-# LINE 795 "src/Data/Graph/Comfort.hs" #-} DocTest.property-{-# LINE 738 "src/Data/Graph/Comfort.hs" #-}+{-# LINE 795 "src/Data/Graph/Comfort.hs" #-} (\(TestGraph gr) nl -> Graph.isConsistent $ evalTraverseNode nl gr)- DocTest.printPrefix "Data.Graph.Comfort:739: "-{-# LINE 739 "src/Data/Graph/Comfort.hs" #-}+ DocTest.printPrefix "Data.Graph.Comfort:796: "+{-# LINE 796 "src/Data/Graph/Comfort.hs" #-} DocTest.property-{-# LINE 739 "src/Data/Graph/Comfort.hs" #-}+{-# 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:752: "-{-# LINE 752 "src/Data/Graph/Comfort.hs" #-}+ DocTest.printPrefix "Data.Graph.Comfort:809: "+{-# LINE 809 "src/Data/Graph/Comfort.hs" #-} DocTest.property-{-# LINE 752 "src/Data/Graph/Comfort.hs" #-}+{-# LINE 809 "src/Data/Graph/Comfort.hs" #-} (\(TestGraph gr) el -> Graph.isConsistent $ evalTraverseEdge el gr)- DocTest.printPrefix "Data.Graph.Comfort:753: "-{-# LINE 753 "src/Data/Graph/Comfort.hs" #-}+ DocTest.printPrefix "Data.Graph.Comfort:810: "+{-# LINE 810 "src/Data/Graph/Comfort.hs" #-} DocTest.property-{-# LINE 753 "src/Data/Graph/Comfort.hs" #-}+{-# 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:764: "-{-# LINE 764 "src/Data/Graph/Comfort.hs" #-}+ DocTest.printPrefix "Data.Graph.Comfort:821: "+{-# LINE 821 "src/Data/Graph/Comfort.hs" #-} DocTest.property-{-# LINE 764 "src/Data/Graph/Comfort.hs" #-}+{-# LINE 821 "src/Data/Graph/Comfort.hs" #-} (\(TestGraph gr) nl el -> Graph.isConsistent $ evalTraverse nl el gr)- DocTest.printPrefix "Data.Graph.Comfort:765: "-{-# LINE 765 "src/Data/Graph/Comfort.hs" #-}+ DocTest.printPrefix "Data.Graph.Comfort:822: "+{-# LINE 822 "src/Data/Graph/Comfort.hs" #-} DocTest.property-{-# LINE 765 "src/Data/Graph/Comfort.hs" #-}+{-# 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:766: "-{-# LINE 766 "src/Data/Graph/Comfort.hs" #-}+ DocTest.printPrefix "Data.Graph.Comfort:823: "+{-# LINE 823 "src/Data/Graph/Comfort.hs" #-} DocTest.property-{-# LINE 766 "src/Data/Graph/Comfort.hs" #-}+{-# 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:767: "-{-# LINE 767 "src/Data/Graph/Comfort.hs" #-}+ DocTest.printPrefix "Data.Graph.Comfort:824: "+{-# LINE 824 "src/Data/Graph/Comfort.hs" #-} DocTest.property-{-# LINE 767 "src/Data/Graph/Comfort.hs" #-}+{-# 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:768: "-{-# LINE 768 "src/Data/Graph/Comfort.hs" #-}+ DocTest.printPrefix "Data.Graph.Comfort:825: "+{-# LINE 825 "src/Data/Graph/Comfort.hs" #-} DocTest.property-{-# LINE 768 "src/Data/Graph/Comfort.hs" #-}+{-# 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'])+ [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'])+ [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'])+ [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'])+ [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'])+ [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\"]"]]