Cyclomatic Complexity Calculator
Loop after loop, your code may get hard to read and understand: our cyclomatic complexity calculator can tell you if adding that nested if would be too much!
Here you will learn an essential part of theoretical computer science, and we hope that it will help you write better code. Keep reading to learn:
- What is programming complexity, and why does it matter;
- How to measure programming complexity: the cyclomatic complexity;
- How to calculate the cyclomatic complexity: the cyclomatic complexity formula; and
- A neat example.
We are here to tell you how to reduce your cyclomatic complexity; what are you waiting for?
Understanding programming complexity
Studying complex system physics, professors tend to repeat a short mantra: complicated and complex are two different things. The distinction is pretty easy to make when talking of problems.
- Complicated means a messy problem, full of variables but theoretically solvable with enough computational power. Think of the exact trajectory of a golf ball. We can calculate the effect of every single air molecule on it: it would take a lot of time, but eventually, we would have an exact result.
- Complex means a problem where even a small number of elements develop iterations which causes the emergence (scientists love this word) of non-deterministic behaviors or deep connections that may make it hard to understand and modify the problem.
Your code, any program, can be analyzed in terms of complexity. Each block of instructions that interacts with others can repeat; there may be bifurcations only to return to the main path.
An increase in complexity reflects a growing set of interactions that, after a while, may reach a point where it would be impossible to modify the program or even understand it!
Representing complexity: the control-flow graph
Frances Allen, the first woman to win a Turing award (the Nobel prize of computer science), introduced a way to represent a program using a graph that made it easy to understand the underlying complexity: the control-flow graph.
Let's check it out!
To build a control-flow graph, follow these steps:
- Each instruction corresponds to a node;
- Each jump in the code (from one instruction to the other) corresponds to an edge;
It is possible to reduce the number of nodes by grouping subsequent nodes if the edge connecting them:
- Departs from a node with a single outbound edge; and
- Ends in a node with a single entry.
This process allows us to reduce to minimize the control-flow graph.
Consider this simple program to check if a number is prime or not, written in pseudocode (visit our prime number calculator for a ready implementation of it).
DECLARE n, i, flag SET flag=0 PRINT "Enter a positive integer: " READ n IF n == 0 OR n == 1 SET flag = 1 FOR i = 2; i <= n/2; INCREMENT i) IF n MOD i == 0 SET flag = 1 BREAK IF flag == 0 PRINT "Prime number." ELSE PRINT "Not a prime number."
We can draw the control-flow graph by assigning a node to each instruction:
There are a lot of instructions, though. Let's reduce them. The next representation will be the one we will use to teach you the cyclomatic complexity of a program.
As you can see, this representation highlights loops and bifurcations. In fact, complexity is all about them. In a program, we can find many types of instruction increasing the complexity:
- Conditional statements: if, if...else, if...else if;
- Loops: for, while, do...while;
- Break statements;
And many more. You can easily understand the representation of such elements when you think of their function.
Calculating complexity: the cyclomatic complexity
To measure the complexity of a program, scientists introduced metrics that allow quantifying how many interactions it contains (and how bad they are). There are many types of complexity metrics, but one is particularly straightforward: the cyclomatic complexity metric .
The concept of cyclomatic complexity heavily borrows terms from graph theory in math. It uses nodes, edges, and components to measure the number of linearly independent paths in the code (what is linear independence? Discover it at the linear independence calculator).
Edges and nodes are the basic elements of a graph. A set of independent edges and nodes is called a connected component. Each program has at least a connected component, but that's the only sure thing!
How to calculate the cyclomatic complexity
The cyclomatic complexity formula is simple. Make sure to know the elements we introduced before: nodes, edges, and connected components. Then, apply the formula:
- is the number of nodes;
- is the number of edges; and
- is the number of connected components.
🔎 Why do we use to indicate the cyclomatic complexity? It comes from the name of its creator, Thomas J. McCabe, Sr.
It is easier to understand the cyclomatic complexity with a few examples:
- A simple code without loops and conditions has cyclomatic complexity . We can reduce it to a single node without edges; hence the cyclomatic complexity formula reduces to:
- A code with a single if...else condition has a control-flow graph where a bifurcation departs from a node; there are two possible sets of instructions (two nodes) that reconnect in a final node. The total number of nodes is , and there are analogously edges. The cyclomatic complexity is Look at the diagram:
- In a while loop, we can identify the starting node (a condition), a set of instructions to be executed in the loop, and an exit node containing the instructions executed after the loop. The total number of nodes is , which equals the number of edges. The cyclomatic complexity formula tells us that there are:
Two independent paths in the program.
As you can see, the cyclomatic complexity is easy to calculate. Remember to count the correct number of nodes, edges, and components.
An example of cyclomatic complexity calculation
We can try to compute the cyclomatic complexity of a bigger program. We chose a code that computes the Collatz conjecture (you can learn more at our Collatz conjecture calculator).
Take a look at the pseudocode:
DECLARE n, i PRINT "Insert the starting number." WHILE n < 0 READ n IF n < 0 PRINT "Insert a nonnegative number" PRINT n WHILE n != 1 IF n MOD 2 == 0 SET n = n/2 ELSE SET n = 3 × n + 1 PRINT n SET i = 0 WHILE i < 3 IF n MOD 2 == 0 SET n = n/2 ELSE SET n = 3 × n + 1 PRINT n INCREMENT i
The code prints the Collatz sequence and repeats three times the final loop . We drew the control-flow graph for you:
Let's count the nodes and the edges. Note that there is again a single connected component.
- nodes; and
We calculate the cyclomatic complexity:
How to use our cyclomatic complexity calculator?
Our cyclomatic complexity calculator is easy to use: insert the parameters of your code, and find out its complexity.
Even if using it is easy, the answer you get can help you write better, more agile code. If you follow the guidelines of the very creator of the cyclomatic complexity, remember to split modules when they reach a certain complexity, originally .
What is cyclomatic complexity?
Cyclomatic complexity is a metric that measures the complexity of a program by computing the number of linearly independent paths in the code. The higher the number of independent paths, the higher the difficulty in reading and modifying the code.
How do I calculate the cyclomatic complexity?
To calculate the cyclomatic complexity, follow the next steps:
- Count the nodes
Ein the control-flow graph;
- Count the number of independent components
P(disjoined groups of nodes and edges); and
- Apply the cyclomatic complexity formula:
M = E - N + 2 × P
Remember that the number of components in a code without functions and methods is
What is the cyclomatic complexity of nested if...else statements?
Nested if...else statements have a cyclomatic complexity of
4. Draw the control-flow graph: it includes
10 nodes (an entry and exit node for each statement, for a total of
4 instructions) and
12 edges. There is a single component. Apply the cyclomatic complex formula:
M = 12 - 10 + 2 × 1 = 4
How to reduce the cyclomatic complexity?
To reduce cyclomatic complexity, split your program into smaller modules. This will make your code easier both to read and manipulate. You can also try to reduce the number of if statements: remember that:
IF a>b RETURN TRUE
Is the same of: