[Haskell-cafe] Wrong Answer Computing Graph Dominators

[Dan Weston]

Your reasoning differs from the usual understanding of a null product (1 
or True), as compared to a null sum (0 or False):

 > the list of nodes for which
 > *any path* from source to x must touch, i.e., the list of dominators
 > of x.

Here, "any path" means all paths, a logical conjunction:

and [True, True] = True
and [True      ] = True
and [          ] = True

The empty case of all sources touching is True, so 12 is a valid 
dominator for 20 if there is no path from 12 to 20.

Dan

Denis Bueno wrote:
> 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.
> 
> 
> 
> ------------------------------------------------------------------------
> 
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe