A LINEAR ALGORITHM TO DECOMPOSE INHERITANCE GRAPHS INTO MODULES

Inheritance graphs of object-oriented languages can be decomposed into independent subgraphs, or modules, which are inheritance graphs thems elves. This paper is devoted to the study of efficient algorithms of d ecomposition into modules similar to substitution decomposition algori thms. For 2-connected inheritance graphs we search for maximal modules (under inclusion), whereas we show that the significant modules of no n-2-connected graphs are the biconnected components. For the 2-connect ed case, a method based upon a property of greedy linear extensions is proposed. However, in both cases a linear-time complexity algorithm i s provided to decompose into modules. Furthermore, the algorithm can b e inserted into the inheritance mechanism (such as in CLOS [14]).