View source for Talk:Directed acyclic graph

{{GA|06:38, 26 May 2016 (UTC)|topic=Mathematics and mathematicians|page=1|oldid=722139796}}
{{annual readership|scale=log}}
{{Did you know nominations/Directed acyclic graph}}
{{DYK talk|8 June|2016|entry= ... that because of [[pedigree collapse]], some [[family tree]]s are better modeled mathematically as '''[[directed acyclic graph]]s''' than as [[Tree (graph theory)|trees]]?|nompage=Template:Did you know nominations/Directed acyclic graph}}
{{WikiProject banner shell|class=GA|vital=yes|1=
{{WikiProject Mathematics|priority=High}}
{{WikiProject Computer science|importance=High}}
}}
{{Archive box|auto=yes}}

==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. [[User:LuciusAeliusSejanus|LuciusAeliusSejanus]] ([[User talk:LuciusAeliusSejanus|talk]]) 12:29, 28 October 2016 (UTC)
:Although we have already taken significant efforts to make the article [[WP:TECHNICAL|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 Mathematics]]for 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. —[[User:David Eppstein|David Eppstein]] ([[User talk: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 {{User|David Eppstein}}. [[User:ImperfectlyInformed|<span style="font-family: Times">II</span>]] | ([[User_talk:ImperfectlyInformed|t]] - [[Special:Contributions/ImperfectlyInformed|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  <!-- Template:Unsigned IP --><small class="autosigned">—&nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/50.245.17.105|50.245.17.105]] ([[User talk:50.245.17.105#top|talk]]) 22:03, 2 January 2020 (UTC)</small> <!--Autosigned by SineBot-->
: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. —[[User:David Eppstein|David Eppstein]] ([[User talk: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.  <!-- Template:Unsigned IP --><small class="autosigned">—&nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/103.30.92.71|103.30.92.71]] ([[User talk:103.30.92.71#top|talk]]) 20:00, 21 November 2016 (UTC)</small> <!--Autosigned by SineBot-->
:The [[Ethereum]] article has no description on how it uses DAGs. Do you have published [[WP:RS|reliable sources]] that detail the connection between the blockchain data structure and the mathematical meaning described in this article? —[[User:David Eppstein|David Eppstein]] ([[User talk: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.
--[[User:Nanite|Nanite]] ([[User talk: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 [[WP:RS|reliable sources]] that detail the connection between the blockchain data structure and the mathematical meaning described in this article? —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 20:51, 16 July 2018 (UTC)

::{{ping|David Eppstein}} there appear to be various publications but none make a big deal out of it, which is understandable. Closest [https://arxiv.org/pdf/1802.07523.pdf 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?). --[[User:Nanite|Nanite]] ([[User talk: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: [https://ieeexplore.ieee.org/abstract/document/7312773/ this one] refers to transactions as a DAG in exactly the sense I was imagining.--[[User:Nanite|Nanite]] ([[User talk: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 [https://www.iota.org/get-started/what-is-iota]. The Iota Foundation has released some academic papers [https://www.iota.org/research/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? [[User:Shhh101|Shhh101]] ([[User talk: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 [[Wikipedia:General sanctions/Blockchain and cryptocurrencies|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? —[[User:David Eppstein|David Eppstein]] ([[User talk: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: [https://www.forbes.com/sites/shermanlee/2018/01/22/explaining-directed-acylic-graph-dag-the-real-blockchain-3-0/][https://arxiv.org/pdf/1804.10013.pdf][https://www.sciencedirect.com/science/article/pii/S2405896318328799][https://www.researchgate.net/publication/330880551_A_Comparative_Analysis_of_DAG-Based_Blockchain_Architectures] [[User:Shhh101|Shhh101]] ([[User talk:Shhh101|talk]]) 18:20, 24 August 2019 (UTC)

== DAG is not customary ==

Although it was conceived by Aho and Ullman <ref>{{cite book |last1=Aho |first1=Alfred |last2=Ullman |first2=Jeffrey |title=The Theory of Parsing, Translation, and Compiling |date=1972 |publisher=Prentice-Hall}}</ref>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. [[User:Mdmi|Mdmi]] ([[User talk:Mdmi|talk]]) 16:48, 10 December 2019 (UTC)
{{reflist-talk}}
:I have only ever seen it upper case. The first usage is less relevant than how people use it now. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 17:18, 10 December 2019 (UTC)
:This is the first time I've seen it written as dag (lowercase). [[User:BernardoSulzbach|BernardoSulzbach]] ([[User talk:BernardoSulzbach|talk]]) 00:02, 11 December 2019 (UTC)
:: In addition to ignoring the two dissenting voices here, it seems worth mentioning that {{u|Mdmi}}'s [https://en.wikipedia.org/w/index.php?title=Directed_acyclic_graph&diff=930336598&oldid=927179471 effort] also had terrible knock-on effects, destroying all en-dashes as well as other symbols.  Thanks {{u|BernardoSulzbach}} for reverting promptly. --[[User:Joel B. Lewis|JBL]] ([[User_talk:Joel_B._Lewis|talk]]) 20:42, 11 December 2019 (UTC)
:If {{u|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). [[User:BernardoSulzbach|BernardoSulzbach]] ([[User talk: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? [[User:Mdmi|Mdmi]] ([[User talk: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. [[User:BernardoSulzbach|BernardoSulzbach]] ([[User talk: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.  [[User:Zaslav|Zaslav]] ([[User talk: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.) —[[User:David Eppstein|David Eppstein]] ([[User talk: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.  [[User:Zaslav|Zaslav]] ([[User talk: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? —[[User:David Eppstein|David Eppstein]] ([[User talk: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.  [[User:Zaslav|Zaslav]] ([[User talk: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. —[[User:David Eppstein|David Eppstein]] ([[User talk: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.  [[User:Zaslav|Zaslav]] ([[User talk: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.
#  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.
#  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.
#  Search for "dag" or "directed acyclic graph" anywhere, subtracting 104 authors named "Dag", leaves 1819 papers.
#  Search for "acyclic directed graph" or "acyclic digraph" anywhere gives 331 items.
#  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.
#  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.  [[User:Zaslav|Zaslav]] ([[User talk: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 [https://www.lister-global.com/news/daggingsheep/], [https://www.wool.com/globalassets/wool/sheep/research-publications/welfare/non-invasive-management-practices/dealing-with-dag-factsheet-v3.pdf]. [[User:LachlanA|LachlanA]] ([[User talk:LachlanA|talk]]) 02:17, 6 December 2024 (UTC)
::https://www.youtube.com/watch?v=zH64dlgyydM —[[User:David Eppstein|David Eppstein]] ([[User talk: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. [[User:LachlanA|LachlanA]] ([[User talk: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. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 02:13, 6 December 2024 (UTC)
::Ahh!  Of course.  I should read more carefully.  Thanks for the prompt explanation. [[User:LachlanA|LachlanA]] ([[User talk:LachlanA|talk]]) 02:19, 6 December 2024 (UTC)