开源软件中结构复杂度的度量方法

—61—

开源软件中结构复杂度的度量方法

黄雅菁，高建华

(上海师范大学计算机科学与工程系，上海 200234)

摘 要：针对大型开源软件的复杂性，提出一种基于随机图和结构熵的开源软件结构复杂度的度量方法。将开源软件中的软件包抽象成点，将软件包之间的依赖关系抽象成有向边，建立随机图，并引入结构熵的概念。结合随机图的特性和结构熵度量开源软件的耦合度和内聚度。利用该方法进行实例分析，结果表明，随着开源软件按版本发展，软件耦合度和内聚度不断增长。 关键词：开源软件；随机图；结构熵；耦合；内聚

Measure Method of Structural Complexity in Open Source Software

HUANG Ya-jing, GAO Jian-hua

(Department of Computer Science and Engineering, Shanghai Normal University, Shanghai 200234)

【Abstract 】 In order to study the complexity of the large-scale open source software, this paper models the packages in the open source software as vertices and the dependency relationships among these packages as directed edges. It uses random graph measure and structure entropy to propose a new method of measuring structural complexity of open source software. It uses the method by the fact to investigate that as the release of the open source software evolves, the coupling and cohesion grow from lower to higher.

【Key words 】open source software; random graph; structure entropy; coupling; cohesion

计 算 机 工 程 Computer Engineering 第36卷 第10期

Vol.36 No.10 2010年5月

May 2010

·软件技术与数据库·

文章编号：1000—3428(2010)10—0061—03

文献标识码：A

中图分类号：TP311.5

1 概述

由于免费开放源代码等优点，开源软件得到广泛应用。但开源软件数据量大，允许开发者自由修改程序，使开源软件复杂性越来越高。软件结构复杂性直接影响软件维护的代价和精力。软件系统的复杂度取决于软件内部结构各子系统之间的控制流与数据流的复杂程度，它包括算法复杂度和结构复杂度。本文所提到的复杂度是指结构复杂度。软件复杂度度量的方法[1-2]已被广泛研究，从不同角度量化了软件的一些特性，但对大型的开源软件不适用。

国内外研究工作者[3-4]已经将随机图论应用在开源软件的管理。经典的随机图特性只能解释某些结构特性，但很难直接应用在软件包管理上。例如，度分析能说明软件包在互相依赖中的选择机制，但不能用来定义整个软件的复杂度。

文献[5]定义了基于随机图的有向图复杂度参数，该参数超越了简单的直接依赖关系，但不能反映软件包之间的紧密程度。

本文以随机图论为基础，把开源软件子包抽象成点，把子包之间的依赖关系抽象成有向边，建立随机图。基于随机

图的特性度量开源软件的耦合度，并引入结构熵的概念度量开源软件内聚度，提出一种基于随机图和结构熵度量开源软件结构复杂度的方法。应用该方法研究和分析了开源软件按版本发、耦合度和内聚度纵向变化情况。

2 软件结构复杂度度量

结构复杂度度量的目标要能反映模块内部结构的复杂度

以及模块间接口的复杂度，决定于代码基本的层级组织，先开始于方法层，然后通过抽象层移植[6]。在方法层，评估软件系统结构复杂度是通过度量圈复杂度，即通过代码主体可执行路径的条数。圈复杂度的值越高，方法的代码就越复杂。在抽象层(例如类、包、元件)，评估软件系统结构复杂度是

通过度量耦合和内聚。耦合是指2个子系统之间的依赖数目，内聚是指子系统内部的依赖数目。

当运行大型复杂代码，传统的圈复杂度、耦合和内聚的度量没有考虑设计依赖的影响。The Structure 101度量框架(/procucts/structure101/index.php)能提供软件在方法层和抽象层设计依赖关系，这种关系是运行时的依赖关系，度量框架界面如图1所示。

图1 The Structure 101度量框架界面

本文主要研究包的级别，评估开源软件结构复杂度主要通过度量耦合和内聚，利用The Structure 101框架度量开源软件可得其包之间的依赖关系。在图1中，区域1显示包的层级关系，即包及其下的子包；区域2显示包两两之间的依

基金项目：国家自然科学基金资助项目(60673067)；上海市教育委员会科研创新基金资助项目(0922135)

作者简介：黄雅菁(1983－)，女，硕士研究生，主研方向：开源软件技术，软件工程；高建华，教授、博士

收稿日期：2009-11-20 E-mail ：yajing_huang@

—62—

赖关系；区域3显示包之间的依赖关系。

3 基于随机图的耦合度度量

