matrixlt's blog
0%

圈复杂度

Posted on Edited on

基路径测试

在进行白盒测试时，我们常常不能穷尽程序的所有路径。这时一个可行的选择是将程序看成是由一个个独立路径组合而成，转而去测试每一条独立路径上程序的行为。
这里 路径 指的是从程序的起始点到结束点的一条通路，这里我们假设程序有且只有一个起始点与结束点。而 独立路径 指的是这条路径不能通过其他路径的线性组合得到。这种将程序分解成独立路径的思想是由McCabe在他1976年的论文 A Complexity Measure 中提出的，在这篇论文中，他也意识到了这是一种有用的测试方法。

独立路径个数 = 圈复杂度

有了这种思想，我们的第一个问题就是对于特定的程序，这样的独立路径有多少个。McCabe直接引用了图论中的结论，我们先给出圈复杂度的定义：设图$G$有$n$个顶点，$e$条边，$p$个连通分枝，那么其圈复杂度（cyclomatic number）定义为：$v(G)=e-n+p$。

定理1

对于一个强连通图，其圈复杂度等于其极大线性无关回路的个数。

这样，McCabe在控制流图中添加一条边，将程序的结束点与开始点相连，使之成为强连通的，此时运用[定理1]，直接
对新得到的图运用公式得到程序的独立路径个数。下面我们就证明这个定理。

我们先证明两个引理。

引理1

对于s-多重图（即两个点之间至多有s条边）$G$，如果在其两个点$a,b$间再增加一条边，构成新图$G’$那么有：

  1. 如果$a,b$是同一顶点，或者是连通的，那么$v(G’) = v(G) + 1$

  2. 对于$a,b$的其他情况，那么$v(G’) = v(G)$

考虑这种操作的影响，如果$a,b$是同一顶点，或者是连通的，那么节点数不变，连通分支数不变，只有边数增加1.
故$v(G’) = v(G) + 1$;对于$a,b$的其他情况，节点数不变，连通分支数减少1，边数增加1，故$v(G’) = v(G)$。

下面为了形式化的表示独立圈的概念，我们将一个圈用向量的形式表示：为边编号为$1,2,\cdots,k$，为边任意指定一个方向
以抵消同一条边相反方向的两次经过，那么向量$(c_1,c_2,\cdots,c_k)$就代表这个圈经过了第$1,2,\cdots,k$条边$c_1,c_2,\cdots,c_k$
次。这种表示方法可以构成一个线性空间，故我们可以如常定义线性独立的含义。下面我们举一个简单的例子。
image
如上图所示，图中$n = 6, e = 7 p = 1,v(G) = 7 - 6 + 1 = 2$.我们选择$a \to b \to c \to d \to a$
和$a \to b \to e \to f \to a$作为一组基。表为向量：$x = (1,1,1,1,0,0,0), y = (1,0,0,0,1,1,1)$，现在考虑图中
另外的圈，如$a \to f \to e \to b \to b \to a, z_1 = (-1,0,0,0,-1,-1,-1) = -y$,又如$c \to b \to e \to f \to a \to d \to c
, z_2 = (0,-1,-1,-1,1,1,1) = -x + y$.我们还可以注意到这里运算的图论意义：对向量取反即圈反向，乘以一个正整数$n$即重复圈$n$次。

引理2

对于s-多重图$G$，其圈复杂度等于其极大线性无关圈数。

我们考虑将图$G$中的边全部去掉，再一条一条增加回去。首先我们知道初始没有边时$v(G) = 0$。
又由[引理1]知，只有在将边连成环时$v(G)$才会增加。现在假设我们已经有了一组基包括
圈$\mu_1,\mu_2,\cdots$,下面添加一条边$u_k$后形成了一些新环$\nu_1,\nu_2,\cdots$。下面我们
说明此时$V(G)$与极大线性无关圈数同时增加1.前者是由[引理1]显然的。考虑向量$\nu_1$,它必然
不能被$\mu_1,\mu_2,\cdots$线性表示，这是因为这些圈不包含边$u_k$,其向量的第$k$个分量均为0，而
$\nu_1$向量的第$k$个分量为1.另一方面$\mu_2,\cdots$不包含新边，已经能够被$\mu_1,\mu_2,\cdots,nu_1$
线性表示。故其极大线性无关圈数也增加1.如此我们就证明了这个引理。

下面我们就来证明定理[定理1]。
首先我们说明证明的思路：在[引理2]中我们已经说明了如何处理无向图，那么在有向图中，如果我们忽略方向，得到对应的2-多重图，再将其中的圈仿照[引理2]处理，将其表示为回路的线性组合，是否就完成了证明呢？这里有一个方向导致的重要问题：
即新得到的图中的圈可能在原图中由于边的方向相对而不是回路,并且要使用回路而不是圈构造。

考虑将这个强连通图变为一个2-多重图。对应这个多重图中的任意一个圈$\mu$,其上的顶点可以分为三类：

  1. 顶点有在原图中有1条出边，1条入边，记为$S$

  2. 顶点有在原图中有2条出边，记为$S’$

  3. 顶点有在原图中有2条入边，记为$S’’$

