基于中介中心性的類重要性度量的研究

成小芹， 王一莉

(南京工業大學電子與信息工程學院，江蘇南京211816)

0 引 言

在面向對象軟件的測試過程中，如何合理有效地分配有限的資源，從而在規定的時間內完成軟件的測試，是一個非常重要的問題。目前是利用內聚性、耦合性和復雜性來判別可能存在缺陷的類，然后據此分配測試資源。但是，僅僅通過識別可能有質量缺陷的類不足以為資源的分配提供依據，還需要識別重要的類。對于重要的類而言，即使它們的內聚性、耦合性和復雜性都很合理，也需要給它們分配相對多的資源進行更加仔細的測試，因為重要的類隱藏的故障就可能越多。從這個角度來說，類的重要性度量可以看作是提高軟件可測試性的一個補充。目前對類的重要性的度量的研究比較少，中心性是網絡分析中的最基本的概念之一，研究人員依據各種標準提出了許多中心性指標來度量網絡中的重要的節點，中介中心性就是其中一個很重要的指標，它可以用在很多方面，如社會關系學，生物學以及道路網絡等，在實際的應用中依據節點的重要性和角色，制定出更加可行的解決方案。由此想到，中介中心性同樣可以應用到類的重要性的度量中，找出類中重要的類，然后對這些類進行重點測試，從而提高軟件可測性?，F在面向對象技術在軟件工業中應用比較廣泛，而除了與傳統測試方法具有相似之處，面向對象軟件還為可測試性制造了一些獨特的障礙。類圖中存在的客戶供應關系會引起可測試性問題。文章針對面向對象軟件，使用UML類圖對其進行類的重要性度量，希望能對合理安排軟件測試資源，保證軟件質量，提供借鑒和參考。

1 類的重要性

1.1 重要類的定義

如果一個類被很多類依賴，那么對這個類進行修改有可能會影響許多依賴于它的類，一般可以認為這樣的類是重要的類。其實對于如何判斷重要的類可以根據用戶給定的標準來定義，例如，如果一個類直接或間接地依賴于許多其他的類，那么這個類就有可能比其他的類更容易產生故障，對測試者而言這樣的類也是重要的類，需要進行重點測試。

1.2 類重要性的標準

上文說到判斷重要的類的標準可以根據用戶的特定需求，下面列出常規的標準：

標準1：一個類是重要的當且僅當有很多重要的類依賴于它。

標準2：一個類是重要的當且僅當它依賴于很多重要的類。

標準3：一個類是重要的當且僅當它接近類間依賴圖的中心。

根據標準1的定義，一個類重要與否取決于2個要素：①依賴于它的類的數量越多，它就越重要；②依賴于它的類的重要程度越高，它就越重要。同樣地，標準2用被一個類依賴的其他類的數量和重要程度來定義該類的重要性。文章僅討論依據標準3來度量類重要性的中介中心性。

2 基于UML類圖的分析

現在面向對象技術在應用中越來越廣泛，而面向對象軟件為測試提出了一些新的挑戰，如繼承、多態、動態綁定等。由于類圖常常不夠明確、完整，會導致對其錯誤的理解，結果可能引起錯誤地實現和無效的測試。由于繼承和動態綁定可能對測試工作產生影響，因此發現和掌握普遍隱含的控制依賴關系能為測試建立較好的基礎。

2.1 類圖中依賴關系

類圖是面向對象方法的核心，UML類圖描述了系統中的類和類之間的相互關系，其本質反映了系統中包含的各種對象的類型以及對象之間的各種靜態關系。在前文中也提到發現和掌握普遍隱含的控制依賴關系能為測試建立較好的基礎，對于一個比較復雜的系統模型來說，類與類之間的關系是非常復雜的，而隱含的控制依賴關系也就更加復雜。

(1)關聯依賴：UML類圖中類間的關聯關系提供了不同的類間對象可以相互作用的連接。關聯可以是二元的，也可以是多元的。其中多元關系可以轉化為二元關系。為了更清楚地描述關聯，關聯可擁有自己的屬性。關聯有單向關聯和雙向關聯。

(2)聚集依賴：聚集關系表示類與類之間的整體與部分的關系。如果部分類完全隸屬于整體類，并且部分類與整體類之間有同樣的生命期，則這樣的聚集關系是強聚合關系，又稱為組成關系。

(3)繼承依賴：繼承是面向對象的一種機制，即利用現有的類來定義新的類，子類(繼承類)可以共享父類(被繼承類)的屬性和行為，也可以擁有自己特殊的屬性和行為，對父類進行擴展。這種機制可以避免重復定義屬性和方法，同時也使類間的關系更加的清晰和直觀。

(4)一般依賴：一般依賴關系描述的是兩個類之間語義上的連接關系。一個類是獨立的，另一個類是非獨立的(也即是依賴的)，它依賴于獨立的類；如果獨立的類發生了改變，將會影響依賴該類的類。也即是一個類使用了另一個類。最常見的一般依賴關系是一個類是另一個類中方法的參數類型。

