Control flow graph & cyclomatic complexity for following procedure

Question

insertion_procedure (int a[], int p [], int N)
{
    int i,j,k;
    for (i=0; i<=N; i++) p[i] = i;
    for (i=2; i<=N; i++)
    {
        k = p[i];
        j = 1;
        while (a[p[j-1]] > a[k]) {p[j] = p[j-1]; j--}
        p[j] = k;
    }
}

I have to find cyclomatic complexity for this code and then suggest some white box test cases and black box test cases. But I am having trouble making a CFG for the code.

Would appreciate some help on test cases as well.

Scroop

What language is this? It looks like C except for the "Int" rather than "int" in the declaration. If it is C, there is no nested for loop, but ratehr a while loop nested in a for loop. – Fisherman

Oh yes there is no nested for loop. Its C – Scroop

Answer 1

Start by numbering the statements:

 insertion_procedure (int a[], int p [], int N)
 {
(1)    Int i,j,k;
(2)    for ((2a)i=0; (2b)i<=N; (2c)i++) 
(3)        p[i] = i;
(4)    for ((4a)i=2; (4b)i<=N; (4c)i++)
       {
(5)       k=p[i];j=1;
(6)       while (a[p[j-1]] > a[k]) {
(7)           p[j] = p[j-1]; 
(8)           j--
          }
(9)          p[j] = k;
       }

Now you can clearly see which statement executes first and which last etc. so drawing the cfg becomes simple.

Now, to calculate cyclomatic complexity you use one of three methods:

1. Count the number of regions on the graph: 4
2. No. of predicates (red on graph) + 1 : 3 + 1 = 4
3. No of edges - no. of nodes + 2: 14 - 12 + 2 = 4.

Bergamot

Out of curiosity, what tool did you use to generate the flow graph? – Nopar

@James McNellis I used MS Visio to draw the CFG. – Bergamot

Ah; I thought it might have been created by some sort of code analysis tool. +1 for taking the effort to draw a really good picture! – Nopar

totally appreciate the effort. Thanks! – Scroop

@VincentRamdhanie Nice explanation. However, I have one doubt: isn't it possible that the control from 4b could directly jump to the end of the function? (similar to a jump from 2b to 4a)? Is there a specific reason the same is not considered? What am I missing here? – Incuse

Actually @Incuse you may be right. 4B is a predicate and as such should have 2 arrows leaving. Strange how no one picked up on that before. – Bergamot

Ok.. I got it. It will go from 4b to 10 but not from 9 to 10. So total regions will remain the same. – Incuse

Answer 2

The cyclomatic complexity is 4.

1 for the procedure +1 for the for loop +1 for the while loop +1 for the if condition of the while loop.

Shurwood

Yes but they are at the same level of nesting, so there's a single path through the code, no ifs. – Shurwood

@Scroop totally agree with you. Have added a similar comment just now in the original answer. Or else, if you know the explanation, you can add it here for benefit of all. – Incuse

2 For + 1 while + 1 procedure = 4 . Need a help if can you confirm the veracity of this wiki Link here. I think the complexity would be 4 here. but it is mentioned 3. I need someone to testify me. en.wikipedia.org/wiki/Cyclomatic_complexity#/media/… – Morbidity

Answer 3

You can also use McCabe formula M = E-N + 2C
E = edges
N = nodes
C = components
M = cyclomatic complexity

E = 14
N = 12
C = 1

M = 14-12 + 2*1 = 4

Joppa