Discrete Mathematics for Computer Science

400 CHAPTER 6 Graph Theory

Before examining the general problem, consider the smaller scheduling problem rep-

resented by the directed graph shown in Figure 6.60.

P

/%

Q

R;

Figure 6.60 A small scheduling problem.

Clearly, P must be scheduled first. For the remaining processes Q, R, and S, any order

in which S precedes R is acceptable. The possible schedules are

P---) Q-- SS--). R P--- S--+ Q--* R P-+S--S+ R--+ Q

What we have accomplished is to take the partial ordering relation represented by a directed

graph in Figure 6.60 and find a linear order of the vertices. The linear order has the property

that for each edge, we have the head of the edge in the directed graph occurring after the

tail of that edge in the final linear order. Check that each of the edges (P, Q), (P, S), and

(S, R) satisfy the property.

More formally, this process is known as embedding a partial order in a linear order

(see Section 3.8.6). The first problem is to know when a directed graph representing a set

of constrained events can be scheduled sequentially so that all the constraints are satisfied.

A second problem is to find a schedule if one is possible.

If the directed graph contains a directed cycle, then clearly, no schedule can satisfy all

the constraints. On the other hand, if the digraph has no directed cycle, then it is always

possible to schedule the events by a process called a topological sort.

Whether a digraph contains a directed cycle can be determined using the algorithm

presented in Section 6.16.1 (Directed Cycle Detection). Directed acyclic graphs are often

called dags.

One algorithm for finding a topological sort of a dag uses a depth first search on a

directed graph. The only difference between a depth first search for a directed graph and

for an undirected graph is that in the case of a directed graph, the edge (i, j) has j occurring

on the adjacency list for i but does not have i occurring on the adjacency list for j unless

the edge (j, i) is also included in the directed graph.

6.171 Algorithm for Topological Sort

An algorithm for topological sorting will be given followed by an argument showing its

correctness. Finally, an example of using the algorithm will be presented.

As an intuitive aid to understanding the algorithm, think of the vertices as representing

jobs and the edges as representing precedence constraints between jobs. At each step, the

list Stack correctly orders the vertices (jobs) considered so far.