Talk:Directed acyclic graph

Intelligibility

The introduction needs a major re-write to make it intelligible to the lay reader. It might make sense in a mathermatics text book but comes across as so much gobbledegook to someone wishing to know what a DAG is and how it might be used. LuciusAeliusSejanus (talk) 12:29, 28 October 2016 (UTC)

Although we have already taken significant efforts to make the article as accessible as possible, I'm sure more improvement is possible, and specific suggestions for improvement would be welcome. However, "as accessible as possible" does not and cannot mean "instantly understandable to the mathematically illiterate", and vague complaints without any specific ideas for improvement are not helpful. Please read the FAQ on Wikipedia talk:WikiProject Mathematicsfor more context concerning the type of complaint you seem to be making, which is not new (Royal Road#A metaphorical “Royal Road” in famous quotations) and is (as the link suggests) a frequently asked question on many mathematics articles. —David Eppstein (talk) 20:01, 28 October 2016 (UTC)

My two cents: in the scheme of impenetrable math articles, this one isn't bad. Which is great, considering that it's a pretty practical topic. Nice work David Eppstein (talk · contribs). II | (t - c) 03:07, 27 June 2018 (UTC)

agreed

this webpage has a much much better description of what a DAG is and how it differs from other graphs https://medium.com/fantomfoundation/an-introduction-to-dags-and-how-they-differ-from-blockchains-a6f703462090 — Preceding unsigned comment added by 50.245.17.105 (talk) 22:03, 2 January 2020 (UTC)

Perhaps it's worth reminding editors that Wikipedia:General sanctions/Blockchain and cryptocurrencies applies, in particular to links that look like they are spam to promote someone's blockchain consulting business. —David Eppstein (talk) 22:20, 2 January 2020 (UTC)

Blockchain

Probably should be added reference to some Blockchain technology such as Ethereum

Before you can find any blocks, however, your computer needs to go through a process called “building a DAG”. This DAG (short for “Directed Acyclic Graph”) is a large data structure (~1GB) required for mining, intended to prevent ASIC machines (“Application Specific Integrated Circuits”) from being mass manufactured for mining ether. Its goal is to protect miners like yourself, so that you will only ever need your home computer to remain competitive. The DAG should take about 10 minutes to generate and as soon as it finishes, Geth will start mining automatically. — Preceding unsigned comment added by 103.30.92.71 (talk) 20:00, 21 November 2016 (UTC)

The Ethereum article has no description on how it uses DAGs. Do you have published reliable sources that detail the connection between the blockchain data structure and the mathematical meaning described in this article? —David Eppstein (talk) 21:09, 21 November 2016 (UTC)

In Bitcoin there are two important DAGs:

• The set of all transactions forms a DAG. On one end of the DAG (source or sink depending on definition) we have all the coinbase transactions. An important subset of this --- all transactions included in the blockchain ("confirmed") --- *also* forms a DAG. Not all cryptocurrencies have a transaction DAG, however, as some are balance-based (like Ethereum).

• The blockchain itself is technically a DAG but we can give it the more restrictive classification of being an Arborescence (graph theory), with root in the genesis block (of course every arborescence is also a DAG). Normally of course we're only interested in the main chain and not the orphaned branches. Even ignoring the orphans, we can consider all the chain forks (Bitcoin Cash, etc.) which share the same genesis root and so the set of all forks' blockchains is a nice arborescence too.

--Nanite (talk) 19:52, 16 July 2018 (UTC)

Let me repeat, since you appear to be answering a different question than the one that is most important here: Do you have published reliable sources that detail the connection between the blockchain data structure and the mathematical meaning described in this article? —David Eppstein (talk) 20:51, 16 July 2018 (UTC)

@David Eppstein: there appear to be various publications but none make a big deal out of it, which is understandable. Closest here perhaps, though it is in a slightly different meaning. And to be honest my statement "all transactions forms a DAG" is vague, as depending on definitions it's actually a multigraph (multi-DAG?). --Nanite (talk) 00:56, 17 July 2018 (UTC)

