Cyclomatic complexity explained

26/01/2019

Cyclomatic complexity

Cyclomatic complexity is a code metric first proposed by Thomas McCabe, Sr. in 1976. For this reason, it is also sometimes known as the McCabe number. As the name suggests, it is a measure of a program's complexity. It is defined as being the number of independent paths of the program. If we take the CFG (Control Flow Graph) of the code, it is easier to count these independent paths. The CFG is a directed graph. Let us call this graph G.

Let's start with two nodes 1 and 2 and a directed edge going from node 1 to node 2. We have 2 nodes, 1 edge and 1 independent path. In order to add a new path, we then always have two choices: either add a new node and two edges or add a single new edge between two existing nodes. Let us call m the number of times we use the first option and n the number of times we use the second option.

We can now write that CYC = 1 + m + n. If we denote the number of nodes by N and the number of edges by E, we can also write: N = 2 + m and E = 1 + 2m + n. we now get after substituting and doing the necessary algebraic gymnastics that CYC = E - N + 2.

This demonstration can also be formalized and turned into a proper demonstration by induction.