11
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.

Cœur
  • 37,241
  • 25
  • 195
  • 267
AJ.
  • 2,561
  • 9
  • 46
  • 81
  • 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. – David Thornley Apr 19 '10 at 18:56
  • Oh yes there is no nested for loop. Its C – AJ. Apr 19 '10 at 19:01

3 Answers3

28

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.
Community
  • 1
  • 1
Vincent Ramdhanie
  • 102,349
  • 23
  • 137
  • 192
  • Out of curiosity, what tool did you use to generate the flow graph? – James McNellis Apr 19 '10 at 20:54
  • 1
    @James McNellis I used MS Visio to draw the CFG. – Vincent Ramdhanie Apr 19 '10 at 22:54
  • 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 Apr 19 '10 at 23:01
  • totally appreciate the effort. Thanks! – AJ. Apr 20 '10 at 09:06
  • @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? – Jay May 15 '13 at 06:41
  • Actually @Jay 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. – Vincent Ramdhanie May 15 '13 at 11:01
  • Ok.. I got it. It will go from 4b to 10 but not from 9 to 10. So total regions will remain the same. – Jay May 15 '13 at 11:38
3

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
  • 1,023,142
  • 271
  • 3,287
  • 2,928
  • Yes but they are at the same level of nesting, so there's a single path through the code, no ifs. – Darin Dimitrov Apr 19 '10 at 19:02
  • @AJ. 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. – Jay May 15 '13 at 06:45
  • 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. https://en.wikipedia.org/wiki/Cyclomatic_complexity#/media/File:Control_flow_graph_of_function_with_loop_and_an_if_statement.svg – Avan Apr 14 '18 at 13:54
2

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

Lineker
  • 305
  • 1
  • 9