Talk:Accessible pointed graph

Origin of terminlogy?

Did anyone before Aczel (1988) use this terminology? I agree that it's less confusing than the received one, which is actually RDG (rooted directed graph or rooted digraph), particularly as Aczel also defines pointed graph. JMP EAX (talk) 17:58, 23 July 2014 (UTC)

Not to my knowledge. I think the initial version of this article was written and named by someone who knew only about Aczel's work and not about earlier uses of the same concept. (Perhaps it's worth noting that Aczel doesn't seem to be limiting the scope of the definition to *finite* graphs, as some other works in this area probably implicitly do.)

And

I think the authors who defined rooted graph (instead of rooted digraph) as this were a bit sloppy. The paper of Aggarwal et al. in particular is so, as they they freely mix the terms graph and directed graph throughout the paper, but they usually mean directed graph when they say graph, e.g. "Suppose that we want to perform depth-first search in an n-vertex directed graph G starting from some vertex r. Any such search will visit exactly the vertices reachable from r using directed paths. We call a graph rooted at a vertex if the vertex can reach all other vertices through directed paths. We assume, for the moment, that G is rooted at r and our goal is to build a directed depth-first search spanning tree rooted at r for G." JMP EAX (talk) 18:05, 23 July 2014 (UTC)

You marked as dubious the claim that this paper uses the phrase "rooted graph" to mean the same thing as the subject of the article. Is that claim in any doubt? Or do you merely object to the paper because they use the word "graph" without every time qualifying it by whether it is directed or undirected? That seems a silly reason to object to a source. —David Eppstein (talk) 18:27, 23 July 2014 (UTC)

It seems a low quality source as far as giving definitions is concerned, for the reasons explained above. The much more common term found in CS papers is rooted digraph or rooted directed graph, which isn't even mentioned on this page. You are assuming they really wanted to defined "rooted graph" as a whole term, but I think the only thing clear is that they are defining the meaning of rooted as a qualifier for directed graphs. Eliding "directed" is not without consequence in this case, because rooted graph is usually defined as something else/simpler in the undirected case. If the paper said "Definition: a rooted graph [with this in emphasis] is a [blah, blah...]" I would agree they really intended to define "rooted graph" as phrase term. But that's not clear at all from their writing, which I interpret as I explained above. So, I think it is a bit of WP:OR to assume they define "rooted graph" as a phrase term from their rather unclear writing. JMP EAX (talk) 18:43, 23 July 2014 (UTC)

It is a peer-reviewed paper published in one of the best journals in algorithms research, by three respected algorithms researchers. It is not a low-quality source. If the terms (plural) "rooted digraph" or "rooted directed graph" also appear in the literature, then we should mention them as well; there's no requirement that we be constrained to mentioning only one alternative name. —David Eppstein (talk) 18:52, 23 July 2014 (UTC)

Agreed on the latter, but I really don't think the paper you plaudit defines the term "rooted graph", but only the qualifier "rooted" for directed graphs. Here's the same quote I gave initially with the italics from the original: "Suppose that we want to perform depth-first search in an n-vertex directed graph G starting from some vertex r. Any such search will visit exactly the vertices reachable from r using directed paths. We call a graph rooted at a vertex if the vertex can reach all other vertices through directed paths. We assume, for the moment, that G is rooted at r and our goal is to build a directed depth-first search spanning tree rooted at r for G." There's no "rooted graph" defined there, only the qualifier rooted is emphasized. And your implication that a good journal can't publish a paper with a minor unclear part is rather silly. Anyway, changing in our article "These graphs have also been called rooted graphs." to "These graphs have also been called rooted." would be in line with the source, but it's of course rather elliptic. JMP EAX (talk) 19:05, 23 July 2014 (UTC)

Merge?

What I'm wondering is why we need three separate articles, this one, rooted graph, and flow graph for what are all the same thing or very close to the same thing. Maybe they should be merged? (I think, if we do merge, that rooted graph should be the primary name — the name here and the flow graph name are both too specific to a particular application.) —David Eppstein (talk) 19:58, 23 July 2014 (UTC)

