# CHAPTER 11: TOPOLOGICAL SORTING: AN ARCHETYPAL SOLUTION

Introduces topological sorting

as an example of the application of the problem solving methodology and programming style presented in this text

background for the problem is given first

each step and decision is explained as the solution evolves

Emphasis is on

top-down design

data abstraction

functional modularization

intelligent choice of information to store and data structure in which to store it

# 11.1: Background

The approach to the topological sorting problem presented in this chapter and the characteristics of the final program are intended to serve as prototypes. The problem is substantial and the algorithm developed important, but it is the process by which it is achieved that is most important. Developing an efficient topological sorting program is a complex process and demonstrates the general problem solving methodology used in this text. It requires the application of structured programming concepts, during which the selection of data structures plays a significant role.

The resultant topological sorting program is a model solution, representing nearly the best programmers can hope to achieve. Few solutions to problems have all its characteristics. It is concise and clear; correctness is easy to determine; and the storage and execution time requirements can be analyzed. Invalid input data are not difficult to deal with. What more can we ask?

The following are some examples of problems whose solutions require topological sorting.

A large skyscraper is to be constructed. Imagine that you must write a program to prescribe the order in which all the tasks are to be performed. The tasks include T3--install windows; T50--install floors; T8--install window sashes; T1000--clear the ground; T7--build the foundation; T9--install doors. For any two tasks, it is possible to specify whether one should be done before the other. Clearly, T8 must be done before T3, and T1000 must be done before T7, while it makes no difference whether or not T3 is done before T9. The constraint that Ti be done before Tj is represented as the pair (i, j).

Imagine that you want to write a book on data structures. All technical words used must be defined. First write down all the relevant words. If word wj uses wi in its definition, represent this constraint by the pair (i, j).

As a student you must take a number of courses to graduate. Represent the fact that course cj has course ci as a prerequisite by the pair (i, j).

A number of books must be read for a course you are taking. Represent the fact that you prefer to read book i before book j by the pair (i, j).

Suppose that an order is given in which the construction tasks of Example 11.1 are to be carried out. If you proceed to carry out the tasks, you may not be able to do the next task, since tasks that must precede it have not yet been finished. The same situation can arise in Examples 11.2, 11.3, and 11.4, when an order is specified in which words are to be defined, courses to be taken, and books to be read, respectively. This is because words used in the next word's definition have not yet been defined, all prerequisites for the next course may not have been taken, or you will not read the next available book because you want to honor your preferences. A topological sort gives an order in which to proceed so that such difficulties will never be encountered.

## 11.1.1 Binary Relations and Partial Orders

You readily understand what is meant by the statements: "Fred is related to Sam"; "John is taller than Sue"; "3 is the square root of 9." The phrases each specify a connection or relation between two objects. In the first two cases the relations refer to two people. In the third case the relation refers to numbers. Each is a binary relation on a set of objects.

Mathematics abstracts from such examples to define a binary relation R on a set S. S is taken as the set or collection of objects referred to by the relation. R contains information, for any two of these objects, on whether or not they are related. R is a set of pairs of objects (a, b), where a and b belong to S. If the pair (a, b) belongs to R, then this is interpreted to mean that a is related to b. This is written as aRb. If (a, b) does not belong to R, then a is not related to b. This is written as .

For instance, specify S to be the set of integers between 2 and 10, so S = {2, 3, . . . , 10}; and take R = {(4, 2), (6, 2), (8, 2), (8, 4), (9, 3), (10, 2), (6, 3), (10, 5)}.Then R captures the "is divided evenly by but is not equal to" relation on S, since a pair (a, b) will belong to R only if a "is divided evenly by but is not equal to" b. By looking at R, we can determine if aRb or for any a and b in S.

Irreflexivity For any a in S,

Asymmetry For any two distinct a and b in S, aRb implies

Transitivity For any three distinct a, b, and c in S, aRb and bRc implies aRc

These properties specify that whenever certain pairs are in R, then other pairs must necessarily be included in R or excluded from R. The "is divided evenly by but is not equal to" relation on S in the preceding paragraph fulfills all three properties of a partial order.

It is irreflexive, since a is divided evenly by but is equal to a for all a in S.

It is asymmetric, since if a "is divided evenly by" b, then b cannot be divided evenly by a when a is not equal to b.

It is transitive, since whenever a is divided evenly by b and b is divided evenly by c, then a must also be divided evenly by c.

To show that a relation does not have a property requires only one counter-example.

Two extreme binary relations on a set S are the null relation, which contains no pairs at all, and the universal relation, which contains all possible pairs. The null relation is a partial order. This is because no counterexamples can be found. The universal relation will never be irreflexive (unless S has no objects in it) or asymmetric (unless S has only one object), but it will always be transitive.

## 11.1.2 Graphic Representation of Partial Orders

One can represent any binary relation R on a set of n objects graphically, as in Figure 11.1. Let S consist of ten objects, the integers 1, 2, 3, . . . , 10. Take R to contain the pairs (1, 2), (8, 3), (7, 6), (2, 7), (5, 4), (7, 8), (2, 4), (4, 7), (2, 8), (8, 5). Create a node for each object in S and draw arrows between two nodes for each pair in R. For example, an arrow will appear from 7 to 8 for the pair (7, 8).

