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).