Reading

These notes.

Homework

Work on your Problem Sets.

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 colored gray. Note: we really need to call DFSVisit repeatedly (though always on an undiscovered vertex (i.e. colored white), 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. We looked at two important ones

  1. Makefiles
  2. 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 of $G$ is performed, and the vertices of $G$ are ordered in the reverse of the order in which they are colored black during the search (i.e. $u$ comes before $v$ only if $u$ was colored black later than $v$), then all edges in the graph aer 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.