Talk:Directed acyclic graph/GA1

GA Review

Article (edit | visual edit | history) · Article talk (edit | history) · Watch

Reviewer: Chiswick Chap (talk · contribs) 16:04, 19 May 2016 (UTC)

I'll take this on. Chiswick Chap (talk) 16:04, 19 May 2016 (UTC)

General comments

This is a well-written and carefully-cited article with few obvious issues.

Some concepts like reachability are quite closely related to the DAG. Reachability, for example, might merit a diagram both to illustrate what it is, to demonstrate its relationship with DAGs, and to reinforce the message that DAGs are conceptually powerful. Transitive closure is another case where a diagram might do all those things: the Hasse diagram seems to apply to the second part of the section it is in, not the first, which might benefit from another diagram. Condensation looks to me like another case where a diagram would be very helpful, in fact the one at the top of that article might do the trick. (One might say that article was strongly connected to this one...)

Added new images for reachability/transitive closure (essentially the same thing) and condensation, and replace the lead image so that it can also cover topological ordering. —David Eppstein (talk) 01:31, 21 May 2016 (UTC)

Thanks! Chiswick Chap (talk) 08:38, 21 May 2016 (UTC)

Specific comments

The lead section should I think mention applications of DAGs, with linked mentions at least of computer science, scheduling, shortest path and other algorithms, data processing, family tree/genealogy, and data compression. All this would make sense as a paragraph to round off the lead by summarizing DAG applications.

I was holding off on doing this until the other changes went through, so that the updated lead would reflect any updates to the rest of the article, but now this is done. Actually, the lead already had a paragraph that attempted to summarize the applications section, but it did it without mentioning any of the specific applications. I replaced it with what I hope is a better application summary, and added another paragraph summarizing the section of the article on algorithms for DAGs. —David Eppstein (talk) 00:16, 26 May 2016 (UTC)

Main links might be useful in the Scheduling, Causal structures, and Data compression sections. The last of these should at least be wikilinked.

I don't know of a good main-link target (something that is primarily about the DAGs for these applications) for Scheduling or Data compression. I added a main link to Causal structures, and wikilinked "compressed representation" in the Data compression section. —David Eppstein (talk) 05:30, 25 May 2016 (UTC)

OK

The discussion of spreadsheets in the Scheduling section is perhaps not the ideal example in that context – a straightforward task scheduling example (like making a building) would be better. The discussion of spreadsheets is close to being repetitive, with both spreadsheet dataflow and dataflow programming languages getting a mention in the DP section, where the spreadsheet discussion would fit better: there's actually little difference between the spreadsheet and the dataflow programming (arguably the spreadsheet is an implementation of the latter) so perhaps we don't need separate bullets there. In fact, wouldn't text be better than a bulleted list there?

I expanded that section. There's actually a significant difference in how spreadsheets are used (a human changes one cell and the software automatically updates everything that depends on it) and how dataflow networks are used (a stream of data values is processed synchronously by the network, with inputs flowing into the source nodes of the network and outputs flowing out of the sink nodes of the network). The problem was the previous description of dataflow, which was inaccurate; I have rewritten it. But there are also significant differences between how DAGS are used to schedule human tasks like making a building (PERT charts, where the vertices represent milestones, edges represent tasks, and the scheduling computation involves longest paths) and to schedule sequential computational tasks like updating a spreadsheet (vertices represent tasks, edges represent ordering constraints, and the scheduling computation involves topological ordering) so I think it's important to describe both. I also removed the bullets in the processing network section. —David Eppstein (talk) 00:21, 25 May 2016 (UTC)

Understood, and many thanks. Chiswick Chap (talk) 08:15, 25 May 2016 (UTC)

"The transitive closure ... may be constructed" - I guess this is a correct formulation, but it isn't very comfortable to a non-mathematician. Could we not say "demonstrated", for instance?

I don't think so. The problem is for a computer to take as input a DAG and produce its output the transitive closure of a DAG. Creating one abstract object as output from another abstract-object input is constructing the output, not demonstrating the output. —David Eppstein (talk) 00:21, 25 May 2016 (UTC)

OK

"Dependency graphs without circular dependencies form directed acyclic graphs.[33]" - this sentence seems slightly out of place, not quite seeming necessary where it is after the more specific detail of makefiles, PERT charts etc, and perhaps fitting better into the DP section that follows it, which actually mentions dependency graphs. Perhaps a little more needs to be said on the matter, or perhaps the sentence just needs to be earlier in the paragraph. The spelling out of the full name of the DAG after the abbreviations also seems a bit surprising.

