Path: utzoo!mnetor!uunet!mcvax!ukc!stc!datlog!dlhpedg!cl
From: cl@dlhpedg.co.uk (Charles Lambert)
Newsgroups: comp.software-eng
Subject: Re: program complexity metrics
Message-ID: <344@dlhpedg.co.uk>
Date: 18 Dec 87 11:12:47 GMT
References: <561@ndsuvax.UUCP> <3850002@wdl1.UUCP>
Sender: news@dlhpedg.co.uk
Reply-To: cl@.co.uk (Charles Lambert)
Organization: FSG@Data Logic Ltd, Queens House, Greenhill Way, Harrow, London.
Lines: 73

In article <3850002@wdl1.UUCP> rion@wdl1.UUCP (Rion Cassidy) writes:
>
>However, except for what the name implies, I really don't know what
>program complexity metrics are and therefore can't answer.  How about
>a brief overview?  Anybody?
>

As the name implies,  they are techniques to measure the complexity of
a (proposed) programming task; they estimate how laborious and difficult
it will be to implement.  From an analysis of complexity, you can predict
several things (according to the advocates),  for instance:
    (i)   how much the implementation will cost (in terms of effort);
    (ii)  the number of errors you can expect;
    (iii) the number and type of test cases you will need;
    (iv)  how costly the system will be to maintain.

Ideally,  you want to make these predictions as early in the development
as possible;  however,  my studies to date show that the current techniques
address the detailed Module Design best, the System Design less well and
the Functional Specification not at all.

In their excellent survey of software development techniques [1],  Birrel
and Ould describe complexity measurements at the stages of System Design
and System Production (the latter being Module Design and Coding).  For
System Design,  they describe only one measurement that I would truly
call a complexity measurement: the "interconnectivity metric" of Kafura
and Henry [2].   In contrast,  three measurements are described for the
Module Design:  "McCabe's (cyclomatic) number [3]", "Halstead's E [4]" and
"control entropy".   I quote, without permission.

    On interconnectivity:
    "[Kafura and Henry] describe it as follows. 'The first [phase]
     involves generating a set of relations indicating the flow of
     information through input parameters, output parameters, returned-
     values functions and data structures. The second phase generates
     an information-flow structure from these relations.  The third
     phase analyses the information-flow structure to determine the
     derived calls, the local flows and the global flows'.  A special
     notation is used to record the result of the first analysis so
     that automated tools can be used for the second and third phases.
     The analysis can be carried out on any level of design or
     production provided a precise enough description is available..."

    On cyclomatic numbers:
    "McCabe (1976) introduced the cyclomatic number of the control flow
     graph of a program as a measure of program complexity.  The
     cyclomatic number of a graph counts the number of linearly
     independent cycles in the graph and thus gives the number of basic
     paths through the program.....

    "Alternatively it can be shown that for structured programs the
     cyclomatic number can be obtained by adding one to the number of
     predicates in the program segment...

    "The cyclomatic number has been shown to correlate quite well with
     the number of errors found in the code and the programming time.
     It can also clearly be used as an indicator of the number of test
     cases that should be applied to a module to test all basic paths."

References
----------
[1] Birrell, N.D. and Ould, M.A; A Practical Handbook for Software Development.
    Cambridge University Press. 1985.  ISBN 0 521 25462 0

[2] Kafura, D. and Henry, S; "Software quality metrics based on
    interconnectivity" in the Journal of Systems and Software, 2, 121-131.
    1981.

[3] McCabe, T.J; "A complexity measure" in IEEE Transactions on Software
    Engineering, SE-2, 308-320. 1976.

[4] Halstead, M; Elements of Software Science. Elsevier North-Holland,
    New York. 1977.