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

成小芹， 王一莉

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

0 引 言

在面向?qū)ο筌浖臏y(cè)試過(guò)程中，如何合理有效地分配有限的資源，從而在規(guī)定的時(shí)間內(nèi)完成軟件的測(cè)試，是一個(gè)非常重要的問(wèn)題。目前是利用內(nèi)聚性、耦合性和復(fù)雜性來(lái)判別可能存在缺陷的類，然后據(jù)此分配測(cè)試資源。但是，僅僅通過(guò)識(shí)別可能有質(zhì)量缺陷的類不足以為資源的分配提供依據(jù)，還需要識(shí)別重要的類。對(duì)于重要的類而言，即使它們的內(nèi)聚性、耦合性和復(fù)雜性都很合理，也需要給它們分配相對(duì)多的資源進(jìn)行更加仔細(xì)的測(cè)試，因?yàn)橹匾念愲[藏的故障就可能越多。從這個(gè)角度來(lái)說(shuō)，類的重要性度量可以看作是提高軟件可測(cè)試性的一個(gè)補(bǔ)充。目前對(duì)類的重要性的度量的研究比較少，中心性是網(wǎng)絡(luò)分析中的最基本的概念之一，研究人員依據(jù)各種標(biāo)準(zhǔn)提出了許多中心性指標(biāo)來(lái)度量網(wǎng)絡(luò)中的重要的節(jié)點(diǎn)，中介中心性就是其中一個(gè)很重要的指標(biāo)，它可以用在很多方面，如社會(huì)關(guān)系學(xué)，生物學(xué)以及道路網(wǎng)絡(luò)等，在實(shí)際的應(yīng)用中依據(jù)節(jié)點(diǎn)的重要性和角色，制定出更加可行的解決方案。由此想到，中介中心性同樣可以應(yīng)用到類的重要性的度量中，找出類中重要的類，然后對(duì)這些類進(jìn)行重點(diǎn)測(cè)試，從而提高軟件可測(cè)性。現(xiàn)在面向?qū)ο蠹夹g(shù)在軟件工業(yè)中應(yīng)用比較廣泛，而除了與傳統(tǒng)測(cè)試方法具有相似之處，面向?qū)ο筌浖€為可測(cè)試性制造了一些獨(dú)特的障礙。類圖中存在的客戶供應(yīng)關(guān)系會(huì)引起可測(cè)試性問(wèn)題。文章針對(duì)面向?qū)ο筌浖?，使用UML類圖對(duì)其進(jìn)行類的重要性度量，希望能對(duì)合理安排軟件測(cè)試資源，保證軟件質(zhì)量，提供借鑒和參考。

1 類的重要性

1.1 重要類的定義

如果一個(gè)類被很多類依賴，那么對(duì)這個(gè)類進(jìn)行修改有可能會(huì)影響許多依賴于它的類，一般可以認(rèn)為這樣的類是重要的類。其實(shí)對(duì)于如何判斷重要的類可以根據(jù)用戶給定的標(biāo)準(zhǔn)來(lái)定義，例如，如果一個(gè)類直接或間接地依賴于許多其他的類，那么這個(gè)類就有可能比其他的類更容易產(chǎn)生故障，對(duì)測(cè)試者而言這樣的類也是重要的類，需要進(jìn)行重點(diǎn)測(cè)試。

1.2 類重要性的標(biāo)準(zhǔn)

上文說(shuō)到判斷重要的類的標(biāo)準(zhǔn)可以根據(jù)用戶的特定需求，下面列出常規(guī)的標(biāo)準(zhǔn)：

標(biāo)準(zhǔn)1：一個(gè)類是重要的當(dāng)且僅當(dāng)有很多重要的類依賴于它。

標(biāo)準(zhǔn)2：一個(gè)類是重要的當(dāng)且僅當(dāng)它依賴于很多重要的類。

標(biāo)準(zhǔn)3：一個(gè)類是重要的當(dāng)且僅當(dāng)它接近類間依賴圖的中心。

