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)
.gif){kind=small}
