## Topic #30: DIRECTED ACYCLIC GRAPHS

Previous Topic | Next Topic

### Introduction

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.

### Examples of Dags

Let us first consider the following examples of dags:

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

The dag will look like:

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

Consider a (1, 3, 5, 7) NIM Game, as described in topic 11.

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.

### Topological Sorting of dags

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.

#### Example of a topologically sorted dag:

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

#### Proof by Construction:

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]

```

Explanations:

#### Time:

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

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

Explanation of max:

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.

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:

• 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"
```

Explanations:

Time: (|V| + |E|).

### Technical Remark:

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.

### Java Applet demonstration of a generic dag

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.

Sorry, but this demonstration requires a Java-enabled browser. It actually may be a good thing that you don't have such a browser (or if Java is disabled) since the Java applet contains many obnoxious sound-effects. If you want to download the source code anyway, you may:

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.

### References

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

### This Web page was created by:

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.