Cyclomatic Complexity Question

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!

Answer 1

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);
}