8 Measuring internal product attributes: structure

8.1 Types of structural measures

We can think of structure as having at least three parts:

1. Control flow: addresses the sequence in which instructions are executed in a program. This aspect of structure reflects the iterative and looping nature of programs.
2. Data flow: follows the trail of a data item as it is created or handled by a program. Data-flow measures depict the behaviour of the data as it interacts with the program.
3. Data structure: is the organization of data itself, independent of the program. The structure of data tells us a great deal about the difficulty in writing programs to handle the data.

8.2 Control-flow structure

A great deal of software metrics work has been devoted to measuring the control flow structure of imperative language programs or algorthms. The control flow measures are usually modeled with directed graphs, where each node (or point) corresponds to a program statement, and each arc (or directed edge) indicates the flow of control from one statement to another. Some further notations:

• in-degree of a node: number of arcs incident to the node
• out-degree of node: number of arcs leaving the node
• procedure node: a node with out-degree 1
• predicate node: a node with out-degree >1
• path: a sequence of consecutive arcs
• simple path: a sequence of consecutive non-repeating arcs
• flowgraph: a directed graph in which the start node is where the execution starts, the stop node is an empty node that has out-degree 0, and all other nodes are on some path from the start node to the stop node. The start node and the stop node are encircled in the flowgraph.
• F(A) : flowgraph of program A

See Figure 8.1 for an example and Figure 8.2 and 8.3 for flowgraphs of some "prime" program control constructs, the most common being P_n: sequence, D₀: if-then, D₁: if-then-else, C_n: case, D₂: while-do, and D₃: repeat-until.