基于圖的譜分割技術的面向對象軟件系統分解

摘要：主要是以一種帶權類依賴圖作為面向對象系統的UML類圖的抽象表示，其中類依賴圖的各邊上權值對應于類圖中的相應關系。針對帶權類依賴圖運用代數圖論中圖的Laplace譜的連通特性以迭代分割的方式對其進行劃分，得到所需開發的系統構件。通過實驗表明，該方法是一種有效的面向對象軟件系統分解方法，并且分解所得到的構件具有較高的內聚性。

關鍵詞：軟件構件； 構件提取； Laplace譜； 內聚耦合

中圖法分類號：TP311．5文獻標識碼：A

文章編號：1001－3695(2007)01－0054－04

1引言

在軟件系統開發過程中，我們可以采用構件技術將一個軟件切分成許多部分來進行單獨開發，然后再組裝起來，每一個部分即為構件，這就是基于構件的軟件開發。其優點是利于控制質量、多人合作和擴充功能，是軟件工程中一種重要的開發方法，并為軟件復用提供了強有力的支持。對于面向對象系統而言，構件可以是類、類樹、類簇，甚至是一個由眾多類組成的框架[1]。

從現有文獻來看，面向對象系統分解方法大致可分為兩類，即知識匹配和結構分析。知識匹配方法以系統中目標構件的相關知識為驅動，將這些知識與系統中的成分進行匹配，相匹配的成分就成為候選構件。這類方法的主要缺點是匹配中所需知識的獲取和表示在實踐中通常比較困難。結構分析方法將軟件系統抽象為可以數學化表示的結構，然后對抽象出來的結構進行分析，將整個結構分解為多個子結構，每個子結構對應一個候選構件。基于結構分析的面向對象系統分解方法有聚類分析法[2]和有向帶權圖迭代法[3]等。聚類分析法必須有一個進行聚類的閾值，而有向帶權圖迭代法得到的是系統的所有獨立性較高的劃分集合，子集與子集間可能存在交集，還需根據語義進行排除。鑒于此，本文依據代數圖論中的Laplace譜的特性提出了一個新的系統分解方法。

代數圖論是近三十年發展起來的一個新興分支，隨著計算機的快速發展，該學科目前在國際上的研究十分活躍。除了傳統的譜理論外，它側重研究圖的對稱性以及在網絡理論、編碼理論等中的應用，而且在通信理論、軟件工程、優化設計等方面均有實際的應用背景。

本文主要是以一種帶權類依賴圖作為面向對象系統的UML類圖的抽象表示，其中類依賴圖的各邊上的權值對應于類圖中的相應關系。針對帶權類依賴圖運用代數圖論中圖的Laplace譜分割技術[4]以迭代的方式對其進行劃分，得到所需開發的系統構件，以備從中挑選出可復用構件，如圖1所示。

2帶權類依賴圖的構造

UML中總共提供了用例圖、類圖、對象圖、序列圖、協作圖、狀態圖、活動圖、組件圖和部署圖這九種圖。在面向對象系統的建模中，類圖是最常用的圖，它用來說明系統的靜態結構。事實上，類是對一組具有相同屬性、操作、關系和語義的對象的描述，它刻畫了各類之間的繼承、關聯、組合、聚集等各種復雜的關系。因此，我們以類為頂點，類與類之間的關系作為邊，構造出表征整個系統的類依賴圖；再根據類與類之間關系的強弱賦予其一定的權值，就得到了一個系統的帶權類依賴圖。

在UML圖中類與類之間的關系有靜態關系和動態關系。類圖表征了系統中類之間的靜態結構，而序列圖、協作圖表征了系統中類之間的動態結構。因此，我們以下列公式來計算類與類之間的權值[2]：

其中RSij為類i與類j之間的靜態權值，RDij為類與類之間的動態權值。

靜態權值根據類圖中的關系來量化。類圖中常見的關系有關聯、泛化、依賴和實現。其中，關聯是一種結構關系，它描述了一組鏈，鏈是用于鏈接對象的，聚集是一種特殊的關聯，它描述了整體與部分之間的結構關系；泛化是一種特殊一般關系，特殊元素(子元素)的對象可以替代一般元素(父元素)的對象，這樣，子元素就可以共享父元素的結構和行為；依賴是兩個設施之間的語義關系，其中一個設施的變化會影響到另一個設施的語義；實現是泛化關系和依賴關系的結合，通常在接口和實現它們的類或組件之間用到這種關系。表1列出了所有的關系，并根據關系的強弱列出了其權值的大小關系[5]。

表1靜態權值表

如果圖G連通，我們可以根據Fiedler向量x2將元素數值大于0的對應點和數值小于0的對應點劃分開；如果圖G不連通，我們可以根據任一零特征值對應的特征向量中元素的兩種數值將這兩種數值的對應點劃分開。這樣，圖G就被分解成兩個子圖，這種劃分使得被切掉的邊的權值總和達到最小。

基于以上描述，我們可以得到一個圖的譜二分算法，將圖G分解成兩個圖N+，N-。本文的Laplace譜二分算法主要依據文獻[4]，但文獻[4]中的算法只是針對連通圖。由于一個連通圖在分割過程中可能會產生不連通的子圖，如何對一個不連通的子圖繼續進行分割，對此本文將文獻[4]中的算法進行了改進，依據不連通圖的Fiedler值為0以及Laplacian矩陣零特征值的特性，在算法中增加了針對不連通圖進行分割的處理。