image
上图中，b，g，d是第一类节点，a，e是第二类节点，c，f是第三类节点。
我们首先可以发现：第二类和第三类顶点是交替出现，数量相等的。
下面开始我们的构造：我们记$x_1’,x_2’,\cdots \in S’$,$x_1’’,x_2’’,\cdots \in S’’$
那么在圈上$x_1’$遇到的第一个非$S$中的顶点为$x_1’’$,依次类推。
我们直接用例子说明这种构造方法：
$$\begin{align}
\mu &= a \to b \to c \to d \to e \to f \to g \to a \\
&= (a \to b \to c) - (e \to d \to c) + (e \to f) - (a \to g \to f) \\
&= (a \to b \to c) - (c \to x \to e \to d \to c) + (c \to x \to e) + (e \to f) - (f \to y \to a \to g \to f) + (f \to y \to a) \\
&= (a \to b \to c) - \mu_1 + (c \to x \to e) + (e \to f) - \mu_2 + (f \to y \to a) \\
&= \mu’ - (\mu_1 + \mu_2)
\end{align}$$
这里的关键在于为什么存在这样的$x,y$节点，原因是图的强连通性，使得$x’’_i$必有一条路径通向$x’_{i+1}$
下面我们定义记号$\mu[a,b]$意为节点$a$到$b$的一条路径，那么证明如下：
$$\begin{align}
\mu &= \mu[x_1’,x_1’’] - \mu[x_2’,x_1’’] + \mu[x_2’,x_2’’] + \cdots \\
&= \mu[x_1’,x_1’’] + \mu[x_1’’,x_2’] + \mu[x_2’,x_2’’] + \cdots - (\mu_1 + \mu_2 + \cdots) \\
&= \mu’ - (\mu_1 + \mu_2 + \cdots)
\end{align}$$
这样，对与图中任意的圈，我们将其分解成了原图中回路的线性组合。这些回路构成了一组基，根据[引理2]
我们知道这一基构成的线性空间维数等于$v(G)$，由此我们证明了这个结论。

圈复杂度的计算方法

构造新图求$v(G’)$

这是McCabe给出的定义。添加一条新边由结束点指向开始点，求$e - n + p$,常常只考虑单个程序$p = 1$故为$e - n + 1$

不构造新图，求$e - n + 2p$

考虑这样新图中新增的边的影响(处于一般性考虑，图$G$由p个互不连通的程序构成)：它将连通分支个数从0变成了p，并将边数增加p。即将图$G$变为图$G’$时，$n’ = n, e’ = e + p, p’ = 0 + p$由此
我们得到了另一个常用的公式：$v(G’) = e’ - n’ + p’ = (e + p) - n + (0 + p) = e - n + 2p$,常常只考虑单个程序$p = 1$故通常形式为$e - n + 2$

对于平面图，求围成区域的个数

借用上一小节的公式$v(G’) = e - n + 2$，结合平面图的欧拉公式：$n - e + f = 2$,立刻得到$v(G’) = f - 2 + 2 = f$
那么控制流图一定是平面图吗？显然不是，考虑$K_{(3,3)}$即可。

对于结束点唯一的程序，求判断节点个数加1

这是非常本质的洞见，是判断节点的增加导致了圈复杂度的增加，顺序执行的代码再长也不会增加圈复杂度。
由此我们还可以设想一种极端情况：程序进入死循环，即控制流图中存在无出口的自环，此时这个自环是不会增加圈复杂度的，因为它并非判断节点。
下面给出对有且只有一个起始点与结束点的程序的证明，这里将多判断节点都转换为2判断节点：

我们仍从公式$v(G’) = e - n + 2$开始，考虑所有边与其起点的关系，可以分为三类：

  1. 结束点，无出边

  2. 判断节点，2条出边，有$n_1$个

  3. 一般节点，1条出边，有$n_2$个

那么我们有$1 + n_1 + n_2 = n$且$2n_1 + n_2 = e$带入公式即得$v(G’) = (2n_1 + n_2) - (1 + n_1 + n_2) + 2 = n_1 + 1$
这就得到了我们想要的结论。McCabe在他的论文中证明了更一般的情况：循环复杂度如下：$\pi - s + 2$,其中,$\pi$是程序中决策点的个数,s为结束点的个数.

参考资料

一般关于基路径测试的知识可见于任何软件工程或软件测试的教材。本文参考或翻译自以下资料：

  1. 维基百科https://zh.wikipedia.org/wiki/

  2. McCabe. A Complexity Measure (PDF). IEEE Transactions on Software
    Engineering. December 1976: 308–320.

  3. C. Berge, Graphs and Hypergraphs. Amsterdam, The
    Netherlands:North-Holland,1973

论文中包含的内容非常丰富，又不十分难懂，可惜时间所限没有细读。McCabe作为数学出身后转向编程的软件工程研究者，
懂得线性代数与图论并不奇怪，但是他能够发现程序的控制流图中的线性空间，并结合理论发展出基于圈复杂度的程序分解与测试
方法十分可贵。数学有趣之处不仅在于其高深的理论与严谨的推理，更在于它应用广泛，无处不在。