McGill University:
School of Computer Science
Winter 1997 Class Notes for 308-251

DATA STRUCTURES AND ALGORITHMS

Topic #30: DIRECTED ACYCLIC GRAPHS

Last modified: May 22, 1997


Table Of Contents

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:


Examples of Dags

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:

{1, 2, 3} --> {1, 2}

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:

Venn diagram Dag diagram

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:

Course Prerequesites 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:

Activity Network image with critical path and time

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)*alpha + (2/ (x+y)) ) * ( (x+y)*alpha )

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:

dag of Expression Tree

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.
{1,3,5,7} sticks for 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.


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:

topologically sorted dag order, all arrows travelling right

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
For all 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]

Pairs of u and v nodes in various colorings

Explanations:
  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,

    Image of grey nodes with cycle 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.


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.

Activity Network dag with topological sort order

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:

List of nodes v adjacent to u with associated times

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:

x, y, alpha, 2, x+y, 2/(x+y), (x+y)*alpha, A, Root

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:

Dag representation of NIM Game

After a topological sort of the dag,

Topologically sorted NIM Game

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:

1: 5, 2   -    2: 3, 4    -    3: 5    -    4: 5    -    5:

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:

1:    -    2: 1    -    3: 2    -    4: 2    -    5: 1, 3, 4

If we perform the same operation on the resulting dag, we get:

1: 2, 5    -    2: 3, 4    -    3: 5    -    4: 5    -    5:     Sorted!

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.


Links to related materials

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

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


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.

Best Viewed With Any Browser... but Lynx rules! This page is, largely, text-only-browser-friendly.


Last updated May 22, 1997 by Vincent Stephen-Ong

Copyright © 1997 by the CS-Lounge-People -- Albert Albala, Wing Yi Chan, Amy Chow, XiaoBo Fan, Vincent Stephen-Ong. All rights reserved. Reproduction of all or part of this work is permitted for educational or research use provided that this copyright notice is included in any copy. Disclaimer: this collection of notes is experimental, and does not serve as-is as a substitute for attendance in the actual class.