Any such diagram can be interpreted as representing a binary relation on a set S. For such a diagram to represent a partial order requires that

No arrows appear from any node to itself (irreflexivity)

No arrows appear from any node i to another node j and back from j to i (asymmetry)

If arrows appear from i to j and from j to k, then an arrow must appear from i to k (transitivity)

In depicting partial orders, it is unnecessary to draw all the arrows needed to represent transitivity, because they are always assumed. With this understanding, it is not difficult to see that a diagram represents a partial order if and only if it contains no loops. This means that no node can be found such that one can follow a series of arrows starting from that node and ending at that node. In Figure 11.1, there is a loop involving nodes 5, 4, 7, and 8. Hence the diagram does not represent a partial order. Note that if one starts with a diagram representing a partial order (no loops), erasing a node and all arrows emanating from it results in a diagram that represents a new partial order on the set of remaining nodes.

## 11.1.3 Topological Sorts: Consistent Rankings

`3  5  1  2  4  6  8  7`

For such a diagram, it seems clear what would be meant by a listing or ranking of the eight objects that is consistent with the given partial order. Such a ranking would be 3, 5, 1, 2, 4, 6, 8, 7. No other ranking would be consistent with the given partial order. This can be generalized to any partial order by interpreting the arrows as constraints on the ordering of objects in a ranking. For example, an arrow from 3 to 5 would mean that 3 must be ranked higher than 5. Then, a ranking consistent with a partial order would mean a ranking of the n objects that violates no constraints (that is, a ranking that violates no arrows or pairs).

Consider the partial order on the set of nine integers represented by Figure 11.2.

The ranking 2, 3, 4, 5, 6, 7, 8, 9, 10 would not be consistent with this partial order, because it violates at least one of the constraints--namely, that 6 be ranked higher than 3, or that 10 be ranked higher than 2. This diagram actually represents the "is divided evenly by but is not equal to" relation introduced earlier.

#### Figure 11.2 A Partial Order on the Integers 2, . . . , 9

The definition of topological sorting can now be stated more formally than at the outset of the chapter. A topological sort is a ranking of the n objects of S that is consistent with the given partial order. Let us try to solve the following topological sorting problem.

Given a partial order on a set S of n objects, produce a topological sort of the n objects, if one exists. If no such ranking exists, then print out a message saying that none exists.*

* If a relation is asymmetric and transitive but not irreflexive, then one can eliminate all pairs of the form (x, x) from the relation or, equivalently, erase all self-loops from its diagram. The resulting relation is a partial order, and it still makes sense to find a topological sort with respect to it. The topological sort then satisfies the constraints of the original relation involving distinct objects.

For simplicity assume that S is always the set of the first n integers 1, 2, 3, . . . , n, and that the partial order is given as m pairs of integers representing arrows in the corresponding diagram. Assume no pairs are replicated. For concreteness, take the input to have the following form:

`10       value of n`

`7 3`

`5 3`

`2 10`

`6 8`

`5 6      m = 9 pairs`

`4 8`

`7 1`

`4 2`

`7 6`

This particular instance of the topological sorting problem will be referred to repeatedly throughout the chapter. Is there an obvious algorithm for this problem? Try to think of one before continuing.

# 11.2: A Searching Solution

A search-based algorithm:

If a ranking is found which violates no constraints, then the ranking is a topological sort, print it and stop. If all possible rankings have been tried and no topological sort found, then print out the message that none exists, and stop.

To implement this algorithm in a programming language requires finding a way to generate the rankings so that all the distinct rankings are eventually generated. The procedure permutations of Chapter 4 does this. Any implementation of the algorithm could take time proportional at least to the number of distinct rankings of n objects. A particular ranking can be constructed by selecting any one of the n objects to be first in the ranking, then selecting any one of the remaining n - 1 objects to be second in the ranking, and so on. Thus there are n X (n - 1) X (n - 2) X X 2 X 1 distinct rankings of n objects. This product is n factorial. Consequently this solution can deal with values of n no greater than 16.* For larger n, an algorithm must be found that need not consider all rankings.

* See Section 1.8.2.

# 11.3: A Constructed Solution

Now suppose the node corresponding to obj1 is erased, as well as all the arrows emanating from obj1. As noted earlier, this results in a new diagram that represents a new partial order on the remaining n - 1 objects. Consider the ranking of these n - 1 objects obtained by taking the original topological sort of the n objects and removing obj1. That is, consider obj2, obj3, . . . , objn. It must be a topological sort of the remaining n - 1 objects in the new diagram with respect to the new partial order. This is because any constraint in the new diagram that is violated by this ranking would have been violated in the original ranking of the n objects. Note that if any topological sort of the remaining n - 1 objects were taken with respect to the new partial order, and obj1 were placed in front of it, the ranking of n objects thus obtained would be a topological sort with respect to the original partial order. Placing obj1 first in this ranking cannot violate any of the original constraints because they did not require that any object precede obj1.

A construction-based algorithm:

While S is not empty

1. Select any object with no predecessors.

2. Place it in the next position of the output ranking.

3. Remove that object from S, and

