Fenton and Whitty has shown that we can associate with each flowgraph a unique decomposition tree to describe how the flowgraph is built by sequencing and nesting primes, for examples see Figures 8.8 and 8.9 and the example.
Let S be an arbitrary set of primes. We say that a measure m is hierarchical if it can be defined on the set of S-graphs by specifying:
- m(F) for each F in S (we call this rule M1)
- the sequencing function(s) (M2)
- the nesting functions hF for each F in S (M3)
A hierarchical measure can thus easily be computed given the composition tree of a flowgraph (program). In Example 8.13 a hierarchical length measure is defined.
McCabe's cyclomatic complexity measure is computed as:v(F) = e - n + 2 where e is the number of edges and n is the number of nodes in F. It can also be written in the following form:
v(F) = 1 + d where d is the number of predicates in F. The measure v can also be defined as a hierarchical measure.
McCabe also proposed a measure to capture the overall level of structuredness in a program. The measure called essential complexity is defined as
ev(F) = v(F) - m where m is the number of number of D-structured subflowgraphs (D0 - D3) of F.