The cross cyclomatic complexity:
a bi-dimensional measure for program complexity on graphs

Maintainability is one of an essential quality in a software system; maintain a program drives evolution and the longevity of a system. Thus, to maintain a piece of software, firstly, we need to understand it. Understandability is the quality aspect that determines the capacity to understand code easily. However, how to measure if our source code is easy to understand? Despite more than 40 years of research for measuring understandability, there is not a consensus on what metrics we should use to evaluate the understandability [1].

As understandability is hard to measure, the software engineering community uses the McCabe’s Cyclomatic Complexity [2] as a proxy of understandability. McCabe’s Cyclomatic Complexity (MCC) measures the number of linearly independent control flow paths within the method, claiming explicitly that ”… it can be used to manage and control program complexity.” [2] There is a commonsense and intuition if a program has more branches, effort to understand it is more significant than a program with fewer branches. Then, if a method has a high CC, intuitively, it should be hard to understand.

Despite its value, MCC is not enough to describe the complexity of a problem. For example, idiomatic Java structures as blocks try/catch do not contribute to increase a program MCC. Moreover, a well-design program - using structure style - can have the same McCabe’s Cyclomatic Complexity than a equivalent program written using GOTOs or ”spaghetti” code [1]. Further, Jbara et al. found hundreds of methods with MCC higher than 100 ¹¹1Visser et al. propose good software system should have the majority of its methods with a MCC lower or equal 10. Then, a method with MCC of 100 should be considered as very complex., but they appreared to be well structured [3]. In fact, MCC does not reflect the complexity in all diversity of situation in a code, espcially in high-MCC programs [3].

In this position paper, we introduce the cross cyclomatic complexity (CCC), a new bi-dimensional complexity measure on graphs that combines the cyclomatic complexity and the weight of a minimum-weight cycle basis as a pair on the Cartesian plan to characterize program complexity using control flow graphs.

The remainder of this paper is organized as follows. In the Section 2, we discuss the characteristics and the main issues of MCC. In Section 3, the mathematical and graph background to define our metric. In Section 4, we define CCC metric, and Section 5, we present how to calculate CCC from 6 different cases. In the Section 6 we present related work to this study. Section 7 discusses the implications of CCC and opportunities of future work.

Cyclomatic Complexity (MCC) is a measure of program complexity that was proposed by Thomas McCabe in 1976. MCC measures the complexity of a program counting the number of linearly independent paths in a control flow graph [2]. Explicitly, McCabe’s measure goal is ”… provide a quantitative basis for modularization and allow us to identify software modules that will be difficult to test or maintain.” Indeed, MCC is a straightforward metric in terms of computation on which developers have an upper bound for the number of test cases required to obtain branch coverage of the code, and cyclomatic complexity could be applied to estimate the required effort for writing tests [4]. Also, MCC has strong mathematical support on graph theory, differently of arbitrary measures as Cognitive Complexity [5], for example. Moever, a recent study found that there is no strong linear correlation between MCC and SLOC of Java methods, so developers should not use only SLOC as a proxy of complexity measure. Thus, it is not a surprise that MCC is one of the most adopted program metrics partly because it is simple to calculate, aligned with developers intuition and there are no widely agreed alternatives [6].

Despite some advantages, MCC has very well-know limitations [6, 3, 4, 5, 1]. First, intuitively while loops are feels more complicate than ifs, as nested sequences of fors and if are more complicated than a switch/case structure. However, MCC can give the same value because it gives the same weight to all structures. We can observe this issue in the Listing 1. The method sumOfPrimes is intuitively more complex (lines 1 to 12) than the method getWords (lines 14 to 23). The first method has 2 for loops and a nested if inside of the second for, and a continue to jump outside of the loops (as GOTO). The second method has just a switch/case with 3 alternatives. Despite the intuitive differences in terms of complexity, both methods have the same MCC (MCC = 4).

Moreover, a method with high MCC yet would easy to understand, as a large state machine implemented using a switch/case structure. Thus, MCC may produce a false positive conclusion about the complexity of methods [1, 7]. Finally, Ajamiet al. [6] found that different code structures take different times to interpret, suggesting that the approach taken by MCC where all branching constructs are given the same weight, is overly simplistic.

