Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I've been studying cyclomatic complexity (McCabe) and reachability of software at uni recently. Today my lecturer said that there's no correlation between the two metrics, but is this really the case?

I'd think there would definitely be some correlation, as less complex programs (from the scant few we've looked at) seem to have 'better' results in terms of reachability.

Does anyone know of any attempt to look at the two metrics together, and if not, what would be a good place to find data on both complexity and reachability for a large(ish) number of programs?

share|improve this question
+1 Even if it was a homework question, since you're asking for references on studies or data it'd still be valid and on-topic. Good question. – Yannis Nov 17 '11 at 17:48
+1 for challenging what your prof has told you instead of just accepting it outright. – Neil N Nov 17 '11 at 18:35
That's a question that definitely is answerable: 1) large amounts of software is available on sourceforge and github 2) there is software to compute both metrics. Therefore the answer should be quantifiable and with known uncertainty, not just a general "no correlation". – Patrick Nov 17 '11 at 22:04
Well, if nothing else, cyclomatic complexity is calculable. Reachability is not, in the general case, due to the halting problem (though software exists that can get the vast majority of cases right). – Billy ONeal Nov 18 '11 at 2:19
Could you clarify (perhaps with a link) what exactly these metrics are? – omouse Nov 19 '11 at 4:09

I'm not familiar with reachability, but if it's a measure of code paths which cannot ever be executed, cyclomatic complexity should be sort of an upper bound of that.

share|improve this answer

I've been studying cyclomatic complexity (McCabe) and reachability of software at uni recently. Today my lecturer said that there's no correlation between the two metrics, but is this really the case?

Actually both yes and no.

First of all, just to remind you, McCabe metric for cyclomatic complexity is calculated on control flow graph where you abstract your source code to a directed graph with basic blocks or statements being the nodes and the transitions between them (either by normal control flow downward or in case of conditioned jumps and loops) being edges. The cyclomatic complexity here can be roughly (if you consider your whole program to have no isolated code, i.e. your graph is connected) seen as the difference between the number of edges and number of nodes.

CC = E - N

Reachability problem is a common problem in graph theory that can be expressed in the way: given two nodes A and B, is the node B reachable from node A, i.e. can one reach B starting from A and following the edges of the graph in correct direction? So, it is again the metric that is applicable to the control flow graph and not on the code.

There are several ways to apply this problem to the control flow graph. One way is so-called "variable reachability analysis", meaning that for the given variable the analysis determines whether its value is still available at certain program point (this technique is also called slicing in software analysis). I also found only some articles that use this term (and generally the reachability problem) for multi-threaded applications.

Basically one can see some sort of correlation between the CC and reachability: with the increase of CC the ratio of edges over nodes also increases and even in case of a directed graph where the direction of the edge is also important, one can speculate that increasing the number of edges eventually leads to the increase of available paths in the graph and thus to increases reachability either via direct or indirect connections between the nodes. So, the answer is Yes here.

On the other side, the notion of reachability in multi-threaded environment requires the analysis of so-called supergraph -- and this is not so trivial. Increase of CC (called here "synchronisation complexity") might lead to the higher probability of deadlocking in software and thereby decrease the reachability of certain nodes / code segments. Therefore "No" is a valid answer here too.

share|improve this answer

There may be some statistics on this but I would say there's no correlation because one does not depend on the other and there is also choice in the design of a software system such that you can eliminate this.

In terms of real world data, there may be a strong correlation but that could be due to badly designed software systems that do not eliminate this correlation. It could be an accidental correlation because of lack of knowledge of graph theory.

share|improve this answer
One depending on the other is causation, not correlation. – JeffO Nov 26 '11 at 21:15

Your Answer


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.