4. Remove its arrows from the partial order.

The output ranking produced will always be a topological sort.

## 11.3.1 Correctness

One difficulty remains. How can the programmer be certain the algorithm can actually be carried out? It may be impossible to carry out because at some point there may be no objects with zero predecessors. That this is indeed an algorithm requires showing that there always is at least one object with no predecessors.

One method of proof for any proposition is to assume it is not true and then show that this assumption leads to a contradiction. This method of proof is applied here. The goal is to prove that every time the loop task is to be carried out, at least one object with no predecessors can be found among those remaining. To assume that this is not true means that at some point the task cannot be carried out because every object left has at least one predecessor. Recall that the original diagram, representing a partial order, had no loops. It will be shown that the assumption implies a loop in the diagram. This will be the contradiction.

Suppose i1 is one of the remaining objects. Under the assumption, every object has at least one predecessor, so i1 has a predecessor (say, i2). Note that i2 cannot be the same object as i1, or the irreflexivity property would not hold. Again, i2 must have a predecessor (say, i3). The object i3 cannot be i1 or i2. If it were i1 or i2, then a loop involving i2 and i1 or a loop with just i2 would exist. Continuing with this argument, i1, i2, i3, i4, . . . must all be distinct objects. But since there are only n objects in total, eventually an object must repeat. This implies that the repeated object is the starting and ending object of a loop. The conclusion is that the assumption was false. Therefore what we wanted to prove must be true, and we never get bogged down--there will always be an object with no predecessors.

This algorithm yields additional insight into the topological sorting problem. Since it is clear that the loop can always be carried out to completion, it will always produce a topological sort of the n objects. In other words, a topological sort always exists. This was certainly not obvious before.

To be sure the algorithm is understood, it is applied next to Example 11.6, depicted again in Figure 11.3. Initially (see Figure 11.3(a)), 4, 7, 5, and 9 have zero predecessors.

The first step is to select and remove 5 (either 4, 7, or 9 could also have been removed) and its successor arrows, to obtain Figure 11.3(b). S is not empty, so the loop must be repeated. Now, 4, 7, and 9 have no predecessors. Select and remove 7 and its successor arrows, and obtain Figure 11.3(c). S is still not empty, and now 4, 9, 1, 3, and 6 have no predecessors. Select 4. Updating produces Figure 11.3(d).

#### Figure 11.3 Graphic Depiction of Example 11.6

S is still not empty, but 9, 1, 3, 6, and 2 now have zero predecessors. Continuing in this way, removing 1, 3, 6, 8, 9, 2, and finally 10 in succeeding iterations yields the final ranking: 5, 7, 4, 1, 3, 6, 8, 9, 2, 10.

Notice that every time an object is selected and removed, the diagram is updated to reflect the new S and the new partial order. As a result, some additional objects may end up with zero predecessors. Once an object has zero predecessors, it will remain in each succeeding diagram, always with zero predecessors, until it is removed.

First refinement:

2. Initialize for phase I.

3. While there is another input pair,

a. record the information in the pair i, j phase I

4. Initialize for phase II. phase II

5. While the set S is not empty,

a. select an object with no predecessors, and output it as the next object in the output ranking;

b. update the records to reflect the removal of the output objects.

Phase I reads into memory the information about the number of objects and the partial order. Every time an i, j pair is read in, the new information that this represents must be incorporated into a representation in memory. The "record the information" of task 3a refers to the modification of this representation to reflect the new arrow, i j.

Phase II describes the processing required by our algorithm. Task 5a involves the selection, removal, and outputting of an object. Task 5b involves modifying the partial order representation and S, to reflect the removal of an object and its arrows, and outputting it in the ranking. After task 5b is carried out, that representation should reflect the new set S and the new partial order resulting from the object's removal.

## 11.3.2 An Initial Implementation

Suppose the while loop of phase II is being executed, and task 5a is to be carried out. An object with no predecessors must be selected. How is such an object found? Any object that has no predecessors will not appear in the second array. Somehow the second array must be searched to select an object with no predecessors. This can be accomplished by using an array S, traversing second, and marking location i of S when object i appears in second. Any location in S left unmarked corresponds to an object with no predecessors.

Suppose this is done, and object 5 is selected. Object 5 can then be output to the next place in the ranking. To accomplish task 5b, the "updating of the records," then requires that the array first be traversed. As it is traversed, each time a 5 is encountered, the program must mark the location of first in which it appears, and the corresponding location of second. The mark signifies that the corresponding arrow emanating from 5 has been removed from the representation.

#### Figure 11.4 Result of Phase I of the First Refinement

This completes one execution of the loop. This same processing must be repeated for each repetition of that loop. The loop will be repeated n times, once for each of the n objects. The first and second arrays must be traversed each time. This will take time proportional to their length, which, in general, will be m. Hence this implementation of the algorithm will take time proportional to n X m. The storage required is roughly 2m locations for first and second, and n locations for S.

## 11.3.3 A Better Implementation

