White Box Testing
Test your code
   Home      cyclomatic complexity
 

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
1-10
a simple program, without much risk
11-20
more complex, moderate risk
21-50
more complex, moderate risk
greater than 50
untestable program , very high risk
 

External References

 
Cyclomatic Code Complexity Analysis for Microsoft .NET Applications