T. McCabe. Proceedings of the 2nd international conference on Software engineering, page 407--. Los Alamitos, CA, USA, IEEE Computer Society Press, (1976)ACM ID: 807712.
Abstract
This paper describes a graph-theoretic complexity measure and illustrates how it can be used to manage and control program complexity. The paper first explains how the graph theory concepts apply and gives an intuitive explanation of the graph concepts in programming terms. The control graphs of several actual FORTRAN programs are then presented to illustrate the correlation between intuitive complexity and the graph theoretic complexity. Several properties of the graph-theoretic complexity are then proved which show, for example, that complexity is independent of physical size (adding or subtracting functional statements leaves complexity unchanged) and complexity depends only on the decision structure of a program. The issue of using non-structured control flow is also discussed. A characterization of non-structured control graphs is given and a method of measuring the ``structuredness'' of a program is developed. The relationship between structure and reducibility is illustrated with several examples. The last section of the paper deals with a testing methodology used in conjunction with the complexity measure; a testing strategy is defined that dictates that a program can either admit of a certain minimal testing level or the program can be structurally reduced.
Proceedings of the 2nd international conference on Software engineering
year
1976
pages
407--
publisher
IEEE Computer Society Press
series
ICSE '76
location
San Francisco, California, United States
review
SUMMARY (Fritz) graph-theoretic approach looking a at a range of potential complexity measures including the widely used cyclometric complexity measure which evaluates the number of possible paths through a graph.
%0 Conference Paper
%1 mccabe_complexity_1976
%A McCabe, Thomas J
%B Proceedings of the 2nd international conference on Software engineering
%C Los Alamitos, CA, USA
%D 1976
%I IEEE Computer Society Press
%K basis; complexity measure; measures
%P 407--
%T A complexity measure
%X This paper describes a graph-theoretic complexity measure and illustrates how it can be used to manage and control program complexity. The paper first explains how the graph theory concepts apply and gives an intuitive explanation of the graph concepts in programming terms. The control graphs of several actual FORTRAN programs are then presented to illustrate the correlation between intuitive complexity and the graph theoretic complexity. Several properties of the graph-theoretic complexity are then proved which show, for example, that complexity is independent of physical size (adding or subtracting functional statements leaves complexity unchanged) and complexity depends only on the decision structure of a program. The issue of using non-structured control flow is also discussed. A characterization of non-structured control graphs is given and a method of measuring the ``structuredness'' of a program is developed. The relationship between structure and reducibility is illustrated with several examples. The last section of the paper deals with a testing methodology used in conjunction with the complexity measure; a testing strategy is defined that dictates that a program can either admit of a certain minimal testing level or the program can be structurally reduced.
@inproceedings{mccabe_complexity_1976,
abstract = {This paper describes a graph-theoretic complexity measure and illustrates how it can be used to manage and control program complexity. The paper first explains how the graph theory concepts apply and gives an intuitive explanation of the graph concepts in programming terms. The control graphs of several actual {FORTRAN} programs are then presented to illustrate the correlation between intuitive complexity and the graph theoretic complexity. Several properties of the graph-theoretic complexity are then proved which show, for example, that complexity is independent of physical size (adding or subtracting functional statements leaves complexity unchanged) and complexity depends only on the decision structure of a program. The issue of using non-structured control flow is also discussed. A characterization of non-structured control graphs is given and a method of measuring the ``structuredness'' of a program is developed. The relationship between structure and reducibility is illustrated with several examples. The last section of the paper deals with a testing methodology used in conjunction with the complexity measure; a testing strategy is defined that dictates that a program can either admit of a certain minimal testing level or the program can be structurally reduced.},
added-at = {2013-02-28T11:13:35.000+0100},
address = {Los Alamitos, {CA}, {USA}},
author = {{McCabe}, Thomas J},
biburl = {https://www.bibsonomy.org/bibtex/21c43d385f34989585dd0e76cac25e326/fritzsolms},
booktitle = {{Proceedings of the 2nd international conference on Software engineering}},
interhash = {d9620825178379d404bc75680dd08901},
intrahash = {1c43d385f34989585dd0e76cac25e326},
keywords = {basis; complexity measure; measures},
location = {San Francisco, California, United States},
note = {{ACM} {ID:} 807712},
pages = {407--},
publisher = {{IEEE} Computer Society Press},
review = {{SUMMARY} {(Fritz)} graph-theoretic approach looking a at a range of potential complexity measures including the widely used cyclometric complexity measure which evaluates the number of possible paths through a graph.},
series = {{{ICSE} '76}},
timestamp = {2013-02-28T11:13:57.000+0100},
title = {{A complexity measure}},
year = 1976
}