My previous article on Managing Technical Debt provided an introduction to the concept of technical debt and also suggested tools to measure the same.
This post discusses a concept called Cyclomatic complexity, a quantitative approach to measure the complexity of code. Complex code is always difficult to maintain and modify. Every good developer knows that. Often this is an issue that is ignored or given less attention than it deserves by non-tech project managers and management. One of the reasons for it is that there is no simple way to express these concerns without getting into the details of the code.
Cyclomatic Complexity of a module should not exceed 10.
Before we get into how to measure complexity, we have to understand the two types of Complexity: Essential complexity and Accidental complexity.
Essential complexity is the inherent complex nature of the problem we are trying to solve. This complexity cannot be avoided. For instance, building software for a stock market will always be more complex than building software for library management.
Accidental complexity is, well, accidental. It is a result of sub-standard code piling up because of all the quick fixes, workarounds, incorrect assumptions, and inept programmers.
The approach detailed next is only to reduce the accidental complexity of the code and not the essential complexity.
McCabe, in his paper illustrates how using the size of the code isn’t a great way to limit the complexity of the code. For example, a program as small as 50 lines consisting of 25 consecutive “IF THEN” constructs could have as many as 33.5 million distinct control paths. In other words, there are 33.5 million different paths in which the program could execute. Only a fraction of that would probably ever be tested and hence is more than likely to have defects. Hence, an alternative approach is needed to restrict and measure complexity of code.
The alternative approach suggested in the same paper is called cyclomatic complexity. The measure of the complexity is based on graph theory.
The cyclomatic number V(G) of a graph G with E edges, N vertices and P connected components is
v(G) = E – N + P.
Cyclomatic complexity is a software measurement technique that is used to indicate the complexity of a program. Developed by Thomas J. McCabe, it provides a quantitative measure of the number of linearly independent paths through the source code. According to P. Jorgensen, Cyclomatic Complexity of a module should not exceed 10.
However note that any program with a backward branch (which luckily is not used much in many new programming languages) has an infinite number of paths. Hence, it is only the number of basic paths that will be taken into account to generate every possible path and the complexity of the program.
Why is measurement of complexity important? It helps us to quantitatively measure the modularization effort the code so the software is testable and maintainable. Testability and maintainability are important because they take up most of the time in the development life-cycle of the product.
Cyclomatic complexity is generally used to measure the complexity at the class or the method level. Determining complexity at the module or the project level is not beneficial to fix the finer issues in the code.
Consider for example a code with no if-else statements. Since the entire code always executes i.e. only one decision point, the Cyclomatic complexity of the program is 1. If there is one if-else statement, the code can only execute one of those blocks and never both. Because there are two decision points, the complexity of this code is 2.
Moving to a more complex example, consider the pseudo code below.
In the graph, the exit point loops back to the entry point. Also, for a single program (such as a subroutine or method), P is always equal to 1. Hence, in total, P is 2. So a simpler formula for calculating complexity is
v(G) = E − N + 2
If you need to measure the complexity across many programs, the appropriate value for P needs to be used.
In Java, the decision points where the complexity needs to be incremented by 1 are:
if-else statements, ?:
while, do, for
catch, switch, case statements
&& and ||
The programmer should always aim to reduce the number of decision points within a module so that the complexity of the code and hence the number of execution points are reduced.
Benefits of Reducing Cyclomatic Complexity
- Reduces the coupling of code. The higher the cyclomatic complexity number, the more coupled the code is. Highly coupled code cannot be modified easily and independently of other code.
- Ease of understanding the code increases as the complexity decreases. With a higher complexity number, the programmer has to deal with more control paths in the code which leads to more unexpected results and defects.
- Ease of testing. If a method has a cyclomatic complexity of 10, it means there are 10 independent paths through the method. This implies is that at least 10 test cases are needed to test all the different paths through the code. The lesser the number, the easier it is to test.
Tools for Calculating Cyclomatic Complexity
Unless you are dealing with a single class or two, of course it is impossible to calculate the cyclomatic complexity manually. Many automated tools exist that statically analyze the code and calculate many quality metrics, one among them being the cyclomatic complexity. These tools can be incorporated into the build life cycle of the code or into the Continuous Integration phases.