Metric - Cyclomatic Complexity

There is a simple and logic explanation: the more “if”, “while”, “for”, and etc. in code the higher the complexity of the code improvement, management, understandability and refactoring.

Cyclomatic (here and on – V(g)) is an a-posteriori metric, the same as LOC. V(g) is being used only after the initial code is written. Some programmers criticise these things saying that better to prevent too complicated code than correct it afterwards. However, in real life very often we have the situation when the code is already written by somebody else and according to the Murphy Law *you* have to deal with it.

The “Cyclomatic Complexity” concept was originally introduced by Thomas McCabe. CFG - control flow graph is the

basis of the metric. Famous IDA Pro demonstrates, probably, the most adequate visual representation of CFG where you can clearly see the basic blocks and the ribs which connect them.

So, V(g) is not interested in what happens inside the basic blocks (here and on BB) but it’s the only interest is the number of possible variants of travel through the ribs. We are not going to present the principles of graph theory which are the fundamental basis of V(g), there is McCabe's article for that.

It’s worth to mention that V(g) works at the function level only. For an empty function:

void some_function()
{
   return;
}

V(g) = 1, because the only possible way via the given function already exists.

For something more complicated:

int some_function(int i)
{
   if (!i)
     return 0;
   return 1;
}

V(g) = 2, we start having branches here; and to pass through “some_function” there are two ways already. Obviously, if we add something like that

int some_function(int i)
{
   if (!i)
     return 0;
   else
     return 1;
}

then V(g) = 2 still because the idea has not been changed.

If we write like this

int some_function(int i, int z)
{
   if (!i && !z)
     return 0;
   return 1;
}

we will get V(g) = 3 because now we have branches inside “if”. Assume, the general idea is clear: all conditional operators including “?:” and other exotic things are taken into consideration.

To read more I would recommend the following:

• http://en.wikipedia.org/wiki/Cyclomatic_complexity
• http://hissa.nist.gov/HHRFdata/Artifacts/ITLdoc/235/chapter2.htm

Advantages

1. Calculation of V(g) is ultimately simple: it’s enough to parse the functions, counting a set of operators for each one for the given language:
   
   • http://www.codeproject.com/KB/architecture/Cyclomatic_Complexity.aspx
   • http://www.codeproject.com/KB/macros/CCMetricViewer.aspx
   
   But sorry to say that this standard tool from McCabe - rsm does not understand, for example, that “С++ exceptions” also increase the cyclomatic. For the following examples V(g) is determined incorrectly:
   

         int main()
         {
            int i = 0;
            try{
               if ( i != 1 ) return 0;
            }
            catch( ... )
            {
               return 1;
            }
         }
   

   
   
   

         int main()
         {
            int i = 0;
            __try{
               if ( i != 1 ) return 0;
            }
            __except( EXCEPTION_EXECUTE_HANDLER )
            {
               return 1;
            }
         }
   

   
   
2. V(g) is understandable by intuition and can be organically enrolled into development. The functions with a high V(g) can be seen even visually.
3. V(g) forms “function risk” criteria which are absolutely formal and mathematically well-grounded (combinatorics):
   
   1. V(g): from 1 to 10 – a program is simple and the risk is low;
   2. V(g): from 11 to 20 – a program of medium complexity with the medium risk level;
   3. V(g): from 21 to 50 – a complex program with high risk;
   4. V(g): > 50 – absolutely NOT testable program.
   
   I would like to emphasise that there is high positive correlation between function V(g) and the bug amount in that function.
   
4. V(g) is the perfect basis for code coverage and as a result of it, for unit-tests writing and white-box testing.

Disadvantages

1. We have already mentioned that V(g) does not deal with BB. Consequently, as an example, a huge function on SEME model will pass by uncontrolled. Suppose now you've missed some free() or some mutex releases. Metric will not see it. At the same time a man who sees a low V(g) will not be concerned about the matter.
2. Due to V(g) deals with CFG only, the data flow graph will be left behind unseen with all the consequences.
3. Some edged cases can be assessed inadequately by V(g), switch+case for instance:
   

         switch( temperature ) {
         case 108: lowerTemp( 2 ); break;
         case 107: lowerTemp( 2 ); break;
         case 106: lowerTemp( 1 ); break;
         case 105: lowerTemp( 1 ); break:
         ….
         case 0: soundAlarm( 0 ); break;
         default: soundAlarm( i ): break;
         }
   

   
   This code will have monstrous V(g) but in reality, the support, refactoring, and coverage are trivial. There are some other cases of V(g) inadequate behaviour.
4. Nesting depth is also inadequately evaluated by V(g). Something like this, where V(g) is low but nesting depth is high:
   
   

         if (...)
            if (...)
               if (...)
                  if (...)
   

   
   

Summary: The metric is very useful for the code complexity evaluation. Of course there is some imperfection in it, but if you know the limits it can be extremely helpful.

cyclomatic complexity, metrics

Posted by: volodya  11.5.2009 at 05:41   ‌ ‌   0 comments

WHAT'S NEW

A couple of words about TDD

Unit-test coding supposes to be one of the most significant methodological achievements of the industry, let’s say, for about last 15 years. The Internet is full of enthusiastic exclamations [1, ...

code coverage, code review, metrics, TDD, test first, test last

February 21, 2010

CodeExample plugin for Trac

The Trac plugin for code examples colouring. It supports three types of examples - a simple, a correct one and an incorrect. Further details see at

pygments, Trac

February 13, 2010

Metrics - LoC

This is going to be a small set of articles devoted to metrics. The first one is about LoC - Line of Code. I think that the first reaction on ...

LoC, metrics

May 11, 2009

Metric - Cyclomatic Complexity

There is a simple and logic explanation: the more “if”, “while”, “for”, and etc. in code the higher the complexity of the code improvement, management, understandability and refactoring. Cyclomatic (here ...

cyclomatic complexity, metrics

May 11, 2009

SESE vs SEME

SESE/SEME are terms of structural programming and were introduced at 80-s. Nothing new. However, experience shows that some programmers do not know about them till today. That’s why it makes ...

nesting depth, SEME, SESE

April 08, 2009