根據(jù)標(biāo)準(zhǔn)1的定義，一個(gè)類重要與否取決于2個(gè)要素：①依賴于它的類的數(shù)量越多，它就越重要；②依賴于它的類的重要程度越高，它就越重要。同樣地，標(biāo)準(zhǔn)2用被一個(gè)類依賴的其他類的數(shù)量和重要程度來(lái)定義該類的重要性。文章僅討論依據(jù)標(biāo)準(zhǔn)3來(lái)度量類重要性的中介中心性。

2 基于UML類圖的分析

現(xiàn)在面向?qū)ο蠹夹g(shù)在應(yīng)用中越來(lái)越廣泛，而面向?qū)ο筌浖闇y(cè)試提出了一些新的挑戰(zhàn)，如繼承、多態(tài)、動(dòng)態(tài)綁定等。由于類圖常常不夠明確、完整，會(huì)導(dǎo)致對(duì)其錯(cuò)誤的理解，結(jié)果可能引起錯(cuò)誤地實(shí)現(xiàn)和無(wú)效的測(cè)試。由于繼承和動(dòng)態(tài)綁定可能對(duì)測(cè)試工作產(chǎn)生影響，因此發(fā)現(xiàn)和掌握普遍隱含的控制依賴關(guān)系能為測(cè)試建立較好的基礎(chǔ)。

2.1 類圖中依賴關(guān)系

類圖是面向?qū)ο蠓椒ǖ暮诵?，UML類圖描述了系統(tǒng)中的類和類之間的相互關(guān)系，其本質(zhì)反映了系統(tǒng)中包含的各種對(duì)象的類型以及對(duì)象之間的各種靜態(tài)關(guān)系。在前文中也提到發(fā)現(xiàn)和掌握普遍隱含的控制依賴關(guān)系能為測(cè)試建立較好的基礎(chǔ)，對(duì)于一個(gè)比較復(fù)雜的系統(tǒng)模型來(lái)說(shuō)，類與類之間的關(guān)系是非常復(fù)雜的，而隱含的控制依賴關(guān)系也就更加復(fù)雜。

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

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

(3)繼承依賴：繼承是面向?qū)ο蟮囊环N機(jī)制，即利用現(xiàn)有的類來(lái)定義新的類，子類(繼承類)可以共享父類(被繼承類)的屬性和行為，也可以擁有自己特殊的屬性和行為，對(duì)父類進(jìn)行擴(kuò)展。這種機(jī)制可以避免重復(fù)定義屬性和方法，同時(shí)也使類間的關(guān)系更加的清晰和直觀。

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

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

2.2 CDG圖的構(gòu)造方法

在文獻(xiàn)[7]中，作者認(rèn)為按照類圖進(jìn)行測(cè)試設(shè)計(jì)時(shí)，類交互是最應(yīng)當(dāng)重視的問(wèn)題。類交互是指兩個(gè)類之間有兩條及兩條以上的依賴路徑。通常這種結(jié)構(gòu)是測(cè)試的難點(diǎn)，所以作者提出了用CDG(classdependencygraph)圖來(lái)捕獲類交互。與CDG圖相關(guān)的概念[7]介紹如下：

定義1 設(shè)類依賴圖CDG=(V,E)，V為節(jié)點(diǎn)vi集合，記為V={vi}，其中每一個(gè)節(jié)點(diǎn)表示面向?qū)ο笙到y(tǒng)的一個(gè)類，并且一個(gè)類有且只能由一個(gè)節(jié)點(diǎn)表示。E為節(jié)點(diǎn)間的有向邊集合，在兩節(jié)點(diǎn)間的一條邊表示在兩類之間存在依賴關(guān)系。每條邊上的標(biāo)記表示類間依賴的類型。

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

定義3 U標(biāo)記。一般我們將方法集和U聯(lián)系起來(lái)，在方法集中，默認(rèn)值是M(d)，轉(zhuǎn)化關(guān)系如圖1所示。

圖1 普通依賴

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

·邊，記為I-Child。從測(cè)試點(diǎn)來(lái)看，是需要從父類到子類的依賴的，因?yàn)槿魏螘r(shí)候父類發(fā)生時(shí)，子類一般也會(huì)發(fā)生。

