fgl 5.8.0.0 → 5.8.1.0

raw patch · 7 files changed

+50/−12 lines, 7 filesdep ~basePVP ok

version bump matches the API change (PVP)

Dependency ranges changed: base

API changes (from Hackage documentation)

Files

• ChangeLog +8/−0
• Data/Graph/Inductive/PatriciaTree.hs +3/−0
• Data/Graph/Inductive/Query/Dominators.hs +2/−1
• Data/Graph/Inductive/Query/TransClos.hs +2/−1
• Data/Graph/Inductive/Tree.hs +3/−0
• fgl.cabal +2/−2
• test/Data/Graph/Inductive/Query/Properties.hs +30/−8

@@ -1,3 +1,11 @@+5.8.1.0+-------++* Data.Graph.Inductive.PatriciaTree.Gr and+  Data.Graph.Inductive.Tree.Gr now have Functor instances.++* 'Gr a' is now an instance of Functor.+ 5.8.0.0 ------- 

@@ -134,6 +134,9 @@   rnf (Gr g) = rnf g #endif +instance Functor (Gr a) where+  fmap = fastEMap+ #if MIN_VERSION_base (4,8,0) instance Bifunctor Gr where   bimap = fastNEMap

@@ -51,6 +51,7 @@  idomWork :: (Graph gr) => gr a b -> Node -> (IDom, ToNode, FromNode) idomWork g root = let+    nds = reachable root g     -- use depth first tree from root do build the first approximation     trees@(~[tree]) = dff [root] g     -- relabel the tree so that paths from the root have increasing nodes@@ -58,7 +59,7 @@     -- the approximation iDom0 just maps each node to its parent     iD0 = array (1, s-1) (tail $ treeEdges (-1) ntree)     -- fromNode translates graph nodes to relabeled (internal) nodes-    fromNode = I.unionWith const (I.fromList (zip (T.flatten tree) (T.flatten ntree))) (I.fromList (zip (nodes g) (repeat (-1))))+    fromNode = I.unionWith const (I.fromList (zip (T.flatten tree) (T.flatten ntree))) (I.fromList (zip nds (repeat (-1))))     -- toNode translates internal nodes to graph nodes     toNode = array (0, s-1) (zip (T.flatten ntree) (T.flatten tree))     preds = array (1, s-1) [(i, filter (/= -1) (map (fromNode I.!)

@@ -34,7 +34,8 @@ G* = (V,Er union E) where Er = {(i,i): i in V} -} rc :: (DynGraph gr) => gr a b -> gr a ()-rc g = newEdges `insEdges` insNodes ln empty+rc g = (newEdges ++ oldEdges) `insEdges` insNodes ln empty   where     ln       = labNodes g     newEdges = [ (u, u, ()) | (u, _) <- ln ]+    oldEdges = [ (u, v, ()) | (u, v, _) <- labEdges g ]

@@ -135,6 +135,9 @@   rnf (Gr g) = rnf g #endif +instance Functor (Gr a) where+  fmap = emap+ #if MIN_VERSION_base (4,8,0) instance Bifunctor Gr where   bimap = nemap

@@ -1,9 +1,9 @@ name:          fgl-version:       5.8.0.0+version:       5.8.1.0 license:       BSD3 license-file:  LICENSE author:        Martin Erwig, Ivan Lazar Miljenovic-maintainer:    Ivan.Miljenovic@gmail.com+maintainer:    athas@sigkill.dk category:      Data Structures, Graphs synopsis:      Martin Erwig's Functional Graph Library 

@@ -133,14 +133,22 @@ -- Dominators  test_dom :: Spec-test_dom = it "dom" $-  sortIt (dom domGraph 1) `shouldMatchList` [ (1, [1])-                                            , (2, [1,2])-                                            , (3, [1,2,3])-                                            , (4, [1,2,4])-                                            , (5, [1,2,5])-                                            , (6, [1,2,6])-                                            ]+test_dom = describe "dom" $ do+  it "regular dom" $+    sortIt (dom domGraph 1) `shouldMatchList` [ (1, [1])+                                              , (2, [1,2])+                                              , (3, [1,2,3])+                                              , (4, [1,2,4])+                                              , (5, [1,2,5])+                                              , (6, [1,2,6])+                                              ]+  it "multiple components dom" $+    sortIt (dom domGraph1 1) `shouldMatchList` [ (1, [1])+                                               , (2, [1, 2])+                                               ]+  it "directed reachable components dom" $+    sortIt (dom domGraph2 1) `shouldMatchList` [ (1, [1]) ]+   where     sortIt = map (second sort) @@ -159,6 +167,20 @@                     , (4,5)                     , (5,2)                     ]++-- This graph has two components (independent subgraphs)+domGraph1 :: Gr () ()+domGraph1 = mkUGraph [1..3]+                     [ (1,2)+                     ]++-- This graph has no reachables from 1 (but 1 is reachable)+domGraph2 :: Gr () ()+domGraph2 = mkUGraph [1..3]+                     [ (2,1)+                     , (2,2)+                     ]+  -- ----------------------------------------------------------------------------- -- GVD