Topological Sorting

ToC

Allegro CL

ANSI Common Lisp

4 Types and Classes

4.3 Classes

4.3.5 Determining the Class Precedence List

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 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₁, ... ,C_n such that C_i precedes C_i+1, 1 <= i<n, and C_n precedes C₁.

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 S_C, are inconsistent.)

In more precise terms, let {N₁, ... ,N_m}, m2, be the classes from S_C with no predecessors. Let (C₁ ... C_n), n1, be the class precedence list constructed so far. C₁ 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₁ and T₂ be subgraphs whose only element in common is the class J. Suppose that no superclass of J appears in either T₁ or T₂, and that J is in the superclass chain of every class in both T₁ and T₂. Let C₁ be the bottom of T₁; and let C₂ be the bottom of T₂. Suppose C is a class whose direct superclasses are C₁ and C₂ in that order, then the class precedence list for C starts with C and is followed by all classes in T₁ except J. All the classes of T₂ are next. The class J and its superclasses appear last.