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 algorithm Severity:  3 - Normal
Item Group:  incorrect behavior Status:  Invalid
Privacy:  Public Assigned 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:

A   B   C
 \ / \ /
  D   E

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 add your encouragement to it.
This task has 0 encouragements so far.

Only logged-in users can vote.




Follow 3 latest changes.

Date Changed by Updated Field Previous Value => Replaced by
2005-11-26 graydon StatusNone => Invalid
    Open/ClosedOpen => Closed
2004-11-17 njs Carbon-Copy- => Added graydon

Back to the top

Powered by Savane 3.5