Lecture
Cyclomatic complexity of a program — a structural (or topological) measure of the complexity of a computer program. The measure was developed by Thomas J. McCabe in 1976.
Calculating cyclomatic complexity uses the program's control flow graph. The nodes of the graph correspond to indivisible groups of program commands, and they are connected by directed edges if the group of commands corresponding to the second node can be executed immediately after the group of commands of the first node. Cyclomatic complexity can also be computed for individual functions, modules, methods, or classes within a program.
McCabe applied the calculation of cyclomatic complexity to testing. His proposed method consisted of testing every linearly independent path through the program, in which case the number of required tests equals the cyclomatic complexity of the program.
The cyclomatic complexity of a piece of program code is the number of linearly independent paths through the program code. For example, if the source code contains no branch points or loops at all, the complexity equals one, since there is only a single path through the code. If the code has a single IF statement containing a simple condition, then there are two paths through the code: one if the condition of the IF statement is TRUE, and one if it is FALSE.
Mathematically, the cyclomatic complexity of a structured program is defined by means of a directed graph whose nodes are the blocks of the program, connected by edges if control can pass from one block to another. Then the complexity is defined as: :
M = E − N + 2P,
where:
M = cyclomatic complexity,
E = the number of edges in the graph,
N = the number of nodes in the graph,
P = the number of connected components.
In another formulation, a graph is used in which every exit point is connected to the entry point. In this case the graph is strongly connected, and the cyclomatic complexity of the program equals the cyclomatic number of that graph (also known as the first Betti number), which is defined as
M = E − N + P.
This definition can be viewed as computing the number of linearly independent cycles that exist in the graph, that is, those cycles that do not contain other cycles within themselves. Since every exit point is connected to the entry point, there is at least one cycle for every exit point.
For a simple program, or subprogram, or method, P is always equal to 1. However, cyclomatic complexity can be applied to several such programs or subprograms (for example, to all the methods in a class), in which case P equals the number of subprograms in question, since each subprogram can be represented as an independent part of the graph.
It can be shown that the cyclomatic complexity of any structured program with only one entry point and one exit point is equivalent to the number of branch points (that is, if statements or conditional loops) contained in that program, plus one.
Cyclomatic complexity can be extended to a program with multiple exit points; in this case it equals
π − s + 2,
where:
π — the number of branch points in the program,
s — the number of exit points.
Formally, cyclomatic complexity can be defined as the relative Betti number:
that is, «the first homology of graph G relative to the terminal nodes t. This is another way of saying «the number of linearly independent paths through the graph from entry to exit».
In addition, cyclomatic complexity can be computed via the absolute Betti number (using absolute homology rather than relative), by merging all the terminal nodes of the given component (which is equivalent to connecting the exit points to the entry point), in which case for the new, extended graph 
The cyclomatic number of a graph is the number equal to the difference between the number of edges and the number of vertices of the graph, increased by one:
The cyclomatic number of a graph shows how many edges need to be removed from the graph so that no cycle remains in it.
Problem 1. Given a graph in which m = 6, n = 9 (fig. 8.18, a). Determine how many edges need to be removed from the graph so that no cycle remains in it.
Fig. 8.18. Original graph (a) and spanning subgraph (b)
(-------) removed edges
For the given graph the cyclomatic number is y = 9 — 6 + 1 = 4. This means that if 4 edges are removed from the graph, no cycle will remain in it. The spanning subgraph will then have the form shown in fig. 8.18, b.
Problem 2. What is the minimum number of doors that need to be provided in the castle (fig. 8.19) in order to reach all the rooms (a door — one edge).
Fig. 8.19. Plan of the castle (top view)
Solution. The number of vertices m = 14, the number of edges n = 21. The cyclomatic number is y = 21 — 14+1 = 8. Hence, 8 doors need to be provided in the castle. Alongside the cyclomatic number, graph theory also introduces the concept of the co-cyclomatic number. Let m — be the number of edges, n — the number of vertices, and p — the number of connected components in the graph. The quantity r = n—p is called the co-cyclomatic number (the number of edges in the spanning trees of allp connected components of the graph).
One of the applications originally proposed by McCabe is that program complexity needs to be limited during development. He recommends that programmers be required to compute the complexity of the modules they develop and split modules into smaller ones whenever the cyclomatic complexity of these modules exceeds ten. This practice was incorporated by NIST into its structured testing methodology, with the remark that since McCabe's original publication the choice of the value 10 has received substantial supporting evidence, although in some cases it may be reasonable to relax the limit and allow modules with a complexity up to 15. This methodology acknowledges that there may sometimes be reasons to go beyond the agreed limit. This is phrased as a recommendation: «For each module, either the cyclomatic complexity should be limited to agreed bounds, or a written explanation should be provided as to why the limit was exceeded».
Another application of cyclomatic complexity is determining the number of tests needed for full code coverage.
It is useful because cyclomatic complexity M has two properties, for a specific module:
Cyclomatic complexity is used as one of the parameters in the maintainability index .
Comments