McCabe's Cyclomatic complexity
Cyclomatic
complexity introduced by thomas McCabe in 1976. It simply measures the
amount of decision logic in the program module.Cyclomatic
complexity gives the minimum number of paths that can generate all
possible paths through the module.Cyclomatic complexity is often
referred to as McCabe's complexity.McCabe's complexity used to define
minimum number of test cases required for a module and it is used during
software development lifecycle to quantify maintainability and
testability.Cyclomatic complexity is defined as
CC = E  N + P
Where
E = the number of edges of the graph
N = the number of nodes of the graph
P = the number of connected components
In case of connected graph
CC = E  N + 2
In simplified way it can be defined as
CC = D +1
Where
D = the number of decision points in the graph
Cyclomatic complexity and Control Flow Graph
Control
flow graph or CFG is a graphical representation of program module.
Control flow graph is a directed graph in which node represent program’s
region and edges represent flow from one program region to other.
Basic construct of CFG
int BinSearch (char *item, char *table[], int n)
{
int bot = 0;
int top = n  1;
int mid, cmp;
while (bot <= top) {
mid = (bot + top) / 2;
if (table[mid] == item)
return mid;
else if (compare(table[mid], item) < 0)
top = mid  1;
else
bot = mid + 1;
}
return 1; // not found
}
In this example
CC = number of edges – number of nodes + 2
CC = 14 – 12 + 2
= 4
Now CC from simplified formula
CC = number of decision point + 1
= 3 + 1
= 4
A multiway decision, the Select Case statement, is counted as several decisions.
Boolean operators add either one or nothing to complexity depending
upon whether they are generating other paths in conditional statement
Decision types 
Effect on CC 
If.. 
+1 
ElseIf.. 
+1 
Else 
0 
switch Case 
+1 for each Case 
For (…) 
+1 
While(…) 
+1 
Do – while(…) 
+1 
Boolean operators 
+1 or 0 
Cyclomatic complexity and linearly independent test
The
McCabe metric measures the number of linearly independent paths that
generate all possible path in any independent set of paths.
These
linearly independent paths becomes linearly independent tests for the
program module, this is the minimum number of test cases required to
achieve maximum test coverage. Any other test path except these will be
redundant and will not be linearly independent
Thus
McCabe cyclomatic complexity also gives the minimum number of test
paths to achieve maximum coverage. See the previous example of binsearch
In
this example the CC is 4, thus this module has 4 linearly independent
paths and this is the minimum number of test paths to achieve maximum
coverage
TC0: 0>1>2>3>11
TC1: 0>1>2>4>5>6>11
TC2: 0>1>2>4>5>7>8>10>2>3>11
TC3: 0>1>2>4>5>7>9>10>2>4>5>6>11
These test paths achieve maximum coverage and any path other than these will dependent on these paths
Limiting CC
Various researches shown,
program module having CC greater than 10 considered complex. Overly
complex module reduces maintainability and testability. See below some
standard ranges of this metrics
Cyclomatic Complexity 
Complexity level and Risk 
110 
a simple program, without much risk 
1120 
more complex, moderate risk 
2150 
more complex, moderate risk 
greater than 50 
untestable program , very high risk 
External References
Cyclomatic Code Complexity Analysis for Microsoft .NET Applications
