Control-Flow Graph and McCabe's Cyclomatic Complexity

Assumed program segment (1 loop + 3 conditional branches)

1  i = 0;
2  while (i < n) {          // loop condition
3     if (a[i] > 0)         // branch 1
4         pos++;
5     if (a[i] < 0)         // branch 2
6         neg++;
7     if (a[i] == 0)        // branch 3
8         zero++;
9     i++;
   }
10 print(pos, neg, zero);

Control-flow graph

• Nodes (N = 10): 1 to 10, one per statement/decision.
• Edges (E = 13): 1-2, 2-3, 2-10, 3-4, 3-5, 4-5, 5-6, 5-7, 6-7, 7-8, 7-9, 8-9, 9-2.
• Predicate nodes (4): node 2 (loop), nodes 3, 5, 7 (branches).

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> (back to 2)
     |    \_____/    \_____/    \_____/
     |   (3 skips 4)(5 skips 6)(7 skips 8)
     +-> 10 (loop exit)

Cyclomatic complexity (three equivalent methods)

1. V(G) = E - N + 2 = 13 - 10 + 2 = 5
2. V(G) = P + 1 (P = predicate nodes) = 4 + 1 = 5
3. V(G) = number of regions = 5 (4 bounded regions + 1 outer region)

Independent paths (V(G) = 5)

Path	Route	Meaning
P1	1-2-10	Loop never entered
P2	1-2-3-5-7-9-2-10	All branches false
P3	1-2-3-4-5-7-9-2-10	Branch 1 true
P4	1-2-3-5-6-7-9-2-10	Branch 2 true
P5	1-2-3-5-7-8-9-2-10	Branch 3 true

Each path adds at least one new edge not used by earlier paths, so they are linearly independent.

Relation to the minimum number of independent paths

V(G) equals the number of linearly independent paths in the graph. It is therefore the minimum number of test cases needed to execute every statement and every branch at least once (basis path testing). Here at least 5 test cases are required.

V(G)	Risk
1 to 10	Simple, low risk
11 to 20	Moderate
21 to 50	High
over 50	Untestable

A complexity of 5 means a simple, easily testable module.