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

[Aaron Bentley]

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

John Yates wrote:
> Have you investigated algorithms for computing the "dominance frontier"?
> You might find that those are exactly the nodes of interest.

I think those are not precisely the same as the dominance frontier.

Given the graph (from oldest to newest)

  A
 / \
B   C
| X |
D   E



The dominance frontier of A is (B, C, D, E).  But the only nodes in the
graph difference are D and E.

We can actually calculate that D and E may be in the graph difference.
The problem we're having is that we don't know when to stop looking for
candidates.

I believe we can stop searching a given path when the current node of
that path is descended from all of the uncommon ancestors, but we've had
trouble implementing that condition efficiently.  One obvious
simplification is to consider only the uncommon ancestors whose
immediate ancestors are common.

So the things we've considered useful are:
1. uncommon ancestors
2. uncommon ancestors that are direct descendants of common ancestors
3. revisions derived from all uncommon ancestors

I don't think the dominance frontier helps us determine any of those.
Please explain further if I'm misunderstanding.

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

iD8DBQFHoWwn0F+nu1YWqI0RAoMVAKCGOJKjWEn/rkggi0wcbUnXfm4KDgCeKIJO
pZ9BmyhGtrUc8Rcm5yZx3po=
=Ou5h
-----END PGP SIGNATURE-----