#

##
4.3.5.1 Topological Sorting

Topological sorting proceeds by finding a class C in SC 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 SC, and remove all pairs of the form (C,D), D<ELEMENT-OF>SC, 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 SC 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 C1,...,Cn such that Ci precedes Ci+1, 1<=i<n, and Cn precedes C1.

Sometimes there are several *classes* from SC 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 Rc, c<ELEMENT-OF>SC, are inconsistent.)

In more precise terms, let {N1,...,Nm}, m>=2, be the *classes* from SC with no predecessors. Let (C1...Cn), n>=1, be the *class precedence list* constructed so far. C1 is the most specific *class*, and Cn is the least specific. Let 1<=j<=n be the largest number such that there exists an i where 1<=i<=m and Ni is a direct *superclass* of Cj; Ni 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 T1 and T2 be subgraphs whose only element in common is the class J. Suppose that no superclass of J appears in either T1 or T2, and that J is in the superclass chain of every class in both T1 and T2. Let C1 be the bottom of T1; and let C2 be the bottom of T2. Suppose C is a *class* whose direct *superclasses* are C1 and C2 in that order, then the *class precedence list* for C starts with C and is followed by all *classes* in T1 except J. All the *classes* of T2 are next. The *class* J and its *superclasses* appear last.

*Copyright 1996-2005, LispWorks Ltd. All rights reserved.*