サイクロマティック複雑度・独立経路数

プログラムの制御構造から線形独立な基底経路の本数を数える。

入口と出口は各成分に1つ。全節点が入口から到達でき、出口へ到達できる有向グラフを入力してください。

複合条件・例外処理は、実際に分岐する経路を確認してから数えてください。

入力すると自動で計算します。Enterで次の項目へ進めます。次の入力欄を選んで進めます。

選択内容に応じて、残りの入力項目を案内します。

計算する内容
節点必須
行節点ID種別操作
1
2

2列を左端の欄へタブ区切りで貼り付けられます。100行まで。

節点IDは表内で一意。各独立グラフに入口・出口を1つずつ設定してください。

有向辺必須
行接続元ID接続先ID分岐名 任意操作
1
2

3列を左端の欄へタブ区切りで貼り付けられます。100行まで。

接続元→接続先の向きで1辺ずつ入力。同じ2節点間の複数の辺には別々の分岐名が必要です。出口→入口の仮想辺は入力しません。


計算結果

必要な値を入力すると自動で計算します。

お気に入り一覧

計算方法・適用範囲・出典

計算方法

制御フローからは V(G)=E−N+2P(E:有向辺数、N:節点数、P:弱連結成分数)。分岐集計では V(G)=P+Σ(k−1)(k:各分岐点の行先数)。V(G)は独立な基底経路の本数であり、全実行経路数やテストの実施・実行可能性を保証する数ではありません。

サイクロマティック複雑度、基底経路数、成分またはモジュールごとの内訳。

計算例(架空の数値)

架空例:1モジュールで2方向の分岐が2つなら V(G)=1+(2−1)+(2−1)=3。節点4・辺5の同等の制御フローなら V(G)=5−4+2=3。

適用対象と限界

単一入口・単一出口の制御フローグラフと、同じ制御フロー定義で分岐を集計したモジュール。ソースコードからの自動解析、基底経路そのものの列挙、到達不能コードを含むグラフ、複数入口・出口、例外フローの自動補完、パス実行可能性の判定は対象外。。

採用した方式

  • 制御フローの有向辺・節点計数(NIST SP 500-235 (1996) §2.2):対象範囲 連結成分ごとに入口・出口を1つずつ持ち、全節点が入口から到達可能かつ出口へ到達可能/適用地域 global
  • 分岐先数の集計(NIST SP 500-235 (1996) §4.1):対象範囲 全分岐先を確定した独立モジュール。複合条件は実際の短絡評価による分岐を数える/適用地域 global

方法と出典

方法:McCabe 1976 / NIST SP 500-235 (1996) §2.2・§4.1 / NISTIR 8289 (2020) §6.4; E342-v1。データ記録日:2026-11-13。