views:

379

answers:

2
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 cyclometric 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.

Thanks a bunch in advance!

+2  A: 

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.

Darin Dimitrov
But there are two for loops?
AJ
Yes but they are at the same level of nesting, so there's a single path through the code, no ifs.
Darin Dimitrov
So shouldn't it be 5?
AJ
+4  A: 

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.

CFG

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.
Vincent Ramdhanie
Out of curiosity, what tool did you use to generate the flow graph?
James McNellis
@James McNellis I used MS Visio to draw the CFG.
Vincent Ramdhanie
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!
James McNellis
@vincent totally appreciate the effort. Thanks!
AJ