Notice that each time through the loop, the program must select an object with no predecessors. To do this requires kdnowing which of the objects left in S have zero predecessors. Suppose that it is known, before and after each execution of the loop body, exactly how many predecessors each remaining object has. With this knowledge, an object with zero predecessor count can be selected. Once an object becomes eligible to be selected (has zero predecessors), it remains eligible until it is actually selected. Why not collect all those initially eligible in the initialization for phase II? The program could then select among them arbitrarily. Think of this collection as kept in a bag from which the object selected for output is pulled.

As the rest of the loop body is executed, the records must be updated to reflect the removal of this object and its arrows. Removing its arrows amounts to reducing the predecessor count of each successor of the object removed.Whenever the predecessor count of one of these successors becomes zero, that successor becomes eligible for selection on the next repetition of the loop. That successor is immediately added to the bag. Consequently, at the start of each loop repetition, the bag will contain exactly those objects eligible for selection, thus eliminating the need to search for them. In fact, the "S not empty" test is now equivalent to asking if the "bag is not empty." Keeping track of the successors of each object eliminates the need to search for them when that object is output. Incidently, we now know two operations that will be needed on the count collection, decrease(i,count) and iszero(i,count). The first reduces the count of the ith object by one, and the second returns true only if the count of the ith object is zero. The precise information needed for processing has now been isolated. What must be known are the predecessor counts and successors for each object, and what's in the bag.

The loop body of phase I must update predecessor counts and successors.The input pair i, j contains the information that j has one more predecessor than currently reflected in j's predecessor count, and that i has one more successor, j, than currently reflected by i's successors. The loop body of phase II must update the predecessor counts of all successors of the removed object. It must also update the bag. We have developed the following better refinement of the algorithm.

2. Initialize

a. Initialize the predecessor counts for each of the n objects to zero.

b. Initialize current successors for each of the n objects to zero.

3. While there is another input pair,

a. increase the predecessor count of j by l;

b. add j to the current successors of i.

4. Place all objects with zero predecessor count into the bag.

5. While the bag is not empty,

a. remove an object from the bag and output it in the output ranking;

b. for each successor of the output object, decrease its predecessor count by l; if the predecessor count becomes zero, add the successor to the bag.

The implementation treats the predecessor counts, the collections of successor counts, the bag, and the output ranking as data abstractions. In order to refine the solution further, we must decide how to store the predecessor counts, the successors of each object, the bag, and the output ranking. These are data structure decisions. They should be based on the kinds of operations to be performed in tasks 1 through 5. First we functionally modularize the solution.

2. a. predinitialization(n,count);

b. succinitialization(n,successor);

3. while nextpair(i,j)

a. increase(j,count);

b. insert(i,j,successor)

4. baginitialization(bag,n,count);

5. while not emptybag(bag)

a. remove(bag,obj);

b. update(successor,obj,bag,count)

Every operation performed in tasks 1 through 5 that involves the bag, any of the n predecessor counts or collections of successors, or the output ranking has been implemented by a corresponding function. Note the use of a prefix to designate the structure involved in some of these operations. When written in this form, the program is independent of the specific details of implementation of each of these structures. This means that even if changes in the data structure implementations are ultimately adopted, this version of the solution will never need to be modified.

The next step is to decide on specific data structures for implementation of the data abstractions. This choice must be based on the functions that operate on the data structures. These functions include predinitialization,succinitialization, increase, decrease, iszero, insert, baginitialization, emptybag, and remove.

We are actually in a position now to make a decision on the implementations for count, successor, and bag. The programmer does not know, in advance, the order in which objects will be output. In task 5b of the better refinement, after an object is output, its successors must be accessed and their predecessor counts updated. This means that the predecessor counts and the collections of successors must be accessed in arbitrary order. Because arrays support random access to their entries, we choose to store the predecessor counts in an array count and pointers to each collection of successors in an array succ. Count[i] and succ [i] will then contain, respectively, the predecessor count and a pointer to the successors of object i. This allows the predecessor count and collection of successors of any object to be selected, taking constant time. Since we shall need to access the collection of successors of objects, we define access_succ(i,succ) as a basic operation that returns a pointer to the collection of successors of object i.

There are n collections of successors, one for each object. These may be stored separately or may share storage. This choice has important ramifications, which will be discussed later. For now, it is best to share storage and to implement each collection of successors as a list of records. The records consist of two integer fields, succobj, containing a successor object, and link, containing a pointer to the next list record. Either dynamic memory or an array may be used to store the records. Selecting the array for storage means the programmer must manage its allocation himself or herself. Dynamic memory is probably a more natural choice, but an array of records is used to illustrate its simple management in this case and to make the later discussion comparing shared or separate storage for the list records more concrete. Lists will be the array for record storage, and a variable t will keep track of the next available record in lists for task 3b. Since only insertions will be made into the lists, the entries of lists will be allocated one after another as needed, starting with the first. Thus t must be initialized correctly.

The apparent choice for the output ranking is an integer array rank, with a variable next specifying where the next output object is to be placed in the rank array. For convenience, we use the record ranking with the two fields rank and next.

The bag could be implemented similarly, in an array with bag pointing to the next available element for a new bag entry. When an object is to be removed from the bag, we can store its value in obj and then decrease bag by 1. Thus an object can be added or removed from the bag in constant time. This implementation is permissible because objects may be selected from the bag in any order. However, implementing the bag as in Figure 11.5 affords an advantage. By allowing the bag and the output ranking to share storage, it saves time. However, this selection is made primarily to emphasize a point to be made later about the independence of modules. In order to simplify the example, only the array entries starting with 1 are used. As you know, in C they start with zero; 0th array positions will not be used in this example so that ranking and array positions will be identical.

