Implementation

Instead of implementing an algorithm that computes a topological sort, we have chosen to implement a traversal that visits the vertices of a DAG in the order given by the topological sort. The topological order traversal can be used to implement many other graph algorithms. Furthermore, given such a traversal, it is easy to define a visitor that computes a topological sort.

In order to implement the algorithm described in the preceding section, an array of integers of length is used to record the in-degrees of the vertices. As a result, it is not really necessary to remove vertices or edges from the graph during the traversal. Instead, the effect of removing a vertex and all the edges emanating from that vertex is simulated by decreasing the apparent in-degrees of all the successors of the removed vertex.

In addition, we use a queue to keep track of the vertices that have not yet been visited, but whose in-degree is zero. Doing so eliminates the need to search the array for zero entries.

Program  defines the topologicalOrderTraversal method of the AbstractGraph class. This method takes as its argument a Visitor. The visit method of the visitor is called once for each vertex in the graph. The order in which the vertices are visited is given by a topological sort of those vertices.

  
Program: AbstractGraph class topologicalOrderTraversal method.

The algorithm begins by computing the in-degrees of all the vertices. An array of integers of length called inDegree is used for this purpose. First, all the array elements are set to zero. Then, for each edge , array element is increased by one (lines 11-20). Next, a queue to hold vertices is created. All vertices with in-degree zero are put into this queue (lines 22-25).

The main loop of the topologicalOrderTraversal method comprises lines 26-37. This loop continues as long as the queue is not empty and the visitor is not finished. In each iteration of the main loop exactly one vertex is dequeued and visited (lines 28-29).

Once a vertex has been visited, the effect of removing that vertex from the graph is simulated by decreasing by one the in-degrees of all the successors of that vertex. When the in-degree of a vertex becomes zero, that vertex is enqueued (lines 30-36).

Copyright © 1998 by Bruno R. Preiss, P.Eng. All rights reserved.