Authors:
Class hierarchy can be conveniently represented using Boolean square matrices. This mathematical rendering makes possible the use of matrix algebra to diagnose problematic class hierarchy structures.
To form the class hierarchy matrix, we use a square Boolean matrix with dimensions equal to the number of classes under consideration. Each class would correspond to both a row and a column. It is important to use the same row and column for each class so that if a class corresponds to the m-th row, then it also corresponds to the m-th column.
Inheritance relationships are denoted by putting Boolean trues in the cells of the matrix where the row class inherits from the column class and by putting Boolean falses everywhere else, including the diagonal where the row class is the same as the column class. For instance, suppose we have three classes of interest, A, B, and C, a 3x3 matrix is called for. We let the first row and column correspond to A; the second row and column correspond to B; the third row and column correspond to C. Furthermore, suppose that C is a subclass of B and B is a subclass of A, then the class hierarchy matrix would be ((0 0 0) (1 0 0) (0 1 0)), where ones denote Boolean trues and zeros denote Boolean falses.
We have found the class hierarchy matrix to aid immensely in finding transitive inheritances and detecting circular inheritances. Transitive inheritances are superclass-subclass relationships separated by at least one generation. For example, if C directly inherits from B and B directly inherits from A, then C inheriting from A would be considered a transitive inheritance. Circular inheritance occurs when a class simultaneously inherits from and is inherited by another class. For projects involving a handful of classes, circular inheritance could be found easily through inspection, but for large-scale object migration projects where hundreds of classes created by different programmers are involved, maintaining legitimate inheritance structures cannot be accomplished by inspection alone. Class hierarchy matrices and matrix algebra remedy the situation by providing a fast and accurate algorithm for finding classes entangled in circular inheritance structures.
To use the class hierarchy matrix to find transitive inheritances and detect circular inheritances, we first form the class hierarchy matrix by inserting trues into cells where the row class inherits from the column class. After the class hierarchy matrix (denoted by the symbol C) has been generated, we form the following series and perform the summation C^1 + C^2 + C^3 + ... + C^rank(C) [*]. The operation yields a new Boolean square matrix with the same dimension as the class hierarchy matrix. All inheritances, both direct and transitive, would be marked in the new matrix with Boolean trues. Classes involved in circular inheritances would be marked in the new matrix with Boolean trues on their corresponding diagonal element.
Here is an example to demonstrate finding transitive inheritances, suppose that we have four classes, A, B, C, D; B is a subclass of A, C is a subclass of B, D is a subclass of A. The class hierarchy matrix would be ((0 0 0 0) (1 0 0 0) (0 1 0 0) (1 0 0 0)). Performing the summation yields the new matrix ((0 0 0 0) (1 0 0 0) (1 1 0 0) (1 0 0 0)). The new matrix contains an extra true in the row corresponding to C and the column corresponding to A, showing that the transitive inheritance of C being a subclass of A has been found.
We now add an inheritance, A is a subclass of C, to the above example to demonstrate detecting circular inheritances. The class hierarchy matrix becomes ((0 0 1 0) (1 0 0 0) (0 1 0 0) (1 0 0 0)). Performing the summation yields the new matrix ((1 1 1 0) (1 1 1 0) (1 1 1 0) (1 1 1 0)). The diagonal of rows corresponding to classes A, B, and C have trues, showing that these classes are involved in circular inheritances.
The use of Boolean matrices as a tool of OO analysis and design need not be limited to class inheritance structures. Any group of objects with well-defined relationships to each other could be represented in a matrix. For example, instead of using inheritance relationship, we could use collaborative relationships. A true would be entered in the cell where a row class collaborates with a column class.
In practice, we have successfully applied the matrix technique to packages in the Digitalk Team/V environment, using packages as rows and columns. A true would be entered in the cell where the row package contains subclasses of classes stored in the column package.
[*] Boolean matrix operations are performed in the same way as numerical matrix operations except that whenever two elements are added in numerical matrices, they must be "Ored" in Byoolean matrices; whenever two elements are multipled, they must be "Anded" in Boolean matrices.