Advanced
We recommend reading Maintenance
of Operational Systems--An Overview before reading this
description; it offers a view of the life cycle of software from
development through reengineering. We also recommend concurrent
reading of Maintainability
Index Technique for Measuring Program Maintainability,
which illustrates a specific application of cyclomatic complexity to
quantify the maintainability of software. These descriptions provide
a framework for assessing the applicability of cyclomatic complexity
and other technologies to a specific environment.
Cyclomatic complexity
is the most widely used member of a class of
static software metrics. Cyclomatic complexity may
be considered a broad measure of soundness and
confidence for a program. Introduced by
Thomas McCabe in 1976, it measures the number of
linearly-independent paths through a program module. This measure
provides a single ordinal number that can be compared to the
complexity of other programs. Cyclomatic complexity is often referred
to simply as program complexity, or as
McCabe's complexity. It is often used
in concert with other software
metrics. As one of the more widely-accepted software metrics, it is
intended to be independent of language and language format
[McCabe
94].
Cyclomatic complexity has also been extended to encompass the
design and structural complexity
of a system [McCabe
89].
The cyclomatic complexity of a software module is calculated from
a connected graph of the module (that
shows the topology of control flow within the program):
Cyclomatic complexity (CC) = E - N + p
where E = the number of edges of the graph
N = the number of nodes of the graph
p = the number of connected components
To actually count these elements requires establishing a counting
convention (tools to count cyclomatic complexity contain these
conventions). The complexity number is generally considered to
provide a stronger measure of a program's structural complexity than
is provided by counting lines of code. Figure 6
is a connected graph of a simple program with a cyclomatic complexity
of seven. Nodes are the numbered locations, which correspond to logic
branch points; edges are the lines between the nodes.
Figure 6: Connected Graph of a Simple Program
A large number of programs have been measured, and ranges of
complexity have been established that help the software engineer
determine a program's inherent risk and stability. The resulting
calibrated measure can be used in development, maintenance, and
reengineering situations to develop estimates of risk, cost, or
program stability. Studies show a correlation between a program's
cyclomatic complexity and its error frequency. A low cyclomatic
complexity contributes to a program's understandability
and indicates it is amenable to modification at lower risk
than a more complex program. A module's cyclomatic complexity is also
a strong indicator of its testability
(see Test planning under Usage Considerations).
A common application of cyclomatic complexity is to compare it
against a set of threshold values. One such threshold set is in
Table 4:
Table 4: Cyclomatic Complexity
|
Cyclomatic
Complexity
|
Risk
Evaluation
|
|
1-10
|
a simple program, without much
risk
|
|
11-20
|
more complex, moderate risk
|
|
21-50
|
complex, high risk program
|
|
greater than 50
|
untestable program (very high
risk)
|
Cyclomatic complexity can be applied in several areas,
including
- Code development risk
analysis. While code is under development, it can be measured
for complexity to assess inherent risk or risk buildup.
- Change risk analysis in maintenance. Code complexity
tends to increase as it is maintained over time. By measuring the
complexity before and after a proposed change, this buildup can be
monitored and used to help decide how to minimize the risk of the
change.
- Test Planning.
Mathematical analysis has shown that cyclomatic complexity gives
the exact number of tests needed to test every decision point in a
program for each outcome. Thus, the analysis can be used for test
planning. An excessively complex module will require a prohibitive
number of test steps; that number can be reduced to a practical
size by breaking the module into smaller, less-complex
sub-modules.
- Reengineering. Cyclomatic
complexity analysis provides knowledge of the structure of the
operational code of a system. The risk involved in reengineering a
piece of code is related to its complexity. Therefore, cost and
risk analysis can benefit from proper application of such an
analysis.
Cyclomatic complexity can be calculated manually for small program
suites, but automated tools are preferable for most operational
environments. For automated graphing and complexity calculation, the
technology is language-sensitive; there must be a front-end source
parser for each language, with variants for dialectic
differences.
Cyclomatic complexity is usually only moderately sensitive to
program change. Other measures (see Complementary Technologies) may
be very sensitive. It is common to use several metrics together,
either as checks against each other or as part of a calculation set
(see Maintainability Index
Technique for Measuring Program Maintainability).
Cyclomatic complexity measurement, an established but evolving
technology, was introduced in 1976. Since that time it has been
applied to tens of millions of lines of code in both Department of
Defense (DoD) and commercial applications. The resulting base of
empirical knowledge has allowed software developers to calibrate
measurements of their own software and arrive at some understanding
of its complexity. Code graphing and complexity calculation tools are
available as part (or as options) of several commercial software
environments.
Cyclomatic complexity measurement tools are typically bundled
inside commercially-available CASE toolsets. It is usually one of
several metrics offered. Application of complexity measurements
requires a small amount of training. The fact that a code module has
high cyclomatic complexity does not, by itself, mean that it
represents excess risk, or that it can or should be redesigned to
make it simpler; more must be known about the specific
application.
Cyclomatic complexity is one measure of structural complexity.
Other metrics bring out other facets of complexity, including both
structural and computational complexity, as shown in Table
5.
Table 5: Other Facets of Complexity
|
Complexity
Measurement
|
Primary Measure
of
|
|
Halstead
Complexity Measures
|
Algorithmic complexity, measured by
counting operators and operands
|
|
Henry and
Kafura metrics
|
Coupling between modules (parameters,
global variables, calls)
|
|
Bowles
metrics
|
Module and system complexity; coupling
via parameters and global variables
|
|
Troy and
Zweben metrics
|
Modularity or coupling; complexity of
structure (maximum depth of structure chart); calls-to and
called-by
|
|
Ligier
metrics
|
Modularity of the structure
chart
|
Marciniak offers a more complete description of complexity
measures and the complexity factors they measure [Marciniak
94].
The following three metrics are specialized measures that are used
in specific situations:
- Essential
complexity. This measures how much unstructured logic exists
in a module (e.g., a loop with an exiting GOTO statement).
- The program in Figure 6 has no such
unstructured logic, so its essential complexity value is one.
- Design complexity.
This measures interaction between decision logic and subroutine or
function calls.
- The program in Figure 6 has a design
complexity value of 4, which is well within the range of
desirability.
- Data complexity. This
measures interaction between data references and decision
logic.
Other metrics that are "related" to Cyclomatic complexity in
general intent are also available in some CASE toolsets.
The metrics listed in Alternatives are
also complementary; each metric highlights a different facet of the
source code.
This technology is classified under the following categories.
Select a category for a list of related topics.
|
[Marciniak 94]
|
Marciniak, John J., ed. Encyclopedia
of Software Engineering, 131-165. New York, NY: John
Wiley & Sons, 1994.
|
|
[McCabe 89]
|
McCabe, Thomas J. & Butler, Charles
W. "Design Complexity Measurement and Testing."
Communications of the ACM 32, 12 (December 1989):
1415-1425.
|
|
[McCabe 94]
|
McCabe, Thomas J. & Watson, Arthur H.
"Software Complexity." Crosstalk, Journal of Defense
Software Engineering 7, 12 (December 1994):
5-9.
|
|
[Perry 88]
|
Perry, William E. A Structured
Approach to Systems Testing. Wellesley, MA: QED
Information Sciences, 1988.
|
|
[Watson 96]
|
Watson, Arthur H. & McCabe, Thomas J.
"Structured Testing: A Testing Methodology Using the
Cyclomatic Complexity Metric." [online]. Available
WWW,
<URL: http://hissa.ncsl.nist.gov/HHRFdata/Artifacts/ITLdoc/235/mccabe.html>
(1996).
|
Edmond VanDoren, Kaman Sciences, Colorado Springs
- 12 Jul 2000: Updated reference list
- 10 Jan 1997 (original)
