SI335: Topological sort and DAGs

Reading

These notes and closely review Unit 5 Section 3 intro and 3.1.

Homework

Review

We reviewed the original DFSVisit algorithm and the loop invariant $I_2$ from last class, and we went through the proof (in last class's notes) that, when DFSVisit(G,s) completes, all vertices reachable from s are marked "processed".

Augmented DFSVisit from homework

In your programming classes you have, hopefully, learned the lesson that it is often good when writing a program to solve a problem, to start with a simple program that solves an easier version of the problem, get that to work, and then augment (i.e. add onto) the program to get closer to solving the original problem. The same thing is true for algorithms. Now that we have DFSVisit, we understand it well, and we know that it is correct ... let's augment it to do even more.

DFSVisit(Graph G, vertex s) ← assume G is an adjacency list rep
initialize S to an empty stack of vertex-integer pairs [ count=0; set starttime and endtime for all vertices to +∞]
mark s active [ set starttime of s to count; count++ ]
S.push((s,0))
while S not empty do
  (u,i) = S.pop()
  if i is less than the number of neighbors of u
    S.push((u,i+1))
    v = G[u][i]
    if v is unvisited
      mark v active [ set starttime of v to count; count++ ]
      S.push((v,0))
  else
    mark u processed [ set endtime of u to count; count++ ]

Here are a few obvious observations about the augmented algorithm and the new starttime/endtime values it tracks:

if $x$ has starttime and endtime equal to +∞ then $x$ is unvisited
if $x$ has starttime < +∞ and endtime = +∞ then $x$ is active
if $x$ has starttime and endtime < +∞ then $x$ is processed

A Deeper loop invariant

One more loop invariant for you!

$I_4$: if there is a path starting from vertex $x$ where starttime $x$ is less than the starttimes of all the other vertices on the path, then the endtime of $x$ is greater than or equal to the endtimes of all the other vertices on the path

This loop invariant (we prove that it is indeed a loop invariant below) is important, because it tells us that if there is a cycle in the graph that is reachable from the start vertex, we will come to a situation where child $v$ of $u$ is marked "active", and that means it completes a cycle!

$I_4$ is loop invariant for the while loop in the augmented DFSVisit algorithm.

Initialization: When only $(s,0)$ is on the stack, $s$ and all other vertices have endtime +∞, so $I_4$ holds trivially.

Maintainance: Assume $I_4$ holds at the beginning of a loop iteration. And consider arbitrary vertex $x$ and path $x\rightarrow y_1 \rightarrow y_2 \rightarrow \cdots \rightarrow y_k$, where all the $y_i$'s have starttime greater than starttime of $x$. [Note: nothing the algorithm does can change which paths satisfy this requirement.] What we need to show is that the endtime of $x$ is greater than or equal to the endtimes of all the $y_i$'s at the end of the loop iteration. We consider three cases:

Case $x$ is visited: This cannot happen, since otherwise starttime of $x$ is +∞, which is not less than any other starttime.
Case $x$ is processed: In this case starttime and endtime of $x$ are fixed (i.e. never change), and endtime of $x$, which we will call $t$, is less than +∞. Since $I_4$ holds, $y_1,y_2,\ldots,y_k$ have endttimes less than $t$. Their endtimes can never be lowered, so they will continue to have endtimes less than $t$.
Case $x$ is active: In this case $x$ is on the stack, and therefore endtime of $x$ is +∞.
- Subcase - the mark of $x$ is not changed to processed in this iteration: Then endtime of $x$ will remain +∞, which is (of course!) greater than or equal to the endtimes of $y_1,y_2,\ldots,y_k$.
- Subcase - the mark of $x$ is changed to processed in this iteration:
  Then $x$ must be at the top of the stack at the beginning of this iteration, which means that all other active vertices have starttime less than that of $x$. So any $y_i$ with starttime less than +∞ must be processed. Assume there is a vertex on the path with starttime equal to +∞. Then let $y_i$ be the first such vertex. If $i=1$, $y_i$ is a child of $x$, which means it can't be unvisited since we are changing the mark of $x$ to processed this iteration. Otherwise, vertex $y_{i-1}$ exists and has starttime less than +∞, which means it is processed, which means that it all of its children (including $y_i$) are either active or processed, which means they have starttime less than +∞. This contradicts our assumption. Therefore all of the $y_i$'s have starttime less than +∞ but greater than starttime of $x$, which means they must be processed. This in turn means that their endtimes are less than the current value of count, which is the value the endtime of $x$ gets in this loop iteration.

Close the loop

We can finally prove the observation made earlier: that DFSVisit will come across an edge from $u$ to $v$ where $v$ is active (i.e. on the stack) if and only if there is a cycle in the graph that i reachable from the start vertex.

Graph $G$ has a cycle reachable from vertex $s$ if an only if at some point during DFSVisit(G,s) vertex $v$ is already marked active prior to the if statement.

First we prove that if $v$ is already active, then there is a cycle. This is clear because $v$ being active means it is already on the stack, so the stack vertices in order from $v$ to $u$ form a path, and then the edge $u\rightarrow v$ closes the cycle.
Second we prove that if there is a cycle, we will eventually find a $v$ that is maked active. Suppose $C$ is a cycle in $G$ that is reachable from $s$. Let $x$ be the first vertex from cycle $C$ to be pushed on the stack. Let $y$ be the prececessor of $x$ in the cycle. There is a path (the cycle) from $x$ to $y$, and $x$ has the only starttime less than +∞ of all those vertices. Moreover, all those vertices are guaranteed to get starttimes greater than starttime of $x$, which means that, as the algorithm progresses, $I_4$ guarantees that endttime of $x$ is greater than or equal to the endtimes of all the other vertices in the cycle - including $y$. Let $i$ be the index such that $x$ is the index $i$ child of $y$. Eventually $(y,i)$ will get popped off the stack, and "vertex $v$" in the algorithm will be $x$. Since $y$'s enddtime will still be +∞ at this point, $x$'s enddtime will be as well, which means $x$ is still on the stack.

What if we want it all?

If we are given a graph $G$ and we want to know if $G$ has any cycles, just calling DFSVisit may be insufficient, because we only discover cycles that are reachable from whatever our start vertex was. So what do we do? We simply call DFSVisit over and over, always starting at a so-far-unvisited node. Like this:

for i from 0 to n-1 do
  if vertex i is unvisited	
    DFSVisit(G,i)

We'd like to think that there is a cycle in $G$ if and only if at least one of the DFSVisit calls encounters "vertex $v$" that is marked "active" (i.e. on the stack). However, our proofs of correctness for DFSVisit and for the cycle property all assume DFSVisit starts with all vertices unvisited, which is not true in the above, which uses DFSVisit multiple times. We'd like to be confident that these results are still true without having to re-prove everything. Here's a little trick. Consider creating a new graph $G'$ by adding to $G$ a new dummy vertex "-1" that has no incoming edges and has outgoing edges to every vertex in $G$. The above algorithm is exactly equivalent to running DFSVisit once on graph $G'$ and start vertex -1. Thus we get that all vertices of $G$ are visited (since all are reachable from -1), and there is a cycle in $G$ if and only if vertex $v$ in DFSVisit is never "active" at the point where we check whether it is "unvisited" (since the -1 vertex cannot be part of a cycle).

Loops and directed acyclic graphs (DAGs)

Review homework, where DFSVisit finds a cycle. Remember: there is a cycle in a directed graph G if and only if DFSVisit finds a vertex v in the inner loop that is marked "active". Note: we really need to call DFSVisit repeatedly (though always on an undiscovered vertex (i.e. "unvisited"), so that we look at all parts of the graph. This is the "DFS" from the previous notes.

Specifically, we will end up looking at every edge exactly once.

This means we can determine whether there is a cycle (and find one if it exists) in time $O(n + e)$, where $n$ is the number of vertices and $e$ is the number of edges.

A Directed Acyclic Graph is called a "DAG", and these graphs have lots of important applications in computer science. I mentioned two important ones

Makefiles
Compiler optimization. I covered an example in class related to DAG-Based Optimization of IR Code in a Basic Block by Harry H. Porter

Topological sort, and reviewing the homework

Reviewed homework some more. What we discovered is this:

Theorem: Given graph $G$, if a full depth-first search (based on DFSVisit) of $G$ is performed, and the vertices of $G$ are ordered in the reverse of the order in which they are marked "processed" during the search (i.e. $u$ comes before $v$ only if $u$ was marked "processed" later than $v$), then all edges in the graph are oriented from vertices earlier in the order to vertices later in the order.

An ordering like this is called a "topological sort" of the graph. Of course, this is only possible for DAGs. We talked about the importance of topological sort in producing schedules for tasks with ordering constraints defined by a DAG.

An example of where DAGs are important

Suppose we have a boolean function represented by the propositional logic formula: (x1∨¬x2)∧(¬x3∨¬(x1∨¬x2))∧(x2∨¬x3)

Hopefully you all recognize that this is represented by the expression tree on the right. If you view this tree as a directed graph with the edges going up from the leaves to the root, you can see this graph as telling us how to evaluate the formula. To evaluate the leftmost ∨-node, we need the values x1 and ¬x2 that feed into it. So they must be fetched/computed first.

Computing the value of the formula based on this tree is inefficient. If you look, you'll see that you are computing/fetching the same thing multiple times. If we imagine wanting to generate assembly code to evaluate this formula, you would rather compute something once, store it in a register, then use it over and over. To represent that kind of evaluation, we simply allow multiple edges out of a vertex to represent using the same value multiple times. With this in hand we arrive at something like the graph shown on the left. This is no longer a tree. Instead it is ... a DAG! It is more efficient to base our evaluation off this DAG, because we avoid duplicate complications. We can label each node with a register number. To compute the value at a vertex, use the register numbers of their predecessors to get input values, and store results in the register label of the vertex. The problem now is this: what order to I compute things in. Well ... do a topological sort! That will give you an order that ensures that the inputs to the operation at a given vertex have been computed and stored in their associated registers before we try to actually perform the operation. In class I also talked about how we could reorder intructions once we had the topological sort to produce more efficient code.