Talk:Directed acyclic graph/Archive 1

Archive 1

Missing term definition

I can not find the term "bicycle" explained in the graph theory glossary.

Thanks for the heads up. I fixed this, and added some explanation and images to the pages describing it. Deco 00:17, 19 Jun 2005 (UTC)

Wikipedia Categories

Directed they are, but acyclic they are not ;-) Gabriel Wicke 09:02, 4 November 2005 (UTC)

There's a category that indirectly includes itself? Really? Deco 09:09, 4 November 2005 (UTC)

I don't know if there is, but there certainly could be. --Saforrest 04:14, 24 February 2006 (UTC)

But should most categories avoid directed cycles? If we had a cycle in the category tree, then all its vertices (categories) would have an identical set of "subarticles", say articles belonging to a category directly or indirectly. It is not good, generally. гык 07:08, 23 May 2006 (UTC)

Definition

"for any vertex v", I believe should be "for all verticies", because if any of the verticies are part of a cycle then the graph is not a DAG.

Longest path

Should we note that finding the longest path in a weighted graph is NP-hard, except for DAGs?

Marking visited edges

I think a depth-first search algorithm should mark nodes that are visited in order not to visit them again in DAGS as well. The algorithm will terminate in finite time, yes, but it can get out of hand real fast. Mauritsmaartendejong 17:50, 15 July 2007 (UTC)

I suppose that depends on how you traverse them. It's true that simple depth-first traversal of a DAG can require exponential time (for example for the graph made of a series of diamonds) and this bears mentioning. Dcoetzee 01:11, 16 July 2007 (UTC)

Sure. The magic seems to be in the term depth-first without iterative deepening. Perhaps someone can explain depth-first with iterative deepening, since this sounds to me as breadth first. And then again, I don't see how you could do a breadth first without marking the nodes which you have visited in some way. Mauritsmaartendejong 09:07, 17 July 2007 (UTC)

See Iterative deepening depth-first search. DFID consists of a sequence of depth-first searches, limited to an increasing sequence of depths. visits the frontier nodes in the same order as breadth first search but can use far less memory. It is effective in situations in which

1. the state space is so huge that it is not feasible to keep any data for all visited items (thus one cannot mark nodes as visited and one cannot store a BFS queue), and
2. the number of states increases exponentially with the depth of the search (so that the total time for all the iterations adds in a geometric series to be proportional to the number of nodes searched).

David Eppstein 14:05, 17 July 2007 (UTC)

Thanks. Still have a feeling I don't want to do this on my compiler dags. The worst case is deep dags rather than wide ones and re-traversing is going to give at least quadratic complexity. The article you gave only refers to trees, where revisits of nodes can only occur through re-traversing. In a DAG each node is going to be visited through all possible paths, no ? Mauritsmaartendejong 15:05, 17 July 2007 (UTC)

If you have enough space to store the whole DAG (as you likely do in a compiler), DFID is pointless. It is more for large state-space searches where the size of the graph is enormous or even infinite. Since it doesn't store any visited tags, you're correct, it would search each path. —David Eppstein 15:10, 17 July 2007 (UTC)

Is Weisstein's conjecture referenced in any peer-reviewed journal, or just on the web pages of Eric Weisstein? Isn't that a bit too much credit - even in bold letters —Preceding unsigned comment added by 71.217.7.79 (talk) 08:13, 9 March 2008 (UTC)

New Site w/Article Series

There is a series detailing development/implementation of a directed acyclic word graph, with open source code, at this site (dotnetperls.com). I don't know if it is Wikipedia-quality, but it ranks on Google searches, and offers code. There are 7 articles in the series.

Use of DAG's in versioning systems

I suggest to add a mention to the application of DAG's in versioning systems as in Git, Bitkeeper, Mercurial. Mariostorti (talk) 14:14, 8 June 2008 (UTC)

I second this call. Decentralized versioning systems are probably the most visible application of DAG's in modern programming environments. -- Stefan Majewsky (talk) 21:24, 9 January 2010 (UTC)

Getting a tree from a DAG

In the Properties section, it says "A DAG can be expanded to a forest of rooted trees using this simple algorithm [...]". Could anyone give a reference for a proof of that claim? —Preceding unsigned comment added by 150.214.239.21 (talk) 11:30, 9 February 2009 (UTC)

Directed acyclic graph beginners guide

i have come to this page a few times over the years to find out what one of these things is. However, the description is so high-level that i have never been able to actually understand what this thing is. So can i suggest a section on this page that starts from the groud-up and explains what this is. Please.

Imagine you wanted to explain this to a 12 year old and go from there. —Preceding unsigned comment added by 86.136.56.47 (talk • contribs)

