comfort-graph 0.0.4.1 → 0.0.5
raw patch · 5 files changed
+328/−133 lines, 5 filesdep +non-emptydep ~semigroupsPVP ok
version bump matches the API change (PVP)
Dependencies added: non-empty
Dependency ranges changed: semigroups
API changes (from Hackage documentation)
+ Data.Graph.Comfort: fromForest :: Forest a -> Graph DirEdge Int () a
+ Data.Graph.Comfort: fromTree :: Tree a -> Graph DirEdge Int () a
+ Data.Graph.Comfort: stronglyConnectedComponentsNE :: Ord node => Graph DirEdge node edgeLabel nodeLabel -> [T node]
Files
- comfort-graph.cabal +6/−3
- src/Data/Graph/Comfort.hs +74/−11
- src/Data/Graph/Comfort/Map.hs +7/−0
- test/Test/Data/Graph/Alternative.hs +81/−0
- test/Test/Data/Graph/Comfort.hs +160/−119
comfort-graph.cabal view
@@ -1,5 +1,5 @@ Name: comfort-graph-Version: 0.0.4.1+Version: 0.0.5 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.1+ Tag: 0.0.5 Type: darcs Location: https://hub.darcs.net/thielema/comfort-graph @@ -79,7 +79,8 @@ QuickCheck >=2.5 && <3, containers >=0.5.8 && <0.9, transformers >=0.5 && <0.7,- semigroups >=0.1 && <1.0,+ non-empty >=0.3 && <0.4,+ semigroups >=0.1 && <1, utility-ht >=0.0.10 && <0.1, base >=4.5 && <5 Hs-Source-Dirs: src@@ -95,6 +96,7 @@ Other-Modules: Test.Base Test.Data.Graph.Comfort+ Test.Data.Graph.Alternative Build-Depends: comfort-graph, doctest-lib >=0.1 && <0.2,@@ -102,6 +104,7 @@ QuickCheck >=2 && <3, transformers, containers,+ non-empty, utility-ht, base Default-Language: Haskell2010
src/Data/Graph/Comfort.hs view
@@ -10,6 +10,7 @@ -- * Construction empty, fromList, fromMap,+ fromTree, fromForest, -- * Extract large portions of the graph graphMap,@@ -28,6 +29,7 @@ components, isConsistent, stronglyConnectedComponents,+ stronglyConnectedComponentsNE, -- * Manipulate labels mapNode, mapNodeWithKey,@@ -63,6 +65,7 @@ import Data.Functor.Classes (Eq1(liftEq), Ord1(liftCompare), Show1(liftShowsPrec)) +import qualified Data.NonEmpty.Set as NonEmptySet import qualified Data.Map as Map import qualified Data.Set as Set import qualified Data.Tree as Tree@@ -73,7 +76,8 @@ import Data.Set (Set) import Data.Tree (Tree, Forest) import Data.Monoid- (Monoid, mempty, mappend, All(All), getAll, Endo(Endo), appEndo)+ (Monoid, mempty, mappend, mconcat,+ All(All), getAll, Endo(Endo), appEndo) import Data.Semigroup (Semigroup((<>)), ) import Data.Tuple.HT (mapFst, fst3, snd3, thd3, mapFst3, mapThd3) @@ -87,23 +91,25 @@ import Data.Bool (Bool(False), not, (&&), (||)) import Data.Eq (Eq, (==)) import Data.Ord (Ord, Ordering(LT,GT), (<), (>))-import Data.Tuple (uncurry)+import Data.Tuple (snd, uncurry) import Data.Function (flip, (.), ($)) import Data.Int (Int) import Text.Show (Show, ShowS, showParen, showString, showChar, shows, showsPrec) -import Prelude (error)+import Prelude (error, (+)) {- $setup >>> 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) >>>@@ -753,6 +759,29 @@ {- |+Edges point from the root to the leaves.+-}+fromTree :: Tree a -> Graph DirEdge Int () a+fromTree = snd . flip MS.evalState 0 . fromTreeState++fromForest :: Forest a -> Graph DirEdge Int () a+fromForest =+ Fold.foldMap snd . flip MS.evalState 0 . Trav.traverse fromTreeState++fromTreeState :: Tree a -> MS.State Int (Int, Graph DirEdge Int () a)+fromTreeState (Tree.Node root subTrees) = do+ n <- MS.get+ MS.put $ n+1+ (subNodes, subTreeGraphs)+ <- fmap List.unzip $ Trav.traverse fromTreeState subTrees+ pure (n,+ insertEdgeSet+ (Map.fromList $ map (\subNode -> (DirEdge n subNode, ())) subNodes) $+ insertNode n root $ mconcat subTreeGraphs)++++{- | prop> \(TestGraph gr) -> Graph.mapNode id gr === gr -} mapNode :: (nl0 -> nl1) -> Graph e n el nl0 -> Graph e n el nl1@@ -875,6 +904,11 @@ [(Graph.DirEdge 1 0, 23), (Graph.DirEdge 0 (1::Int), 42::Integer)] :} [Node {rootLabel = 0, subForest = [Node {rootLabel = 1, subForest = []}]}]++prop> :{+ \(TestGraph gr) ->+ Graph.depthFirstSearch gr === GraphAlt.depthFirstSearch gr+:} -} depthFirstSearch :: (Edge edge, Ord node) =>@@ -992,6 +1026,34 @@ ["agr","d","hp"] +Compare against alternative implementation:++prop> :{+ \(TestGraph gr) ->++ Set.fromList (Graph.stronglyConnectedComponentsNE gr)+ ===+ Set.fromList (GraphAlt.stronglyConnectedComponents gr)+:}+++Forests have no strongly connected components:++prop> :{+ \forest ->+ let gr = Graph.fromForest (forest :: Forest Char) in+ all (\comp -> Set.size comp == 1) $ Graph.stronglyConnectedComponents gr+:}++prop> :{+ \forest -> let gr = Graph.fromForest (forest :: Forest Char) in+ QC.forAll (genShuffledGraph gr) $ \(shuffled, _nodeMap) ->++ all (\comp -> Set.size comp == 1) $+ Graph.stronglyConnectedComponents shuffled+:}++ Strongly connected components are invariant under reordering of nodes: prop> :{@@ -1017,18 +1079,19 @@ -} stronglyConnectedComponents :: (Ord node) => Graph DirEdge node edgeLabel nodeLabel -> [Set node]-stronglyConnectedComponents gr =- let forest = depthFirstSearch gr- queue = List.foldl (flip buildReverseQueue) [] forest+stronglyConnectedComponents =+ map NonEmptySet.flatten . stronglyConnectedComponentsNE++stronglyConnectedComponentsNE ::+ (Ord node) => Graph DirEdge node edgeLabel nodeLabel -> [NonEmptySet.T node]+stronglyConnectedComponentsNE gr =+ let queue = List.foldl (flip buildReverseQueue) [] $ depthFirstSearch gr 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 $+ Fold.traverse_ (assignComponent root) $ predecessors gr n+ in Map.elems $ MapU.transpose $ MS.execState (Fold.mapM_ (\n -> assignComponent n n) queue) Map.empty
src/Data/Graph/Comfort/Map.hs view
@@ -1,5 +1,6 @@ module Data.Graph.Comfort.Map where +import qualified Data.NonEmpty.Set as NonEmptySet import qualified Data.Set as Set import qualified Data.Map as Map import Data.Set (Set)@@ -100,3 +101,9 @@ compose :: (Ord a, Ord b) => Map b c -> Map a b -> Map a c compose bc ab = Map.mapMaybe (P.flip Map.lookup bc) ab++transpose :: (Ord k, Ord a) => Map k a -> Map a (NonEmptySet.T k)+transpose =+ Map.foldl (Map.unionWith NonEmptySet.union) Map.empty .+ Map.mapWithKey+ (\n root -> Map.singleton root $ NonEmptySet.singleton n)
+ test/Test/Data/Graph/Alternative.hs view
@@ -0,0 +1,81 @@+module Test.Data.Graph.Alternative where++import qualified Data.Graph.Comfort as Graph+import Data.Graph.Comfort (Graph)++import qualified Control.Monad.Trans.State as MS+import Control.Monad (when)+import Control.Applicative (liftA2)++import qualified Data.NonEmpty.Set as NonEmptySet+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 Data.Map (Map)+import Data.Set (Set)+import Data.Tree (Tree, Forest)+import Data.Maybe (catMaybes)+import Data.Tuple.HT (mapFst, mapSnd)++++depthFirstSearch ::+ (Graph.Edge edge, Ord node) =>+ Graph edge node edgeLabel nodeLabel -> Forest node+depthFirstSearch gr =+ let go = do+ unvisited <- MS.get+ case Set.toAscList unvisited of+ n:_ -> liftA2 (:) (depthFirstSearchFrom gr n) go+ [] -> pure []+ in MS.evalState go $ Graph.nodeSet gr++depthFirstSearchFrom ::+ (Graph.Edge edge, Ord node) =>+ Graph edge node edgeLabel nodeLabel ->+ node -> MS.State (Set node) (Tree node)+depthFirstSearchFrom gr n = do+ MS.modify $ Set.delete n+ fmap (Tree.Node n . catMaybes) $+ Trav.for (Graph.successors gr n) $ \suc -> do+ unvisited <- MS.gets $ Set.member suc+ if unvisited+ then fmap Just $ depthFirstSearchFrom gr suc+ else pure Nothing++++transposeMap :: (Ord k, Ord a) => Map k a -> Map a (NonEmptySet.T k)+transposeMap =+ Map.foldl (Map.unionWith NonEmptySet.union) Map.empty .+ Map.mapWithKey+ (\n root -> Map.singleton root $ NonEmptySet.singleton n)++{-+Direct imperative implementation of+<https://en.wikipedia.org/wiki/Kosaraju%27s_algorithm>+-}+stronglyConnectedComponents ::+ (Ord node) =>+ Graph Graph.DirEdge node edgeLabel nodeLabel -> [NonEmptySet.T node]+stronglyConnectedComponents gr =+ let visit u = do+ unvisited <- MS.gets snd+ when (Set.member u unvisited) $ do+ MS.modify (mapSnd $ Set.delete u)+ mapM_ visit $ Graph.successors gr u+ MS.modify (mapFst (u :))+ (queue, []) =+ mapSnd Set.toList $+ MS.execState+ (mapM_ visit $ Graph.nodes gr)+ ([], Graph.nodeSet gr)+ assign root u = do+ assignments <- MS.get+ when (Map.notMember u assignments) $ do+ MS.put $ Map.insert u root assignments+ mapM_ (assign root) $ Graph.predecessors gr u+ in Map.elems $ transposeMap $+ MS.execState (Fold.mapM_ (\n -> assign n n) queue) Map.empty
test/Test/Data/Graph/Comfort.hs view
@@ -1,19 +1,21 @@ -- Do not edit! Automatically created with doctest-extract from src/Data/Graph/Comfort.hs-{-# LINE 99 "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 100 "src/Data/Graph/Comfort.hs" #-}+{-# 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) @@ -88,247 +90,286 @@ test :: DocTest.T () test = do- DocTest.printPrefix "Data.Graph.Comfort:418: "-{-# LINE 418 "src/Data/Graph/Comfort.hs" #-}+ DocTest.printPrefix "Data.Graph.Comfort:424: "+{-# LINE 424 "src/Data/Graph/Comfort.hs" #-} DocTest.property(-{-# LINE 418 "src/Data/Graph/Comfort.hs" #-}+{-# LINE 424 "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.printPrefix "Data.Graph.Comfort:425: "+{-# LINE 425 "src/Data/Graph/Comfort.hs" #-} DocTest.property(-{-# LINE 419 "src/Data/Graph/Comfort.hs" #-}+{-# LINE 425 "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.printPrefix "Data.Graph.Comfort:476: "+{-# LINE 476 "src/Data/Graph/Comfort.hs" #-} DocTest.property(-{-# LINE 470 "src/Data/Graph/Comfort.hs" #-}+{-# LINE 476 "src/Data/Graph/Comfort.hs" #-} Graph.isEmpty (Graph.empty :: MonoGraph) )- DocTest.printPrefix "Data.Graph.Comfort:471: "-{-# LINE 471 "src/Data/Graph/Comfort.hs" #-}+ DocTest.printPrefix "Data.Graph.Comfort:477: "+{-# LINE 477 "src/Data/Graph/Comfort.hs" #-} DocTest.property(-{-# LINE 471 "src/Data/Graph/Comfort.hs" #-}+{-# LINE 477 "src/Data/Graph/Comfort.hs" #-} Graph.isConsistent (Graph.empty :: MonoGraph) )- DocTest.printPrefix "Data.Graph.Comfort:525: "-{-# LINE 525 "src/Data/Graph/Comfort.hs" #-}+ DocTest.printPrefix "Data.Graph.Comfort:531: "+{-# LINE 531 "src/Data/Graph/Comfort.hs" #-} DocTest.property(-{-# LINE 525 "src/Data/Graph/Comfort.hs" #-}+{-# LINE 531 "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.printPrefix "Data.Graph.Comfort:549: "+{-# LINE 549 "src/Data/Graph/Comfort.hs" #-} DocTest.property(-{-# LINE 543 "src/Data/Graph/Comfort.hs" #-}+{-# LINE 549 "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.printPrefix "Data.Graph.Comfort:600: "+{-# LINE 600 "src/Data/Graph/Comfort.hs" #-} DocTest.property(-{-# LINE 594 "src/Data/Graph/Comfort.hs" #-}+{-# LINE 600 "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.printPrefix "Data.Graph.Comfort:601: "+{-# LINE 601 "src/Data/Graph/Comfort.hs" #-} DocTest.property(-{-# LINE 595 "src/Data/Graph/Comfort.hs" #-}+{-# LINE 601 "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.printPrefix "Data.Graph.Comfort:602: "+{-# LINE 602 "src/Data/Graph/Comfort.hs" #-} DocTest.property(-{-# LINE 596 "src/Data/Graph/Comfort.hs" #-}+{-# LINE 602 "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.printPrefix "Data.Graph.Comfort:628: "+{-# LINE 628 "src/Data/Graph/Comfort.hs" #-} DocTest.property(-{-# LINE 622 "src/Data/Graph/Comfort.hs" #-}+{-# LINE 628 "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.printPrefix "Data.Graph.Comfort:629: "+{-# LINE 629 "src/Data/Graph/Comfort.hs" #-} DocTest.property(-{-# LINE 623 "src/Data/Graph/Comfort.hs" #-}+{-# LINE 629 "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.printPrefix "Data.Graph.Comfort:630: "+{-# LINE 630 "src/Data/Graph/Comfort.hs" #-} DocTest.property(-{-# LINE 624 "src/Data/Graph/Comfort.hs" #-}+{-# LINE 630 "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.printPrefix "Data.Graph.Comfort:641: "+{-# LINE 641 "src/Data/Graph/Comfort.hs" #-} DocTest.property(-{-# LINE 635 "src/Data/Graph/Comfort.hs" #-}+{-# LINE 641 "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.printPrefix "Data.Graph.Comfort:694: "+{-# LINE 694 "src/Data/Graph/Comfort.hs" #-} DocTest.property(-{-# LINE 688 "src/Data/Graph/Comfort.hs" #-}+{-# LINE 694 "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.printPrefix "Data.Graph.Comfort:695: "+{-# LINE 695 "src/Data/Graph/Comfort.hs" #-} DocTest.property(-{-# LINE 689 "src/Data/Graph/Comfort.hs" #-}+{-# LINE 695 "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.printPrefix "Data.Graph.Comfort:707: "+{-# LINE 707 "src/Data/Graph/Comfort.hs" #-} DocTest.property(-{-# LINE 701 "src/Data/Graph/Comfort.hs" #-}+{-# LINE 707 "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.printPrefix "Data.Graph.Comfort:708: "+{-# LINE 708 "src/Data/Graph/Comfort.hs" #-} DocTest.property(-{-# LINE 702 "src/Data/Graph/Comfort.hs" #-}+{-# LINE 708 "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.printPrefix "Data.Graph.Comfort:742: "+{-# LINE 742 "src/Data/Graph/Comfort.hs" #-} DocTest.property(-{-# LINE 736 "src/Data/Graph/Comfort.hs" #-}+{-# LINE 742 "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.printPrefix "Data.Graph.Comfort:785: "+{-# LINE 785 "src/Data/Graph/Comfort.hs" #-} DocTest.property(-{-# LINE 756 "src/Data/Graph/Comfort.hs" #-}+{-# LINE 785 "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.printPrefix "Data.Graph.Comfort:798: "+{-# LINE 798 "src/Data/Graph/Comfort.hs" #-} DocTest.property(-{-# LINE 769 "src/Data/Graph/Comfort.hs" #-}+{-# LINE 798 "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.printPrefix "Data.Graph.Comfort:834: "+{-# LINE 834 "src/Data/Graph/Comfort.hs" #-} DocTest.property(-{-# LINE 805 "src/Data/Graph/Comfort.hs" #-}+{-# LINE 834 "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.printPrefix "Data.Graph.Comfort:835: "+{-# LINE 835 "src/Data/Graph/Comfort.hs" #-} DocTest.property(-{-# LINE 806 "src/Data/Graph/Comfort.hs" #-}+{-# LINE 835 "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.printPrefix "Data.Graph.Comfort:848: "+{-# LINE 848 "src/Data/Graph/Comfort.hs" #-} DocTest.property(-{-# LINE 819 "src/Data/Graph/Comfort.hs" #-}+{-# LINE 848 "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.printPrefix "Data.Graph.Comfort:849: "+{-# LINE 849 "src/Data/Graph/Comfort.hs" #-} DocTest.property(-{-# LINE 820 "src/Data/Graph/Comfort.hs" #-}+{-# LINE 849 "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.printPrefix "Data.Graph.Comfort:860: "+{-# LINE 860 "src/Data/Graph/Comfort.hs" #-} DocTest.property(-{-# LINE 831 "src/Data/Graph/Comfort.hs" #-}+{-# LINE 860 "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.printPrefix "Data.Graph.Comfort:861: "+{-# LINE 861 "src/Data/Graph/Comfort.hs" #-} DocTest.property(-{-# LINE 832 "src/Data/Graph/Comfort.hs" #-}+{-# LINE 861 "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.printPrefix "Data.Graph.Comfort:862: "+{-# LINE 862 "src/Data/Graph/Comfort.hs" #-} DocTest.property(-{-# LINE 833 "src/Data/Graph/Comfort.hs" #-}+{-# LINE 862 "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.printPrefix "Data.Graph.Comfort:863: "+{-# LINE 863 "src/Data/Graph/Comfort.hs" #-} DocTest.property(-{-# LINE 834 "src/Data/Graph/Comfort.hs" #-}+{-# LINE 863 "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.printPrefix "Data.Graph.Comfort:864: "+{-# LINE 864 "src/Data/Graph/Comfort.hs" #-} DocTest.property(-{-# LINE 835 "src/Data/Graph/Comfort.hs" #-}+{-# LINE 864 "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.printPrefix "Data.Graph.Comfort:901: "+{-# LINE 901 "src/Data/Graph/Comfort.hs" #-} DocTest.example(-{-# LINE 872 "src/Data/Graph/Comfort.hs" #-}+{-# LINE 901 "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.printPrefix "Data.Graph.Comfort:908: "+{-# LINE 908 "src/Data/Graph/Comfort.hs" #-}+ DocTest.property(+{-# LINE 908 "src/Data/Graph/Comfort.hs" #-}+ + \(TestGraph gr) ->+ Graph.depthFirstSearch gr === GraphAlt.depthFirstSearch gr+ )+ DocTest.printPrefix "Data.Graph.Comfort:945: "+{-# LINE 945 "src/Data/Graph/Comfort.hs" #-} DocTest.example(-{-# LINE 911 "src/Data/Graph/Comfort.hs" #-}+{-# LINE 945 "src/Data/Graph/Comfort.hs" #-} mapSnd Graph.nodes $ Graph.topologicalSort $ unlabGraph [] ['a'*->'a'] ) [ExpectedLine [LineChunk "(\"\",\"a\")"]]- DocTest.printPrefix "Data.Graph.Comfort:913: "-{-# LINE 913 "src/Data/Graph/Comfort.hs" #-}+ DocTest.printPrefix "Data.Graph.Comfort:947: "+{-# LINE 947 "src/Data/Graph/Comfort.hs" #-} DocTest.example(-{-# LINE 913 "src/Data/Graph/Comfort.hs" #-}+{-# LINE 947 "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:915: "-{-# LINE 915 "src/Data/Graph/Comfort.hs" #-}+ DocTest.printPrefix "Data.Graph.Comfort:949: "+{-# LINE 949 "src/Data/Graph/Comfort.hs" #-} DocTest.example(-{-# LINE 915 "src/Data/Graph/Comfort.hs" #-}+{-# LINE 949 "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:938: "-{-# LINE 938 "src/Data/Graph/Comfort.hs" #-}+ DocTest.printPrefix "Data.Graph.Comfort:972: "+{-# LINE 972 "src/Data/Graph/Comfort.hs" #-} DocTest.example(-{-# LINE 938 "src/Data/Graph/Comfort.hs" #-}+{-# LINE 972 "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:940: "-{-# LINE 940 "src/Data/Graph/Comfort.hs" #-}+ DocTest.printPrefix "Data.Graph.Comfort:974: "+{-# LINE 974 "src/Data/Graph/Comfort.hs" #-} DocTest.example(-{-# LINE 940 "src/Data/Graph/Comfort.hs" #-}+{-# LINE 974 "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:985: "-{-# LINE 985 "src/Data/Graph/Comfort.hs" #-}+ DocTest.printPrefix "Data.Graph.Comfort:1019: "+{-# LINE 1019 "src/Data/Graph/Comfort.hs" #-} DocTest.example(-{-# LINE 985 "src/Data/Graph/Comfort.hs" #-}+{-# LINE 1019 "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.printPrefix "Data.Graph.Comfort:1025: "+{-# LINE 1025 "src/Data/Graph/Comfort.hs" #-} DocTest.example(-{-# LINE 991 "src/Data/Graph/Comfort.hs" #-}+{-# LINE 1025 "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.printPrefix "Data.Graph.Comfort:1031: "+{-# LINE 1031 "src/Data/Graph/Comfort.hs" #-} DocTest.property(-{-# LINE 997 "src/Data/Graph/Comfort.hs" #-}+{-# LINE 1031 "src/Data/Graph/Comfort.hs" #-} \(TestGraph gr) ->++ Set.fromList (Graph.stronglyConnectedComponentsNE gr)+ ===+ Set.fromList (GraphAlt.stronglyConnectedComponents gr)+ )+ DocTest.printPrefix "Data.Graph.Comfort:1042: "+{-# LINE 1042 "src/Data/Graph/Comfort.hs" #-}+ DocTest.property(+{-# LINE 1042 "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:1048: "+{-# LINE 1048 "src/Data/Graph/Comfort.hs" #-}+ DocTest.property(+{-# LINE 1048 "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:1059: "+{-# LINE 1059 "src/Data/Graph/Comfort.hs" #-}+ DocTest.property(+{-# LINE 1059 "src/Data/Graph/Comfort.hs" #-}+ + \(TestGraph gr) -> QC.forAll (genShuffledGraph gr) $ \(shuffled, nodeMap) -> Set.fromList@@ -336,10 +377,10 @@ === Set.fromList (Graph.stronglyConnectedComponents shuffled) )- DocTest.printPrefix "Data.Graph.Comfort:1011: "-{-# LINE 1011 "src/Data/Graph/Comfort.hs" #-}+ DocTest.printPrefix "Data.Graph.Comfort:1073: "+{-# LINE 1073 "src/Data/Graph/Comfort.hs" #-} DocTest.property(-{-# LINE 1011 "src/Data/Graph/Comfort.hs" #-}+{-# LINE 1073 "src/Data/Graph/Comfort.hs" #-} \(TestGraph gr) -> Set.fromList (map Graph.nodeSet (Graph.components gr))