# Is there a correlation between complexity and reachability?

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?

-
+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

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.

-
One depending on the other is causation, not correlation. – JeffO Nov 26 '11 at 21:15

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.

-

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.

-