#### Figure 11.5 Data Structure Implementation of Bag and Output-Ranking Data Abstractions

The X's represent nine objects placed in the rank array. Next, pointing to position 6, indicates that the next object to be selected from the bag will be the one in rank[next],rank[6] in this case. Bag, pointing to 10, indicates that when a successor is to be added to the bag, it should be placed in rank[bag],rank[10] in this case. In other words, the bag contains all objects in rank between next and bag-1.

The bag is initialized by traversing the count array and placing any object with zero count into the location of the rank array to which bag points. Bag, of course, must then be updated by 1 to move its pointer down. Bag must initially be 1, and next must initially be 1. Objects are then output in the order in which they are placed into the bag, easing processing and keeping the time constant for addition or removal of an object. Each time an object is selected, next must be increased by 1 to move it down. The bag is empty when next equals bag.

Before proceeding, phase I is illustrated by applying it to Example 11.6. For this example, count, succ, t, and list would appear as in Figure 11.6, after the first eight pairs have been input. Figure 11.7 graphically depicts the successor lists.

At the start of phase I, no information was processed yet on predecessors or successors for any object. The first pair, 7 3, contains the information that 3 has one more predecessor than was known, and that 7 has one more successor than was known, namely 3. One must be added to the count for 3, and 3 to the list of successors of 7, and so on for the other seven pairs.

#### Figure 11.6 Data Structures Involved in Phase I after Input of First Eight Pairs

The detailed processing of an input pair is illustrated for the last pair of this example. It is the ninth pair, 7 6. To update the count for 6, add 1 to count[6]. To create a record to contain the successor 6, place 6 into lists[9].succobj and add this new record to the current successor list for 7 by changing two pointers. First, copy the pointer from succ[7], the head of the list to which the new record is to be added, into the link field of the new record lists[9].link. Then place a pointer into succ[7] so that it points to the new record. In this case, 9 is placed into succ[7]. Since successors need not be kept in any special order, always adding records at the front of successor lists saves processing time. Adding the record anywhere else on the list would require traversal time from the head of the list to the insertion place. T must be incremented by 1 so that it points to the next available record in lists. The final situation after all nine input pairs have been read and processed is shown in Figures 11.8 and 11.9. An X indicates a null pointer.

#### Figure 11.8 Data Structures of Figure11.7 after Processing Last Input Pair of Phase I

We are now ready to consider the actual implementations for the functions of the data abstractions. Following is the code that might be used for those functions whose implementation may not be apparent.

#### Figure 11.9 Graphic Depiction of Successor Lists of Figure 11.8

increase

`count[j] = count[j] + 1;`

decrease

`count[i] = count[i] - 1;`

iszero

`return(count[i] == 0);`

avail

`static int t=0;`

`t++;`

`return(t);`

insert

`pointer = avail();`

`setinfo(pointer,j);`

`setlink(pointer,succ[i]);`

`succ[i] = pointer;`

succinitialization

`for (i=1;i<=n;i++)`

`succ[i] = setnull();`

emptybag

`emptybag =(bag == ranking.next);`

remove

`*pobj = ranking.rank[ranking.next];`

`ranking.next = ranking.next + 1;`

Note that avail must correctly initialize and update t.

Task 5b of the better (or "bag") refinement of the algorithm could be done by writing the procedure update from scratch. Instead, it is done here using a tool that is available, the traverse procedure of Chapter 3. First, traverse is modified by adding bag and count as additional parameters of both traverse and process, and changing its name to update.

Process, called by update, must now be implemented so that update does its job. Its code is

`currentsucc = info(recordpointer);`

`decrease(currentsucc,count);`

`if(iszero(currentsucc,count))`

`{`

`ranking.rank[*pbag] = currentsucc;`

`*pbag = *pbag + 1;`

`}`

A complete program using topsort follows. Notice that topsort has two parameters. It is the same as our version, except it copies the rank field of ranking into the output array as a last step.

Because of the implementation, some functions must have access to specific variables. C requires these variables to be either passed as pointers or declared as global. For example, process must have access to rank, and emptybag to next. Incidentally, as written, topsort does not depend on the medium assumed for the input pairs. Normally, we want programs to be independent of the form of the input. This has been accomplished here for the pairs by using the function nextpair(i,j), which inputs the next pair and returns true if it is a nonsentinel pair. The program uses 0 0 as the sentinel pair.

`#defineLIMIT 21`

`typedef int outputarray[LIMIT];`

`main()`

`/* Reads the number of objects n and the input pairs`

`specifying a partial order on the objects, and prints`

`a topological sort of the n objects. Each pair should`

`not occur more than once in the input and n should`

`not exceed twenty. The sentinel pair is 0 0.`

`*/`

`{`

`int n,i;`

`outputarray topologicalsort;`

`topsort(&n,topologicalsort);`

`printf("\n A TOPOLOGICAL SORT IS");`

