CSE 589, Spring 1999: Assignment 1

Due 4/6/99

In industrial scheduling problems there is often an underlying directed graph that describes the tasks and the temporal relationships among the tasks. The tasks are vertices in the graph and there is a directed edge (u,v) in the graph if task u must precede task v. We don't want to pour the concrete until the forms are built. Naturally, there is a problem if the directed graph has a cycle. A cycle corresponds to a sequence of tasks where each must precede the next and the last one must precede the first. Your job in this assignment is to design and evaluate an algorithm for detecting if a directed graph has a cycle and reporting at least one cycle if there is one. Your algorithm should work efficiently using the adjacency lists representation of directed graphs.

Depth first search can be used to solve this problem. First depth first search on directed graphs works exactly like it does on undirected graphs. That is, depth first search is a recursive marking algorithm. For directed graphs it is very helpful to augment the marking to keep track of the ordering of the following events for each vertex: (i) the discovery time which is the time the vertex is first visited and (ii) finish time which is the time when all the edges from the vertex have been traversed. To do this marking we simply use a counter as seen in the following algorithm. 

DFS(i: vertex)
   D[i] := time;
   time := time + 1;
   for each vertex j adjacent to i do
      if D[j] = 0 then DFS(j)
   F[i] := time;
   time := time + 1
end{DFS}
This DFS algorithm will only search the vertices that are reachable from the vertex where the algorithm is first called. Thus, we need to apply it to all the vertices. 
Main
   for each vertex i do
      if D[i] = 0 then DFS(i)
end{Main}
Initially, D[i] and F[i] are set to 0 for all i and time is set to 1. In the end D[i] indicates the discovery time for vertex i and F[i] indicates the finish time for the vertex i.

Given the discovery and finish times we can classify each edge (i,j) of the directed graph.

A forward edge (i,j) is also called a tree edge if j is discovered while visiting the vertex i, that is, D[j] is found to be 0 during the call DFS(i). The tree edges form a forest of trees called the depth first search forest. To understand these labels, I suggest that you do a depth first search on a small directed graph, marking the vertices with their discovery and finish times. You will see that during the call DFS(i) if j is adjacent to i then (i,j) is a forward edge if j is a descendent of i in a tree in the depth first search forest, (i,j) is a backward edge if j is an ancestor of i in a tree in the depth first search forest, and (i,j) is a cross edge otherwise.

It can be shown that a graph has a cycle if and only if in any depth first search some edge is classified as a backward edge (cf. page 486 of CLR).

Your assignment is to design and evaluate an algorithm that detects if a directed graph has a cycle and to identify a cycle if it has one. A cycle is identified by listing the vertices of the cycle in the order encountered in a traversal of the edges in the cycle. You should do a high level design first, with a careful explanation of why the algorithm is correct. Then you should design the pseudo-code (with comments) using the adjacency lists representation of graphs. Finally, you should evaluate the time and storage requirements for your algorithm as a function of the number of vertices and edges in the graph.

For more information about depth first search I recommend that you read pages 477-497 in CLR.