Cyclomatic complexity is a metric for measuring the complexity of a program. It indicates the maximum number of independent paths through which control may flow in a program throughout its execution. It has many applications in understanding the structuredness of a program and ensuring thorough testing for source code.
A program that has no branching statements like if-else or switch-case has a cyclomatic complexity of 1. A single if statement (or an if-else statement) increments the complexity to 2, as now there are two paths through which control may flow.
How is cyclomatic complexity calculated?
Cyclomatic complexity calculations employ a directed graph that maps each statement in the program to a node. A directed edge connects two nodes if control may flow from the first node to the second. Each exit node must be connected back to the entry node, hence the name "cyclomatic complexity."
The complexity, denoted by M, is defined as M = E - N + 2, where E is the number of edges in the graph and N is the number of nodes. Here we see that if a program has no branching statements, E will be one less than N as there is one edge between two sequential nodes, which gives us a complexity of 1.
What is the significance of cyclomatic complexity?
- Cyclomatic complexity helps visualize the flow of control and thus in understanding the inherent complexity of an algorithm. Suppose the complexity of a module exceeds a threshold such as 10. In that case, we should break it into simpler modules.
- Cyclomatic complexity analysis determines the number of test cases sufficient to test all paths of a program thoroughly. Code with a complexity of M requires at most M test cases to test every possible branch.