How to draw a Control flow graph & Cyclometric complexity for a given procedure

Cyclomatic Complexity 

Cyclomatic complexity is a software metric used to measure the complexity of a program.

These metric, measures independent paths through program source code.Independent path is defined as a path  that has at least one edge which has  not been traversed before in any other paths.

Cyclomatic complexity can be calculated with respect to functions, modules, methods or classes within a program.

Cyclomatic Flow

Compound Condition 

where one or more Boolean operators such as logical OR, AND, NAND, NOR are present is a conditional statement

IF a OR b
then procedure x
else procedure y
ENDIF

A predicate node will be created for each statement.
Compound Logic

Check the following code fragment

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;
    }
}
  • first and foremost start numbering the statement
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

That’s about it , Happy Coding :)

About these ads

One comment

  1. amarvashishth · March 8

    nice, thanx

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s