Halstead Complexity Measures was developed to measure a program module's complexity directly from source code, with emphasis on  computational complexity.

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.

Metrics collection tools for C and C++ Source Code  offers access to a collection of static code analysis tools that compute various metrics defined on C and C++ source code. The metrics are primarily size and complexity of various types (lines of code, Halstead, McCabe, etc.).

NIST Special Publication 500-235  Structured Testing: A Testing Methodology Using the Cyclomatic Complexity Metric [PDF] by Arthur H. Watson and Thomas J. McCabe. [DjVu format]

Prepared under NIST Contract 43NANB517266

Abstract

The purpose of this document is to describe the structured testing methodology for software testing, also known as basis path testing. Based on the cyclomatic complexity measure of McCabe, structured testing uses the control flow structure of software to establish path coverage criteria. The resultant test sets provide more thorough testing than statement and branch coverage. Extensions of the fundamental structured testing techniques for integration testing and object-oriented systems are also presented. Several related software complexity metrics are described. Summaries of technical papers, case studies, and empirical results are presented in the appendices.

Keywords

Basis path testing, cyclomatic complexity, McCabe, object oriented, software development, software diagnostic, software metrics, software testing, structured testing.

Acknowledgments

The authors acknowledge the contributions by Patricia McQuaid to Appendix A of this report.

Disclaimer

Certain trade names and company names are mentioned in the text or identified. In no case does such identification imply recommendation or endorsement by the National Institute of Standards and Technology, nor does it imply that the products are necessarily the best available for the purpose.

Executive Summary

This document describes the structured testing methodology for software testing and related software complexity analysis techniques. The key requirement of structured testing is that all decision outcomes must be exercised independently during testing. The number of tests required for a software module is equal to the cyclomatic complexity of that module. The original structured testing document [NBS99] discusses cyclomatic complexity and the basic testing technique. This document gives an expanded and updated presentation of those topics, describes several new complexity measures and testing strategies, and presents the experience gained through the practical application of these techniques.

The software complexity measures described in this document are: cyclomatic complexity, module design complexity, integration complexity, object integration complexity, actual complexity, realizable complexity, essential complexity, and data complexity. The testing techniques are described for module testing, integration testing, and object-oriented testing.

A significant amount of practical advice is given concerning the application of these techniques. The use of complexity measurement to manage software reliability and maintainability is discussed, along with strategies to control complexity during maintenance. Methods to apply the testing techniques are also covered. Both manual techniques and the use of automated support are described.

Many detailed examples of the techniques are given, as well as summaries of technical papers and case studies. Experimental results are given showing that structured testing is superior to statement and branch coverage testing for detecting errors. The bibliography lists over 50 references to related information.

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).

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.

Authoritative sources such as:

http://hissa.nist.gov/HHRFdata/Artifacts/ITLdoc/235/title.htm

and:

http://www.sei.cmu.edu/str/descriptions/cyclomatic.html

give different formulas for calculating Cyclomatic Complexity.

The SEI gives this one:

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

NIST gives these:

V(G) = E - N + 1
V(G) = E - N + 2

The + 1 comes from the fact that you can not have zero branches. The difference between + 2 and + 1 has to do with a virtual path from the exit back to the entry point. + 2 appears to be the more common variation.

I have seen these variations as well:

V(G) = P + 1; which does give the same answer as E - N + 2 given in NIST version.

V(G) = E - N + 2p

In this case p is the number of connected components; the number of independent procedures if each has its own graph. Because most examples shown are for a single graph the term is usually simplified to 2 rather than the more correct (2 * 1).

While these types of metrics are important they should not be relied up on totally.

This example taken from Goodenough and Gerhart via Dunn in Software Defect Removal show why:

if( ((x + y + z)/3) == x )
    printf( "X, Y and Z are equal in value\n" );
else
    printf( "X, Y and Z are NOT equal in value\n" );

Neither counting lines of code/statements or branch testing show the flaw in the logic of the program(mer).