Edit add: I don't think it's really exciting or worth mentioning in this article, to be honest.

Edit add 2: this one refers to transactions as a DAG in exactly the sense I was imagining.--Nanite (talk) 01:03, 17 July 2018 (UTC)

Distributed Ledger Technology

Since the blockchain comment above there have been several DLTs that specifically use DACs as a core technology, distinct from blockchain (a series of blocks). The most notable of these is IOTA . The Iota Foundation has released some academic papers and there has been considerable discussion of the DAC technology in the crypto press and outside. Rather than just jumping in and adding a "contentious" DLT section to the main page, I wonder if there could be some discussion here first? Shhh101 (talk) 17:27, 24 August 2019 (UTC)

My impression is that 99% of attempts to add content related to blockchain is actually spam for cryptocurrencies. (As such, you should be aware that these topics are under additional editing restrictions beyond the usual norms for Wikipedia behavior.) Can you persuade me that this specific one that you want to add stands out in any way from all the rest in its Wikipedia notability (coverage in reliable sources independent of the subject) and relevance for the general topic of abstract directed acyclic graphs? —David Eppstein (talk) 17:36, 24 August 2019 (UTC)

Well I am not at all interested in spamming Wikipedia about any cryptocurrency, as it would be somewhat futile endeavour. However, it would be possible to mention that the technology is in use in several DlT projects, and give an outline of the proposed benefits, without necessarily mentioning particular projects. A quick Google search turns up a number of RS articles and papers on the topic, eg: Shhh101 (talk) 18:20, 24 August 2019 (UTC)

DAG is not customary

Although it was conceived by Aho and Ullman 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)

References

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)

Transitive closure graphs switched?

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)

Definition uses "cycle" incorrectly

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)

Issue with use of "path" in definition

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 $t$ is reachable from $s$ if there exists a walk which starts with $s$ and ends with $t$.

@David Eppstein: It is true that the existence of a walk from $u$ to $v$ implies the existence of a path from $u$ to $v$, but the existence of a nontrivial walk from $v$ to $v$ does not imply the existence of a nontrivial path from $v$ to $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)

Reachability definition

@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)

Reverted edit...

If you look at the mode=cs2 removals on individual templates, that fixes their CS1 maint: overridden warnings. MathWorld and similar templates are just wrappers on cite web / cite book / etc and there's a page-wide override to CS2 that auto-applies to all such templates (via their base CS1 templates), so nothing changed with their actual presentation AFAICT, and I left the page-wide override set to CS2. I may have missed one that was suddenly using full stops, but generally all of the source templates wrap a CS1. So that part wasn't actually a formatting change, just a maint one and a simplification of a few refs.

I do agree with you about rp itself being an abomination, I consider it less distracting but that's just me...

Ignoring the removal of the partial harvard citing, I found other weirdness going on there:

• Somebody might want to glance at the ref that's duplicated entirely in the first 10 (Bang-Jensen) with different page numbers and an ISBN one digit off between them (the hardback vs. paperback or physical vs. PDF version? I dunno) along with the single harvard ref to one of those two which appears to exist to point to page 38 when the ref itself is already 36-39 which is sufficiently narrowed down for verification purposes
• Why the Cormen et. al. harvard refs don't properly link to their full cite like the other harvard refs... I think those were what got me going on the editing here in the first place because my vision isn't fantastic and I didn't spot Cormen in the reflist with no link after a couple of skims.
• Similarly, the Skiena harvard links work or I'd never have spotted it in the middle of a long sentence footnote in front of the full cite which presumably doesn't apply to the other two and should probably be an actual footnote attached to that single use so the formatting isn't weird for that one cite.

Hopefully some of those help, I don't really care all that much either way so it's up to you.

Cheers, A Shortfall Of Gravitas (talk) 05:19, 25 July 2026 (UTC)