Can someone explain in simple terms to me what a Directed acyclic graph is? I have looked on Wikipedia but it doesn't really make me see its use in programming.
views:
243answers:
7
+8
A:
graph = structure consisting of nodes, that are connected to each other with edges
directed = the connections between the nodes (edges) have a direction: A -> B is not the same as B -> A
acyclic = "non-circular" = moving from node to node by following the edges, you will never encounter the same node for the second time.
Basically a directed acyclic graph is a tree.
Roland Bouman
2010-02-17 19:29:41
I understand what nodes are. When you say "edge", do you mean an arrow pointing from Node A to Node B?
Zubair
2010-02-17 19:30:31
Better explanation. So what has this got to do with programming? Is it related to functional programming?
Zubair
2010-02-17 19:32:01
It's typically represented by an arrow, but it's really just that there is a relation between A and B. In your program this might be a true value in an adjacency matrix at the indices representing those two nodes.
tvanfosson
2010-02-17 19:32:34
Yes, "edge" is the arrow. If you imagine a larger graph, one which IS cyclic, as a 3-dimenional object, the "edge" term makes more sense.
James Curran
2010-02-17 19:33:59
Trees are what first came to mind when I thought of how a directed acyclic graph might apply in programming, but there's a minor technicality: trees don't have to be directed.
htw
2010-02-17 19:34:21
Zubair, the relation to programming is that many data structures take the form of a graph. So some components in your code play the role of node, some of edge. For example, a parse tree can be seen as a directed acyclic graph: the nodes are the operators and constants, and the edges represent association. For example, parsing 1+2*3 would give you a tree with + as root, 1 as leftmost child, * as rightmost child, and * would have 2 as leftmost child, and 3 as rightmost child
Roland Bouman
2010-02-17 19:37:30
This I understand, thanks Roland. So its really discussign a type of data structure, is that correct? Or is it program flow?
Zubair
2010-02-17 19:39:25
Not to mention that a directed acyclic graph doesn't have to be one directed tree, but could be many. Of course, a connected directed acyclic graph is a directed tree.
David Thornley
2010-02-17 19:39:36
All directed trees are DAGs, but not all DAGs are trees. The DAG A->B, A->C, B->C cannot be represented as a tree since node C has more than one parent.
Jason S
2010-02-17 19:39:55
Zubair, well, the term graph really is in the field of mathematics. The graph and terminology can sometimes be used to express the nature of a data structure, so it is a useful analogy. But I think the graph analogy could equally well be used to talk about program flow. Take again the parse tree example: the parse tree is a data structure, and to evaluate it (=program flow) you have to walk the graph, executing the expressions as you encounter them whilst walking the tree.
Roland Bouman
2010-02-17 19:44:08
Actually, a tree is a UNdirected graph that is acyclic and connected. If you erase the arrows from a DAG, you won't necessarily get a tree. That's because a pair of nodes can have more than one path between them.
Derek Ledbetter
2010-02-17 19:59:01
Directedness of edges is not the only feature separating DAGs from trees. A DAG can have more than |V|-1 edges, unlike a tree. For instance, A->B, A->C, B->D, C->D is a DAG but clearly not a tree since it has the same number of edges and nodes.
stubbscroll
2010-02-24 10:17:23
+1
A:
A directed acyclic graph is useful when you want to represent...a directed acyclic graph! The canonical example is a family tree or genealogy.
Jonathan Feinberg
2010-02-17 19:33:49
+5
A:
Hi
Directed Acyclic Graphs (DAG) have the following properties which distinguish them from other graphs:
- Their edges show direction.
- They don't have cycles.
Well, I can think of one use right now - DAG (known as Wait-For-Graphs - more technical details) are handy in detecting deadlocks as they illustrate the dependencies amongst a set of processes and resources (both are nodes in the DAG). Deadlock would happen when a cycle is detected.
I hope this helps.
cheers
Andriyev
2010-02-17 19:36:38
Andriyev, +1 for the deadlock example. This is in fact used by MySQL's InnoDB engine, and they call it a "wait-for-graph", as in, "that row has to wait for the lock on that row to be released"
Roland Bouman
2010-02-17 19:40:16
yes, you are dead right with the name - Wait For Graph. Some how missed that. Updated the response. :)
Andriyev
2010-02-17 19:43:44
How do they know there is a dependency? Is it by checking to see if two nodes have a common ancestor?
Zubair
2010-02-18 08:38:57
This link -http://www.cis.temple.edu/~ingargio/cis307/readings/deadlock.html has more technical details.
Andriyev
2010-02-18 14:10:05
+2
A:
Graphs, of all sorts, are used in programming to model various different real-world relationships. For example, a social network is often represented by a graph (cyclic in this case). Likewise, network topologies, family trees, airline routes, ...
tvanfosson
2010-02-17 19:37:01
+4
A:
Example uses of a directed acyclic graph in programming include more or less anything that represents connectivity and causality.
For example, suppose you have a computation pipeline that is configurable at runtime. As one example of this, suppose computations A,B,C,D,E,F, and G depend on each other: A depends on C, C depends on E and F, B depends on D and E, and D depends on F. This can be represented as a DAG. Once you have the DAG in memory, you can write algorithms to:
- make sure the computations are evaluated in the correct order (topological sort)
- if computations can be done in parallel but each computation has a maximum execution time, you can calculate the maximum execution time of the entire set
among many other things.
Outside the realm of application programming, any decent automated build tool (make, ant, scons, etc.) will use DAGs to ensure proper build order of the components of a program.
Jason S
2010-02-17 19:43:26
+1 for mention of causality. This comes up a lot when you need to represent a complex systems where the output of one process is the input for one or more other processes.
Alex Feinman
2010-02-17 20:03:19
+2
A:
Several answers have given examples of the use of graphs (e.g. network modeling) and you've asked "what does this have to do with programming?".
The answer to that sub-question is that it doesn't have much of anything to do with programming. It has to do with problem solving.
Just like linked-lists are data structures used for certain classes of problems, graphs are useful for representing certain relationships. Linked lists, trees, graphs, and other abstract structures only have a connection to programming in that you can implement them in code. They exist at a higher level of abstraction. It's not about programming, it's about applying data structures in the solution of problems.
Jonathon
2010-02-17 19:45:39
Can be implemented in programming. Yes, I like that, as graphs exist in the real world independant of computers!
Zubair
2010-02-18 08:44:32
+1
A:
I assume you already know basic graph terminology; otherwise you should start from the article on graph theory.
Directed refers to the fact that the edges (connections) have directions. In the diagram, these directions are shown by the arrows. The opposite is an undirected graph, whose edges don't specify directions.
Acyclic means that, if you start from a random node X and walk through all possible edges (following the edge directions), you will not return to X. Naturally, this is only possible in a directed graph (otherwise you could go from node X to some node Y, then back to X).
Several applications:
- Spreadsheets; this is explained in the DAG article.
- Revision control: if you have a look at the diagram in that page, you will see that the evolution of revision-controlled code is directed (it goes "down", in this diagram) and acyclic (it never goes back "up").
- Family tree: it's directed (you are your parents' child, not the other way around) and acyclic (your ancestors can never be your descendant).
Johannes Sasongko
2010-02-17 20:04:46