A2.5 Control Flowgraph Metrics

A control flowgraph of a program is constructed from a directed graph representation of the program that can be defined as follows:

A directed graph, G = (N, E, s, t) , consists of a set of nodes N; a set of edges E; a distinguished node s, the start node; and a distinguished node t, the exit node. An edge is an ordered pair of nodes (a, b).
The in-degree I(a) of node a is the number of entering edges to a.
The out-degree O(a) of node a is the number of exiting edges from a.

The flowgraph representation of a program, F = (E', N', s, t) is a directed graph that satisfies the following properties:

There is a unique start node s such that I(s) = 0.
There is a unique exit node t such that O(t) = 0.

All other nodes are members of exactly one of the following three categories:

Processing node. It has one entering edge and one exiting edge. They represent processing node a, I(a) = 1 and O(a) = 1.
Predicate node. It represents a decision point in the program as a result of if statements, case statements, or any other statement that will cause an alteration in the control flow. For a predicate node a, I(a) ≥ 1 and (a) > 1.
Receiving node. It represents a point in the program where two or more control flows join, for example, at the end of a while loop. For a receiving node a, I(a) > 1 and O(a) = 1.

If (a, b) is an edge from node a to node b, then node a is an immediate predecessor of node b and node b is an immediate successor of node a. The set of all immediate predecessors for node a is denoted as IP(a). The set of all immediate successors for node b is denoted as IS(b). No node can have itself as a successor. That is, a cannot be a member of IS(a). In addition, no processing node can have a processing node as a successor node. All successor nodes to a processing node must be either predicate nodes or receiving nodes. Similarly, no processing node can have a processing node as its predecessor.

From this control flowgraph representation, two essential control flow primitive metrics emerge:

Number of nodes
Number of edges

A path P in a flowgraph F is a sequence of edges where all a_i (i = 1,...,N) are elements of N'. P is a path from node a₁ to node a_n. An execution path in F is any path P from s to t.

The average length of the paths measured in numbers of edges constitutes a second program characteristic. A program that has a large number of relatively short control-flow paths differs greatly in terms of testing or maintenance from one having a few relatively long control-flow paths.

Whether or not a node lies on a cycle relates to the concept of connectedness defined as follows:

A flowgraph F is weakly connected if any two nodes a and b are connected by a sequence of edges.
A flowgraph F is strongly connected if each node lies on a cycle.

Any flowgraph might potentially contain weakly connected subsets of nodes that are flowgraphs in their own right. To examine this potential hierarchical structure of the flowgraph representation, the notion of a sub-flowgraph is essential.

A sub-flowgraph F' = (N", E", s', t') of a flowgraph F= (N', E' s, t) is a flowgraph if the out-degree of every node in F' is the same as the out-degree of the corresponding node in F with the exception of the nodes s' and t'. All nodes in the sub-flowgraph are weakly connected only to nodes in N".

A sub-flowgraph of F is a sub-flowgraph with the property that the cardinality of N" > 2 and F' ≠ F. That is, the sub-flowgraph must contain more nodes than the start and exit nodes and cannot be the same flowgraph.

A flowgraph is an irreducible flowgraph if it contains no proper sub-flowgraph. A flowgraph is a prime flowgraph if it contains no proper sub-flowgraph for which the property I(s') = 1 holds. A prime flowgraph cannot be built by sequencing or nesting other flowgraphs, and it must contain a single entrance and a single exit structure. The primes are the primitive building blocks of a program control flow.

In the C language, the primes relate to the basic control structures shown in Exhibit 8.

Exhibit 8: C Language and Basic Control Structures

click to expand

A2.5.1 Nodes

The node count represents the number of nodes in the flowgraph representation of the program module. The minimum number of nodes that a module can have is three: the start node, a single processing node, and an exit node.

If a module has more than one exit point, then a virtual receiving node must be created to meet the condition that there be but one exit node. This virtual node helps to keep the consistency in the flowgraph by ensuring that there is a unique exit node.

The return statement should be considered a processing node (or as a part of a processing node) because it sets the value of what is been returned to the caller function. The processing node must be followed by an edge to the virtual receiving node if multiple return statements are present.

A2.5.2 Edges

The Edge metric represents the number of edges in the control flow representation of the program module. The minimum number of edges that a module can have is two, in that there must be at least one processing node.

A2.5.3 Paths

A path through a flowgraph is an ordered set of edges (s, ... , t) that begins on the starting node s and ends on the terminal node t. A path can contain one or more cycles. Each distinct cycle cannot occur more than once in sequence. That is, the subpath (a, b, c, a) is a legal subpath but the subpath (a, b, c, a, b, c, a) is not permitted.

The total path set of a node a is the set of all paths (s, a) that go from the start node to node a itself. The cardinality of the set of paths of node a is equal to the total path count of the node a. Each node singles out a distinct number of paths to the node that begin at the starting node and end with the node itself. The path count of a node is the number of such paths.

The number of distinct execution paths, Paths, is computed by systematically decomposing the control flowgraph representation of a program module into constituent prime flowgraphs, a process that systematically eliminates all predicate nodes. The Path metric will tally the number of paths that begin at node s and end at node t.

Cycles are permitted in paths. For each cyclical structure, exactly two paths are counted: one that includes the code in the cycle and one that does not. In this sense, each cycle contributes a minimum of two paths to the total path count.

A2.5.4 Maximum Path Length

This metric represents the number of edges in the longest path. From the set of available paths for a module, all the paths are evaluated by counting the number of edges in each of them. The greatest value is assigned to this metric. This metric gives an estimate of the maximum path flow complexity that might be obtained when running a module.

A2.5.5 Average Path Length

The average path length is the mean of the length of all paths in the control-flow graph. If the average path is not an integer, it is rounded:

[x.0, x.499] average path length = x
[x.500, x.999] average path length = x + 1

A2.5.6 Cycles

A cycle is a collection of strongly connected nodes. From any node in the cycle to any other, there is a path of length one or more, wholly within the cycle. This collection of nodes has a unique entry node. This entry node dominates all nodes in the cycle. A cycle that contains no other cycles is called an inner cycle.

The cycles metric counts the number of cycles in the control flowgraph. There are two different types of cycles:

Iterative loops are those that result from the use of the for, while, and do/while structures.
Control loops are created by the backward reference of instructions. If the label object of a goto is above the goto and there is a possible path from the label to the goto statement, it causes a cycle. Thus, each occurrence of such a cycle increases the count of the cycle metric.