循環的複雑度

循環的複雑度（英: Cyclomatic complexity）とは、ソフトウェア測定法の一種である。Thomas McCabe が開発したもので、プログラムの複雑度を測るのに使われる。プログラムのソースコードから、線形的に独立した経路の数を直接数える。

手法としてではなく、そのコンセプトは文章の可読性（複雑度）を測定する Flesch-Kincaid Readability Test に似ている。

循環的複雑度は、プログラムの制御フローをグラフとして描くことで計算される。グラフのノードはプログラムのコマンドに相当する。2つのノードを結ぶ有向エッジは、第一のコマンドを実行後、次に第二のコマンドが実行される可能性があることを示している。

定義

M = E − N + 2P

ここで

M = 循環的複雑度

E = グラフのエッジ数

N = グラフのノード数

P = 連結成分の個数

"M" の別の定義として、モジュール（サブルーチン、プロシージャ、その他）やシステム全体の制御フローの分岐点数とする場合がある。

別の定義

v(G) = e − n + p

G = プログラムの制御フローグラフ

e = 制御グラフ内のエッジ数

n = 制御グラフ内のノード数

p = 連結成分の個数

他の手法

他にも、循環的複雑度の値を決定する単純な方法がある。制御フローグラフ内の閉じたループの個数を数え、それに 1 を加えた値である。

すなわち、

M = 閉じたループの数 + 1

ここで、

M = 循環的複雑度

ソフトウェアテストにおける意味

M は、制御フローグラフ上でとりうる経路数の下界の1つである。
M は、完全な分岐網羅率を達成するのに必要なテストケース数の上界の1つである。

例えば、次のような if-then-else 文が2つ連続しているプログラムを考えてみよう。

if (c1) {
    f1();
} else {
    f2();
}
if (c2) {
    f3();
} else {
    f4();
}

完全な分岐網羅率を達成するには、2個のテストケースで十分である。
完全な経路網羅率を達成するには、4個のテストケースが必要である。
循環的複雑度 M は 3 であり、上記の2つの値の間にある。これはどんなプログラムでも成り立つ。

語源など

循環的複雑度（Cyclomatic Complexity）という名称は、単にプログラム内のループの個数を数えるものであると誤解されやすい。この名称は、プログラムの制御フローグラフ内の閉じたループの個数に、最終ノードから開始ノードへとエッジを追加することで得られる仮想的なループを加えた値であることから来ている。より実情に近い用語として条件複雑度（Conditional Complexity）がある^[1]。

主な概念

ソースコードの一部の循環的複雑度は、ソースコード内の線形独立な経路の数である。実際、分岐点（if文やfor文など）のないソースコードの場合、その複雑度は 1 であり、そのコードには1つの経路しかない。コードに1つのif文が含まれていれば、コードには2つの経路があることになる。つまり、一方はif文での条件が真となる場合の経路で、もう一方はそれが偽となる場合の経路である。

循環的複雑度は、ソースコードの各行をノードとし、実行の流れをノード間の有向エッジで表したグラフを描くことで計算できる。プログラミング言語によっては、非常に簡潔でコンパクトな表現を用いることができるため、ソースコードの1行がグラフでは複数のノードで表されることもある（例えば、C言語、C++、C#、Javaなどにあるif文を式にしてしまう三項演算子 "?:" ）。

一般に、あるモジュールを完全にテストしようとした場合、全ての実行経路を通す必要がある。これの意味するところは、循環的複雑度の大きいモジュールの方が経路数が多く、従ってテストケースも多く必要になるということである。また、複雑度の大きいモジュールは、ソースコードの意味を理解するのに多くの経路を追わなければならず、読解がより困難になる。

また、複雑度の大きいモジュールは凝集度が低いと予想される。この相関を想定する理由は、分岐点（判断ポイント）が多いモジュールは、単一の機能以上のものを詰め込もうとしている可能性が高いためである。しかし、凝集度とは関係なく、モジュールの種類によっては必然的に複雑度が大きくなることもある。例えば、ユーザインタフェース・モジュールに入力データの妥当性確認とエラー復旧のコードが含まれている場合などである。

脚注

^ A Complexity Measure - McCabe's original paper (1976)

外部リンク

Cyclomatic complexity - at Software Engineering Institute, Carnegie Mellon University
Python complexity - Python のコードの循環的複雑度を分析するツール（Perl で書かれている）
lint_php: PHP cyclomatic complexity - PHP のコードの循環的複雑度をオンラインで分析するツール（PHP で書かれており、ダウンロードも可能）
McCabe Software, Inc. - 循環的複雑度を生み出した Thomas J. McCabe が創立した企業。循環的複雑度やコード網羅率に関するツール群を提供している。
Compuware's Xpediter/DevEnterprise - COBOL と PL/I の循環的複雑度を測るツールなど
Structure101 - 循環的複雑度をベースとして、ソースコードの品質に点数を付ける。
CyVis - Java で書かれたソースについて、循環的複雑度を視覚化してみせるフリーソフトウェア
C & C++ Code Counter - 循環的複雑度も含めた様々な静的測定法ツールのフリーソフトウェア
Some thoughts on Cyclomatic Complexity from From The Trench
Perl::Metrics::Simple - Perl のソースを静的に分析するオープンソースライブラリ。循環的複雑度も測れる。

[1] A Complexity Measure - McCabe's original paper (1976)

[1]

定義