Last modified: May 22, 1997
Directed acyclic graphs are directed graphs with no cycles. Called dags, they are an important class of graphs, being part tree, part graph, and having many applications, such as those involving precedence among "events". Using dags, many problems in graphs become simpler, such as critical path analysis, expression tree evaluation, and game evaluation. The property of dags which is optimal for these problems is their ability to be topologically sorted using depth-first search.
Let us first consider the following examples of dags:
Let us first consider a simple example involving two sets: {1,2,3} and {1,2}, where the partial order relation is containership. The relation of {1,2,3} containing {1,2} can be represented by a dag as follows:
A larger and more complicated example can be expressed by using a visual representation of the sets. The containership relation of the sets: A, B, C, D, E, and F can be represented by the following Venn diagram and dag:
Dags can model prerequisite trees, such as those used for course ordering. For example, at McGill, CS 250 must be taken before CS 251 and, after adding in a few other Computer Science courses, we can produce the following dag:
This image was modified from one found in Topic#1: Abstract Data Types, from the discussion of the graph-coloring problem.
Another use of dags is in modelling activity networks, in which each node represents a task to be completed and the directed edges refer to the next tasks and their associated times of completion, as in the following graph:
An activity network has at least one critical path, which is the longest sequence of tasks in the project, and therefore the time needed to complete the project. Examples of activity networks are snow removal (coordination of different vehicles along different streets), cooking pasta (ordering of food purchases and cooking times of various ingredients), and software engineering (interdependence of modules and their deadlines).
Dags can represent expression trees, which can be used to optimize compilers. Compared to other expression trees, dags use less nodes in the trees. Consider the expression:
Here, we have one root. Each leaf corresponds to an operand (such as x, y), and each internal node to a subexpression (such as x+y). An internal node has associated with it an operator (such as +) which operates on the left and right subtree expressions.
Question: How do we evaluate the expression dag?
It seems that we should evaluate
it from the bottom up. The actual technique is to traverse the dag via
a variation on the
depth-first search (DFS) called the topological sort, as
explained below.
A more efficient solution that allows one to play NIM perfectly, other than that of a game tree, would be to employ a dag, where each node represents a situation, as explained below.
A topological sort is an ordering of vertices in a dag such that, if there is path from node u to node v, then v appears after u in the ordering. Therefore, a cyclic graph cannot have a topological order. A topological sort of a graph can be viewed as an ordering of its vertices along a horizontal line so that all directed edges go in one direction.
Referring to the earlier example of the dag representation of the containership relation of a Venn Diagram, a corresponding topological sort would appear as follows:
Note that all of the edges are pointing in the same direction. In general, the vertex order produced by a topological sort is not unique. We could reorder the nodes while maintaining the property of a topologically sorted dag (for example, we could switch the positions of A and D).
We can prove by construction that a dag can be topologically sorted as follows. First, we employ the DFS algorithm and list the nodes in order of f[u]. We then add, after the line "f[u] = Time", an additional line of "Output u", and the result is the topological sort algorithm.
Now, at any node u edges u->v, v listed before u 1) v is white means f[v] < f[u] 2) v is gray is an impossible case 3) v is black means f[v] < f[u]
If the node v is white, then, at time d[u], there is a path of white nodes from u to v. By the white path theorem, vertex v is a descendant of u in the depth first tree, therefore f[v] < f[u].
If the node v is grey,
this means it has already been examined. Looking at a previously-examined node implies that there is a cycle in the graph, which is impossible in the case of a dag. |
If the node v is black, this means that v is completely finished with, which is expected.
The topological sort algorithm is essentially the same as a
DFS. If we
assume that the added line Output(u)
takes Time O(0), then we
have the following time for the topological sort algorithm:
Time= O( |E| + |V| ), as further explained in topic#26: depth-first search.
1. Activity Network:
We want to know how long it takes to complete the project defined by an activity network. First, we topologically sort the dag on the left resulting in the output to the right.
The nodes in the output are numbered from right to left, 1 to n. We then perform the following algorithm:
Time(1)=0 for u=2 to n Time(u)=max(Time(v)+Time(v->u)) Output(Time(n))
For a node u, the Time(u) is defined as: |
2. Expression Tree
To answer the earlier question regarding the evaluation of an expression tree in linear time, we can topologically sort the dag:
After numbering the nodes from left to right, going from 1 to n, we can evaluate the expression as follows:
for u=1 to n do if (u is an internal node) then Value(u)=Value(left[u]) . Operator(u) . Value(right[u]) Output(Value(n))
3. NIM Game
In actuality, a game tree is not the best way to approach the solution of the NIM Game. We can represent the (1, 3, 5, 7) NIM Game as a dag like so:
After a topological sort of the dag,
we can perform the following linear time algorithm in order to mark the nodes as G and B (after having once again numbered the nodes from 1 to n from left to right):
node[1] = "B" for u=2 to n do node[u] = "B" for v=1 to u-1 do if (u,v) is an edge if (node[v] == "B") then node[u] = "G"
Explanations:
for v=1 to u-1 do
"
loops through all of the nodes other than u that are eligible to be neighbors
of u (the valid nodes have been narrowed down to those less than u
because of the property of the topological ordering).
if (u,v) is an edge
"
narrows this down by accepting only those nodes which share an edge
from u to v.
Time: (|V| + |E|).
Suppose we are given a dag in a tabular form, where we are given information regarding the neighbors of each node as follows:
The problem is that we would like to have the neighbor nodes sorted. Using linear time, we can sort the neighbors by reversing the directions of the edges. The technique is to re-list the nodes, and then traverse from left to right the neighbor nodes originally given, adding the originator node on the right side of the new list as follows:
If we perform the same operation on the resulting dag, we get:
The result is a dag with neighbor nodes sorted.
The following applet allows you to construct a dag by building nodes and edges. Choose your operation on the right and click to insert a node or click and drag to add a directed edge. Selecting the same node or edge twice removes it. When you are done, click on the Topological Sort button and the Step Control will appear, allowing you to set the pace of the topological sort demonstration. If the applet gets messy for some reason (which it should not, but just in case) then just move the mouse pointer outside of the boundaries of the applet.
Note: This applet may take a few seconds to initialize; please be patient. You do not need to wait for all of the sounds to load, but the sounds do make the applet more interesting. As soon as the main panels appear, you may begin.
Some of the sounds were converted from .wav to .au format using Tony Crude's "Wav2Au" java applet, downloadable at Tony's Stuff. I release this code freely to the public domain and ask only that if you actually use anything you find here, to please include a reference to Vincent Stephen-Ong.
Research Interests: Graph Theory. | Spiram Pemmaraju of the University of Iowa lets you download research papers, including two which have to do with stack and queue layouts of dags. |
UF/CISE Technical reports 1990 | Doowon Paik of the University of Minnesota has a site at the University of Florida which deals with a practical use of dags: circuit design. Your browser needs to support PostScript files. |
An Oklahoma State online lecture | Nick Street of the University of Oklahoma provides a straightforward explanation of graphs, including dags. Many definitions are provided. |
An online lecture from USB | J. Richard Bradley of Stony Brook University provides a more in-depth description of graphs, including dags. Many interesting examples are provided. |
STS: A simple tool for scheduling | Daniel Ortiz-Arroyo of Oregon State provides a detailed description of how a dag was used to create a scheduling program. |
For more information on directed acyclic graphs consider these selected materials:
A general textbook with a good section on dags.
In-depth description of directed acyclic graphs.
For a discussion of how dags can be used for compiler optimization.
Description of directed acyclic graphs.
Wing Yi was in charge of the graphics and diagrams. Albert searched for Internet links and print references. Vincent wrote the java applet and generated some formula-related graphics using latex2e and latex2html. Xiaobo converted all of the group members' class notes, two double-sided audio tapes, and personal research into the text for the webpage. Amy converted and edited the text and put everything together into HTML. Everyone contributed to the extensive editing and revising of the webpage, as well as other miscellaneous tasks.
This page is, largely, text-only-browser-friendly.