Talk:Directed acyclic graph

Although it was conceived by Aho and Ullman ^[1]as an acronym, dag was written in lower case (like radar). In this form, it has become a standard computer-science term. I am accordingly changing the article's peculiar upper-case DAG to dag. Mdmi (talk) 16:48, 10 December 2019 (UTC)

I have only ever seen it upper case. The first usage is less relevant than how people use it now. —David Eppstein (talk) 17:18, 10 December 2019 (UTC)

This is the first time I've seen it written as dag (lowercase). BernardoSulzbach (talk) 00:02, 11 December 2019 (UTC)

In addition to ignoring the two dissenting voices here, it seems worth mentioning that Mdmi's effort also had terrible knock-on effects, destroying all en-dashes as well as other symbols. Thanks BernardoSulzbach for reverting promptly. --JBL (talk) 20:42, 11 December 2019 (UTC)

If Mdmi (or someone else) still wants to make this change, a better way to make the point rather than citing one paper which used "dag" would be to count "dag" and "DAG" ocurrences in a massive set of research documents and see if one comes out on top. However, DAG seems to be so much the preferred term that it is used even on patents (https://patents.google.com/patent/US8489765B2/en). BernardoSulzbach (talk) 21:11, 11 December 2019 (UTC)

I didn't notice the loss of special characters in the preview. My apologies; I should have done a diff. Unlike other commenters, I have always seen the word in lower case. It's in the authoritative algorithms textbook by Cormen, Leiserson, Rivest and Stein, for example. The only hint of DAG that I have encountered is a curious occurrence in the title of a paper by Diomidis Spinellis et al, the body of which consistently uses dag! Given our divergent experiences, it is clear that the article should mention both forms. Agreed? Mdmi (talk) 02:38, 12 December 2019 (UTC)

That is a much better reference for your side of the argument than the paper from 1972. I prefer Skiena's text (which used DAG) and have never given Cormen et al. much thought. I just retrieved Cormen et al. to check your claim and yes, they use dag (lowercase). I agree with a mention but would not change the article as I am fairly confident that frequency-wise DAG (uppercase) is more common and settling this argument requires some statistics. BernardoSulzbach (talk) 22:10, 14 December 2019 (UTC)

"DAG", not "dag", is what I've seen, but it is not used in graph theory aside from the computer science side, and it is an inaccurate name, as it is not an acyclic graph that is directed. The proper descriptive name, generally used in graph theory, is "acyclic directed graph" (or digraph), as it is a digraph without (directed) cycles. Zaslav (talk) 03:46, 4 May 2022 (UTC)

MathSciNet, a listing of mathematics papers only, has 677 hits for "directed acyclic graph", 240 for "acyclic digraph", and only 91 for "acyclic directed graph". I suspect that your personal experience with nomenclature in this area may not be reflective of the literature as a whole. A search for listings that included both "DAG" and "directed acyclic graph" found 224 of them. If we go to DBLP (a CS database, but with titles only, no reviews) searching for "directed acyclic graph" and "acyclic directed graph" produce identical results (sigh) but checking the results found only 33 of the "acyclic directed" ordering. There were only 18 hits for the exact phrase "acyclic digraph". So you appear to be correct that the DAG ordering is more strongly preferred in CS than in math, but incorrect that the ADG ordering is preferred in math. (I do agree that DAG should be uppercase in any formal context.) —David Eppstein (talk) 07:15, 4 May 2022 (UTC)

MathSciNet is (rightly) full of mathematical CS papers. You found 677 dag's and 331 adg's, which suggests adg is quite common. Is it important to demote "acyclic digraph"? All I am recommending is equal billing in the top line. Zaslav (talk) 02:51, 4 August 2022 (UTC)

Again, you are for some reason prioritizing pure math and some theoretical CS (what MathSciNet lists) over other fields that also study these graphs. Why? What justification is there for only counting some disciplines as the ones whose nomenclatural choices are relevant? —David Eppstein (talk) 05:26, 4 August 2022 (UTC)

But you are the one who is prioritizing. You are the one who only counts some disciplines as relevant. I do not understand your viewpoint. I understand your argument, but it is invalid on its face, according to your own data.

As for intro clutter, all common names should be given equal weight (but I don't think "digraph" is needed; I agree there). the pronunciation guide for DAG is clutter; it is much less important than common names. That and "digraph" can be put in the "also" paragraph. Again, I understand your argument but it seems invalid. Zaslav (talk) 09:45, 4 August 2022 (UTC)

The names do not have equal weight in the literature, and we should not misrepresent the literature by pretending they do. I agree re pronunciation. —David Eppstein (talk) 16:34, 4 August 2022 (UTC)

Good move about pronunciation. Your literature data would seem to justify "often", which does not mean a majority. Zaslav (talk) 07:23, 6 August 2022 (UTC)

I did my own MathSciNet search. I got different numbers, possibly because of a different search. Here are my conclusions, starting with the preliminaries.

1. MathSciNet (MSN) is not exclusively for non-CS math. It includes a very large number of CS articles because a lot of theoretical CS is math. There is a difference but it is very fuzzy.
2. Yes, few economics articles (for example) will appear in MSN. It seems safe for our purpose to say MSN covers math and theoretical CS pretty well.
3. Search for "dag" or "directed acyclic graph" anywhere, subtracting 104 authors named "Dag", leaves 1819 papers.
4. Search for "acyclic directed graph" or "acyclic digraph" anywhere gives 331 items.
5. My search includes all the citations from most papers (as they are listed in MSN) so the numbers might be inflated, but perhaps not much and perhaps about equally for both searches.
6. Conclusion: "often" is an overstatement.

Final conclusion: I was not convinced by your data (about 2:1 for the dags) but I am convinced by my data (about 6:1 for dags). Objection withdrawn. Zaslav (talk) 00:35, 7 August 2022 (UTC)

Note also that "dag" in lower case is already a word that DAGs should not be confused with , . LachlanA (talk) 02:17, 6 December 2024 (UTC)

https://www.youtube.com/watch?v=zH64dlgyydM —David Eppstein (talk) 02:21, 6 December 2024 (UTC)

The figures with the captions "A DAG" and "its transitive closure" seem to be the wrong way around. I would fix it myself, except the figures are names Tred-G.svg and Tred-Gprime.svg, which suggests that the one which I think is the transitive closure is really intended to be the original, and it isn't just that the figures were accidentally in the wrong order. LachlanA (talk) 02:11, 6 December 2024 (UTC)

You seem to be looking at the figures with captions "A DAG" and "its transitive reduction". The transitive reduction is not the same thing as the transitive closure. —David Eppstein (talk) 02:13, 6 December 2024 (UTC)

Ahh! Of course. I should read more carefully. Thanks for the prompt explanation. LachlanA (talk) 02:19, 6 December 2024 (UTC)

The current definition states that "A path in a directed graph is a sequence of edges having the property that the ending vertex of each edge in the sequence is the same as the starting vertex of the next edge in the sequence; a path forms a cycle if the starting vertex of its first edge equals the ending vertex of its last edge." I have three issues with the definition as stated:

• This definition does not give a path with zero edges a well-defined start or end vertex, which is a problem because the following paragraph states that "every vertex is considered to be reachable from itself (by a path with zero edges)."
• In graph theory, a path is typically defined to have distinct internal vertices, which is not specified in the current definition.
• A cycle is also defined to have distinct internal vertices.

The first two issues are maybe debatable, but I think it's important to specify that cycles must have distinct internal vertices. It would be fine to reformulate the definition as "a DAG is a directed graph with no closed walks", but the current definition is using terminology incorrectly. Tibia mariner (talk) 05:51, 22 November 2025 (UTC)

The current definition states that "If a vertex can reach itself via a nontrivial path (a path with one or more edges), then that path is a cycle". However, most definitions of path require vertices to be all distinct. This means that a cycle is not a path because the first and last vertex of a cycle are not distinct. I think this should be changed to "walk" rather than "path" so that it agrees with the most common definition of path. This would also be consistent with the existing article on reachability, which says that ${\displaystyle t}$ is reachable from ${\displaystyle s}$ if there exists a walk which starts with ${\displaystyle s}$ and ends with ${\displaystyle t}$.

@David Eppstein: It is true that the existence of a walk from ${\displaystyle u}$ to ${\displaystyle v}$ implies the existence of a path from ${\displaystyle u}$ to ${\displaystyle v}$, but the existence of a nontrivial walk from ${\displaystyle v}$ to ${\displaystyle v}$ does not imply the existence of a nontrivial path from ${\displaystyle v}$ to ${\displaystyle v}$. (The latter does not exist under the standard definition of path.) Tibia mariner (talk) 20:43, 30 December 2025 (UTC)

(You would also need to change the wording to "that walk contains a cycle" rather than "is a cycle". See my article edit, which was reverted.) Tibia mariner (talk) 20:50, 30 December 2025 (UTC)

That's not the definition of a path that I've generally used and seen. Invariable it allows length-zero paths with one vertex and no edge. Otherwise, for instance, the output for the starting vertex in the single-source shortest path problem would make no sense. —David Eppstein (talk) 20:53, 30 December 2025 (UTC)

Yes, I completely agree that length-zero paths are fine. My issue is that the current version talks about if "a vertex can reach itself via a nontrivial path (a path with one or more edges)". Tibia mariner (talk) 20:56, 30 December 2025 (UTC)

I don't think that paragraph is important enough to keep. If you try to reword it to avoid talking about nontrivial paths from a vertex to itself, it just boils down to a tautology. —David Eppstein (talk) 21:04, 30 December 2025 (UTC)

I'm fine with that outcome. Thanks for taking a look. Tibia mariner (talk) 21:08, 30 December 2025 (UTC)

@EulerianTrail: The most recent version of your definition edit contains this sentence: "If a vertex can reach itself via a directed walk, then that path is a directed cycle, so another way to define directed acyclic graphs is that they are the graphs in which no vertex can reach itself by a directed path." Please see this talk post regarding the usage of "path" in this context. Although terminology differs among authors, the standard on Wikipedia is that a path is defined to have all vertices distinct. A nontrivial walk with the same start and end vertex cannot be a path by definition, so "walk" should be used here. This is consistent with the existing article on reachability. Furthermore, your paragraph should clarify that this definition of DAG requires reachability by a nontrivial walk; every vertex can reach itself via a walk of length zero. Tibia mariner (talk) 19:52, 2 February 2026 (UTC)

@David Eppstein Every time I try to improve/fix the definition based on your suggestions, you remove it. You called the citation from the Bondy and Murty book "falsified and failed verification" which goes against WP:NPA. My edits are made in good faith WP:GF. Page 25 defines "acyclic graph is one that contains no cycles". At the top of page 172, it states cycles, path, tours are similarly defined for digraphs. It also explains on page 172 diconnected which is the opposite of acyclic. I hope these comments help clear up the misunderstandings. Would you like to provide some productive feedback or perhaps even fix up a definition with citations here? Thanks for your contributions, David; I know you put in a lot of time into this. EulerianTrail (talk) 03:27, 4 February 2026 (UTC)

Page 25 is about undirected graphs. Pages 171-172 do not discuss acyclicity at all. So these pages of this book do not provide a source for using reachability as an alternative definition of directed acyclic graphs, because they do not define directed acyclic graphs in that way nor discuss directed acyclic graphs at all.

What I am wondering now is whether you did a cursory search for the terms in your claims without actually checking, whether you checked but failed to understand what you read, or whether you trusted an LLM to find a source for you and are only now discovering that trust to be misplaced. The use of the access-date parameter on a citation template that does not allow that parameter is also odd; where did that come from? —David Eppstein (talk) 06:54, 4 February 2026 (UTC)

The access date parameter is an option when filling out the template. I occasionally forget to ignore that box when using a book as a source as I try to fill out the citation. It appears that we disagree on our interpretation of the source. EulerianTrail (talk) 08:17, 4 February 2026 (UTC)