I've been thinking to suggest something like that too, but I have some reservations. The issue of merging flow graph and accessible pointed graph (APG) is probably the easiest to decide because they're both relatively narrow notions, meaning consistently defined across authors. The only variation for the flow graph def I found is the single-sink issue, and APG probably has no def variations. But ironically I couldn't find a single paper/book to notice APG and flow graph are the same. Actually, I'm not sure there is even a source to explicitly link APGs with rooted [di]graphs, but I found like 3+ papers saying RDGs and flow graphs are the same thing. Hopefully nobody will quibble that linking these with APG is WP:OR. ¶ The issue that gives me pause in merging all three pages is that rooted graph (as I largely rewrote it, heh) is really talking about two+ notions, because (in all the sources I found) the rooted digraph is not defined as a straightforward/trivial lifting of the notion for undirected graphs, but adds the [directed] reachability requirement. So it's more of a case of names being similar, i.e. more like a WP:DABCONCEPT page. Never mind the variations, like multiple roots etc. that both of these notions have. I have't read Joel Spencer's book besides the definition he uses, but there appears to be non-trivial material about multi-rooted undirected random graphs. There is also a fair bit that can be said about reducible flow graphs (RFGs); there are at least 5 equivalent characterizations of those (see the papers I added to interval (graph theory)), and the notions introduced by at least two of these characterizations (intervals and natural loops) have practical applications too, so they appear in most compiler textbooks. Plus there's stuff like doi:10.1145/640128.604141 about RFGs and some algorithms too. But these things have little in common with the undirected case (or the variations thereoof). So, I'm not sure that everything should go on one page; at least reducible flow graphs seem to warrant a separate/sub-page. ¶ To conclude my equivocation somehow, perhaps merging APG with flow graph but leaving rooted graph as a separate, DAB-ish page and also putting most "hardcore" stuff about RFGs to a separate article is the best way to go. (By the way, I've added a heading for this merge issue above your post. I hope that's okay.) JMP EAX (talk) 20:57, 23 July 2014 (UTC)

I've actually tried to merge all three at User:JMP EAX/draft merge. Let me know what you think, and actually feel free to improve it and/or paste it in the rooted graph page if it seems reasonable. I've left out a few bits from the APG article that I thought were dubious/unnecessary, including the confusion about the other meanings of "rooted graph" (which is now better explained in the lead as being less of an issue of confusion and more an issue of different notions for the undirected vs. directed case) and the "global source" issue discussed below this section. Other than that, unless I've accidentally missed something, I think I pulled everything else from the three existing pages. JMP EAX (talk) 22:27, 23 July 2014 (UTC)

The draft looks pretty good to me (modulo some minor copyediting). I'm probably not going to have much time in the next week or so to work on this, so please feel free to continue without much input from me. As long as they're so obviously the same, it doesn't much bother me that we don't have sources explicitly pointing out that these different names are really the same. —David Eppstein (talk) 22:47, 23 July 2014 (UTC)

"Global source"

Is the paper cited in support of that (rather plausible) terminology really talking about rooted [di]graphs (i.e. APGs) in general? The only occurrence of the phrase "global source" is in this passage (p. 687 in the journal): "It is worth mentioning that G-orientation should not be confused with the well-known st-orientation, which is widely used in graph theory and algorithms. (For its definition and applications, see, for example, [8, 13].) First of all, any st-orientation of a 2-connected plane graph has one and only one global source and sink, while this is not necessarily true in the case of G-orientation (although in G-orientation, each face has one source and one sink, which is similar to st-orientation)." The emphasis is all mine, there's none in the source. It seems to me that st-orientation is indeed an APG, but I'm not really seeing "global source" being defined there, other than to say the obvious thing that in an st-orientation "s" is normally the global source and "t" is the (global) sink... JMP EAX (talk) 22:12, 23 July 2014 (UTC)

An st-orientation is also acyclic, something not true of most of the other material here. Because of that (and the not-usually-mentioned assumption that they are finite), the requirement of having only one source and only one sink automatically implies that they can reach and be reached from everything else. —David Eppstein (talk) 22:49, 23 July 2014 (UTC)