Some remarks on this that I idly write up...
Specifically, for the Wikipedia equation of M = E − N + 2P
That equation is very wrong.
For some reason, McCabe indeed uses it in his original paper ("A Complexity Measure", IEEE Transactions on Software Engineering, Vo.. SE-2, No.4, December 1976), but without justifying it and after actually citing the correct formula on the first page, which is
v(G) = e - v + p
(Here, the formula elements have been relabeled)
Specifically, McCabe references the book C.Berge, Graphs and Hypergraphs (abbreviated below to G&HG). Directly from that book:
Definition (page 27 bottom of G&HG):
The cyclomatic number v(G) of an (undirected) graph G (which may have
several disconnected components) is defined as:
v(G) = e - v + p
where e = number of edges, v = number of vertices, p = number of
connected components
Theorem (page 29 top of G&HG) (not used by McCabe):
The cyclomatic number v(G) of a graph G is equal to the maximum number
of independent cycles
A cycle is a sequence of vertices starting and ending at the same vertex, with each two consecutive vertices in the sequence adjacent to each other in the graph.
Intuitively, a set of cycles is independent if none of the cycles can be constructed from the others by superimposing the walks.
Theorem (page 29 middle of G&HG) (as used by McCabe):
In a strongly connected graph G, the cyclomatic number is
equal to the maximum number of linearly independent circuits.
A circuit is a cycle with no repetitions of vertices and edges allowed.
A directed graph is said to be strongly connected if every vertex is reachable from every other vertex by passing through the edges in their designated direction.
Note that here we passed from undirected graphs to strongly connected graphs (which are directed ... Berge doesn't make this entirely clear)
McCabe now applies the above theorem to derive a simple way to compute a “McCabe Cyclomatic Complexity Number” (CCN) thusly:
Given a directed graph representing the “jump topology” of a procedure (the instruction flow graph), with a designated vertex representing the unique entry point and a designated vertex representing the unique exit point (the exit point vertex may need to be “constructed” by adding it in case of multiple returns), create a strongly connected graph by adding a directed edge from the exit point vertex to the entry point vertex, thus making the entry point vertex reachable from any other vertex.
McCabe now posits (rather confusingly I might say) that the cyclomatic number of the modified instruction flow graph "conforms to our intuitive notion of 'minimum number of paths'", and so we shall use that number as complexity measure.
Cool, so:
The cyclomatic complexity number of the modified instruction flow graph can be determined by counting the "smallest" circuits in the undirected graph. This is not particularly hard to do by man or machine, but applying the above theorem gives us an even easier way to determine it:
v(G) = e - v + p
if one disregards the directionality of the edges.
In all cases, we just consider a single procedure, so there is only one connected component in the whole graph, and so:
v(G) = e - v + 1.
In case one considers the original graph without the added "exit-to-entry" edge, one obtains simply:
ṽ(G) = ẽ - v + 2
as ẽ = e - 1
Let's illustrate by using McCabe' example from his paper:
Here we have:
- e = 10
- v = 6
- p = 1 (one component)
- v(G) = 5 (we are clearly counting 5 cycles)
The formula for the cyclomatic number says:
v(G) = e - v + p
which yields 5 = 10 - 6 + 1 and so correct!
The "McCabe cyclomatic complexity number" as given in his paper is
5 = 9 - 6 + 2 (no further explanations are given in the paper as to how)
which happens to be correct (it yields v(G)) but for the wrong reasons, i.e. we use:
ṽ(G) = ẽ - v + 2
and thus ṽ(G) = v(G) ... phew!
But is this measure any good?
In two words: Not very
- It is not entirely clear how to establish the "instruction flow graph" of a procedure, especially if exception handling and recursion enter the picture. Note that McCabe applied his idea to code written in FORTRAN 66, a language with no recursion, no exceptions and a straightforward execution structure.
- The fact that a procedure with a decision and a procedure with a loop yield the same CCN is not a good sign.