`for (i=1;i>=n;1++)`

`printf("\n %d",topologicalsort[i]);`

`}`

`typedef int countcollection[LIMIT];`

`predinitialization(n,count)`

`/* Initializes all n counts to zero. */`

`int n;`

`countcollection count;`

`{`

`int i;`

`for (i=1;i<=n;i++)`

`count[i] = 0;`

`}`

`increase(j,count)`

`/* Increases the jth count by one. */`

`int j;`

`countcollection count;`

`{`

`count[j] = count[j] + 1;`

`}`

`decrease(j,count)`

`/* Decreases the jth count by one. */`

`int j;`

`countcollection count;`

`{`

`count[j] = count[j] - 1;`

`}`

`iszero(i,count)`

`/* Returns true only if the ith count is zero. */`

`int i;`

`countcollection count;`

`{`

`return(count[i] == 0);`

`}`

`#define RECORDLIMIT 191`

`/* RECORDLIMIT should be at least`

`(((LIMIT-1)*(LIMIT-2))/2)+1`

`*/`

`#define NULL - 1`

`typedef int listpointer;`

`typedef struct`

`{`

`int succobj;`

`listpointer link;`

`}listrecords,recordsarray[RECORDLIMIT];`

`recordsarray lists;`

`listpointer setnull()`

`/* Returns a null pointer. */`

`{`

`return(NULL);`

`}`

`anotherrecord(recordpointer)`

`/* Returns true only if recordpointer`

`points to a record.`

`*/`

`listpointer recordpointer;`

`{`

`return(recordpointer != NULL);`

`}`

`info(pointer)`

`/* Returns the contents of the succobj field`

`of the record pointed to by pointer.`

`*/`

`listpointer pointer;`

`{`

`return(lists[pointer].succobj);`

`}`

`listpointer next(pointer)`

`/* Returns the link field value of`

`the record pointed to by pointer.`

`*/`

`listpointer recordpointer;`

`{`

`return(lists[recordpointer].link);`

`}`

`setinfo(pointer,value)`

`/* Copies value into the succobj field`

`of the record pointed to by pointer.`

`*/`

`listpointer pointer;`

`int value;`

`{`

`lists[pointer].succobj = value;`

`}`

`setlink(pointer1,pointer2)`

`/* Copies pointer 2 into the link field`

`of the record pointed to by pointer 1.`

`*/`

`listpointer pointer1,pointer2;`

`{`

`lists[pointer 1].link = pointer2;`

`}`

`listpointer avail()`

`/* Returns a pointer to storage allocated`

`for a list record.`

`*/`

`{`

`static int t=0;`

`t++;`

`return(t);`

`}`

`typedef listpointer succ_collection[LIMIT];`

`insert(i,j,succ)`

`/* Add j into the ith collection in succ. */`

`int i,j;`

`succ_collection succ;`

`{`

`listpointer pointer,avail();`

`pointer = avail();`

`setinfo(pointer,j);`

`setlink(pointer,succ[i]);`

`succ[i] = pointer;`

`}`

`succinitialization(n,succ)`

`/* Initializes all n collections of succ to empty. */`

`int n;`

`succ_collection succ;`

`{`

`int i;`

`listpointer setnull();`

`for (i=1;i<=n;i++)`

`succ[i] = setnull();`

`}`

`listpointer access_succ(i,succ)`

`/* Returns a pointer to the i collection in succ. */`

`int i;`

`succ_collection succ;`

`{`

`return(succ[i]);`

`}`

`typedef struct`

`{`

`outputarray rank;`

`int next;`

`}rankingrecord;`

`rankingrecord ranking;`

`1 allocates storage for ranking`

`copy(n,topologicalsort,ranking)`

`/* Copies the rank field of ranking`

`into topologicalsort.`

`*/`

`int n;`

`outputarray topologicalsort;`

`rankingrecord ranking;`

`{`

`int i;`

`for (i=1;i<=n;i++)`

`topologicalsort[i] = ranking.rank[i];`

`}`

`typedef int bagcollection;`

`baginitialization(pbag,n,count)`

`/* Initializes the bag so it contains`

`only objects whose counts are zero.`

`*/`

`bagcollection *pbag;`

`int n;`

`countcollection count;`

`{`

`int i;`

`ranking.next = 1;`

`*pbag = 1;`

`for(i=1;i<=n;i++)`

`if(iszero(i,count))`

`{`

`ranking.rank[*pbag] = i;`

`*pbag = *pbag + 1;`

`}`

`}`

`emptybag(bag)`

`/* Returns true only if bag is empty. */`

`bagcollection bag;`

`{`

`return(bag == ranking.next);`

`}`

`remove(pbag,pobj)`

`/* Sets obj to an object to be removed`

`from bag, and removes it.`

`*/`

`bagcollection *pbag;`

`int *pobj;`

`{`

`*pobj = ranking.rank[ranking.next];`

`ranking.next = ranking.next + 1;`

`}`

`process(listname,recordpointer,pbag,count)`

`/* Decreases the count of the successor pointed`

`to by recordpointer and adds it to the bag if`

`its count has become zero.`

`*/`

`listpointer listname,recordpointer;`

`bagcollection *pbag;`

