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.
