ISSN:
1432-0541
Keywords:
Inheritance graphs
;
Linear-time complexity
;
Modules
;
Dominators
;
Decomposition
;
Substitution
;
2-Connectivity
;
Linear extension
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract Inheritance graphs of object-oriented languages can be decomposed into independent subgraphs, or modules, which are inheritance graphs themselves. This paper is devoted to the study of efficient algorithms of decomposition into modules similar to substitution decomposition algorithms. For 2-connected inheritance graphs we search for maximal modules (under inclusion), whereas we show that the significant modules of non-2-connected graphs are the biconnected components. For the 2-connected case, a method based upon a property of greedy linear extensions is proposed. However, in both cases a linear-time complexity algorithm is provided to decompose into modules. Furthermore, the algorithm can be inserted into the inheritance mechanism (such as in CLOS [14]).
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01189070