以随机图论为基础，首先把开源软件子包抽象成点，把子包之间的依赖关系抽象成有向边，建立随机图。文献[5]定义了基于随机图的有向图复杂度参数，即该软件包运行时所需要的所有其他软件包。但这个参数只能反映软件包之间的依赖关系，不能反映软件包之间的紧密程度。因此，可以使用这个复杂度参数度量开源软件的耦合度。

以图2的软件包1为例，软件包1的耦合度为4。对应于图，某个节点耦合度的定义可以等价于以该节点为根节点按边的方向生长的树中子节点的个数。整个图的耦合度定义为所有软件包耦合度的平均值，即开源软件的耦合度。

图2 软件耦合度实例

4 基于结构熵的内聚度度量

开源软件的内聚度是指开源软件中软件包之间关系的密

切程度。为了度量这种关系，引入了结构熵的概念。对于一个广义的系统来说，熵可作为状态的混乱性或无序性的度量。结构熵的特性取决于系统的组织结构，组织化程度越高，结构熵越小；反之，结构熵越大[7]。

如果一个系统X 有n 个子系统X 1, X 2,…, X n ，子系统X i 与X j 有关联，则g ij =1，否则g ij =0。令N (i )=1n

ij j g =∑；联结强度

ρ(i )=1

()()n j N i N j =∑。系统X 的结构熵为H =-1

()ln ()n

i i i ρρ=∑，其

中，1

()n

i i ρ=∑=1。

根据结构熵的概念，有如下定义：如果一个开源软件S 有n 个子包P 1, P 2,…, P n ，集合P _DEP 记录P i 所依赖的其他软件包的集合。令N (i )=1|_()|n

k k P DEP P =∑；联结强度

ρ(P i )=

1

|_()|

|_()|

i n

k k P DEP P P DEP P =∑。其中，||表示集合中元素的个数。

软件S 中包之间的内聚度为 Cohesion (P _P )=-1|_()|()ln ()

*ln n

i i i i P DEP P P P n n

ρρ=∑

内聚度Cohesion (P _P )的取值范围为[0,1]。当内聚度为0

时，表示2个软件包没有任何依赖关系，包之间的内聚度最小；当内聚度为1时，说明任意2个包之间都具有依赖关系，包之间的内聚度最大。

5 基于随机图和结构熵的结构复杂度度量

基于随机图和结构熵的开源软件结构复杂度度量方法 如下：

(1)在开源软件网站()下载待测量的开源软件。

(2)用The Structure 101测量开源软件的核心包，得到开源软件核心包中子包的信息。

(3)将核心包里的子包抽象成点，把子包之间的依赖关系抽象成有向边，建立子包之间的随机图。

(4)利用有向图的复杂度参数，计算随机图中各节点的耦合度，各节点的平均耦合度近似为该开源软件的耦合度。

(5)根据随机图中的依赖关系结合结构熵的概念，计算开源软件软件包之间的内聚度。

6 实例分析

本节以开源软件JFreeChart 的0.8.1版本为例进行分析，描述基于随机图和结构熵的开源软件结构复杂度度量方法：

(1)用The Structure 101测量开源软件JFreeChart 的核心包org.jfree.chart ，得到8个软件子包以及子包之间的依赖关系，每个包以数值标识，如表1所示。

表1 核心包org.jfree.chart 中子包之间的依赖关系

包名

标识值

依赖包

demo 1 chart,data,combination,tooltips ui 2 chart combination 3

Chart,event

data 4 - chart 5 event,tooltips,ui,combination event 6

ui tooltips 7 - jdbc 8

-

(2)将核心包中的子包抽象成点，子包之间的依赖关系抽

3所示。

图3 核心包org.jfree.chart 中子包之间的随机图

(3)由图3计算耦合度，忽略孤立包的影响，首先计算各节点的耦合度，软件的耦合度近似为各个节点耦合度的平均值。求得耦合度为2.86，如表2所示。

表2 图3的耦合度

节点

耦合度

1 6

2 4

3 3

4 0

5 4

6 3

7 0

8 孤立 平均值

2.86

(4)由图3计算内聚度，首先计算联结强度，ρ(P i )=

1

|_()|

|_()|

i n

k k P DEP P P DEP P =∑。P_DEP 记录P i 所依赖的其它软件包的集

合，则|P _DEP (P i )|大小等于各节点的耦合度。这样很容易求

得各节点的联合强度，如表3所示。

表3 图3的联结强度

节点

联结强度

1 0.3

2 0.2

3 0.15

4 0

5 0.2

6 0.15

7 0 8

孤立