·邊，記為I-Parent。這個(gè)從子類到父類的依賴是顯而易見的：當(dāng)b調(diào)用方法m，m∈MINH(a)時(shí)，b依賴a。

I標(biāo)記的轉(zhuǎn)化關(guān)系如圖2所示。

圖2 繼承依賴I的表示

這里要注明的是當(dāng)a是接口的時(shí)候，邊是不存在的，因?yàn)樵谶@種情況下，b是不能調(diào)用a的方法的，因此這時(shí)的轉(zhuǎn)化關(guān)系如圖3所示。而當(dāng)a還依賴于其他的類的時(shí)候，從a發(fā)出的邊U標(biāo)記是不存在的，這時(shí)U標(biāo)記的邊被轉(zhuǎn)移到a的具體類，圖4是這一情況的轉(zhuǎn)化表示。

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

3 中介中心性

3.1 基本概念

中介中心性的測(cè)量公式如下

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

式中： ——從頂點(diǎn) s∈V到頂點(diǎn) t∈V的最短路徑的條數(shù)，

——從s到t經(jīng)過(guò)頂點(diǎn) 的最短路徑的條數(shù)。

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

定義1 從頂點(diǎn)s出發(fā)的最短路徑上頂點(diǎn) 的前驅(qū)頂點(diǎn)集合為：Ps()={u∈V|∈E,dG(s,)=dG(s,u)+ (u,)}；是邊上的權(quán)值函數(shù)。

引理2 對(duì)于頂點(diǎn)

定義2 通過(guò)給定的成對(duì)的頂點(diǎn)的距離及路徑條數(shù)，可以得到經(jīng)過(guò) 的一對(duì)頂點(diǎn)s，t∈V的對(duì)-依賴性，也即式(2)所示

為了得到頂點(diǎn) 的中介中心性值必須計(jì)算出這個(gè)頂點(diǎn)上所有的對(duì)-依賴性

定理1 任何頂點(diǎn) 上的s∈V的依賴性遵循關(guān)系

由此可以看出計(jì)算頂點(diǎn)的中介中心性需要兩部分：①計(jì)算所有頂點(diǎn)之間的最短路徑的長(zhǎng)度和數(shù)目；②計(jì)算所有的對(duì)-依賴性。

3.2 中介中心性的計(jì)算

圖的廣度優(yōu)先搜索(breadth_firstsearch)遍歷算法能夠用于計(jì)算圖中任何兩點(diǎn)之間的最短路徑值。為了計(jì)算任意兩點(diǎn)之間的最短路徑的條數(shù)以及節(jié)點(diǎn)的中介中心性值(以下稱Betweenness值)，在傳統(tǒng)的廣度優(yōu)先搜索算法基礎(chǔ)上，對(duì)此進(jìn)行了擴(kuò)展，在擴(kuò)展了的廣度優(yōu)先搜索算法中，采用隊(duì)列和棧兩種數(shù)據(jù)結(jié)構(gòu)來(lái)存放節(jié)點(diǎn)，依據(jù)節(jié)點(diǎn)不同的存儲(chǔ)位置，把圖中的每個(gè)節(jié)點(diǎn)在遍歷的過(guò)程中標(biāo)記為3個(gè)狀態(tài)：①?zèng)]有進(jìn)入隊(duì)列的節(jié)點(diǎn)，將其狀態(tài)定義為未探查；②進(jìn)入隊(duì)列的節(jié)點(diǎn)，將其狀態(tài)定義為已探查但未訪問(wèn)；③出隊(duì)列且入棧的節(jié)點(diǎn)，將其狀態(tài)定義為已訪問(wèn)。

為計(jì)算節(jié)點(diǎn)的Betweenness值，算法可以分為兩個(gè)部分來(lái)實(shí)現(xiàn)：①遍歷算法，主要是實(shí)現(xiàn)對(duì)圖進(jìn)行廣度優(yōu)先遍歷，計(jì)算節(jié)點(diǎn)從源點(diǎn)s到 的距離，最短路徑條數(shù)等。②回溯算法，計(jì)算節(jié)點(diǎn) 的前驅(qū)節(jié)點(diǎn)的對(duì)-依賴性。

