8 Measuring internal product attributes: structure

8.2 Control-flow structure, prime composition

We will demonstrate how the decomposition tree can be derived. The principle is to reduce primes in the graph to nodes. This is done recursively until no further primes can be found. Assume that our set of primes is S={P_n, D₀ - D₃}

As an example take the flowgraph below with nodes 0-9 and directed arcs (a b). The start node and the stop node are 0 and 9 respectively. The corresponding graph can be found in the folder.

(0 1) (1 2) (2 3) (3 4) (3 5) (4 2) (5 6) (6 5) (6 2) (2 7) (7 8) (7 9) (8 9)

We first assess that the set of arcs is a legal flowgraph. We then recognize the primes

      a   P2: (0 1)
      b   D3: (5 6) (6 5) (6 2)
      c   D0: (7 8) (7 9) (8 9)

After the decomposition we have:

(a 2) (2 3) (3 4) (3 b) (4 2) (b 2) (2 c)

Here we recognize the prime

      d   D1: (3 4) (3 b) (4 2) (b 2)

giving

(a 2) (2 d) (d 2) (2 c)

Here we recognize the prime

      e   D2: (2 d) (d 2) (2 c)

giving

(a e) (e c)

which is just a sequence, giving the final decomposition

P₂; D₂(D₁(D₃)); D₀