Last modified: May 22, 1997

• Introduction
  • Basic Terminology
• Examples of Dags
  1. Partial Orders
  2. Prerequesite Tree
  3. Activity Network
  4. Expression Trees
  5. NIM Game
• Topological Sorting of dags
  • Example of a topologically sorted dag
  • Proof by construction
    • Explanations:
      1. Node is white
      2. Node is grey
      3. Node is black
  • Time (complexity)
  • Application Examples
    1. Activity Network
       • Completion time algorithm
       • Explanation of max
    2. Expression Tree
       • Expression evaluation algorithm
    3. NIM Game
       • Definition of Terms
       • Good/Bad node-marking algorithm
         • Explanations and Complexity
• Technical Remark
• Java Applet demonstration of a generic dag
• Links to related materials
• References
• Author Information

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.

Basic terminology:

• root: a node with no incoming edges.
• leaf: a node with no outgoing edges.

Let us first consider the following examples of dags:

1. Partial Orders
2. Prerequisite Tree
3. Activity Network
4. Expression Trees
5. NIM Game
   

1. Partial Orders:

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:

2. Prerequisite Tree:

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.

3. Activity Network:

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).

4. Expression Trees:

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:

( (x+y)* + (2/ (x+y)) ) * ( (x+y)* )

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.

5. NIM Game

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]

1. 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].

2. 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.

3. 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.

Application Examples

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: max (Time(v1)+Time(v1->u),...) over all v such that (v,u) is an edge.

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))

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:

• A node represents a position in the NIM game, such that:
  • a good node (G)== a win position in the game
  • a bad node (B)== a lose position in the game
• The directed edges represent reachable positions. For example, the arrow starting at the G node "2" and pointing to the B node "1" at the root indicates that we can reach the B node "1" from the G node "2" in one move (i.e.: that the two nodes are one position, or one turn in the gameplay, away).
• The rules for defining a "Good" node (G) and a "Bad" Node (B) are:
  • G: If we can reach >= 1 B node.
  • B: All reachable nodes areG nodes (i.e.: there are 0 reachable B nodes).

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"

• The line "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).
• The next line, "if (u,v) is an edge" narrows this down by accepting only those nodes which share an edge from u to v.

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.

• Source code
• The "My" package of tools (save in a directory called "My/")
• Sounds in .au format for applet (save in a subdirectory called "audio/")

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.

For more information on directed acyclic graphs consider these selected materials:

• Berman, Kenneth A. et al., Fundamentals of sequential and parallel algorithms. PWS Publishers, 1997: 744 pages.

  A general textbook with a good section on dags.

• Cormen, Thomas H., Charles E. Leiserson, Ronald L. Rivest. Introduction to Algorithms. The MIT Press, 1990: 485-488.

  In-depth description of directed acyclic graphs.

• Kessler, Christoph, et al. "Generating Optimal Contiguous Evaluation dags" Computer Languages. v21 num 2, July 1995: 113-127.

  For a discussion of how dags can be used for compiler optimization.

• Weiss, Mark Allen. Data Structures and Algorithm Analysis in C. Benjamin/Cummings, 1993: 284-288.

  Description of directed acyclic graphs.

• Albert Albala -- spin@cs.mcgill.ca
• Wing Yi Chan -- wchan@cs.mcgill.ca
• Amy Wai Yu Chow -- silly@cs.mcgill.ca
• Xiaobo Fan -- xbfan@cs.mcgill.ca
• Vincent Stephen-Ong -- zibalatz@cs.mcgill.ca

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.