為計(jì)算類依賴關(guān)系圖(CDG)中的節(jié)點(diǎn)的Betweenness值，算法的原理描述如下：

(1)從CDG圖中任意選擇一個(gè)節(jié)點(diǎn)作為源節(jié)點(diǎn)s，以此節(jié)點(diǎn)開始對(duì)圖進(jìn)行廣度優(yōu)先搜索遍歷，同時(shí)計(jì)算出從源節(jié)點(diǎn)s到每個(gè)節(jié)點(diǎn) 的距離d(s,)、最短路徑的條數(shù) (s,)、節(jié)點(diǎn) 的前驅(qū)節(jié)點(diǎn)集合P()以及記錄節(jié)點(diǎn)的訪問(wèn)順序。

(2)在(1)遍歷的基礎(chǔ)上，以s為源節(jié)點(diǎn)的遍歷順序記錄在棧中，從棧頂?shù)墓?jié)點(diǎn)開始對(duì)每個(gè)節(jié)點(diǎn)進(jìn)行回溯，也即按照節(jié)點(diǎn)的逆序訪問(wèn)順序?qū)γ總€(gè)節(jié)點(diǎn)進(jìn)行回溯處理，用下面的公式對(duì)節(jié)點(diǎn) 的前驅(qū)節(jié)點(diǎn)的對(duì)-依賴性的值進(jìn)行更新

之所以采用逆序訪問(wèn)順序是因?yàn)閷?duì)節(jié)點(diǎn) 進(jìn)行回溯處理完后，節(jié)點(diǎn) 的 ()值就不會(huì)再改變，而采用廣度優(yōu)先搜索遍歷為任意先后進(jìn)行回溯的節(jié)點(diǎn) ，，滿足d(s,)≥d(s,)提供了保障，當(dāng)d(s,)≥d(s,)這樣的關(guān)系成立時(shí)，說(shuō)明s到 的最短路徑一定不經(jīng)過(guò) 。

(3)對(duì)每個(gè)節(jié)點(diǎn) ，計(jì)算CBnew()=CBold()+ ()

(4)對(duì)CDG圖中的每個(gè)節(jié)點(diǎn)重復(fù)執(zhí)行(1)～(3)，最后得到圖中所有節(jié)點(diǎn)的Betweenness值。

算法實(shí)現(xiàn)的代碼如下表示：

4 應(yīng)用示例

在本文研究的基礎(chǔ)上結(jié)合一個(gè)小規(guī)模的類圖，應(yīng)用文章所介紹的方法作分析。

4.1 CDG圖的節(jié)點(diǎn)的中介中心性

這一節(jié)中將通過(guò)一個(gè)小型類圖，應(yīng)用上文所介紹的CDG圖，計(jì)算其頂點(diǎn)的Betweenness值，通過(guò)比較各個(gè)節(jié)點(diǎn)的中介中心性的值來(lái)識(shí)別重要的類。圖5是個(gè)小規(guī)模的類圖，其對(duì)應(yīng)的CDG圖如圖6所示。

圖5 小型類圖

圖6 小型類圖的CDG圖

利用文章描述的算法，可以計(jì)算出這個(gè)小型類圖的CDG圖的各個(gè)節(jié)點(diǎn)的中介中心性值，如表1所示。根據(jù)這個(gè)值可以看出圖中b1的Betweenness值是最大的，說(shuō)明b1的依賴性較強(qiáng)，是重要的類，在測(cè)試中應(yīng)該分配較多的資源以發(fā)現(xiàn)該類中隱藏的質(zhì)量缺陷，而c的Betweenness值是最小的，說(shuō)明它的重要性很低，在圖中也可以很清晰地看出來(lái)，那么在測(cè)試的過(guò)程中就可以花費(fèi)相對(duì)少的人力和時(shí)間。通過(guò)分析比各個(gè)節(jié)點(diǎn)的Betweenness值，可以很明了地看出節(jié)點(diǎn)重要性的等級(jí)，在測(cè)試的過(guò)程中就可以有的放矢，充分合理地分配有限的資源。

