cyclomatic complexity = 1 + #if statements?

Question

I found the following paragraph regarding cyclomatic complexity on Wikipedia:

It can be shown that the cyclomatic complexity of any structured program with only one entrance point and one exit point is equal to the number of decision points (i.e., "if" statements or conditional loops) contained in that program plus one.

That would imply a cyclomatic complexity of 3 for two arbitrary nested if statements:

if (a)
{
    if (b)
    {
        foo();
    }
    else
    {
        bar();
    }
}
else
{
    baz();
}

Since exactly one of the three functions is going to be called, my gut agrees with 3.

However, two arbitrary if statements could also be written in sequence instead of nesting them:

if (a)
{
    foo();
}
else
{
    bar();
}

if (b)
{
    baz();
}
else
{
    qux();
}

Now there are four paths through the code:

• foo, baz
• foo, qux
• bar, baz
• bar, qux

Shouldn't the cyclomatic complexity of this fragment hence be 4 instead of 3?

Am I misunderstanding the quoted paragraph?

Answer 1

Cyclomatic complexity is defined as the number of linearly independent paths through the code.

In your second example we have the following paths that runs...

| # |   A   |    B  |  Nodes hit   |
| 1 | true  | true  |  foo() baz() |
| 2 | true  | false |  foo() qux() |
| 3 | false | true  |  bar() baz() |
| 4 | false | false |  bar() qux() |

You are completely correct that the number of execution paths here is 4. And yet the cyclomatic complexity is 3.

The key is in understanding what cyclomatic complexity measures:

Definition:

A linearly independent path is any path through the program that introduces at least one new edge that is not included in any other linearly independent paths.

from http://www.ironiacorp.com/

The 4th path is not linearly independent of the first three paths, as it does not introduce any new nodes / program statements that were not included in the first three paths.

As mentioned on the wikipedia article, the cyclomatic complexity is always less than or equal to the number of theoretical unique control flow paths, and is always greater than or equal to the minimum number of actually achievable execution paths.

(to verify the second statement, imagine if b == a was always true when entering the code block you described).

Answer 2

I agree with the explanation of perfectionist. Here is a more informal explanation in the case of the Java language:

McCabe's Cyclomatic Complexity (McCC) for a method is expressed as the number of independent control flow paths in it. It represents a lower bound for the number of possible execution paths in the source code and at the same time it is an upper bound for the minimum number of test cases needed for achieving full branch test coverage. The value of the metric is calculated as the number of the following instructions plus 1: if, for, foreach, while, do-while, case label (which belongs to a switch instruction), catch, conditional statement (?:). Moreover, logical “and” (&&) and logical “or” (||) expressions also add 1 to the value because their short-circuit evaluation can cause branching depending on the first operand. The following instructions are not included: else, switch, default label (which belongs to a switch instruction), try, finally.