fgl 5.8.1.0 → 5.8.1.1
raw patch · 6 files changed
+23/−10 lines, 6 filesdep ~deepseqPVP ok
version bump matches the API change (PVP)
Dependency ranges changed: deepseq
API changes (from Hackage documentation)
Files
- ChangeLog +6/−0
- Data/Graph/Inductive/Query/Dominators.hs +4/−3
- Data/Graph/Inductive/Query/TransClos.hs +3/−3
- fgl.cabal +2/−2
- test/Data/Graph/Inductive/Query/Properties.hs +6/−0
- test/TestSuite.hs +2/−2
ChangeLog view
@@ -1,3 +1,9 @@+5.8.1.1+-------++* Data.Graph.Inductive.Query.Dominators.{dom,iDom} could fail for some+ graphs (issue #109, regression in 5.8.1.0).+ 5.8.1.0 -------
Data/Graph/Inductive/Query/Dominators.hs view
@@ -17,16 +17,17 @@ import Data.Graph.Inductive.Query.DFS import Data.IntMap (IntMap) import qualified Data.IntMap as I+import Data.Maybe (mapMaybe) import Data.Tree (Tree (..)) import qualified Data.Tree as T {-# ANN iDom "HLint: ignore Use ***" #-}--- | return immediate dominators for each node of a graph, given a root+-- | return immediate dominators for each reachable node of a graph, given a root iDom :: (Graph gr) => gr a b -> Node -> [(Node,Node)] iDom g root = let (result, toNode, _) = idomWork g root in map (\(a, b) -> (toNode ! a, toNode ! b)) (assocs result) --- | return the set of dominators of the nodes of a graph, given a root+-- | return the set of dominators of the reachable nodes of a graph, given a root dom :: (Graph gr) => gr a b -> Node -> [(Node,[Node])] dom g root = let (iD, toNode, fromNode) = idomWork g root@@ -62,7 +63,7 @@ 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.!)+ preds = array (1, s-1) [(i, filter (/= -1) (mapMaybe (`I.lookup` fromNode) (pre g (toNode ! i)))) | i <- [1..s-1]] -- iteratively improve the approximation to find iDom. iD = fixEq (refineIDom preds) iD0
Data/Graph/Inductive/Query/TransClos.hs view
@@ -18,8 +18,8 @@ outU gr = map toEdge . out gr {-|-Finds the transitive, reflexive closure of a directed graph.-Given a graph G=(V,E), its transitive closure is the graph:+Finds the reflexive-transitive closure of a directed graph.+Given a graph G=(V,E), its reflexive-transitive closure is the graph: G* = (V,E*) where E*={(i,j): i,j in V and either i = j or there is a path from i to j in G} -} trc :: (DynGraph gr) => gr a b -> gr a ()@@ -30,7 +30,7 @@ {-| Finds the reflexive closure of a directed graph.-Given a graph G=(V,E), its transitive closure is the graph:+Given a graph G=(V,E), its reflexive closure is the graph: G* = (V,Er union E) where Er = {(i,i): i in V} -} rc :: (DynGraph gr) => gr a b -> gr a ()
fgl.cabal view
@@ -1,5 +1,5 @@ name: fgl-version: 5.8.1.0+version: 5.8.1.1 license: BSD3 license-file: LICENSE author: Martin Erwig, Ivan Lazar Miljenovic@@ -20,7 +20,7 @@ tested-with: GHC == 7.2.2, GHC == 7.4.2, GHC == 7.6.3, GHC == 7.8.4, GHC == 7.10.3, GHC == 8.0.2, GHC == 8.2.2, GHC == 8.4.3, GHC == 8.6.2, GHC == 8.8.2, GHC == 8.10.7, GHC == 9.0.2,- GHC == 9.2.3, GHC == 9.4.2+ GHC == 9.2.4, GHC == 9.4.4 source-repository head type: git
test/Data/Graph/Inductive/Query/Properties.hs view
@@ -149,6 +149,9 @@ it "directed reachable components dom" $ sortIt (dom domGraph2 1) `shouldMatchList` [ (1, [1]) ] + it "unreachable nodes dom" $+ sortIt (dom domGraph3 1) `shouldMatchList` [(1,[1]), (2,[1,2])]+ where sortIt = map (second sort) @@ -181,6 +184,9 @@ , (2,2) ] +-- From #109: 1 -> 2 <- 3+domGraph3 :: Gr () ()+domGraph3 = mkUGraph [1..3] [(1,2), (3,2)] -- ----------------------------------------------------------------------------- -- GVD
test/TestSuite.hs view
@@ -79,7 +79,7 @@ propType "subgraph" valid_subgraph where- proxyProp str = prop str . ($p)+ proxyProp str = prop str . ($ p) propType :: (Testable pr) => String -> (GraphType gr -> pr) -> Spec propType = prop@@ -126,7 +126,7 @@ propP "tc" test_tc propP "rc" test_rc where- propP str = prop str . ($p)+ propP str = prop str . ($ p) p :: PatriciaTreeP p = Proxy