10 Essential Complexity

In addition to the quantity of decision logic as measured by cyclomatic complexity, the quality of that logic is also a significant factor in software development [PRESSMAN]. Structured programming [DAHL] avoids unmaintainable "spaghetti code" by restricting the usage of control structures to those that are easily analyzed and decomposed. Most programming languages allow unstructured logic, and few real programs consist entirely of perfectly structured code. The essential complexity metric described in this section quantifies the extent to which software is unstructured, providing a continuous range of structural quality assessments applicable to all software rather than the "all or nothing" approach of pure structured programming.

10.1 Structured programming and maintainability

The primitive operations of structured programming, shown in Figure 10-1, are sequence, selection, and iteration.

Figure 10-1. Structured programming primitives.

The fundamental strength of structured programming is that the primitive operations give a natural decomposition of arbitrarily complex structures. This decomposition facilitates modularization of software because each primitive construct appears as a component with one entry point and one exit point. The decomposition also allows a "divide and conquer" strategy to be used to understand and maintain complex software even when the software is not physically decomposed. Unstructured code must typically be understood and maintained as a single unit, which can be impractical even for programs of moderate cyclomatic complexity.

Since poor module structure makes software harder to understand, it also impedes testing. First, as discussed in section 5.3, poorly understood software requires extra testing to gain confidence. Second, it requires more effort to construct each specific test case for poorly understood code, since the connection between input data and the details of the implementation tends to be unclear. Finally, poorly understood code is both error-prone and hard to debug, so an iterative process of testing and error correction may be required.

10.2 Definition of essential complexity, ev(G)

The essential complexity, ev(G) [MCCABE1], of a module is calculated by first removing structured programming primitives from the module's control flow graph until the graph cannot be reduced any further, and then calculating the cyclomatic complexity of the reduced graph. An immediate consequence is that 1 <= ev(G) <= v(G). A somewhat less obvious consequence, which can help when evaluating complexity analysis tools, is that ev(G) can never be equal to 2. This is because after all sequential nodes have been eliminated, the only graphs with v(G) equal to 2 are structured programming primitives, which can then be removed to get an ev(G) of 1. The reduction proceeds from the deepest level of nesting outward, which means that a primitive construct can be removed only when no other constructs are nested within it.

It is important to note that the structured programming primitives used in the calculation of essential complexity are based on the control flow graph rather than the source code text. This allows the essential complexity metric to measure structural quality independently of the syntax of any particular programming language. For example, a bottom-test loop is a structured primitive whether it is written using a high-level looping construct or an assembly language conditional branch. Programming language constructs such as the "goto" statement only increase essential complexity when they are actually used to implement poorly structured logic, not just because they could be used that way. Of course, any program that is written entirely with high-level "structured programming" language constructs will have a perfectly structured control flow graph and therefore have an essential complexity of 1.

The essential complexity calculation process is similar to the calculation of module design complexity as described in section 7.4 (and in fact was developed first), but there are two key differences. First, primitive constructs can be removed whether or not they involve module calls when calculating essential complexity. Second, only entire primitive constructs can be removed when calculating essential complexity. The module design complexity reduction rules allow removing partial decision constructs when there are no module calls involved, which can eliminate unstructured code. Thus, despite the similarity between the two calculation methods, there is no mathematical relationship between the two metrics.

10.3 Examples of essential complexity

Figure 10-2 illustrates the calculation of essential complexity from a control flow graph. The original graph has a cyclomatic complexity of 8. First the innermost primitive constructs are removed (a bottom-test loop and two decisions). Then, the new innermost primitive construct is removed (a top-test loop), after which no further reductions are possible. The cyclomatic complexity of the final reduced graph is 4, so the essential complexity of the original graph is also 4.

Figure 10-2. Essential complexity calculation example.

Figure 10-3 shows the source code for a module with cyclomatic complexity 9 and essential complexity 4. The essential complexity is caused by the conditional break out of the loop. Figure 10-4 shows the essential control flow graph for the same module, in which the unstructured logic is superimposed on the entire flow graph structure. This representation identifies the control structures that contribute to essential complexity.

Figure 10-3. Source code for module with v(G) = 9 and ev(G) = 4.

Figure 10-4. Essential graph for module with v(G) = 9 and ev(G) = 4.

[Title Page] [TOC] [Prev] [Next] [End]