Decomposition of Weighted Graphs Using the Interchange Partitioning Technique.

摘要

The objective of this study is to develop a systematic approach to the architectural design of complex software systems. This contract builds on earlier work, in which a graph modelling and decomposition methodology was used to operate upon a set of functional requirements and their interrelationships to generate an architectural design. This report introduces a new algorithm for partitioning weighted graphs in a hierarchical manner. The algorithm, termed the interchange partitioning technique, has been developed to aid in the analysis of requirements graphs generated through the Systematic Design Methodology. However, it is sufficiently general to be of use in many other types of graph analysis problems as well. As well as describing and giving examples of the basic interchange technique, this report also includes a discussion of certain simplifications that may be made to the algorithm in order to significantly improve its efficiency without hampering its effectiveness. Also, a master control algorithm is presented for guiding the execution of a complete graph decomposition using the interchange partitioning technique. (Author)