介于以上介紹的4種依賴關系，為便于討論，將其合并為主要的兩類，一類是普通依賴，當一個類C使用了另一個類D時，我們稱之為普通依賴。另一類是繼承依賴，當C≠D時，并且C繼承自D時，我們稱之為繼承依賴。

2.2 CDG圖的構造方法

在文獻[7]中，作者認為按照類圖進行測試設計時，類交互是最應當重視的問題。類交互是指兩個類之間有兩條及兩條以上的依賴路徑。通常這種結構是測試的難點，所以作者提出了用CDG(classdependencygraph)圖來捕獲類交互。與CDG圖相關的概念[7]介紹如下：

定義1 設類依賴圖CDG=(V,E)，V為節點vi集合，記為V={vi}，其中每一個節點表示面向對象系統的一個類，并且一個類有且只能由一個節點表示。E為節點間的有向邊集合，在兩節點間的一條邊表示在兩類之間存在依賴關系。每條邊上的標記表示類間依賴的類型。

定義2 邊標記，在CDG圖中的每一條邊表示系統中的兩個類之間的依賴。假設a∈C，b∈C，邊的標記代表依賴的類型。主要有兩種，正如前文所敘述的：①普通依賴(usage dependency)，用U表示，表示類a調用b，②繼承依賴 (inheritance)，用I表示，表示a繼承自b。

定義3 U標記。一般我們將方法集和U聯系起來，在方法集中，默認值是M(d)，轉化關系如圖1所示。

圖1 普通依賴

定義4 I標記。繼承標記包括兩個方面。假設a∈C，b∈C-{a}，且 a∈Parent(b)。

·邊，記為I-Child。從測試點來看，是需要從父類到子類的依賴的，因為任何時候父類發生時，子類一般也會發生。

·邊，記為I-Parent。這個從子類到父類的依賴是顯而易見的：當b調用方法m，m∈MINH(a)時，b依賴a。

I標記的轉化關系如圖2所示。

圖2 繼承依賴I的表示

這里要注明的是當a是接口的時候，邊是不存在的，因為在這種情況下，b是不能調用a的方法的，因此這時的轉化關系如圖3所示。而當a還依賴于其他的類的時候，從a發出的邊U標記是不存在的，這時U標記的邊被轉移到a的具體類，圖4是這一情況的轉化表示。

圖3 父類是接口情況的表示

3 中介中心性

3.1 基本概念

中介中心性的測量公式如下

圖4 接口依賴于其他類的情況

式中： ——從頂點 s∈V到頂點 t∈V的最短路徑的條數，

——從s到t經過頂點 的最短路徑的條數。

引理1 頂點 在頂點s到t的最短路徑上，，s，t∈V，當且僅當dG(s,t)=dG(s,)+dG(,t)。這里dG表示兩頂點之間的距離。

定義1 從頂點s出發的最短路徑上頂點 的前驅頂點集合為：Ps()={u∈V|∈E,dG(s,)=dG(s,u)+ (u,)}；是邊上的權值函數。

引理2 對于頂點

定義2 通過給定的成對的頂點的距離及路徑條數，可以得到經過 的一對頂點s，t∈V的對-依賴性，也即式(2)所示

為了得到頂點 的中介中心性值必須計算出這個頂點上所有的對-依賴性

定理1 任何頂點 上的s∈V的依賴性遵循關系

由此可以看出計算頂點的中介中心性需要兩部分：①計算所有頂點之間的最短路徑的長度和數目；②計算所有的對-依賴性。

3.2 中介中心性的計算

圖的廣度優先搜索(breadth_firstsearch)遍歷算法能夠用于計算圖中任何兩點之間的最短路徑值。為了計算任意兩點之間的最短路徑的條數以及節點的中介中心性值(以下稱Betweenness值)，在傳統的廣度優先搜索算法基礎上，對此進行了擴展，在擴展了的廣度優先搜索算法中，采用隊列和棧兩種數據結構來存放節點，依據節點不同的存儲位置，把圖中的每個節點在遍歷的過程中標記為3個狀態：①沒有進入隊列的節點，將其狀態定義為未探查；②進入隊列的節點，將其狀態定義為已探查但未訪問；③出隊列且入棧的節點，將其狀態定義為已訪問。

為計算節點的Betweenness值，算法可以分為兩個部分來實現：①遍歷算法，主要是實現對圖進行廣度優先遍歷，計算節點從源點s到 的距離，最短路徑條數等。②回溯算法，計算節點 的前驅節點的對-依賴性。

為計算類依賴關系圖(CDG)中的節點的Betweenness值，算法的原理描述如下：

(1)從CDG圖中任意選擇一個節點作為源節點s，以此節點開始對圖進行廣度優先搜索遍歷，同時計算出從源節點s到每個節點 的距離d(s,)、最短路徑的條數 (s,)、節點 的前驅節點集合P()以及記錄節點的訪問順序。

(2)在(1)遍歷的基礎上，以s為源節點的遍歷順序記錄在棧中，從棧頂的節點開始對每個節點進行回溯，也即按照節點的逆序訪問順序對每個節點進行回溯處理，用下面的公式對節點 的前驅節點的對-依賴性的值進行更新

