[Haskell-cafe] Wrong Answer Computing Graph Dominators

[Denis Bueno]

On Thu, Apr 17, 2008 at 11:32 AM, Denis Bueno <dbueno at gmail.com> wrote:
> On Wed, Apr 16, 2008 at 2:33 PM, Bertram Felgenhauer
>  <bertram.felgenhauer at googlemail.com> wrote:
>  >  No. Data.Graph.Inductive.Query.Dominators is just buggy.

I have one more problem.  For the attached graph, the dominators of
the -20 node are computed correctly (namely, [-20,-1,11,12]).  But the
list of dominators for 20 is present, when in fact 20 isn't reachable
from 12.  I think 20 should be absent from the return value of `dom
graph 12'.  (And hence a call to `lookup 20 (dom graph 12)' should
return Nothing.)  Instead it returns [-20,-1,-3,11,12,-14,17].

Is my reasoning correct?  I'd try to fix the code, but, I don't
understand how it works.

-- 
Denis
-------------- next part --------------
A non-text attachment was scrubbed...
Name: bad-dominators2.ps
Type: application/postscript
Size: 12915 bytes
Desc: not available
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20080417/51544b32/bad-dominators2.ps