Cyclomatic Complexity

Pre-Requisite: Complexity of a Program

The cyclomatic complexity of a code section is the quantitative measure of the number of linearly independent paths in it. It is a software metric used to indicate the complexity of a program. It is computed using the Control Flow Graph of the program. The nodes in the graph indicate the smallest group of commands of a program, and a directed edge in it connects the two nodes i.e. if the second command might immediately follow the first command.

For example, if the source code contains no control flow statement then its cyclomatic complexity will be 1, and the source code contains a single path in it. Similarly, if the source code contains one if condition then cyclomatic complexity will be 2 because there will be two paths one for true and the other for false. 

Mathematically, for a structured program, the directed graph inside the control flow is the edge joining two basic blocks of the program as control may pass from first to second. 
So, cyclomatic complexity M would be defined as, 

M = E – N + 2P where E = the number of edges in the control flow graph 
N = the number of nodes in the control flow graph 
P = the number of connected components 

In case, when exit point is directly connected back to the entry point. Here, the graph is strongly connected, and cyclometric complexity is defined as

M = E – N + P

where

E = the number of edges in the control flow graph 
N = the number of nodes in the control flow graph 
P = the number of connected components 

In the case of a single method, P is equal to 1. So, for a single subroutine, the formula can be defined as

M = E – N + 2

where

E = the number of edges in the control flow graph 
N = the number of nodes in the control flow graph 
P = the number of connected components 

How to Calculate Cyclomatic Complexity?

Steps that should be followed in calculating cyclomatic complexity and test cases design are:  

Construction of graph with nodes and edges from code.

• Identification of independent paths.
• Cyclomatic Complexity Calculation
• Design of Test Cases

Let a section of code as such: 

A = 10
   IF B > C THEN
      A = B
   ELSE
      A = C
   ENDIF
Print A
Print B
Print C

Control Flow Graph of the above code

Cyclomatic Complexity

The cyclomatic complexity calculated for the above code will be from the control flow graph. The graph shows seven shapes(nodes), and seven lines(edges), hence cyclomatic complexity is 7-7+2 = 2. 

Use of Cyclomatic Complexity

• Determining the independent path executions thus proven to be very helpful for Developers and Testers.
• It can make sure that every path has been tested at least once.
• Thus help to focus more on uncovered paths.
• Code coverage can be improved.
• Risks associated with the program can be evaluated.
• These metrics being used earlier in the program help in reducing the risks.

Advantages of Cyclomatic Complexity

• It can be used as a quality metric, given the relative complexity of various designs.
• It is able to compute faster than Halstead’s metrics.
• It is used to measure the minimum effort and best areas of concentration for testing.
• It is able to guide the testing process.
• It is easy to apply.

Disadvantages of Cyclomatic Complexity

• It is the measure of the program’s control complexity and not the data complexity.
• In this, nested conditional structures are harder to understand than non-nested structures.
• In the case of simple comparisons and decision structures, it may give a misleading figure.

Important Questions on Cyclomatic Complexity

1. Consider the following program module.

int module1 (int x, int y) {
   while (x!=y){
      if(x>y)
         x=x-y,
      else y=y-x;
      }
   return x;
}

What is the Cyclomatic Complexity of the above module? [GATE CS 2004]

(A) 1

(B) 2

(C) 3

(D) 4

Answer: Correct answer is (C).

2. With respect to software testing, consider a flow graph G with one connected component. Let E be the number of edges, N be the number of nodes, and P be the number of predicate nodes of G. Consider the following four expressions:

i. E-N+P
ii. E-N+2
iii. P+2
iv. P+1

The cyclomatic complexity of G is given by [GATE CS 2006]

(A) 1 or 3

(B) 2 or 3

(C) 2 or 4

(D) 1 or 4

Solution: Correct Answer is (C).

3. What is the appropriate pairing of items in the two columns listing various activities encountered in a software lifecycle? [GATE CS 2010]

(A) P-3, Q-2, R-4, S-1

(B) P-2, Q-3, R-1, S-4

(C) P-3, Q-2, R-1, S-4

(D) P-2, Q-3, R-4, S-1

Solution: Correct Answer is (B).

FAQs on Cyclomatic Complexity

1. What is Cyclometric Complexity?

Answer:

Cyclometric Complexity is basically a software metric that is used to determine the complexity of a program.

2. Why it is recommended to reduce Cyclometric Complexity?

Answer:

High Cyclometric Complexity can lead to difficulties in code and also increases the risk of errors in code.

3. Is Cyclomatic Complexity a good or a bad thing?

Answer:

Cyclomatic Complexity is good if they are in fewer numbers and are bad if they are in more number.