Useful theory: cyclomatic complexity

(10.02.2009)

When faced with a test suite that doesn’t show errors we may have two possible ends:

So the question coming to mind is: how and when we should stop writing tests?

Cyclomatic complexity to the rescue!

The number of tests required for a software “module” is equal to the cyclomatic complexity (although under particulare circumstances it can be lowered).

When testing we adopt generally two approaches: (1) tests derived from requirementes (our application does what it is supposed to do) and (2) “white box” tests (our application works correctly with inputs, conditions, and so on).

While the case (1) involves only a small fraction of test “discovered” (eg: in requirements no one mentioned robustness on wrong/missing input parameters, but they are important), the case (2) are generally more tedious to write because code is more rich of details than requirements. McCabe said that “the cyclomatic complexity measures the amount of decision logic in a single software module” (McCabe, T. “A complexity Measure”, IEEE Transaction of software engineering, December 1976). So the lesser the cyclomatic complexity the better: simple code is easier to test.

In fact, it’s worth to note that cyclomatic complexity equals the number of indipendent paths of control flow in the “module” so, again: the smaller the better.

How can it be measured?

There are some ways to measure the cyclomatic complexity. A common base is done by representing the software “module” we are considering as a directed graph where nodes represent statements and edges represent transfer control between statements.

Then having:

e = number of edge (transition between two statements)
n = number of nodes (statements)
p = number of decision predicate nodes (if, else, while, etc)

we can express cyclomatic complexity as:

V(G) := e - n + 2

or:

V(G) := p + 1

Example:

if a or b
  x = compute_some_function(x)
else
  x = y
end
r = x + Time.now

Applying the above formulae we obtain a value of V(G) = e - n + 2 = 7-6+2 = 3.

Obviously we don’t need to compute it by hand, there are specific tools for main used programming language.

Finally, we can say that cyclomatic complexity is a measure that helps us to evaluate logic complexity of our code in order to:



Comments

(Comments)
blog comments powered by Disqus