3

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:

enter image description 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!

  • 5
    This looks suspiciously like a homework problem. – Beefster Feb 23 '18 at 0:19
  • 3
    Possible duplicate of Understanding Cyclomatic Complexity – Robert Harvey Feb 23 '18 at 1:23
  • 3
    @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
  • 1
    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
4

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:

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.