dom-lt 0.2.1 → 0.2.2

raw patch · 5 files changed

+66/−25 lines, 5 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

• Changelog.md +5/−0
• Data/Graph/Dom.hs +13/−5
• Data/Graph/Dom/Internal.hs +22/−0
• dom-lt.cabal +9/−3
• tests/Main.hs +17/−17

@@ -1,5 +1,10 @@ ## Changes in version 0.2.1 +* Fixed #2. Another bug that resulted in incorrect results+  for some inputs.++## Changes in version 0.2.1+ * Fixed a bug that resulted in incorrect results.  ## Changes in version 0.2.0

@@ -151,9 +151,9 @@   n <- gets dfsE   forM_ [n,n-1..1] (\i-> do     w <- ndfsM i-    sw <- sdnoM w     ps <- predsM w     forM_ ps (\v-> do+      sw <- sdnoM w       u <- eval v       su <- sdnoM u       when (su < sw)@@ -290,9 +290,10 @@  initEnv :: Rooted -> ST s (Env s) initEnv (r0,g0) = do+  -- Graph renumbered to indices from 1 to |V|   let (g,rnmap) = renum 1 g0-      pred      = predG g-      r         = rnmap IM.! r0+      pred      = predG g -- reverse graph+      root      = rnmap IM.! r0 -- renamed root       n         = IM.size g       ns        = [0..n]       m         = n+1@@ -314,13 +315,14 @@   ndfs      <- newI m   dfn       <- newI m +  -- Initialize all arrays   forM_ [0..n] (doms.=0)   forM_ [0..n] (sdno.=0)   forM_ [1..n] (size.=1)   forM_ [0..n] (ancestor.=0)   forM_ [0..n] (child.=0) -  (doms.=r) r+  (doms.=root) root   (size.=0) 0   (label.=0) 0 @@ -328,7 +330,7 @@     {rnE        = rna     ,dfsE       = 0     ,zeroE      = 0-    ,rootE      = r+    ,rootE      = root     ,labelE     = label     ,parentE    = parent     ,ancestorE  = ancestor@@ -399,6 +401,7 @@ infixl 9 !: infixr 2 .= +-- | arr .= x idx => write x to index (.=) :: (MArray (A s) a (ST s))      => Arr s a -> a -> Int -> ST s () (v .= x) i = unsafeWrite v i x@@ -531,6 +534,10 @@ --                                   (f a) --                                   (g a) m) mempty +-- | renum n g: Rename all nodes+--+-- Gives nodes sequential names starting at n.+-- Returns the new graph and a mapping. -- (renamed, old -> new) renum :: Int -> Graph -> (Graph, NodeMap Node) renum from = (\(_,m,g)->(g,m))@@ -555,6 +562,7 @@  ----------------------------------------------------------------------------- +-- Nothing better than reinvinting the state monad. newtype S z s a = S {unS :: forall o. (a -> s -> ST z o) -> s -> ST z o} instance Functor (S z s) where   fmap f (S g) = S (\k -> g (k . f))

@@ -0,0 +1,22 @@+module Data.Graph.Dom.Internal where
+
+import Data.Graph.Dom as D
+
+import Data.Foldable as F
+import Data.List
+import Data.IntMap.Strict as IM
+import Data.IntSet as IS
+
+newline :: [Char]
+newline = "\n"
+
+-- | For debugging only
+asDotFile :: D.Graph -> String
+asDotFile g =
+    let pprNode :: (Int, IntSet) -> String
+        pprNode (node,targets) =
+            concat $ intersperse newline $ fmap (pprEdge node) $ IS.toList targets
+        pprEdge v u = show v ++ " -> " ++ show u ++ ";"
+    in "digraph G {" ++ newline ++
+            (concat $ intersperse newline $ fmap pprNode (IM.toList g)) ++ newline ++
+            "}"

@@ -1,8 +1,7 @@ name:               dom-lt-version:            0.2.1+version:            0.2.2 cabal-version:      >= 1.10 build-type:         Simple-tested-with:        GHC == 8.10.1 || == 8.8.4 || == 8.0.1 license:            BSD3 license-file:       LICENSE category:           Algorithms, Graphs@@ -17,6 +16,11 @@      Included are ways to compute domination and post-domination relationships. +tested-with:+  GHC == 8.10.1 || == 8.10.2,+  GHC == 8.8.4  || == 8.8.3,+  GHC == 8.0.1+ Extra-Source-Files:   Changelog.md @@ -36,7 +40,9 @@       base >= 4.9 && < 5     , array     , containers >= 0.5 && < 0.7-  exposed-modules:  Data.Graph.Dom+  exposed-modules:+    Data.Graph.Dom,+    Data.Graph.Dom.Internal  test-suite dom-lt-tests   Default-Language: Haskell2010

@@ -7,20 +7,7 @@ import System.Exit  import Test.HUnit hiding (Node,Path)--- import Test.Framework.Providers.QuickCheck2--- import Test.QuickCheck (Property, (===))--- import Test.QuickCheck.Function (Fun, apply)--- import Test.QuickCheck.Poly (A, OrdA, B, OrdB, C) --- main = defaultMain---   [ test_dom---   , testtest_pdom---   , test_idom---   , test_ipdom---   , test_domTree---   , test_pdomTree---   ]- g0 :: Graph g0 = fromAdj   [(1,[2,3])@@ -46,13 +33,18 @@   ,(7,[])]  main = do-  counts <- runTestTT tests-  putStrLn $ showCounts counts-  if (errors counts + failures counts) > 0+  result_counts <- runTestTT tests+  putStrLn $ showCounts result_counts+  if (errors result_counts + failures result_counts) > 0     then exitWith $ ExitFailure 1     else exitWith   ExitSuccess -tests = TestList $ map TestCase [dom0, dom1, pdom0, pdom1, ipdom0, ipdom1, dom_t_g0, dom_t_g1, dom_pt_g0, dom_pt_g1]+tests :: Test+tests =+  TestList $+    map TestCase+      [dom0, dom1, pdom0, pdom1, ipdom0, ipdom1, dom_t_g0, dom_t_g1, dom_pt_g0, dom_pt_g1,+       dom_T2_g3]  g0_rooted, g1_rooted :: Rooted g0_rooted = (1,g0)@@ -98,7 +90,15 @@               (  Node {rootLabel = 0, subForest = []}  )               (pdomTree g1_rooted) +g3_edges :: Graph+g3_edges = fromAdj [(0,[3,6]), (3,[8,9]), (6,[99]), (8,[11]), (9,[16]), (11,[99]), (12,[99]), (13,[99]), (16,[12,13]), (99,[])]+g3 :: (Int, Graph)+g3 = (0 :: Int, g3_edges) +dom_T2_g3 :: Assertion+dom_T2_g3 = assertEqual "dom #2"+              [(99,[0])]+              ( filter (\x -> fst x == 99) $ dom g3)   -- applyDomFunctions :: Rooted