DAGs and Topological Ordering

DAGs and Topological Ordering v1 v2 v3 v4 v5 v6 v7 2 Directed Acyclic Graphs Def. A DAG is a directed graph that contains no directed cycles. Ex. Precedence constraints: edge (vi, vj) means vi must precede vj. Def. A topological order of a directed graph G = (V, E) is an ordering of its nodes as v1, v2, …, vn so that for every edge (vi, vj) we have i < j. a DAG v2 v3 v6 v5

v4 v7 v1 v1 a topological ordering v2 v3 v4 v5 v6 v7 Superhero Strength DAG Superhero Strength Ordering 5 Precedence Constraints Precedence constraints. Edge (vi, vj) means task vi must occur before vj. Applications. Course prerequisite graph: course vi must be taken before vj. Compilation: module vi must be compiled before vj. Pipeline of computing jobs: output of job vi needed to determine input of job vj. 6 Directed Acyclic Graphs Lemma. If G has a topological order, then G is a DAG. Pf. (by contradiction) Suppose that G has a topological order v1, …, vn and that G also has a directed cycle C. Let's see what happens. Let vi be the lowest-indexed node in C, and let vj be the node just before vi; thus (vj, vi) is an edge. By our choice of i, we have i < j. On the other hand, since (vj, vi) is an edge and v1, …, vn is a topological order, we must have j < i, a contradiction. ▪ v1 vi vj vn the supposed topological order: v1, …, vn the directed cycle C 7 Directed Acyclic Graphs Lemma. If G has a topological order, then G is a DAG. Q. Does every DAG have a topological ordering? Q. If so, how do we compute one? Superman Lemma 8 Directed Acyclic Graphs Lemma. If G is a DAG, then G has a node with no incoming edges. Pf. (by contradiction) Suppose that G is a DAG and every node has at least one incoming edge. Let's see what happens. Pick any node v, and begin following edges backward from v. Since v has at least one incoming edge (u, v) we can walk backward to u. Then, since u has at least one incoming edge (x, u), we can walk backward to x. Repeat until we visit a node, say w, twice. Let C denote the sequence of nodes encountered between successive visits to w. C is a cycle. ▪ w x u v 9 Directed Acyclic Graphs Lemma. If G is a DAG, then G has a topological ordering. Pf. (by induction on n) Base case: true if n = 1. Given DAG on n > 1 nodes, find a node v with no incoming edges. G - { v } is a DAG,...

Website: homes.cs.washington.edu | Filesize: -
No of Page(s): 29
Download 3.6 DAGs and Topological Ordering.pdf