Moved much earlier in what is now three paragraphs, expanded, and put the full name earlier and the abbreviation later. —David Eppstein (talk) 00:21, 25 May 2016 (UTC)

Thanks

"Because no one can become their own ancestor," - seems a bit of an Easter egg; and it seems to be related to the previous section, Causal structures? I agree it relates to the sentence about graphs of matrilineal and patrilineal descent but even that is an aside in parentheses, the second in the paragraph. Perhaps the paragraph and concepts could be rearranged to suppress the asides or promote them to be part of the main story.

That link used to be relevant, but it was broken in the July 2015 merge of bootstrap paradox into another article. I was tempted to link All You Zombies but instead I just removed the wikilink. But I think it's important as an explanation for why these graphs are acyclic, not merely an aside. As for the connection between this section and the previous one on causal structures: maybe it needs clarification but all the "causal" examples are about probability or possibility of a causal connection, and not necessarily one that is sequential in time, while all the "history" examples are all about sequentiality with no probability (those events definitely happened). —David Eppstein (talk) 14:51, 21 May 2016 (UTC)

Ok, as long as it's had conscious thought!

Images

The 2 existing images are fine as they stand (and correctly licensed), but as mentioned above they could well be supplemented with other images to explain more of the subject.

Adding comment. The Images currently being used in the article seem to prefer the 'appearance' that DAGs have one start point and one end point, which is not the case. Since in general there can be multiple start points and multiple end points in general DAGs, without any cycles whatsoever, then it would be nice for this type of case to be represented in the article perhaps both in the images as well as in the text. Fountains-of-Paris (talk) 17:36, 23 May 2016 (UTC)

The images already had multiple sinks, but I added another image copied from polytree which has multiple sources. —David Eppstein (talk) 18:01, 23 May 2016 (UTC)

Many thanks to both. Chiswick Chap (talk) 18:16, 23 May 2016 (UTC)

I will mention here one small thing that won't obstruct progress to GA but did strike me could be done better. The image File:Graph Condensation.svg with the caption "The yellow directed acyclic graph is the condensation of the blue directed graph. It is formed by contracting each strongly connected component of the blue graph into a single yellow vertex." actually shows the contracted yellow components as LARGER than the expanded sets of blue components. I can see why this has been done (each yellow node 'contains' the strongly connected set of blue components) but still, having a visual which represents contraction as expansion is not ideal. I also don't much like the broad yellow arrows, but that's an aesthetic thing. Chiswick Chap (talk) 08:20, 25 May 2016 (UTC)

Contraction is a technical term that I should have wikilinked, to indicate that it does not have its more colloquial meaning involving size. I have added the wikilink to the caption and the corresponding article text. The big arrows show that the same phenomenon of one feature of the condensation coming from multiple features of the original graph happens at the edge level. But if you have ideas for a clearer way of depicting the correspondence between features of the original graph and features of the condensation, I'm open to suggestions. —David Eppstein (talk) 15:54, 25 May 2016 (UTC)

Ok, I'll see if I can think of something. Chiswick Chap (talk) 16:01, 25 May 2016 (UTC)

Summary

Rate	Attribute	Review Comment
1. Well-written:
	1a. the prose is clear, concise, and understandable to an appropriately broad audience; spelling and grammar are correct.
	1b. it complies with the Manual of Style guidelines for lead sections, layout, words to watch, fiction, and list incorporation.	Lead: ok; Layout: ok; weasel: ok; fiction: n/a; list: n/a
2. Verifiable with no original research:
	2a. it contains a list of all references (sources of information), presented in accordance with the layout style guideline.
	2b. reliable sources are cited inline. All content that could reasonably be challenged, except for plot summaries and that which summarizes cited content elsewhere in the article, must be cited no later than the end of the paragraph (or line if the content is not in prose).
	2c. it contains no original research.
	2d. it contains no copyright violations or plagiarism.
3. Broad in its coverage:
	3a. it addresses the main aspects of the topic.
	3b. it stays focused on the topic without going into unnecessary detail (see summary style).
	4. Neutral: it represents viewpoints fairly and without editorial bias, giving due weight to each.
	5. Stable: it does not change significantly from day to day because of an ongoing edit war or content dispute.
6. Illustrated, if possible, by media such as images, video, or audio:
	6a. media are tagged with their copyright statuses, and valid non-free use rationales are provided for non-free content.
	6b. media are relevant to the topic, and have suitable captions.
	7. Overall assessment.	Happy to award a GA to this interesting article, connecting mathematics to practical applications. I hope you feel that the changes made during the process were worthwhile improvements: for me, they've made the article clearer and a more effective summary of the topic. Chiswick Chap (talk) 06:30, 26 May 2016 (UTC)