ISSN:
1432-0541
Schlagwort(e):
Inheritance graphs
;
Linear-time complexity
;
Modules
;
Dominators
;
Decomposition
;
Substitution
;
2-Connectivity
;
Linear extension
Quelle:
Springer Online Journal Archives 1860-2000
Thema:
Informatik
,
Mathematik
Notizen:
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]).
Materialart:
Digitale Medien
URL:
http://dx.doi.org/10.1007/BF01189070
Permalink
