Cyclomatic complexity

Cyclomatic complexity is a software metric (measurement). It was developed by Thomas McCabe and is used to measure the complexity of a program. It directly measures the number of linearly independent paths through a program's source code. It is computed using a graph that describes the control flow of the program. The nodes of the graph correspond to the commands of a program. A directed edge connects two nodes if the second command might be executed immediately after the first command.


Definition

M = E − N + 2P

where

M = cyclomatic complexity
E = the number of edges of the graph
N = the number of nodes of the graph
P = the number of connected components.

"M" is alternatively defined to be one larger than the number of decision points (if/case-statements, while-statements, etc) in a module (function, procedure, chart node, etc.), or more generally a system.

Separate subroutines are treated as being independent, disconnected components of the program's control flow graph.


Alternative definition

v(G) = e − n + p
G is a program's flowgraph
e is the number of edges (arcs) in the flowgraph
n is the number of nodes in the flowgraph
p is the number of connected components


Alternative way

There is another simple way to determine the cyclomatic number. This is done by counting the number of closed loops in the flow graph, and incrementing that number by one.

i.e.

M = Number of closed loops + 1

where

M = Cyclomatic number.


Implications for Software Testing:

• M is a lower bound for the number of possible paths through the control flow graph.
• M is an upper bound for the number of test cases that are necessary to achieve a complete branch coverage.

For example, consider a program that consists of two sequential if-then-else statements.

if (c1) {
f1();
} else {
f2();
}

if (c2) {
f3();
} else {
f4();
}

• To achieve a complete branch coverage, two test cases are sufficient here.
• For a complete path coverage, four test cases are necessary.
• The cyclomatic number M is three, falling in the range between these two values, as it does for any program.
  

Cyclomatic complexity can be applied in several areas, including:

• Code development risk analysis: While code is under development, it can be measured for complexity to assess inherent risk or risk buildup.
• Change risk analysis in maintenance: Code complexity tends to increase as it is maintained over time. By measuring the complexity before and after a proposed change, this buildup can be monitored and used to help decide how to minimize the risk of the change.
• Test Planning: Mathematical analysis has shown that cyclomatic complexity gives the exact number of tests needed to test every decision point in a program for each outcome. Thus, the analysis can be used for test planning. An excessively complex module will require a prohibitive number of test steps; that number can be reduced to a practical size by breaking the module into smaller, less-complex sub-modules.
• Re-engineering: Cyclomatic complexity analysis provides knowledge of the structure of the operational code of a system. The risk involved in reengineering a piece of code is related to its complexity. Therefore, cost and risk analysis can benefit from proper application of such an analysis.