Previous    Next

### DAGs

##### Screenshot DAG model of Fibonacci computation

The tree at the top shows the dependence of computing each Fibonacci number on computing its two predecessors. The DAG at the bottom shows the same dependence with only a fraction of the nodes.

```void traverseR(Graph G, int v)
{
visit(v);
for (int t = A.beg(); !A.end(); t = A.nxt())
traverseR(G, t);
}
```

We rarely use a full traversal of this kind, however, because we normally want to take advantage of the same economies that save space in a DAG to save time in traversing it (for example, by marking visited nodes in a normal DFS). The same idea applies to a search, where we make a recursive call for only one link incident on each vertex. In such an algorithm, the search cost will be the same for the DAG and the tree, but the DAG uses far less space. Because they provide a compact way to represent trees that have identical subtrees, we often use DAGs instead of trees when we represent computational abstractions. In the context of algorithm design, the distinction between the DAG representation and the tree representation of a program in execution is the essential distinction behind dynamic coding (see, for example, Screenshot and Exercise 19.78). DAGs are also widely used in compilers as intermediate representations of arithmetic expressions and programs (see, for example, Screenshot) and in circuit-design systems as intermediate representations of combinational circuits.

##### Screenshot DAG representation of an arithmetic expression

Both of these DAGs are representations of the arithmetic expression (c*(a+b))-((a+b))*((a+b)+e)). In the binary parse tree at left, leaf nodes represent operands and internal nodes each represent operators to be applied to the expressions represented by their two subtrees (see Figure 5.31). The DAG at right is a more compact representation of the same tree. More important, we can compute the value of the expression in time proportional to the size of the DAG, which is typically significantly less than the size of the tree (see Exercises 19.112 and 19.113).

Along these lines, an important example that has many apps arises when we consider binary trees. We can apply the same restriction to DAGs that we applied to trees to define binary trees. Definition 19.6 A binary DAG is a directed acyclic graph with two edges leaving each node, identified as the left edge and the right edge, either or both of which may be null. The distinction between a binary DAG and a binary tree is that in the binary DAG we can have more than one link pointing to a node. As did our definition for binary trees, this definition models a natural representation, where each node is a structure with a left link and a right link that point to other nodes (or are null), subject to only the global restriction that no directed cycles are allowed. Binary DAGs are significant because they provide a compact way to represent binary trees in certain apps. For example, we can compress an existence trie into a binary DAG without changing the search implementation, as shown Screenshot and Program 19.5.

##### Screenshot Binary tree compression

The table of nine pairs of integers at the bottom left is a compact representation of a binary DAG (bottom right) that is a compressed version of the binary tree structure at top. Node labels are not explicitly stored in the data structure: The table represents the eighteen edges 1-0, 1-0, 2-1, 2-1, 3-1, 3-2, and so forth, but designates a left edge and a right edge leaving each node (as in a binary tree) and leaves the source vertex for each edge implicit in the table index. An algorithm that depends only upon the tree shape will work effectively on the DAG. For example, suppose that the tree is an existence trie for binary keys corresponding to the leaf nodes, so it represents the keys 0000, 0001, 0010, 0110, 1100, and 1101. A successful search for the key 1101 in the trie moves right, right, left, and right to end at a leaf node. In the DAG, the same search goes from 9 to 8 to 7 to 2 to 1.

An equivalent app is to view the trie keys as corresponding to rows in the truth table of a Boolean function for which the function is true (see Exercises 19.84 through 19.87). The binary DAG is a model for an economical circuit that computes the function. In this app, binary DAGs are known as binary decision diagrams (BDDs). Motivated by these apps, we turn, in the next two sections, to the study of DAG-processing algorithms. Not only do these algorithms lead to efficient and useful DAGADT implementations, but also they provide insight into the difficulty of processing digraphs. As we shall see, even though DAGs would seem to be substantially simpler structures than general digraphs, some basic problems are apparently no easier to solve.

## Representing a binary tree with a binary DAG

This code snippet is a postorder walk that constructs a compact representation of a binary DAG corresponding to a binary tree structure (see Chapter 12) by identifying common subtrees. It uses the indexing class ST from Program 17.15 to assign a unique integer to each distinct tree structure for use in representing the DAG as a vector of 2-integer structures (see Screenshot). The empty tree (null link) is assigned index 0, the single-node tree (node with two null links) is assigned index 1, and so forth. The index corresponding to each subtree is computed recursively. Then a key is created such that any node with the same subtrees will have the same index and that index returned after the DAG's edge (subtree) links are filled.

```int compressR(Node h)
{
if (h == null) return 0;
l = compressR(h.l);
r = compressR(h.r);
t = st.index(l + "", r + "");
return t;
}
```

#### Exercises

19.75 Implement a DFS method for use by clients to verify that a DAG has no cycles.

19.76 Write a program that generates random DAGs by generating random digraphs, doing a DFS from a random starting point, and throwing out the back edges (see Exercise 19.40). Run experiments to decide how to set parameters in your program to expect DAGs with E edges, given V.

19.77 How many nodes are there in the tree and in the DAG corresponding to Screenshot for FN, the Nth Fibonacci number?

Give the DAG corresponding to the dynamic-programming example for the knapsack model from Chapter 5 (see Figure 5.17).

19.79 Develop an ADT for binary DAGs.

• 19.80 Can every DAG be represented as a binary DAG (see Property 5.4?

19.81 Write a method that performs an inorder traversal of a single-source binary DAG. That is, the method should visit all vertices that can be reached via the left edge, then visit the source, then visit all the vertices that can be reached via the right edge.

19.82 In the style of Screenshot, give the existence trie and corresponding binary DAG for the keys 01010011.

Implement an ADT based on building an existence trie from a set of 32-bit keys, compressing it as a binary DAG, then using that data structure to support existence queries.

19.84 Draw the BDD for the truth table for the odd parity function of four variables, which is true if and only if the number of variables that have the value true is odd.

Write a method that takes a 2n-bit truth table as parameter and returns the corresponding BDD. For example, given the input 1110001000001100, your program should return a representation of the binary DAG in Screenshot.

Write a method that takes a 2n-bit truth table as parameter, computes every permutation of its parameter variables, and, using your solution to Exercise 19.85, finds the permutation that leads to the smallest BDD.

• 19.87 Run empirical studies to determine the effectiveness of the strategy of Exercise 19.87 for various Boolean functions, both standard and randomly generated.

Write a program like Program 19.5 that supports common subexpression removal: Given a binary tree that represents an arithmetic expression, compute a binary DAG that represents the same expression with common subexpressions removed.

19.89 Draw all the nonisomorphic DAGs with two, three, four, and five vertices.

•• 19.90 How many different DAGs are there with V vertices and E edges?

••• 19.91 How many different DAGs are there with V vertices and E edges, if we consider two DAGs to be different only if they are not isomorphic?

 Previous    Next