A DAG is a special kind of graph, so the article focuses on the special conclusions one can make by knowing it is not only a graph, but more specifically directed, and also acyclic. To understand it, you must first understand what a graph is. In the beginning of this article, there is a link to Graph_(mathematics), which has the desired beginners guide. Maybe it should be made more clear that this is where to go if the article feels too complex. If you don't understand the article about Graphs, then maybe the problem after all isn't that it's too complex, but that it's too simple. Remember that since it's a mathematical concept, it really "is" not anything, but rather a way of thinking, or a mental concept used to build mental/theoretical models of something. Or perhaps you already think this way, but just don't have the vocabulary to express it. The first part in the Graph article is really just a vocabulary lesson. 129.16.29.83 (talk) 19:06, 15 October 2009 (UTC)

I disagree. It's perfectly possible to understand what a directed acyclic graph is without any prior knowledge of graph theory. And to say "it really is not anything, but rather a way of thinking" is simply not true. A DAG is not a weltanschauung or a philosophical doctrine. Qwfp (talk) 09:48, 17 October 2009 (UTC)

Qwfp, your criticism has a point, so let me rephrase it: A DAG is a mathematical concept or model. Understanding what a DAG is might be easier if one has previous knowledge of graph theory. Some terms used in this article are more thoroughly defined in Graph_(mathematics) which could make it useful to read that article first if one has difficulty to understand this article. It is perfectly possible to find the Graph_(mathematics) article from here since it's linked from the very first sentence, but since some users (see above) apparently have difficulties realizing they could be helped by reading this article first, I suggest it be made more clear, perhaps even include

Further information: Graph theory

or

Further information: Graph_(mathematics)

in the top.129.16.29.83 (talk) 18:42, 19 October 2009 (UTC)

I agree with the original entry in this section; when I came to this article I was completely lost. I'd add the {{see|Graph theory}} or the {{see|Graph_(mathematics)}} as most recently suggested, but I don't know which would be more correct or helpful. MeekMark (talk) 01:56, 20 May 2011 (UTC)

DAGs in epidemiology

I wondered if it would be appropriate to give an example of the use of DAGs in epidemiology. There is quite some literature on the subject. If no one more expert in this field has a go at this, perhaps I'll be bold and attempt to add a section. Is it reasonable to add a section of how these are applied in a specific field in this way? Any thoughts?Jimjamjak (talk) 00:26, 15 November 2011 (UTC)

Maybe something less application-specific about using DAGs to model causal relationships, and the connection to Bayesian networks and influence diagrams? That is how they are used in epidemiology, right? If we had a section on this general topic, some material that is more specific to the epidemiology application could also fit into it. The current placement of Bayesian networks within the data processing section seems a bit off. —David Eppstein (talk) 01:23, 15 November 2011 (UTC)

That sounds like a very sensible suggestion to me. You're right about the way that DAGs tend to be used in epidemiology. The first usage was in the late 1980s and although it is still not common practice, there is a growing body of researchers employing DAGs as a particularly useful way of identifying variables (i.e. any extraneous factor) that must be measured and controlled for in analysis of epidemiological data, as a way of dealing with possible confounding. I think I'd be able to write the epidemiological part of this, but I fear my lack of knowledge on Bayesian networks doesn't really put me in a position to start this more general section.Jimjamjak (talk) 10:25, 15 November 2011 (UTC)

DAGs are strict partial orders

The section titled "Partial orders and topological ordering" currently says that "Each directed acyclic graph gives rise to a partial order \leq". However, to be more exact, DAGs represet _strict_ partial orders. So, the \leq notation should be "<" and "partial order" should be replaced with "strict partial order" in that section. I'm not sure if this is too pedantic or not, but at least a mention of the strictness condition on the partial order would help here. — Preceding unsigned comment added by 2607:4000:200:13:C81B:819A:C731:A9AC (talk) 19:02, 8 October 2012 (UTC)

DAGs in class structure of object-oriented programming languages

It should be mentioned that multiple inheritance in class structure of OO languages like C++ also forms directed acyclic graph. Mclaudt (talk) 22:37, 15 March 2013 (UTC)

Please do. Maybe it would make sense as a paragraph in the partial order section, since the is-a relation for type hierarchies with multiple inheritance forms a partial order? —David Eppstein (talk) 23:02, 15 March 2013 (UTC)

Implementation?

But how do you implement a DAG or even a G (Graph)? - neither article describes how or even provides a pointer as far as I can tell. 98.169.58.20 (talk) 19:50, 15 April 2014 (UTC)The Arcadian

The things one implements are algorithms. DAGs are not algorithms. Perhaps you mean: how do you represent a graph in a computer? In which case see Graph (abstract data type). There is little in that subject that is specialized to DAGs, so it doesn't belong in this article. —David Eppstein (talk) 21:04, 15 April 2014 (UTC)