Talk:Polytree

A problem with definitions

The first paragraph of this article allows the underlying undirected graph to be disconnected. However other parts of the paper assume it is connected, such as the alternative name "oriented tree" and the OEIS listing. McKay (talk) 05:48, 10 August 2012 (UTC)

I notice that has been fixed. Zaslav (talk) 22:27, 9 January 2013 (UTC)

@David Eppstein: The messages above pertain to something that was already fixed 9 years ago. Why did you put them back? Dr. Universe (talk) 02:01, 27 June 2022 (UTC)

@Dr. Universe: You should not remove comments from talk pages. You may be blocked for this behavior. Don't do it. See Wikipedia:Talk page guidelines, and particularly WP:ARCHIVENOTDELETE. Some talk pages have archives for old talk comments, when there are so many that they make it difficult to find current conversations, but this one is not very cluttered. —David Eppstein (talk) 06:38, 27 June 2022 (UTC)

@David Eppstein:I've finally got around to reading those two WP pages. I wonder if there's ever been any precedent for blocking someone for deleting talk comments? It seems a bit extreme to say that I "may be blocked" for it when I wasn't aware of those two WP pages before, and I was genuinely just trying to clean up the talk page a bit. May I create a new heading for the issues being discussed below? This would separate the above discussion which was already resolved, from the below discussions which are still on-going. Dr. Universe (talk) 18:35, 3 July 2022 (UTC)

Of course you're not going to be blocked for doing it once or twice without knowing you shouldn't. It's after you have been warned not to do it tha it becomes problematic. That's what the warning is for. Yes, new threads should have new titles, but it seems we only have old threads here. —David Eppstein (talk) 05:06, 4 July 2022 (UTC)

@David Eppstein: Thanks for the reply. I didn't see it until now because there was no ping. I came to this talk page because I'm seeing "directed tree" and "oriented tree" more often in the literature than "polytree". The article also says that polytree is one of the newer definitions. I deleted the above conversation because that part was already resolved, and I wanted to shift focus more towards the discussions below, which I think are still important to resolve. Can we "archive" the above discussion (up to here) and keep the two comments that are below, so that they can be seen more clearly and hopefully lead to more discussion? I know that there's not been any discussion since 2013, but I would reply to those comments with my own thoughts, and encourage others to discuss too. Dr. Universe (talk) 19:31, 21 July 2022 (UTC)

There's no point in archiving a discussion page with so few comments, and generally when pages are archived it is done an entire thread at a time rather than taking some comments and leaving others. Also, ironically for a comment complaining about no ping, your ping of me did not work. Pings do not work when you add them afterwards to an existing comment. I only saw your comment because I have this talk page watchlisted. —David Eppstein (talk) 19:41, 21 July 2022 (UTC)

@David Eppstein Did the ping work this time? Also, when I said "May I create a new heading for the issues being discussed below?" what I meant was, can we have the two comments below in a second "thread"? Dr. Universe (talk) 22:25, 22 July 2022 (UTC)

Ping worked. If you just want to add a header, that seems harmless enough. —David Eppstein (talk) 03:58, 23 July 2022 (UTC)

Thanks! While doing that I noticed that the two comments below were actually completely unrelated (but I thought they were part of the same comment since there was no space between them), so I made two headings. Dr. Universe (talk) 20:44, 27 July 2022 (UTC)

On the choice of the name "polytree"

I put the simplest name "oriented tree" first. (I also wonder how many graph theorists use the name "polytree"?) Zaslav (talk) 22:30, 9 January 2013 (UTC)

@Zaslav: I'm also wondering the same thing. I've seen the term "directed tree" the most, but people working in the various different subfields might have various different experiences. Historically the article points to articles from as early as 1976 (for "directed tree"), 1980 (for "oriented tree"), 1983 (for "singly connected network"), and 1987 (for "polytree") and it says that the term "polytree" was coined in 1987 so it's the newest of these names by a several years. Google Scholar finds the 2380 results for "polytree" with the most cited one having only 60 citations. For oriented tree it's 3730 results, most cited having 71 citations. Directed tree gives 17,300 results, with 3 of them having more than 71 citations, and the top two having 200+ citations. @David Eppstein: I'm beginning to think this article should not be called "polytree" and that "oriented tree" is an older term that is still being used more often today, and that "directed tree" is the oldest of all terms in the present article, and is also used more than the other two terms by a large amount. Dr. Universe (talk) 20:55, 27 July 2022 (UTC)

Thanks for your research. I always prefer a name that explains itself to one that does not (subject to considerations such as universally agreed usage), so with your data I would strongly prefer to demote "polytree" in favor of "directed" or possibly "oriented" tree. We should not confuse this with an out-tree or arborescence, with all edges directed away from a root. Zaslav (talk) 21:02, 27 July 2022 (UTC)

I suspect that a lot of the usage of "directed tree" is actually about rooted trees, directed away from or towards their roots. "Oriented tree" is less ambiguous, but still easily confused with rooted trees by readers who don't notice the distinction in meanings between directed and oriented. Counting Google Scholar results is dubious because the top hits for "oriented tree" appear to really be about something else: "object-oriented tree traversal", "sink-oriented tree", etc. "Polytree" has the advantage of only meaning this one thing. But it appears that the polytree terminology is mainly used in the machine learning literature, while the other nomenclature is more used in mathematics. (If there's a standard for what to call these things in graph algorithms, I don't know what it is; it looks like the current references are only in mathematics and machine learning, not graph algorithms.) Our article is mostly about the mathematics of these structures, so maybe a more mathematical name makes sense for the overall article, but it would be helpful to explain the differences in naming between different fields, if we can find sources for that. —David Eppstein (talk) 22:26, 27 July 2022 (UTC)

Confusion about the meaning of "undirected"

I find this confusing: In other words, it is a directed graph with exactly one directed path between any two vertices;. What is meant is an undirected path (i.e. a path in the undirected tree), isn't it? Below there is talk of an undirected cycle to refer to a cycle in the undirected graph, so the adjectives seem to be used in different senses here. — Preceding unsigned comment added by 2.230.4.151 (talk) 13:12, 11 May 2013 (UTC)

It has been fixed. Zaslav (talk) 21:07, 27 July 2022 (UTC)