Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I've recently come across Cyclomatic Complexity and I'd like to try to understand it better.

What are some practical coding examples of the different factors that go into calculating the complexity? Specifically, for the Wikipedia equation of M = E − N + 2P, I want to better understand what each of the following terms means:

  • E = the number of edges of the graph
  • N = the number of nodes of the graph
  • P = the number of connected components

I suspect that either E or N may be the number of decision points (if, else if, for, foreach, etc) in a block of code, but I'm not quite sure which is which or what the other signifies. I'm also guessing that P refers to function calls and class instantiations, but there isn't a clear definition given that I can see. If someone could shed a little more light with some clear code examples of each, it would help.

As a follow-up, does the Cyclomatic Complexity directly correlate to the number of unit tests needed for 100% path coverage? As an example, does a method with a complexity of 4 indicate that 4 unit tests are needed to cover that method?

Finally, do regular expressions affect Cyclomatic Complexity, and if so, how?

share|improve this question
add comment

2 Answers

up vote 2 down vote accepted

Regarding the formula: nodes represent states, edges represent state changes. In every program, statements bring changes in the program state. Each consecutive statement is represented by an edge, and the state of the program after (or before...) the execution of the statement is the node.

If you have a branching statement (if for example) - then you have two nodes coming out, because the state can change in two ways.

Another way to calculate the Cyclomatic Complexity Number (CCN) is to calculate how many "regions" in the execution graph you have (where "independent region" is a circle that doesn't contain other circles). In this case the CCN will be the number of independent regions plus 1 (which would be exactly the same number as the previous formula gives you).

The CCN is used for branching coverage, or path coverage, which is the same. The CCN equals to the number of different execution paths possible in a single threaded application. You have to have at least that number of different test cases (can be more since some test cases might be repeating paths covered by previous ones, but not less assuming each case covers a single path).

As to regular expressions - of course they affect, as any other piece of code. However, the CCN of the regex construct is probably too high to cover in a single unit test, and you can assume that the regex engine has been tested, and ignore the expressions' branching potential for your testing needs (unless you're testing your regex engine, of course).

share|improve this answer
    
+1: Actually, you must trust that the regex engine has been tested. If you don't trust it, get one that you do trust. –  S.Lott Sep 27 '11 at 10:05
add comment

As a follow-up, does the Cyclomatic Complexity directly correlate to the number of unit tests needed for 100% path coverage?

Yes, basically. It's also a good idea to make use of cyclomatic complexity as an indicator of when to refactor. In my experience, testability and reusability greatly increase for lower CC (although you should be practical - don't over-refactor, and some methods will have high CC due to their nature - it doesn't always make sense to try and force it lower).

Finally, do regular expressions affect Cyclomatic Complexity, and if so, how?

Yes, if you want to be exact, although most code analysis tools don't seem to take them into consideration in that way. Regular expressions are just finite state machines, so I'm guessing their CC could be calculated from the FSM graph, but it would be quite a large number.

share|improve this answer
    
+1 - I'm guessing that calculating the CC for RegExes isn't a fun task. –  VirtuosiMedia Sep 27 '11 at 7:05
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.