I am having a hard time to understand cyclomatic complexity. I went through some videos in youtube for this. I got negative value for cyclomatic complexity when I use this formula M = E – N + P. I found this formula as well E = E – N + 2P. I would be happy to get some brief description about cyclomatic complexity and why it can or cant be negative?
Can we have a negative cyclomatic complexity
cyclomatic-complexity
Related Solutions
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 branching paths theoretically possible in a single threaded application (that may include branches like "if x < 2 and x > 5 then
", but that should be caught by a good compiler as an unreachable code). 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). If you cannot cover a path with any possible test case - you found unreachable code (although you'll need to actually prove to yourself why it is unreachable, probably some nested x < 2 and x > 5
lurking somewhere).
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).
The first sample is just wrong. Not wrong in terms of the result, but the style is terrible. It is repetitive and error prone. The second sample is actually the step to do to obtain the readable, well written code. It's not a hack. It's just badly written code rewritten correctly. The fact that it reduces cyclomatic complexity doesn't surprise me, since there are less operations (at least in source; I'm pretty sure every decent compiler/interpreter will rewrite the first sample into the second one in all cases).
The third sample is more complicated to read for beginners who don't have enough practice with arrays, with filtering, with closures, etc. Personally, given the second sample, I would avoid the third one. Still, reduction in cyclomatic complexity is not surprising neither: you are migrating the complexity from your code to the filter
method.
Best Answer
In each connected component of a graph the number of edges must be at least greater or equal to the number of nodes minus 1 (that follows by induction, a component with one node does not need any edge, but whenever you add an additional node to a component, you need another edge to connect it with the previous ones: two nodes need at least one edge, three nodes at least two, and so on). So summing up the number of edges and nodes over P components, this leads to
and thus
Since P is >=1 for any graph with at least one node, finally
(except for the "empty" graph, where this is 0).