Denis Bueno wrote:
I'm using the Data.Graph.Inductive.Query.Dominators library (http://haskell.org/ghc/docs/latest/html/libraries/fgl/Data-Graph-Inductive-Q...) with GHC 6.8.2. The library is a bit spare on comments, so I may or may not be using it correctly.
[snip]
But what I am getting is: --> uips = [-9,20] --> domConfl = [2,-9,20] --> domAssigned = [-2,-9,-12,20] --> lastd = 20
But -9 is not a dominator for 2, since 20,-7,8,6,2 is a path from 20 to 2 that does not touch 9. -9 is also not a dominator for -2, since 20,-7,8,6,-2 is a path from 20 to -2 not touching 9.
Am I missing something?
No. Data.Graph.Inductive.Query.Dominators is just buggy. 1) domr is meant to find a fixed point of builddoms by iteratively applying builddoms, but in fact it calls builddoms at most twice. 2) the code doesn't handle nodes with no predecessors correctly. Here's a quick fix: diff -rN -u old-fgl/Data/Graph/Inductive/Query/Dominators.hs new-fgl/Data/Graph/Inductive/Query/Dominators.hs --- old-fgl/Data/Graph/Inductive/Query/Dominators.hs 2008-04-16 20:13:35.000000000 +0200 +++ new-fgl/Data/Graph/Inductive/Query/Dominators.hs 2008-04-16 20:13:35.000000000 +0200 @@ -18,13 +18,13 @@ builddoms :: DomSets -> [Node] -> DomSets builddoms ds [] = ds builddoms ds (v:vs) = builddoms ((fs++[(n,p,sort(n:idv))])++(tail rs)) vs - where idv = intersection (getdomv p ds) - (n,p,_) = head rs + where idv = intersection ((q \\ [n]):getdomv p ds) + (n,p,q) = head rs (fs,rs) = span (\(x,_,_)->x/=v) ds domr :: DomSets -> [Node] -> DomSets domr ds vs|xs == ds = ds - |otherwise = builddoms xs vs + |otherwise = domr xs vs where xs = (builddoms ds vs) {-| Bertram