[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Monotone-devel] Bug in monotone lca
From: |
Nathaniel Smith |
Subject: |
Re: [Monotone-devel] Bug in monotone lca |
Date: |
Thu, 19 May 2005 14:52:10 -0700 |
User-agent: |
Mutt/1.5.9i |
On Thu, May 19, 2005 at 07:29:14PM +0200, Wim Oudshoorn wrote:
> Timothy Brownawell <address@hidden> writes:
> > But A *is* the least common ancestor (M->K->B->A; N->L->D->A). That
> > it's also an ancestor of a more distant common ancestor doesn't
> > matter. Distances can be funny that way.
>
> Ah, I interpreted the least common ancestor in a different way.
>
> My interpretatio was:
> Look at all common ancestors, in this case (A, C)
> And take from all common ancestors the "latest", in this case
> "C".
> [Ignoring for the moment that this in the general case this
> does not give a unique lca].
>
> Apparently this is not the monotone interpretation.
> So could you explain, or provide a pointer to,
> what is the definition of lca?
Hrm, I'm actually more used to the "minimal common ancestor"
definition (i.e., a node A such that no common ancestors are
descendents of A), than the "nearest common ancestor" (which seems to
be what we use). It doesn't make much of a difference for anything
that monotone uses its LCA algorithm for, though; in fact, "nearest
common ancestor" is probably better. (We just use LCA when we want a
nearby common ancestor, that we can use to generate a path from one
node to another, for instance.)
This is why, though, if someone wanted to make
unique-lca-or-else-lca+dom into the merge ancestor selection
algorithm as a temporary stopgap measure, they would have to actually
do some work, since for merging you really do need to use the "minimal
common ancestor" variant.
-- Nathaniel
--
"Of course, the entire effort is to put oneself
Outside the ordinary range
Of what are called statistics."
-- Stephan Spender
- [Monotone-devel] Bug in monotone lca, Wim Oudshoorn, 2005/05/19
- Re: [Monotone-devel] Bug in monotone lca, Timothy Brownawell, 2005/05/19
- Re: [Monotone-devel] Bug in monotone lca, Wim Oudshoorn, 2005/05/19
- Re: [Monotone-devel] Bug in monotone lca,
Nathaniel Smith <=
- [Monotone-devel] Re: Bug in monotone lca, Wim Oudshoorn, 2005/05/20
- Re: [Monotone-devel] Re: Bug in monotone lca, Nathaniel Smith, 2005/05/20
- [Monotone-devel] Re: Bug in monotone lca, Wim Oudshoorn, 2005/05/20
- Re: [Monotone-devel] Re: Bug in monotone lca, Nathaniel Smith, 2005/05/20
- [Monotone-devel] Re: Bug in monotone lca, Wim Oudshoorn, 2005/05/20
- Re: [Monotone-devel] Re: Bug in monotone lca, Nathaniel Smith, 2005/05/20
- Re: [Monotone-devel] Re: Bug in monotone lca, Florian Weimer, 2005/05/20
- [Monotone-devel] Re: Bug in monotone lca, Wim Oudshoorn, 2005/05/20
- Re: [Monotone-devel] Re: Bug in monotone lca, Nathaniel Smith, 2005/05/20