之所以采用逆序訪問順序是因為對節點 進行回溯處理完后，節點 的 ()值就不會再改變，而采用廣度優先搜索遍歷為任意先后進行回溯的節點 ，，滿足d(s,)≥d(s,)提供了保障，當d(s,)≥d(s,)這樣的關系成立時，說明s到 的最短路徑一定不經過 。

(3)對每個節點 ，計算CBnew()=CBold()+ ()

(4)對CDG圖中的每個節點重復執行(1)～(3)，最后得到圖中所有節點的Betweenness值。

算法實現的代碼如下表示：

4 應用示例

在本文研究的基礎上結合一個小規模的類圖，應用文章所介紹的方法作分析。

4.1 CDG圖的節點的中介中心性

這一節中將通過一個小型類圖，應用上文所介紹的CDG圖，計算其頂點的Betweenness值，通過比較各個節點的中介中心性的值來識別重要的類。圖5是個小規模的類圖，其對應的CDG圖如圖6所示。

圖5 小型類圖

圖6 小型類圖的CDG圖

利用文章描述的算法，可以計算出這個小型類圖的CDG圖的各個節點的中介中心性值，如表1所示。根據這個值可以看出圖中b1的Betweenness值是最大的，說明b1的依賴性較強，是重要的類，在測試中應該分配較多的資源以發現該類中隱藏的質量缺陷，而c的Betweenness值是最小的，說明它的重要性很低，在圖中也可以很清晰地看出來，那么在測試的過程中就可以花費相對少的人力和時間。通過分析比各個節點的Betweenness值，可以很明了地看出節點重要性的等級，在測試的過程中就可以有的放矢，充分合理地分配有限的資源。

表1 節點的Betweenness值及等級

為了便于問題的討論，以上只是一個小型類圖的CDG圖的類重要性的度量。而在實際的應用中，面向對象軟件的規模是很大的，其對應的類圖也是錯綜復雜的，而類圖對應的CDG圖也必將更加的復雜。通過上述方法所度量的節點的中介中心性值可以指導我們的測試活動，從而提高軟件的可測試性、保證軟件的質量。

4.2 分析總結

類圖中反映的類之間的依賴關系是基于類圖的重要性度量的基礎，而將由類圖轉化而來的CDG圖與中介中心性結合起來分析節點的重要性，對軟件測試有指導作用。在現代軟件工程理論中，軟件測試應該貫穿于軟件的整個生命周期，可見軟件測試在軟件產品的開發過程中的地位是非常關鍵的，而且它的測試工作量也是非常多且繁重的。

從測試方法角度看，目前軟件測試主要分為靜態測試和動態測試，文章所提出的方法主要是屬于靜態測試范疇，對CDG圖的節點的重要性進行度量，根據結果進行測試資源的合理分配。從動態測試的角度來看，類測試是動態測試的一個方面，從這方面來說，度量類重要性對動態測試也是有一定的優化作用，可以提高動態測試的效率。

5 結束語

由以上分析可知，本文提出的將中介中心性應用到類依賴關系圖(CDG圖)中的方法，用來度量和分析面向對象軟件的類間依賴結構，以此分析面向對象軟件的類的重要性，對合理分配測試資源、減少軟件測試成本、提高軟件質量有指導作用。文中所研究的內容，對現實中大型的面向對象軟件的測試有一定的參考價值。當然，文中所研究的中介中心性的算發的時間復雜度是O(n3)，可以從邊的類型考慮，以降低其時間復雜度，需要后續的研究發現，這也是今后研究的重要方向。

[1]Ulrik Brandes.On variants of shortest-path betweenness centrality and their generic computation[J].Social Networks,2008,30(2):136-145.

[2]He Shan,Li Sheng,Ma Hongru.Betweenness centrality in finite components of complex networks[J].Physica A:Statistical Mechanics and its Applications,2009,388(19):4277-4285.

[3]Tore Opsahl,Filip Agneessens,John Skvoretz.Node centrality in weighted networks:Generalizing degree and shortest paths[J].Social Networks,2010,32(3):245-251.

[4]Newman M E J.A measure of betweenness centrality based on random walks[J].Social Networks,2005,27(1):39-54.

[5]胡順仁,陳偉民,廖昌榮,等.基于UML類圖的類之間依賴關系圖論問題研究[J].計算機工程,2006,32(12):1-2.

[6]殷劍宏,吳開亞.圖論及其算法[M].合肥:中國科學技術大學出版社,2003.

[7]Benoit Baudry,Yves Le Traon.Measuring design testability of a UML class diagram[J].Information and Software Technology,2005,47(13):859-879.

[8]范晶,秦卓瓊,張國清.基于中介中心性提高復雜網絡容量的方法[J].計算機仿真,2008,25(3):167-170.

[9]唐晉韜,王挺.復雜社會網絡的介數性質近似計算方法研究[J].計算工程與科學,2008,30(12):9-14.