表1 節(jié)點(diǎn)的Betweenness值及等級(jí)

為了便于問(wèn)題的討論，以上只是一個(gè)小型類圖的CDG圖的類重要性的度量。而在實(shí)際的應(yīng)用中，面向?qū)ο筌浖囊?guī)模是很大的，其對(duì)應(yīng)的類圖也是錯(cuò)綜復(fù)雜的，而類圖對(duì)應(yīng)的CDG圖也必將更加的復(fù)雜。通過(guò)上述方法所度量的節(jié)點(diǎn)的中介中心性值可以指導(dǎo)我們的測(cè)試活動(dòng)，從而提高軟件的可測(cè)試性、保證軟件的質(zhì)量。

4.2 分析總結(jié)

類圖中反映的類之間的依賴關(guān)系是基于類圖的重要性度量的基礎(chǔ)，而將由類圖轉(zhuǎn)化而來(lái)的CDG圖與中介中心性結(jié)合起來(lái)分析節(jié)點(diǎn)的重要性，對(duì)軟件測(cè)試有指導(dǎo)作用。在現(xiàn)代軟件工程理論中，軟件測(cè)試應(yīng)該貫穿于軟件的整個(gè)生命周期，可見軟件測(cè)試在軟件產(chǎn)品的開發(fā)過(guò)程中的地位是非常關(guān)鍵的，而且它的測(cè)試工作量也是非常多且繁重的。

從測(cè)試方法角度看，目前軟件測(cè)試主要分為靜態(tài)測(cè)試和動(dòng)態(tài)測(cè)試，文章所提出的方法主要是屬于靜態(tài)測(cè)試范疇，對(duì)CDG圖的節(jié)點(diǎn)的重要性進(jìn)行度量，根據(jù)結(jié)果進(jìn)行測(cè)試資源的合理分配。從動(dòng)態(tài)測(cè)試的角度來(lái)看，類測(cè)試是動(dòng)態(tài)測(cè)試的一個(gè)方面，從這方面來(lái)說(shuō)，度量類重要性對(duì)動(dòng)態(tài)測(cè)試也是有一定的優(yōu)化作用，可以提高動(dòng)態(tài)測(cè)試的效率。

5 結(jié)束語(yǔ)

由以上分析可知，本文提出的將中介中心性應(yīng)用到類依賴關(guān)系圖(CDG圖)中的方法，用來(lái)度量和分析面向?qū)ο筌浖念愰g依賴結(jié)構(gòu)，以此分析面向?qū)ο筌浖念惖闹匾?，?duì)合理分配測(cè)試資源、減少軟件測(cè)試成本、提高軟件質(zhì)量有指導(dǎo)作用。文中所研究的內(nèi)容，對(duì)現(xiàn)實(shí)中大型的面向?qū)ο筌浖臏y(cè)試有一定的參考價(jià)值。當(dāng)然，文中所研究的中介中心性的算發(fā)的時(shí)間復(fù)雜度是O(n3)，可以從邊的類型考慮，以降低其時(shí)間復(fù)雜度，需要后續(xù)的研究發(fā)現(xiàn)，這也是今后研究的重要方向。

[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類圖的類之間依賴關(guān)系圖論問(wèn)題研究[J].計(jì)算機(jī)工程,2006,32(12):1-2.

[6]殷劍宏,吳開亞.圖論及其算法[M].合肥:中國(guó)科學(xué)技術(shù)大學(xué)出版社,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]范晶,秦卓瓊,張國(guó)清.基于中介中心性提高復(fù)雜網(wǎng)絡(luò)容量的方法[J].計(jì)算機(jī)仿真,2008,25(3):167-170.

[9]唐晉韜,王挺.復(fù)雜社會(huì)網(wǎng)絡(luò)的介數(shù)性質(zhì)近似計(jì)算方法研究[J].計(jì)算工程與科學(xué),2008,30(12):9-14.