[Haskell-cafe] Wrong Answer Computing Graph Dominators
Bertram Felgenhauer
bertram.felgenhauer at googlemail.com
Wed Apr 16 14:33:56 EDT 2008
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-Query-Dominators.html)
> 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
More information about the Haskell-Cafe
mailing list