# Cyclomatic Complexity Question

I have a general question pertaining to Cyclomatic Complexity. Please have a look at the attached source code:

``````private void downShift(int index)
{
// index of "child", which will be either index * 2 or index * 2 + 1
int childIndex;

// temp storage for item at index where shifting begins
Comparable temp = theItems[index];

// shift items, as needed
while (index * 2 <= theSize)
{
// set childIndex to "left" child
childIndex = index * 2;

// move to "right" child if "right" child < "left" child
if (childIndex != theSize && theItems[childIndex + 1].compareTo(theItems[childIndex]) < 0)
childIndex++;

if (theItems[childIndex].compareTo(temp) < 0)
{
// shift "child" down if child < temp
theItems[index] = theItems[childIndex];
}
else
{
// shifting complete
break;
}

// increment index
index = childIndex;
}

// position item that was originally at index where shifting began
theItems[index] = temp;
}
``````

From the above code, I drew out a flow graph as illustrated here: and I counted out the number of nodes to be 10, and the number of edges to be 10 as well. Using the following formula, V(G) = E - N + 2P, I calculated 3 to be the cyclomatic complexity ( or V(G)).

Is my calculation correct? Thanks!

• This looks suspiciously like a homework problem. – Beefster Feb 23 '18 at 0:19
• Possible duplicate of Understanding Cyclomatic Complexity – Robert Harvey Feb 23 '18 at 1:23
• @Beefster Even if it is, they did the work and are asking for feedback rather than asking for the answer. That seems acceptable to me. This falls under "methods and practices" as described in the help. – user1118321 Feb 23 '18 at 2:00
• Please have a look at the attached source code”. I tried. But the code is too difficult to see as it’s obscured by a ridiculous set of comments. – David Arno Feb 23 '18 at 6:32

I am not convinced your control flow graph is correct because it shows two terminal nodes 9 and 12. Instead, there should be a single terminal node for the return.

A difficulty with your code is that it contains many irrelevant details for the purpose of calculating cyclomatic complexity. So let's strip it down to the relevant control flow:

``````f() {
...;                  // enter
while (condWhile) {   // whilecond
...;              // whilebody
if (condIncr)
...;          // incr
if (condNoBreak)  // ifbreak
...;          // whileend
else
break;
...;              // whileend
}
...;                  // end
}
``````

It is worth noting that the control flow `if (cond) { a(); } else { break; } b();` is equivalent to `if (!cond) { break; } a(); b();`. Keeping that in mind, we can separate the code into basic blocks. A basic block starts with a jump target, and ends with a jump or branch to another basic block.

If you split the source code into more basic blocks that is not a problem. It will still lead to the same complexity, as an unnecessary block adds one edge and one vertex to the control flow graph, which cancels each other out. Here are the assembly-style basic blocks I chose:

``````ENTER:
...
jump WHILECOND
WHILECOND:
branch condWhile ? WHILE : END
WHILEBODY:
...
branch condIncr ? INCR : IFBREAK
INCR:
...
jump IFBREAK
IFBREAK:
branch condNoBreak ? WHILEEND : END
WHILEEND:
...
...
jump WHILECOND
END:
...
return
``````

We can now draw the control flow graph: This is a fairly complex graph, but I've tried to lay it out as a planar graph that corresponds roughly to the appearance of the source code.

There are a number of substantial differences to your graph. E.g. you only have a single path that leaves the loop. This ignores that both the loop condition and the `break` can leave the loop. And once you enter the loop body, your graph does not continue.

We can the see that the CC of this function is 4, either by applying the formula or by counting independent paths by hand.

This also shows that CC as a metric of software quality has its limits. The code you've shown is very complex and not easy to understand. Yet it has the same CC as this much simpler method (note that `&&` is a control flow operator):

``````boolean inBounds(int x, int y) {
return (0 <= x) && (x < 10)
&& (0 <= y) && (y < 10);
}
``````
• Of course, for calculating cyclomatic complexity in a structured language like Java, there's a much easier way: start with 1, then read the code line by line, adding 1 each time you see a condition with a branching point (including, as you point out, shortcircuiting boolean operators). I believe this approach may fail in the presence of "goto" statements, but for Java programs it should always work. – Jules Feb 23 '18 at 16:10
• @Jules That counts branch points, but not paths. E.g. consider `if (a) f(); if (b) g();` which has CC=4, versus `if (a) return f(); if (b) g();` which has CC=3. Early returns and loop controls such as `break` or `continue` complicate everything. If you however impose an idealistic Clean-Codeish coding style “Only guard clauses that return immediately! At most one loop per function!”, then the CC is 1 + number of guard clauses + 1 if there's a loop. – amon Feb 23 '18 at 16:21
• There are actually 11 nodes in my code, but 12 edges, I agree it is complex, but I just did a count from line to line starting with the int childIndex; declaration statement. – Al-geBra Feb 23 '18 at 20:34