LCA's and graphs

[Aaron Bentley]

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

Robert Collins wrote:
> This paper: http://citeseer.ist.psu.edu/bender01finding.html is an
> interesting read. In particular they use the same definition for least
> common ancestor of two nodes as we desire for our merge basis: The
> common ancestor with the longest path from the origin.

For DAGs, they actually use the same definition of LCA as I used in
London: "An LCA w of nodes u and v in a DAG is an ancestor of both u and
v where w has no descendants that are ancestors of both u and v."

In my view, the common ancestor with the longest path from the origin is
not actually desirable, because of its behavior in criss-cross
merge situations.  But it appears this algorithm does produce LCAs that
are useful in finding what I consider a good merge base.

> The preprocessing work that is talked about is potentially useful in
> terms of indexes: A large blob with the entire repo in it could have a
> preprocessed graph stored somewhere. We'd need to consider the
> distributed nature of our system and combining such preprocessed things
> at runtime.

Certainly there are practical issues, e.g. whether preprocessed data
from a subgraph can be efficiently reused in a larger graph.

I hope and believe that the algorithm I've proposed for merging will be
practical, especially with current-gen repositories.  But for future
formats, constant-time queries would certainly be compelling.

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

iD8DBQFGbpaS0F+nu1YWqI0RAhiiAJ98Avf3VrA3yfIL0tgaNbgzvIO6qQCcDWbx
AsnPgNM8UGi2MOJ3+AsVPoU=
=aURT
-----END PGP SIGNATURE-----