bugmonotone - Bugs: bug #11034, Least dominator+ancestor is not...


You are not allowed to post comments on this tracker with your current authentication level.

bug #11034: Least dominator+ancestor is not correct for finding merge ancestors

Submitted by:  Nathaniel Smith <njs>
Submitted on:  Wed 17 Nov 2004 10:26:25 AM UTC  
Category: merge algorithmSeverity: 3 - Normal
Item Group: incorrect behaviorStatus: Invalid
Privacy: PublicAssigned to: None
Open/Closed: Closed
mtn version --full: 

Sat 26 Nov 2005 12:50:53 AM UTC, comment #1:

Multiply-rooted graphs are an obsolete concept, as is LCAD. I think this bug is dead.

graydon hoare <graydon>
Project Member
Wed 17 Nov 2004 10:26:25 AM UTC, original submission:

The following case is a counter-example:

\ / \ /

obviously we should use B for the merge, but in this graph there is no least dominator+ancestor.

I knew multiply rooted graphs would cause problems, bleh...

I conjecture that if we recursively remove roots that are ancestors of only one of the to-be-merged nodes, and then apply the current algorithm, we will be Correct. (I.e., for each root, if it is an ancestor of one node but the other, remove it from the graph. Repeat until we stabilize. There is likely a more efficient way to do this.)

Unfortunately, I am too sleepy to try to prove it right now. But last time I tried to prove it I went "ew, I keep needing a constraint on the roots for this to go through", and that gives one that seems promising...

Nathaniel Smith <njs>
Project Member


No files currently attached


Depends on the following items: None found

Items that depend on this one: None found


CC list is empty


Do you think this task is very important?
If so, you can click here to add your encouragement to it.
This task has 0 encouragements so far.

Only logged-in users can vote.


Please enter the title of George Orwell's famous dystopian book (it's a date):



Follow 3 latest changes.

Date Changed By Updated Field Previous Value => Replaced By
Sat 26 Nov 2005 12:50:53 AM UTCgraydonStatusNone=>Invalid
Wed 17 Nov 2004 10:26:25 AM UTCnjsCarbon-Copy-=>Added graydon

Back to the top

Powered by Savane 3.1-cleanup1