Alternatives to MCC that use different weights to different control structures ware proposed (as Halstead metrics [8] or Cognitive Complexity [5], but they did not report empirical evidence supporting proposed weights [6]. Thus, Hummel [4] suggest that

The sad truth is that there probably is no single simple measurement that can express an abstract concept such as complexity in a single number. But this does not imply that we cannot measure and control complexity. It just has to be done with multiple metrics and checks that cover the various aspects of complexity.

Vinju and Godfrey [1] share a similar perspective. They propose a schematic diagram (Figure 1) to highlight and explain the factors for the correlation of high CC with failure. The diagram suggests the number of failures should not be determinate by a single aspect (number of branches). Thus, they highlighted the fact that there are several aspects to explain the failures.

All in all, MCC is a useful measure to help developers to find methods that are hard to test, but MCC is not enough. Thus, in Section 3, we present essential concepts before introducing our metric. After, we introduce our metric in Section 4.

We now recall some important concepts from graph theory and linear algebra necessary in order to define our metric. Additional examples and details of proofs can be found in [9]. Let $G=(V,E)$ be a connected graph without loops or multiple edges. If the edges of $G$ are non-ordered pairs (resp. ordered pairs), we say $G$ is a simple graph (resp. a simple digraph). A $uv$-path is a sequence of adjacent edges $P(u,v)=(e_{1},e_{2},\ldots,e_{n})$ such that $u$ is incident to $e_{1}$, $v$ is adjacent to $e_{n}$. A cycle $C(u,v)$ is a path where $u=v$. Also, $P(u,v)$ is simple if it does not contain repeated vertices, except for possibly $u$ and $v$. A spanning tree of $G$ is an acyclic subgraph $T$ such that $V_{T}=V_{G}$. Spanning trees are easily computed using Breadth-First Search or Depth-First Search algorithms. Note that in the case of digraphs, those algorithms return a spanning tree only if $G$ is strongly connected, that is if there exists a path between each pair of vertices. Otherwise, the resulting tree depends on the choice of a starting vertex. A weighted graph is a graph $G=(V,E)$ together with a function $\omega:E\longrightarrow\mathbb{R}$ where the image $\omega(e)$ is the edge-weight of e. By extension, the weight of a subset $E^{\prime}\subseteq E$ is the sum $\omega(E^{\prime})=\sum_{e\in E^{\prime}}\omega(e)$. The weight of a graph is the weight of its edge set. For example, if $\omega(e)=1$ for all $e\in E$, then $\omega(P)$ corresponds to the length of the path $P$. Figure 2 illustrates a weighted graph and one of its spanning tree.

Now, let $T$ be a spanning tree of $G$. The relative complement of $T$ in $G$ is the graph $G-T$ obtained from $G$ by deleting the edges of $T$. A fundamental cycle associated to $T$ is the cycle obtained by adding any edge of $G-T$ to $T$. Existence and unicity are guaranteed since $T$ is acyclic and spans $G$. The fundamental system of cycles of $T$ is the set of fundamental cycles associated to $T$. It is worth noting that in the case of simple digraphs, the cycles obtained are not oriented (see Figure 3 for an example). This will be further discussed in the next section.

As its name suggest, a fundamental system of cycles depends on the choice of $T$. The following discussion on the links between linear algebra and graph theory expands on this idea. Recall from linear algebra that $GF(2)$ (often noted $\mathbb{Z}/2\mathbb{Z}$) is the Galois Field on $2$ elements. That is, the set $\{0,1\}$ with addition and multiplication modulo $2$. Now, let $E_{1}$ and $E_{2}$ be subsets of $E$ for a given graph $G=(V,E)$. Define the ring sum $E_{1}\oplus E_{2}$ as the symmetric difference between $E_{1}$ and $E_{2}$, that is

If we denote by $W_{E}(G)$ the set of all subsets of $E_{G}$, then $W_{E}(G)$ together with $\oplus$ is a vector space over $GF(2)$. Finally, the cycle space of $G$ is the subspace of $W_{E}(G)$ consisting of $\emptyset$, all cycles of $G$ and all union of disjoint cycles. The next theorem establishes important results concerning basis of the cycle space.

The dimension of the cycle space is called the cycle rank of $G$ (or Betti number or cyclomatic number) and is denoted by $\nu(G)$. For example, the graph of Figure 2 has cycle rank $3$. The cycles $c_{1}=\langle a,e,b\rangle$, $c_{2}=\langle b,e,d\rangle$ and $c_{3}=\langle b,d,c\rangle$ form a basis and we have $c_{1}\oplus c_{2}=\langle a,e,d,b\rangle$.

By considering the control flow graph $G$ of a computer program and adding an extra virtual arc between the end and start node, one obtains the well-known cyclomatic complexity of the program, as first introduced by McCabe in [2].

We close this section by studying cycle basis for weighted graphs. Given a weighted graph $G=(V,E)$, the weight of a basis is the sum of the weight of all its cycles. A minimum-weight basis is a cycle basis such that its weight is smaller than any other basis. Figure 4 shows three possible cycle basis for a weigthed graph.

As stated in Section 2, MCC is an interesting metric to measure complexity of graphs but is clearly not sufficient. Indeed, many structural properties of $G$ are osculated by $\nu(G)$. Thus, we could augment cyclomatic complexity by considering, on one axis, $\nu(G)$, and on another, the weight of a minimum-weight cycle basis for $G$. Intuitively, it is an extension of the traditional MCC: Whereas $\nu(G)$ merely gives the number of independent cycles in $G$, $\omega_{min}(G)$ describes the internal structure of those cycles. Also, as is the case for the $\nu(G)$, the weight of a minimum-weight cycle basis is well-defined for any given graph. So, we define a new bi-dimensional complexity measure on graphs and study its applications to control flow graphs. Let $G=(V,E)$ be a weighted simple graph or digraph. Then, the cross cyclomatic complexity²²2Technically, since no cross product is involved, it should be called something along the line of ”cartesian cyclomatic complexity”. We chose the term ”cross” simply because we found it slightly less boring. of G is the tuple

where $\omega_{min}(G)$ is the weight of a minimum-weight cycle basis for $G$.

We now describe how $c_{\omega}$ can be applied to measure complexity of computer programs. A control flow graph is a simple digraph $G=(V,E)$ where all paths are oriented from a start vertex $s$ to an exit vertex $r$ together with a virtual arc $(r,s)$. Such graphs are always strongly connected, otherwise some part of the program would be inaccessible. It is worth noting that cycles in $G$ correspond to independent paths in $G-\{(r,s)\}$. We define the cross cyclomatic complexity of a computer program as $c_{\omega}$ with $\omega(e)=1$ for all $e\in G$. It is obvious from the definition that $\nu(G)=\#E-\#V+2$. The computation of $c\omega(G)$ is a little more involved and thus is studied in the next section. Finally, our metric offers some flexibility on how to treat independent paths in control flow graphs. Indeed, by assigning different weight to arcs, one could, for instance, penalize certain paths in the control flow graph. Remark that we insist on using both $\nu(G)$ and $\omega_{min}(G)$ in the expression for $c_{\omega}$ because, although $\omega_{min}$ comes from $\nu$, one cannot explicitly compute $\nu$ from the value of $\omega_{min}$.

Before closing this section, we derive some useful properties of $c\omega$. First, since $\omega(e)=1$ for all $e\in G$, $\omega_{min}(G)$ corresponds to the length of a minimal-length cycle basis. Also, $\omega_{min}(G)\geq\nu(G)$ since any cycle contains at least one edge. Further, the equality holds if and only if $G$ is an isolated vertex or a sequence of two instructions. Finally, we can plot the complexity in a halfplane as in Figure 5. Section 5 presents examples supporting this claim.

As mentioned in Section 3, computing a minimum-weight cycle basis is not trivial. Several algorithms have been proposed [10, 11].

We present here a $\mathcal{O}(\#E^{3}\#V)$ algorithm due to Horton [11] (Algorithm 1). The idea is to construct a $\mathcal{O}(\#E\#V)$-sized set of cycles guaranteed to contain a minimum-weight cycle basis. Then, elements of this set are greedily extracted and linear independence in checked using Gaussian elimination.

Line 5 can be computed using, for example, Dijkstra’s algorithm [12]. For Line 13, one can check check linear independence as follows: Given a cycle $c=\langle e_{1},e_{2},\ldots,e_{n}\rangle$, construct the $\#E$-dimensional incidence vector $[\delta_{e_{i}}]_{e_{i}\in E}$ where $\delta_{e_{i}}=1$ if and only if $e_{i}$ belongs to $c$ and $0$ otherwise. Then, linear independence of a set of cycle $\{c_{1},c_{2},\ldots,c_{k}\}$ is easily checked by constructing the matrix $[c_{1}\;c_{2}\;\cdots c_{k}]$ and using Gaussian elimination over $GF(2)$.

For small graphs, the cross cyclomatic complexity of the control structures of a program are rather easy to compute since there exists very few cycle basis (see Figure 6). For instance, the unique (and thus minimal-weight) cycle basis for the graph in Figure 6c is the set of two independent cycles $\langle s,a,r\rangle$ and $\langle s,b,r\rangle$ giving complexity $c_{min}(G)=(2,4)$

A more complex example is presented in Figure 4. Using Horton’s algorithm, one determine that the three lowest weight simple cycles are $c_{1}=\langle a,b,c\rangle$, $c_{2}=\langle a,e,d\rangle$ and $c_{3}=\langle a,d,c\rangle$ of weight $6$, $15$ and $15$ respectively. Since they are linearly independent, we find $\omega_{min}(G)=36$.

The associated matrix, with edge ordering $e_{1}$ through $e_{7}$, is

It is easily checked that this matrix reduces to

and thus $c_{1}$, $c_{2}$ and $c_{3}$ are linearly independent.

Despite being mathematically more accurate, the computation of $\omega_{min}(G)$ demands a significant effort. To simplify its computation, we now propose a simplified version of our complexity measure. The idea rises from the following simple observation: Given a graph $G$ and one of its cycle basis $\mathcal{B}$, then

From Section 3, one can deduced the following simple algorithm for computing an upper bound on $\omega_{min}$.

For example, the graph in Figure 4b gives the approximation $(3,45)$ whereas $c_{\omega}=(3,36)$. In a more tangible example, consider the control flow graph of a Java implementation of Bubble sort from Rosetta Code [13] (Figure 7). Our approximation for the given spanning tree (red arcs) gives $c_{\omega}(G)=(4,12)$. Next, we extract from McCabe’s original paper two more graphs for which he illustrated his measure (Figures 8 and 9). The values $c_{\omega}(G)$ of each graph is shown in Figure 10.

Analyzing Figure 10, we can easily compare the three graphs’ complexities. The three regions in the chart represent some properties of $c_{\omega}(G)$: No graph $G$ can have cross cyclomatic complexity located in the dark gray region of the plane since each cycle in a basis is of length at least $1$. The light gray region of the plane contains the complexity of valid graphs, but not non-trivial computer programs. Finally, the white region represents the $c_{\omega}(G)$ of valid non-trivial computer programs. In terms of design optimization, developers should aim to design programs with complexity near the line $\nu(G)=2\omega_{min}$. Following this criterion, we observe that the Bubble sort implementation as modelled by the graph in Figure 7 is considered optimized (near to the line), whereas the graph in Figure 9 could be be refactored.

Vinju et al. [1] investigated the relationship between the shape of control flow patterns observed in Java methods to their CC metric values, proposing the concept of abstract control flow patterns (CFPs) and compressed control flow patterns (CCFPs), which allow us to produce statistical evidence that the CC metric indeed does not adequately model the likely complexity of control flow in Java methods.

Jbara et al. [3] discuss there are no agreement on how to measure code complexity, favouring simple general purpose metrics, such as lines of code or MCC. They claims such metrics just count syntactic features, and ignore details of the code’s global structure, which may also have an effect on understandability. To address this issue, they suggested that code regularity—where the same structures are repeated time after time—may significantly reduce complexity.

Understanding a computer program is a time consuming and complex cognitive task. To control program complexity, researchers and practitioners have proposed single metrics to address this issue. However, those single metrics can not solve the problem yet. McCabe’s Cyclomatic Complexity is one of those metrics. The MCC abstracts the control flow graph as merely the analysis of branches and the fan-outs of its nodes. Doing so, it reduces the rich structure of the underlying graphs as a single number [1].

Thus, we claim for addressing the program complexity without throw out previous useful metrics (as MCC), we introduce the cross cyclomatic complexity (CCC), a new bi-dimensional complexity measure on graphs that combines the cyclomatic complexity and the weight of a minimum-weight cycle basis as a pair on the Cartesian plane to characterize program complexity using control flow graphs. Using solid mathematical and graph backgrounds, CCC provides a combined approach to address some of the issues on MCC without losing its advantages.

Hence, we claim that Cross Cyclomatic Complexity gives a criterion for highlight refactoring opportunities to control the complexity of computer programs. Namely, we suggest that one should aim to keep the complexity as close as possible to the line $\nu=\omega_{min}$. Further, CCC is agnostic of computer languages, and robust graph theorems support it. Also, CCC addresses distortions of MCC, which ignores the complexity associated with the size of programs or structures as long switch/case statements.

However, it is a positional work, lacking an in-depth empirical evaluation to observe how CCC can address complexity issues in program comprehension and support refactoring tasks. In the future, we will evaluate our metric to identify the diversity of scenarios to apply it and results on a large dataset of programs for different languages. Thus, this paper is the first step in order to provide a new way to see software metrics using graph properties.