Calculation Formula of JaCoco for Cyclomatic Complexity

[external.m...@gmail.com]

Hi there,

we are just asking ourselve why Jacoco uses the following formula to calculate the cyclomatic complexity:

v(G) = B - D + 1 (B = number of branches, D = number of decision points)

as far as we did research into cyclomatic complexity there are 3 methods to calculate the cyclomatic complexity:

Method 1: CC = E - N + 2 (N = Nodes / E = Edges)

Method 2: CC = Total number of bounded areas + 1 (bounded area = any region enclosed by nodes and edges)

Method 3: CC = Total number of Decision Points + 1

I am asking this question because we have cases where the total number of branches in a class is higher than the cyclomatic complexity. Is this the right behaviour? Why do you subtract the decision points from the number of branches?

[Marc R. Hoffmann]

Hi,

out formula is basically the "Method 3" in case of pure binary
decission. E.g. for a simple if statement we have 2 branches at 1
decission point. Our formula also works where decission points have more
than two branches (e.g. switch statements). Here every additional case
adds 1 to complexity.

The number of branches is typically higher than cyclomatc complexity.
Consider the following method body:

if (cond1) {
...
} else {
...
}
if (cond2) {
...
} else {
...
}

Here we have 4 branches in total, but complexity is 3.

Regards,
-marc

[markus...@googlemail.com]

As far is we understood, the cyclomatic complexity indicates how many "linearly independent paths" exists in a program's source code [1]. This number therefore represents the minimum needed test cases to ensure all possible paths in the source code (e.g. a method) are covered [2][3].
So for your example you would need 4 test cases to reach all possible combinations / outcomes:
1.) cond1 = true, cond2 = true
2.) cond1 = true, cond2 = false
3.) cond1 = false, cond2 = true
4.) cond1 = false, cond2 = false

On the other hand to achieve 100% branch coverage you would just need 2 test cases. For example:
1.) cond1 = true, cond2 = true
2.) cond1 = false, cond2 = false
See also example from [4].

In addition 100% path coverage implies 100% branch coverage [4] but not vice versa.

So I conclude that the number of (linearly independent) paths through a method needed for 100% path coverage should always be greater or equals than the number of branches to achieve 100% branch coverage. That's why the cyclomatic complexity number should always be greater or equals than the number of branches, right?

I hope I used the correct naming and I'm not missing something. Please correct me if I'm wrong.

Best regards
Markus

Sources:
[1] https://en.wikipedia.org/wiki/Cyclomatic_complexity
[2] http://www.onjava.com/pub/a/onjava/2007/03/02/statement-branch-and-path-coverage-testing-in-java.html?page=2
[3] http://users.csc.calpoly.edu/~jdalbey/206/Lectures/BasisPathTutorial/
[4] https://sites.google.com/site/swtestingconcepts/home/test-design-techniques/for-white-box/statement-branch-and-path-coverage