[MERGE][1.0] Fixes for find_differences() and get_parents_map()

[Aaron Bentley]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

John S. Yates, Jr. wrote:
> Aaron Bentley replied:

>> Given the graph (from oldest to newest)
>>
>>   A
>>  / \
>> B   C
>> | X |
>> D   E
>>
>>
>>
>> The dominance frontier of A is (B, C, D, E).

> Aaron does not specify an actual definition of the dominance frontier.
> I always found the name somewhat counter-intuitive.  I wonder whether
> Aaron simply tried to guess its significance.

No, I looked it up.

>  The actual definition is
> 
>     The dominance frontier of X is the set of nodes DF such that
>     for every node Y in DF:
>       X dominates a predecessor of Y, but
>       X does not strictly dominate Y.
> 
> Given that A dominates every node in Aaron's sample graph by this
> definition it has no meaningful dominance frontier.

Actually, no.  The edges in my graph were meant to be from child to
parent, that is B->D, C->A, etc.  This is the direction we
conventionally draw our graphs in.  So A dominates only itself.
However, I misunderstood the meaning of "predecessor", so I believed
that A was a predecessor of B (being its parent revision in Bazaar
terminology).  That lead me to believe that B and C were in the
dominance frontier, since their parents were dominated but they were not.

I would agree that if we reverse the directions of the edges, A has no
dominance frontier.

> My suggestion amounted simply to considering the dominance frontier of
> the tips looking back up the graph toward the root.  Each tip has a
> region of the DAG which it dominates.  The dominance frontier is the
> boundary at which backwards exploration from either tip would first
> overlap.  All nodes beyond the frontier are common.

Thank you for that explanation.  It seems rather counterintuitive to
invoke the dominance frontier, because we are looking for the nodes that
are dominated by the tips, not those that are in the dominance frontier.
 Still, I imagine knowing one allows us to determine the other.

> I particularly recommend Bilardi and Pingali's  "Algorithms for
> Computing the Static Single Assignment Form"
> 
> http://citeseer.ist.psu.edu/727701.html

Thank you for the reference.  Although somehow I have become Bazaar's
main graph guy, I have no background in graph theory, so new terminology
and resources are always welcome.

Aaron
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFHopua0F+nu1YWqI0RAkvKAJ9sJh1S308TI4pdcSJ4Q0Wl7EzV6gCfbkYu
K1hkXX30D7kfCEy4tGUyolY=
=+zc2
-----END PGP SIGNATURE-----