Talk:Lowest common ancestor

[untitled]

@David Eppstein: the binary tree in my implementation doesn't have to be balanced (I know that pictures suggest that), as long as nodes have proper numbering. (This isn't big problem, since the depth of BT can be remembered while building BT and BT depth can be used to for calculation of node's number). GiM 18:47, 13 June 2007 (UTC)

It does have to be balanced (by which I mean, not necessarily a complete binary tree, but having relatively small depth) because, if I understand it correctly, the numbering you use assumes that the depth of the tree is less than the number of bits per word. —David Eppstein 19:55, 13 June 2007 (UTC)

If I understand you correctly, yes. The maximum depth of BT is number_of_bits_in_word - 1 (so that would be 31, which is rather small). That is definitely limitation. Thanks for clearing this out. —GiM 10:35, 14 June 2007 (UTC)

External links modified

Hello fellow Wikipedians,

I have just modified one external link on Lowest common ancestor. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

• Added archive https://web.archive.org/web/20110720050818/http://stanford-online.stanford.edu/knuth/071203-knuth-300.asx to http://stanford-online.stanford.edu/knuth/071203-knuth-300.asx

When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 5 June 2024).

• If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
• If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 17:39, 7 January 2018 (UTC)

The archived resource is not the video, but rather a playlist file still containing the old video URL (http://proedvid.stanford.edu/knuth/071203/071203-knuth-300.wmv). This link is still broken. Some of Knuth's lectures are now provided by Stanford on YouTube (see https://www-cs-faculty.stanford.edu/~knuth/musings.html), though I do not know if any of these correspond to the original video. 174.52.135.226 (talk) 00:11, 22 July 2020 (UTC)

Baruch Schieber

Please add a link from the second paragraph of the history section to the newly created article on Baruch Schieber --Adig-pt (talk) 05:28, 12 July 2021 (UTC)

 Done —David Eppstein (talk) 06:43, 12 July 2021 (UTC)

There is a mistake in the first image in this article

Hello,

I assume the person who created the first image (Lowest common ancestor#/media/File:Lowest common ancestor.svg) just mixed up the direction of the arrows by mistake, especially because in another image in the article by the same author it is depicted correctly (Lowest common ancestor#/media/File:Lowest common ancestors in a DAG.svg). However, the first image is incorrect at the moment and should be fixed such that the people looking at this article don't get the wrong intuition. Unfortunately, I cannot do it because I don't have enough credits.

In case one does not see the mistake immediately, here are the mathematical details:

The image in this article shows a directed tree, i.e. a DAG (directed acyclic graph) such that the underlying graph is a tree (see e.g. Tree (graph theory), second paragraph).

In DAGs, node a is an ancestor of node b if there is a directed path from a to b as correctly defined in the section "Extension to directed acyclic graphs" of this article based on Aït-Kaci et al. (1989).

That may be true of DAGs, but it's not true of the first image in the article. The text explains "each node points to its parent". Maproom (talk) 19:19, 24 March 2024 (UTC)

I cannot yet understand your point: The figure shows a graph without cycles and with directed edges. Could you explain why you say this is not a DAG (a directed acyclic graph)? Do you mean that in this case this should not be read as a directed graph but as an undirected rooted tree with a data structure that does not influence the concept of lowest common ancestors in undirected rooted trees? In the article, they do not talk about data structures but they do talk about the concept of lowest common ancestors for DAGs: Lowest common ancestor#Extension to directed acyclic graphs. Could you clarify why you think this is not a typo a bit more @Maproom? Thank you in advance This-is-sof (talk) 10:54, 26 March 2024 (UTC)

This-is-sof, yes, I was mistaken, the image in the article is a DAG (directed acyclic graph). But it does not fit your claim "In DAGs, node a is an ancestor of node b if there is a directed path from a to b". It has arrows that go from descendants to ancestors. This is explained in the text alongside the image. Maproom (talk) 15:43, 26 March 2024 (UTC)

Thank you for your answer, @Maproom. Yes, what you write is true – and exactly the mistake I want to fix. You say that "[the figure] has arrows that go from descendants to ancestors" – but that contradicts the definition of ancestors and descendants in DAGs. Ancestors in DAGs have directed paths to their descendants and not the other way around. I am pretty positive that the person who did the figure just flipped the direction of the arrows by mistake. As said, later in the article there is a correct version of a lowest common ancestor in a DAG.

The text alongside the figure says "In this tree, the lowest common ancestor of the nodes x and y is marked in dark green. Other common ancestors are shown in light green." However, the dark green nodes are not lowest common ancestors – they are not even ancestors but descendants.

I hope I could make my point clearer now. This-is-sof (talk) 10:23, 28 March 2024 (UTC)

"Directed acyclic graph" is a mathematical term. Its definition does not use the term "descendant". If you want the image edited to reverse the direction of the arrows, I (and I expect many other editors) could do that. But I'll be away from home, without access to an editing program, until at least Wednesday April 3rd. I'll have another look at this page then. Maproom (talk) 10:56, 28 March 2024 (UTC)

Thanks, that would be great! Hopefully I can clarify what I mean by "the definition of descendants and ancestors in DAGs": In a DAG, a descendant and ancestors are defined as stated in my original message: "In DAGs, node a is an ancestor of node b if there is a directed path from a to b as defined in the section "Extension to directed acyclic graphs" of this article based on Aït-Kaci et al. (1989)." This-is-sof (talk) 16:14, 28 March 2024 (UTC)

Hello @Maproom, just wanted to check the status. Best wishes! This-is-sof (talk) 11:30, 9 May 2024 (UTC)

Hello This-is-sof. I had assumed I'd be able to modify the current SVG file, and upload it in place of the old one. But it's not so easy. The current file was created by a free package called "Graphviz", using a file proided by its uploader {{u|Qwertyus}] and available at its page on Commons. I've spent several hours downloading Graphviz and figuring out how to run it, and can get it to recrate the current file (which is doesn't now get quite right, the circles are elliptical). But I've failed to figure out the logic of the syntax of its input file, so as to be able to get the required output. I'm sorry, but I'm giving up on this. Maproom (talk) 14:50, 9 May 2024 (UTC)

A lowest common ancestor of two nodes x and y in a DAG is a node z that 1. is a common ancestor of a and b and 2. no descendant of z is also a common ancestor of x and y. See e.g. https://link.springer.com/chapter/10.1007/978-3-540-75520-3_25, https://www3.cs.stonybrook.edu/~bender/pub/JALG05-daglca.pdf.

The green nodes in the graph in the first figure are not ancestors of x and y but descendants. For the figure to be correct for directed trees, the directions of all arrows must be flipped, then it is correct for that case.

That said, it might be a good idea to delete the arrowheads entirely, as one always starts with rooted trees (undirected) instead of directed trees when talking about the lowest common ancestor. There, the definition is easy – the lowest common ancestor is the node that is the farthest away from the root. This means changing the directed arrows in the figure to undirected arrows would also be correct and might even provide a better first intuition.

Best, Sofia This-is-sof (talk) 18:22, 10 March 2024 (UTC)