4

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?

  • How did you get more nodes than edges? – Ewan Jun 8 '16 at 17:36
  • @Ewan: the control flow graph of print "Hello world" has one node and zero edges. – Doc Brown Jun 9 '16 at 11:27
  • @doc yeah i guess, but i cant imagine calculating the complexity of that function and being confused. wondering what graph the OP used to get their negative value – Ewan Jun 9 '16 at 12:59
  • @Ewan: I am pretty sure the OP must have made an error in his calculation (since the proof I gave below works for arbitrary graphs, not just control flow graphs). Lets see if we get a response from him. – Doc Brown Jun 9 '16 at 13:27
7

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

E >= N - P,

and thus

E - N + P >=0

Since P is >=1 for any graph with at least one node, finally

E - N + 2P > 0

(except for the "empty" graph, where this is 0).

3

No cyclomatic complexity can never be negative. It always has to be at least one. Cyclomatic complexity is simply a measure of how many different paths a piece of code or an entire program has that execution could potentially follow. Therefore it always has to be at least one for executable code. E = E - N + 2P is the correct way to calculate it by hand, but outside of exercises for a class automated tools can handle this for you so calculating this isn't that important.

Cyclomatic complexity is a way to get number to compare parts of your code to identify areas where refactoring would bring a bigger potential benefit, its really only useful to compare the cyclomatic complexity of different functions within the same application.

1

Cyclomatic complexity is always greater than or equal to one. The reason for this is easier to see if you step away from the formulae that can be used to calculate cyclomatic complexy, and it look at what it actually does.

Cyclomatic complexity (as originally written) works on control flow graphs where the exit node has an additional edge connecting back to the entrance node. For such a graph, it counts the number of independent cycles that exist in the graph (hence the name). The simplest possible graph, a single node which is both the entrance and exit of the function, has an edge connecting it to itself, and hence has 1 cycle. Anything added to the graph can only increase this number.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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