`countcollection count;`

`{`

`int currentsucc;`

`currentsucc = info(recordpointer);`

`decrease(currentsucc,count);`

`if (iszero(currentsucc,count))`

`{`

`ranking.rank[*pbag] = currentsucc;`

`*pbag = *pbag + 1;`

`}`

`}`

`topsort(pn,topologicalsort)`

`/* Inputs the number of objects n and the`

`partial order and generates a solution in`

`topologicalsort.`

`*/`

`int *pn;`

`outputarray topologicalsort;`

`{`

`countcollection count;`

`succ_collection succ;`

`bagcollection bag;`

`int i,j,obj;`

`printf("\n enter n between 1 and %d\n",LIMIT-1);`

`scanf("%d",pn);`

`predinitialization(*pn,count);`

`succinitialization(*pn,succ);`

`while (nextpair(&i,&j))`

`{`

`increase(j,count);`

`insert(i,j,succ);`

`{`

`baginitialization(&bag,*pn,count);`

`while(!emptybag(bag))`

`{`

`remove(&bag,&obj);`

`update(succ,obj,&bag,count);`

`}`

`copy(*pn,topologicalsort,ranking);`

`}`

`nextpair(pi,pj)`

`int*pi,*pj;`

`/* Input the next pair and return true`

`only if it was not the sentinel pair.`

`*/`

`{`

`print("\n enter a pair \n");`

`scanf("%d %d",pi,pj);`

`return(!((*pi == 0) && (*pj == 0)));`

`}`

`update(succ,obj,pbag,count)`

`/* Update the counts of all successors of obj`

`and place any whose counts become zero`

`into bag.`

`*/`

`succ_collection succ;`

`int obj;`

`bagcollection *pbag;`

`countcollection count;`

`{`

`listpointer listname,recordpointer,access_succ();`

`listname = access_succ(obj,succ);`

`recordpointer = listname;`

`while(anotherrecord(recordpointer))`

`{`

`process(listname,recordpointer,pbag,count);`

`recordpointer = next(recordpointer);`

`}`

`}`

Note that the ranking and bag implementations are not independent. Thus, if it is desirable to change the implementation of one, the other is also affected. As written, the bag acts as a stack, but it may be important to pick the entry to be removed from the bag more selectively. One way to do this is to implement the bag as a priority queue. In any case, to make ranking and bag independent requires changing their declarations, definitions, and basic operations.

# 11.4: Analysis of Topsort

Initializing the bag at the start of phase II takes time proportional to n, since it involves traversing the count array and placing each object whose count is zero into the bag. The while loop body of phase II, unlike that of phase I, does not take the same amount of time on every repetition. Task 5a takes constant time, but task 5b depends on the number of successors of the object that was removed by task 5a. The loop itself is executed n times, once for each object output.

How can we determine the total loop time required? Notice that each of the n objects will eventually be output in some loop execution. We do not know in what order the objects will be output. However, the time taken in its particular loop execution for each object output is the same. This time is at most a constant plus time proportional to the number of successors of the object. Thus, the total time for the while loop in phase II is the sum of the time required to output each object. The total time is then a constant times n plus time proportional to the sum

[(number of successors of object 1) plus (number of successors of object 2) . . . plus the (number of successors of object n)]

This sum is just the total number of successors, m. Hence the total time for phase II is made up of the same kinds of components as the total time for phase I. We conclude that the total time for this implementation has the same form.

Note that the search-based algorithm could take time O(n!). The straight-forward implementation of the construction-based algorithm could take time O(n m). Topsort takes time of the form c1 + c2n + c3m and represents a very substantial improvement. It was made possible because we were able to determine precisely, and to obtain efficiently, the information required to do the processing steps of the algorithm. The topological sort problem is more complex than earlier ones in this book, but it illustrates the same theme. The processing to be done determines the data structures that are most appropriate. Clearly, any implementation of an algorithm that does topological sorting must take time of the form an + bm, since it is necessary to read in all m input pairs and output all n objects.

How much storage does the implementation require? Suppose the program is to run correctly for values of n between 1 and 20. The only difficulty in determining the actual amount of storage required is in deciding what length to declare for lists. This depends on how large m may be. In general, if there are n objects, each object can have no more than n - 1 successors--that is, an arrow to every other object. There are then at most n(n - 1) possible successors. Each successor requires one record of the lists array. Actually, because of the asymmetry property, at most one-half of the n(n - 1) possibilities can appear. Hence we need a total of at most 1/2 n(n - 1) records for lists. If n is 20, then (20 19)/2 records will do. The storage required is proportional to n2.

# 11.5: Behavior for Replicated Pairs or Loops

In the solution to the topological sorting problem, it is assumed that each distinct input pair appears only once and also that the input contains no loops. Either assumption might be violated. Of course, more obvious errors could occur. For example, n or one of the input pair members could be negative or out of range. It is not difficult to add a validation routine to check for these kinds of input errors. Subtler errors, such as replication of pairs or the occurrence of loops, are not as obviously remedied.

