循環的複雑度と分岐網羅
次の C 言語の関数について，McCabe の循環的複雑度 v(G) とテストとの関係に関する記述として，適切なものはどれか。ここで，a と b は互いに独立に任意の整数値を取り得るものとする。
int f(int a, int b) {
int r = 0;
if (a > 0) {
r = 1;
}
while (b > 0) {
r += 2;
b--;
}
return r;
}- アv(G) は 2 である。while 文は繰返しの構造なので判定の数に数えず，if 文の判定 1 個に 1 を加える。
- イv(G) は 3 である。v(G) は関数を通る全ての実行経路の数なので，3 個のテストケースで全ての経路を網羅できる。
- ウv(G) は 3 である。分岐網羅を満たすには，少なくとも v(G) と同じ 3 個のテストケースが必要である。
- エv(G) は 3 である。線形独立な 3 個の基底パスを実行するテストは，全ての分岐を通るので分岐網羅も満たす。
正解と解説を見る
正解 エ
この問題の基礎知識
- McCabe の循環的複雑度 v(G) は，制御フローグラフの辺の数を e，節点の数を n とすると v(G) ＝ e − n ＋ 2 で求める。判定が全て 2 分岐で，その数が p のときは v(G) ＝ p ＋ 1 となる。
- 判定には，if 文の条件のほか，while 文や for 文の繰返しを続けるか抜けるかの条件も含まれる。
- v(G) は，線形結合で全ての経路を表せる線形独立な経路（基底パス）の数であり，ループを含むプログラムの全経路の数とは異なる。基底パステストは，基底パスをそれぞれ実行するテストである。
- 命令網羅は全ての命令を，分岐網羅（判定条件網羅）は全ての判定の真と偽を，それぞれ少なくとも 1 回実行するテストの基準であり，一般に，分岐網羅を満たせば命令網羅も満たす。
while 文は，ループを続けるか抜けるかを決める 2 分岐の判定であり，if 文と同様に複雑度に 1 を加える。判定は if 文と while 文の 2 個なので，v(G) は 2 ＋ 1 ＝ 3 である。
v(G) は，線形結合で全ての経路を表せる線形独立な経路（基底パス）の数であり，全経路の数ではない。while 文の繰返し回数は b の値によって変わるので，経路の数は v(G) よりはるかに多い。
v(G) は分岐網羅に必要なテストケース数の上限であり，下限ではない。この関数では a＝1，b＝1 と a＝0，b＝0 の 2 個で，if 文と while 文の真と偽を全て実行でき，分岐網羅を満たす。
判定は if 文と while 文の 2 個で，v(G) ＝ 2 ＋ 1 ＝ 3 である。基底パスの集合は制御フローグラフの全ての辺を通るので，基底パステスト（構造化テスト）は分岐網羅を包含する。
照合の根拠（6 件）
- エ（正解）・ア（誤り）: 2 分岐の判定が p 個なら v(G) = p + 1。if 文と while 文の 2 個で v(G) = 3
If all decisions are binary and there are p binary decision predicates, v(G) = p + 1
NIST SP 500-235 · Section 4.1 Counting predicates（新しいタブで開きます） - ア（誤り）: ループによる判定 2 個の図 4-2 も 2 分岐の判定として数えて v(G) = 3 とし，続けて「the same counting technique applies」とする。while 文を判定に数えないとするアは誤り
Figure 4-2 has two binary decision predicate nodes (1 and 3), so complexity is 3. Since the decisions in Figure 4-2 come from loops
NIST SP 500-235 · Section 4.1 Counting predicates（新しいタブで開きます） - イ（誤り）: v(G) は線形結合で全経路を生成する独立な経路の集合の要素数であり，全実行経路の数ではない
This means that the cyclomatic complexity is the number of paths in any independent set of paths that generate all possible paths by linear combination.
NIST SP 500-235 · Section 2.3（新しいタブで開きます） - イ（誤り）: ループを含むプログラムの経路は潜在的に無限であり，3 個のテストケースで全経路は網羅できない
Notice that most programs with a loop have a potentially infinite number of paths, which are not subject to exhaustive testing even in theory.
NIST SP 500-235 · Section 5.1（新しいタブで開きます） - エ（正解）: 基底パスの集合は制御フローグラフの全ての辺と節点を通るので，構造化テストは分岐網羅・命令網羅を包含する（同段落 "structured testing subsumes branch and statement coverage testing"）
First of all, since any basis set of paths covers all edges and nodes of the control flow graph
NIST SP 500-235 · Section 5.2（新しいタブで開きます） - ウ（誤り）: v(G) = 3 の図 5-1 の関数でも分岐網羅は 2 個のテストで満たせるとしており，分岐網羅に v(G) 個のテストが必要とは限らない（本問でも 2 個で足りる）
The branch testing criterion can be satisfied with two tests that
NIST SP 500-235 · Section 5.2（新しいタブで開きます）
検算: 節点 {r=0 と a>0 判定, r=1, b>0 判定, ループ本体, return}，辺 {判定1→r=1, 判定1→判定2, r=1→判定2, 判定2→本体, 本体→判定2, 判定2→return} で e−n+2 = 6−5+2 = 3（= p+1 = 2+1）。分岐網羅は (a=1,b=1) で if 真・while 真→偽，(a=0,b=0) で if 偽・while 偽となり 2 個で全 4 分岐を実行できる。sources の節番号（2.3，4.1，5.2）は原文と一致し，5.1 を追記した。