算法的偽代碼表示如下：

4系統分解算法

根據面向對象系統的UML圖，繪制以類為頂點、關系為邊的帶權類依賴圖。以上述分割技術為一次迭代算法，對帶權類依賴圖進行迭代分解，直至分解的子圖不如其父圖內聚性好時為止。這樣我們可以得到一系列的子圖，每一個子圖就是一個構件。

算法的偽代碼表示如下：

5構件的環形依賴

對于構件化軟件系統來說，系統的構件化應遵從無環依賴原則，即在構件的依賴關系圖中不允許存在環。因為環形依賴的存在會使開發流程復雜化，很難確定構件構建的順序，甚至就不存在恰當的順序[9]。

要清除環形依賴首先要發現環形依賴。我們仍舊根據UML圖抽象出來的帶權類依賴圖，再根據構件分解出來的子圖對帶權類依賴圖進行化簡。以每個子圖作為新的頂點，從帶權類依賴圖中提取出子圖與子圖間的依賴關系作為頂點間的邊，構造出有向構件依賴圖。針對構件依賴圖求其所有強連通分量，如果強連通分量的個數小于圖中點的個數，則說明在構件依賴圖中存在環形依賴，而點數大于1的強連通分量就是環形依賴所在。

要清除環形依賴主要是更改設計。如果存在環形依賴的構件規模均不大的話，可以直接將它們進行合并即可消除環形依賴。

環形依賴發現算法的偽代碼如下：

輸入：模塊子圖集合GraphList、面向對象系統的帶權類依賴圖G；

輸出：去除環形依賴后的模塊子圖集合GraphList′。

6度量

本文主要使用幾個簡單的度量值去量化構件的內聚性、耦合性屬性[9]。

6．1內聚性度量

（1）輸出依賴（We），指處于該構件的內部并依賴于該構件外的類的所有依賴值的總和。

（2）內部依賴（Wi），指處于該構件內部的類之間所有依賴值的總和。

（3）內聚性（Coh）

Coh=WiWe+Wi

該度量的取值范圍是[0，1]。N=1表示該構件具有最大的內聚性。

6．2耦合性度量

耦合性(Cou）：

Cou=WeWe+Wi

該度量的取值范圍是[0，1]。C=1表示該構件具有最大的耦合性。

7實例研究

下面針對一個面向對象的MIS——日清月結系統為例具體驗證本文方法。日清月結系統為某軍區大型戰區油網管理系統的一個子系統，主要由24個類構成。圖2為從UML圖抽象出來的帶權類依賴圖。

表2系統分解結果表

5罐裝界面、罐裝證件管理、罐裝事務、罐裝證件、罐裝記錄管理、罐裝記錄(0，1)

從表2的分解結果來看，每個構件的劃分與人工依據用例圖進行劃分的結果基本相符。從圖3可以看出，每個構件均滿足高內聚低耦合的要求。

表3為針對八個大小不等的面向對象軟件系統（部分取自文獻[5，9]）運用本方法進行分解的結果。可以看出本方法分解出來的構件規模適中，且內聚性較高。

表3分解構件內聚性結果

8結束語

有效的系統分解是構件提取的關鍵技術之一。本文在分析現有面向對象系統分解方法的基礎上，提出了一種基于圖的譜分割技術的面向對象系統分解方法。這種方法根據類之間的依賴關系，充分利用了系統的構造性，結合科學的數學方法，因而能有效地對面向對象系統進行分解，為構件提取奠定基礎。本文構件性能的評價使用了比較簡單的度量方法，下一步我們將采取更精細的度量方法，從而對靜態權值的量化作更精確的分析，以及更好地識別可復用構件。同時，我們將針對遺產工程運用本方法作進一步的研究。

參考文獻：

［1］吳穹. 構件組裝技術研究[D］.北京：北京大學， 1998.

［2］徐瑋， 尹寶林， 李昭原. 企業信息系統業務構件設計研究[J].軟件學報， 2003，14(7):12131220.

［3］羅景，趙偉，姜人寬， 等. 基于有向帶權圖迭代的面向對象系統分解方法[J]. 軟件學報， 20-04，15(9):12921299.

［4］Spiros Xanthos.Clustering ObjectOriented Software Systems Using Spectral Graph Partitioning[A]. ACM Student Research Competition[EB/OL].http：//leto.cs.uiuc.edu/~spiros/publications/ACMSRC.pdf，2005.

［5］周毓明. 軟件度量中的若干問題研究[D].南京：東南大學， 2002.

［6］B Mohar. Some Applications of Laplace Eigenvalues of Graphs[C]. Kluwer， Dordrecht: Algebraic Methods and Applications， volume 497 of NATO ASI Series C， 1997.227275.

［7］M Fiedler.Algebraic Connectivity of Graphs[J].Czechoslovak Mathe￣matical Journal， 1973，23(98):298305.

［8］M Fiedler. A Property of Eigenvectors of Nonnegative Symmetric Matrices and Its Applications to Graph Theory[J]. Czechoslovak Mathematical Journal， 1975，25(100):619633.

［9］Robert C Martin. 敏捷軟件開發：原則、模式與實踐[M]. 鄧輝. 北京：清華大學出版社， 2003.249256.

作者簡介：

齊晶晶(1979)，男，河北蠡縣人，碩士研究生，主要研究方向為面向對象分析和設計；郭跟成（1971），男，河南孟州人，副教授，碩士，主要研究方向為軟件工程、面向對象、軟件復用。

注:本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文