Cyclomatic Complexity与应用

(vUVAF9| H9o0Cyclomatic Complexity

Reference:http://www.sei.cmu.edu/str/descrīptions/cyclomatic.html51Testing软件测试网MR8rPOj(f q

Z2_Un|%`_]0+目的：结构复杂度的测量方法，可以用来度量软件的复杂性，评估软件的内在风险和稳定性。51Testing软件测试网!H%c4]+l%s4u

4LHf,nn KN0+基本原理51Testing软件测试网:H2a(^R)EU
++相关概念51Testing软件测试网c.ZG&f1Kk?
1. 强连通图(strongly-connected graph，有向图)51Testing软件测试网}DV\d$y7h
图中任意两个节点A和B之间，存在一条从A到B的路径，也存在一条从B到A的路径。
? CyJ o{.O02. 控制流图(control flow graph)
Q2x8y|yg {W0G=(N,E)，一组节点和边的集合，用来表述程序模块的流程，节点可以是程序语句或基本块（即只有一个入口和一个出口的语句的序列）。51Testing软件测试网H6m6_)S c*QRn!y&u
3. 图的秩数(cyclomatic number,这个词怎么翻译好呢？)51Testing软件测试网r)B ]JqI@"}&m]
v=e-n+1（e是图中边的个数，n是图中节点的个数）
q%K0Uh:~04. 线性独立路径(linearly independent path)
(I+Y$n;v3Q%xJ:\0线性独立路径的集合中的任意一条路径不能用集合中的其他路径构造而成，而集合外的任意一条路径可以用集合内的路径构造而成。51Testing软件测试网7@"E;w)h
n9r
5. 定理：强连接图的秩数等于线性独立路径的个数51Testing软件测试网h`6[nx_*}`

x]]6G2k~QL0+Cyclomatic Complexity的计算
yD8sfb"J]0The cyclomatic complexity of a software module is calculated from a connected graph of the module (that shows the topology of control flow within the program):

Cyclomatic complexity (CC) = E - N + p51Testing软件测试网P4KlL-}fk

where E = the number of edges of the graph
V ]wd$m0MCa I0N = the number of nodes of the graph51Testing软件测试网_"WzE/k
p = the number of connected components

0_7ppGQ0assisted byCyclomatic Complexity Analyzersfor various types of source codes51Testing软件测试网 R?:c(Y [*z*u\i

4o Y#Zp5Rb mj0+Cyclomatic complexity能告诉我们什么？51Testing软件测试网.EP}Xwe{
L8E

  CC               Risk Evaluation
E!G/Ol2q0 1-10             a simple program, without much risk51Testing软件测试网6W Oz(^Bj;z
 11-20            more complex, moderate risk
4r'@KleP!V0 21-50            complex, high risk program
+LJ;QO%f[0greater than 50   untestable program (very high risk)

&ZwY0XLm0Cyclomatic complexity越大，软件的复杂度就越高，开发和维护软件的风险就越大，可测试性也越低。
rM} C UPvQ-M0当>10时，我们应该考虑程序本身的设计是否合理，是否存在缺陷。51Testing软件测试网D2R\!Xy1C8Z"x
[ |

+在测试中的应用
3h{$~g#a)Nq01. 根据软件的复杂性，估计测试的工作量，作为制定测试计划的基础。51Testing软件测试网0?@+V}n(vazg _
2. 基本路径测试（basis path testing）
D\G/[!R rj0这是一种基于代码的测试技术（白盒），保证能达到全语句的覆盖程度。
Ea"P7a1LG0全路径覆盖的白盒测试是不经济、不现实的。基本路径测试相对于全路径测试，需要较少的测试用例。51Testing软件测试网]3f$Sp H|C
任意程序的控制流图都不是强连通的，从退出点到进入点加上一条有向边，把控制流图变成强连通图。51Testing软件测试网m(Vi-m3`7A}^
%流图的cyclomatic number的计算方法：
z#\-S{E5PzO(Z$b0a. V=e-n+251Testing软件测试网ep"B3P|
b. 对于一个结构化的程序（无GOTO）,可以通过下列方法确定V:
Ga-sp"wi(w!]n_0V = number of binary decision nodes + 1,
.n1qu;Xl0• IF statement is counted as 1 binary decision.
:G\'z;Uw(p6?XT/[0• 3-way CASE is counted as 2 binary decisions.
4~7M%iTA4ofP7Q M0• n-way CASE is counted as (n-1) binary decisions.51Testing软件测试网*y~8qpV
• Loop is counted as 1 binary decision.51Testing软件测试网m^$^7u8u6~
%测试步骤51Testing软件测试网'HOP-q$a-s!m+O
1. 根据设计或代码，画控制流图51Testing软件测试网sAkC\a*|
2. 计算流图的cyclomatic number: V，即基本路径的个数
(p;qV[)W02. 确定独立路径集51Testing软件测试网$V0j
Y8Fu?}1f7i
2. 设计测试用例，保证基本路径集的路径都被遍历到
'C4}0V3x+l0%确定基本路径集的算法51Testing软件测试网tp
n(M+od ]dQ
n
1. select a baseline path, an arbitrary path that represents a typical function, and not just an error or exceptional condition51Testing软件测试网4r1L ^"[P'Fc t
2. locate the first decision node in the baseline path, go to another decision branch to find 2nd basis path51Testing软件测试网hFQB9X
3. locate the second decision node in the baseline path, go to one decision branch to find 3nd basis path51Testing软件测试网e%[,NE'^;l-e
4. continue till all the decision nodes in the baseline path have been traversed51Testing软件测试网9X,fd&_ wM
5. follow the second path and traverse all its decision nodes
)^%i_#x&a+t[06. continue till all the basis paths have been found51Testing软件测试网2eGQ#s#HPz
Note that other basis paths try to follow as close to the baseline path as possible; this eases the design of test input.
l~0K xl*sW0%缺陷51Testing软件测试网ZdV9Gg7I4J
要使用控制流图；没有考虑更加复杂的分支结构；算法可能产生不可能路径；测试不充分。51Testing软件测试网%]O\1j xQC}