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

成小芹， 王一莉

(南京工业大学电子与信息工程学院，江苏南京211816)

0 引 言

在面向对象软件的测试过程中，如何合理有效地分配有限的资源，从而在规定的时间内完成软件的测试，是一个非常重要的问题。目前是利用内聚性、耦合性和复杂性来判别可能存在缺陷的类，然后据此分配测试资源。但是，仅仅通过识别可能有质量缺陷的类不足以为资源的分配提供依据，还需要识别重要的类。对于重要的类而言，即使它们的内聚性、耦合性和复杂性都很合理，也需要给它们分配相对多的资源进行更加仔细的测试，因为重要的类隐藏的故障就可能越多。从这个角度来说，类的重要性度量可以看作是提高软件可测试性的一个补充。目前对类的重要性的度量的研究比较少，中心性是网络分析中的最基本的概念之一，研究人员依据各种标准提出了许多中心性指标来度量网络中的重要的节点，中介中心性就是其中一个很重要的指标，它可以用在很多方面，如社会关系学，生物学以及道路网络等，在实际的应用中依据节点的重要性和角色，制定出更加可行的解决方案。由此想到，中介中心性同样可以应用到类的重要性的度量中，找出类中重要的类，然后对这些类进行重点测试，从而提高软件可测性。现在面向对象技术在软件工业中应用比较广泛，而除了与传统测试方法具有相似之处，面向对象软件还为可测试性制造了一些独特的障碍。类图中存在的客户供应关系会引起可测试性问题。文章针对面向对象软件，使用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.