Abhinav Rai

Cyclomatic complexity

Cyclomatic complexity is a software metric used to measure the complexity of a program. These metric, measures independent paths through program source code. Independent path is defined as a path that has at least one edge which has not been traversed before in any other paths.

Cyclomatic complexity can be calculated with respect to functions, modules, methods or classes within a program.

Firstly, what is software metric?

Measurement is nothing but quantitative indication of size / dimension / capacity of an attribute of a product / process.

Software metric is defined as a quantitative measure of an attribute a software system possesses with respect to Cost, Quality, Size and Schedule.

Flow graph notation for a program:

Flow Graph notation for a program is defines. several nodes connected through the edges. Below are Flow diagrams for statements like if-else, While, until and normal sequence of flow.

Here nodes represent the task and edges represent the flow between the nodes.

Mathematical representation:

Mathematically, it is set of independent paths through the graph diagram. The complexity of the program can be defined as -

V(G) = E — N + 2

Where,

E — Number of edges

N — Number of Nodes

V (G) = P + 1

Where P = Number of predicate nodes (node that contains condition)

We can also get the V(G) is we count the number of independent paths in Control Flow Diagram.

Lets take an example —

If (Condition 1)
  Statement 1
Else
  Statement 2
If (Condition 2)
  Statement 3
Else
  Statement 4
Statement 5

Control Flow Graph for the same Control Flow Graph for the same

Nodes = 6, Edges = 8

Cyclomatic complexity = 8–6+2 = 4

How this metric is useful for software testing?

Basis Path testing is one of White box technique and it guarantees to execute atleast one statement during testing. It checks each linearly independent path through the program, which means number test cases, will be equivalent to the cyclomatic complexity of the program.

This metric is useful because of properties of Cyclomatic complexity (M) -

  • M can be number of test cases to achieve branch coverage (Upper Bound)
  • M can be number of paths through the graphs. (Lower Bound)

As in the above example — we have 4 as cyclomatic complexity, we need 4 tests for the same.

Good videos on cyclomatic complexity — https://www.youtube.com/watch?v=JwTQywqpZ5Y, https://www.youtube.com/watch?v=ihkUVzUzztY&t=280s.

For any details, you may contact the author at me@abhinavrai.com