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.

The concept, although not the method, is somewhat similar to that of general text complexity measured by the Flesch-Kincaid Readability Test.

Cyclomatic complexity 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.