A large share of the resources are used to find errors, debug, and retest; thus, an associated measure of complexity is the number of software errors.

Items to consider under resources are:

- time and memory space;
- man-hours to supervise, comprehend, design, code, test, maintain and change software; number of interfaces;
- scope of support software, e.g. assemblers, interpreters, compilers, operating systems, maintenance program editors, debuggers, and other utilities;
- the amount of reused code modules;
- travel expenses;
- secretarial and technical publications support;
- overheads relating to support of personnel and system hardware.

Measures of complexity are useful to:

- Rank competitive designs and give a "distance" between rankings.
- Rank difficulty of various modules in order to assign personnel.
- Judge whether subdivision of a module is necessary.
- Measure progress and quality during development.

Statistical approach, used by Halstead, looked at total number of operators and operands, and related this to man-hours. This measure was rooted in information theory -- Zipf's laws of natural languages, Shannon's information theory.

n(r) /n . r = constant (c)

or n(r) = c n / r

n is sample size

e.g. X-set elements, M-set mapping rules

- Positions of pieces on a chess board
- Rules for moving and capturing pieces

- A group of relatives
- Parenthood relationships

- Units of electrical appratus
- Wires connecting the units

- Instructions in a computer program
- Rules of syntax a sequence which govern the processing of the instructions

**A directed graph and a "regular" graph**

- Two
**arcs**are**adjacent**if they are distinct and have a vertex in common. - Two
**vertices**are**adjacent**if they are distinct and there exists an arc between them. - A
**path**is a sequence of arcs of a graph such that the terminal vertex of each arc conicides with the initial vertex of the succeeding arc. - A path is
**simple**if it does not use the same arc twice, and composite otherwise.

e.g. 1, 3, 7 or a, b, x, d is a simple path 1, 3, 4, 4, 7 or a, b, x, x, d is composite - A path is
**elementary**if it does not meet the same vertex more than once.

e.g. simple: (1, 3, 7), (1, 3, 4, 7), (1, 3, 6, 5, 7) elementary: (1, 3, 7) only - A
**circuit**is a finite path where the initial and terminal nodes coincide. - An
**elementary circuit**is a circuit in which no vertex is traversed more than once. - A
**simple circuit**is a circuit in which no arc is used more than once. - The
**length**of a**path**is the number of arcs in the sequence. - The
**length**of a**circuit**is the length of its path. - A
**digraph**is complete if every distinct node pair is connected in at least one direction, e.g. node e is not connected, so graph is not complete. - A digraph is
**strongly connected**if there is a path joining every pair of vertices in the digraph, e.g. not strongly connected as can not go d to c.

In linear algebra, a set of vectors x(1), x(2), ..., x(n) is linearly dependent if there exists a set of numbers not all zero s.t. a(1)x(1) + a(2)x(2) + ... + a(n)x(n ) = 0. If no such set of numbers exists then the set of vectors are linearly independent.

Any system of n linearly independent vectors e(1), e(2), ..., e(n) forms a basis in n-dimensional vector space.

In graph theory, if the concept of a vector is associated with each circuit or cycle, then there are analogous concepts of independent cycles and a cycle basis.

where there are m arcs

n vertices

and p separate components

e.g. m=9, n=5, p=1, v(G)=5

There are various other methods for calculating the cyclomatic number of a graph.

e.g. digraph of program flowchart given:

nodes a and k correspond to start and stop nodes

node c corresponds to GET A

node i corresponds to L = L + 1

The cycle (loop) is composed of arcs 4, 5, 6, 7, 8

IF THEN ELSE appears as 5, 6 and 9, 10.

The ** cyclomatic number** of the digraph gives a

A graph is constructed with a single start node and a single stop node. If there is an unreachable node, that represents unreachable code or coding error which must be corrected.

In general the graph is not strongly connected, so form a loop round the entire program (phantom arc).

e.g. v(G)= 13 - 11 + 1 = 3

number of arcs m = 13

number of nodes (vertices) n = 11

separate parts p = 1

**Results**

McCabe says that v(G) is a good measure of complexity and all modules
should have v(G)__<__10. This replaces the general rule of thumb that a
module should be one page of code (50 to 60 lines). He has shown that programs
with a large v(G) are error-prone.

Much theory exists in this area, but as yet has not been applied on a wide scale.

Practical Software Engineering, Department of Computer Science