Talk:Directed acyclic graph

From Wikipedia, the free encyclopedia

Contents

[edit] 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)

[edit] 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)

[edit] 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.

[edit] Longest path

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

[edit] 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)

[edit] 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.

[edit] 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)