Cyclomatic Complexity (McCabe)

Definition

Cyclomatic complexity is a software metric that measures the number of linearly independent paths through a program's control-flow graph (CFG). It was introduced by Thomas J. McCabe in 1976 as a measure of a module's structural complexity and testability.

Computation

Given the control-flow graph (nodes = statements/decision points, edges = control flow):

$$V(G) = E - N + 2$$

where:

• $E$ = number of edges,
• $N$ = number of nodes.

Equivalent forms:
$$V(G) = P + 1$$
where $P$ = number of predicate/decision nodes (e.g., if, while, case, &&, ||), and
$$V(G) = R$$
where $R$ = number of regions into which the graph partitions the plane.

Example — a program with:

if (a) { ... } else { ... }     → 1 decision
while (b) { ... }               → 1 decision

$P = 2 \Rightarrow V(G) = 2 + 1 = 3$ (three independent paths: if-true, if-false-through-loop, and loop iterations).

What it measures / insight it provides

1. Minimum number of test cases — $V(G)$ equals the number of independent paths, so it gives the minimum number of test cases needed to execute every statement & branch (basis-path testing).
2. Complexity / maintainability — high $V(G)$ ⇒ more decision paths ⇒ harder to understand, test, and maintain; more likely to contain defects.
3. Guidelines: modules with $V(G) \le 10$ are considered simple and maintainable; values > 10 (some say > 15/20) flag modules that should be refactored/split or given extra testing & review.
4. Testing focus: it identifies the structural risk areas so testers can concentrate effort where paths and branches are numerous.

Benefits

• Objective, easily automated (computed directly from source/CFG).
• Combines with other metrics (LOC, coupling) for quality prediction.
• Used in safety-critical and aviation standards (e.g., DO-178B) as a threshold for module complexity.

Summary: cyclomatic complexity quantifies the logical path structure of a program — guiding how many tests to write and which modules are dangerously complex — making it one of the most widely used structural metrics.