What does happen if pairs are replicated or loops occur in the input ? How would you recognize loops? Replication of an input pair i, j causes the count of j to be 1 larger than it should be. It also causes the successor j to appear on the list of successors of i one more time. When object i is eventually removed, its list of successors is traversed. This results in the count of j being reduced one additional time, so that the extra increase due to the i, j replication is cancelled. The implementation will thus work correctly as long as there is room for the extra successor records to appear in lists. If there is no room to accommodate these extra records, it is not possible to predict what will occur when the implementation is executed.

Loops, on the other hand, result in some objects never being output. Objects that are involved in a loop, or that are the successors of an object in a loop, will never have their counts go to zero, and will never appear in the bag of objects. In fact, had the test for completion been "S not empty" or "n objects output," loops in the input would cause an infinite loop in the program. It should now be clear that next-1, when the loop in phase II is exited, will be the actual number of objects that were output by the loop. If this is less than n, then loops occurred in the input. This can provide a simple test for loops.

# 11.6: Final Comments on Topsort

As already noted, the implementation of the output ranking and the bag are coupled because they share storage. As a result they are not independent. This means that a change in the choice of implementation for one will affect the other. In general, such a situation is to be avoided--and, as pointed out earlier, could have been avoided. Certainly the small saving in time and storage did not warrant the added complexity.

There are, however, some important storage considerations that were alluded to earlier. Topsort will run out of storage before it runs out of time, since storage requirements grow as n2. The bulk of the storage needed is taken by the lists array. Suppose a maximum size, based on the available storage of the computer system, is declared for the lists array. Say its length is 50,000. Assuming each of its records takes two entries, this provides enough storage to guarantee the solution of any problem with no more than 25,000 successors (m 25,000). It makes no difference how the successors are distributed among the objects; only the total number is relevant.

Suppose, instead, that the decision had been to represent each collection of successors by dedicating an array to the collection. Since the programmer does not know in advance how the successors will be distributed, each of the required n arrays should have the same length. Lists are no longer necessary, since the successors can be placed sequentially in the proper array. Of course, a variable will be needed to keep track of the last successor in each array. An additional array may be used for these pointers. If n is to be no greater than (say) 500, then each of the arrays containing the successors can be declared of length 50,000/500, or 100. The upshot is that the solution may now be guaranteed for a different class of problems. These problems must have n 500, and each object may have no more than 100 successors. Even though the total number of successors may now be 50,000 (twice as many as before), their distribution is critical. When storage is at a premium, such considerations are important.

Had dynamic memory been used instead of the lists array for storage of the successor records, the program would contain no explicit storage limitation (other than the declarations for the length of count, succ, and rank). Still, the maximum dynamic memory size would have imposed a limit on the value of m for which the program would execute.

# 11.7: Reviewing Methodology

A topological sort produces a ranking of objects that satisfies constraints on their allowable positions within the ranking. The obvious algorithm for finding a topological sort, searching through all rankings until one satisfying the constraints is found, is not feasible. A feasible algorithm was developed by constructing a ranking that satisfied the constraints. The initial implementation merely produced an image of the input data in memory. It was improved significantly by using an array to contain predecessor counts, creating lists of successors, and introducing a bag to hold objects whose predecessor counts became zero. This solution was achieved by a process of stepwise refinement, stressing data abstraction, encapsulation, modularity, and the proper choice of data structures. The functional modularity of the final solution allowed immediate application of a routine developed earlier--the list traversal routine. Again, because of functional modularity, it was not difficult to determine where and how to build in appropriate checks of the input data.

More generally, the analysis of the storage and time requirements of a fairly complex program was demonstrated. Even though this cannot always be accomplished, or may be difficult for complex programs, it serves as an example of what we hope to be able to do.

# Exercises

1. Within a textbook, chapters cover specific topics. The information required to understand each topic is expected to have appeared before the topic appears in the book. Suppose you are given a list of topics and the other topics on which each depends. How might you select an ordering of the topics for their appearance in the book?

2. Which of these binary relations is a partial order on S?

a. "Square root of" on the set S of all real numbers greater than 1

b. "Is older than" on the set S of all your relatives

c. "Sits in front of" on the set S of all students in a class

d. "Lives diagonally across from" on the set S of all people

S = 1, 2, 3, . . . , 12

R = (3, 2), (4, 6), (7, 9), (12, 10), (5, 6), (2, 4), (8, 9), (2, 6), (3, 6), (7, 12), (3, 4), (7, 10)

b. Suppose the output ranking is not kept in the ranking record but, instead, is simply printed. How must the program and data abstraction implementations change?

5b.i. For each successor of the output object, decrease its predecessor count by 1.

5b.ii. For each successor of the output object, if its predecessor count is zero, add the successor to the bag.

a. ow should the implementation of the data abstraction algorithm (on p. 503) be modified to reflect this refinement?

b. rite implementations for tasks 5b.i and 5b.ii that use traverse as a tool. This should include writing the corresponding two process functions.

c. ow will this expansion of task 5b affect the time required for the algorithm?

`7 3, 5 6, 4 2, 7 3, 6 8`

# Suggested Assignments

a. What does this mean?

b. Write a function, number, that also treats them as data abstractions and returns the number of objects in the bag when it is invoked. When it returns, the bag must contain exactly the same objects as before number was invoked. Assume number does not have access to information about the output ranking.