4.3.5.1 Topological Sorting

Topological sorting proceeds by finding a class C in~S_C such that no other class precedes that element according to the elements in~R. The class C is placed first in the result. Remove C from S_C, and remove all pairs of the form (C,D), D\in S_C, from R. Repeat the process, adding classes with no predecessors to the end of the result. Stop when no element can be found that has no predecessor.

If S_C is not empty and the process has stopped, the set R is inconsistent. If every class in the finite set of classes is preceded by another, then R contains a loop. That is, there is a chain of classes C_1,...,C_n such that C_i precedes C_{i+1}, 1<= i<n, and C_n precedes C_1.

Sometimes there are several classes from S_C with no predecessors. In this case select the one that has a direct subclass rightmost in the class precedence list computed so far. (If there is no such candidate class, R does not generate a partial ordering—the R_c, c\in S_C, are inconsistent.)

In more precise terms, let {N_1,...,N_m}, m>= 2, be the classes from S_C with no predecessors. Let (C_1... C_n), n>= 1, be the class precedence list constructed so far. C_1 is the most specific class, and C_n is the least specific. Let 1<= j<= n be the largest number such that there exists an i where 1<= i<= m and N_i is a direct superclass of C_j; N_i is placed next.

The effect of this rule for selecting from a set of classes with no predecessors is that the classes in a simple superclass chain are adjacent in the class precedence list and that classes in each relatively separated subgraph are adjacent in the class precedence list. For example, let T_1 and T_2 be subgraphs whose only element in common is the class J. Suppose that no superclass of J appears in either T_1 or T_2, and that J is in the superclass chain of every class in both T_1 and T_2. Let C_1 be the bottom of T_1; and let C_2 be the bottom of T_2. Suppose C is a class whose direct superclasses are C_1 and C_2 in that order, then the class precedence list for C starts with C and is followed by all classes in T_1 except J. All the classes of T_2 are next. The class J and its superclasses appear last.