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

Submitter:  Nathaniel Smith <njs>
Submitted:  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>
Group 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>
Group Member

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

No files currently attached

 

Depends on the following items: None found

Items that depend on this one: None found

 

CC list is empty

 

There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.

 

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.13-cf05.
Corresponding source code