| dc.description.abstract | The purpose of this thesis involved the implementation, validation, complexity analysis, and comparison of two graph decomposition approaches. The two approaches are Forman's algorithm for prime decomposition of a program flow graph, and Cunningham's approach for decomposing a program digraph into graph-oriented components. To validate the two implementations, each was tested with six inputs. Comparison of these two approaches was based on these dimensions time and space complexities, composability, repeated decomposition, and uniqueness. Forman's algorithm appears to have four advantages over Cunningham's algorithm 1. the algorithm overhead (i.e, the time and space complexities) was lower in Forman's algorithm; 2. Forman's algorithm yields a unique set of decomposed units, whereas Cunningham's does not; 3. in Forman's algorithm, reconstructing the original graph from the decomposed prime graphs results in the original graph that was decomposed, whereas in Cunningham's algorithm, the attempt at the reconstruction of the original graph from the decomposed parts does not always yield the graph that was decomposed; 4 Forman's approach can be used to decompose a graph until it is irreducible (all its part are primes), whereas in Cunningham's algorithm, the algorithm decomposes the graph only once even if it is still decomposable Thus, Forman's approach could be recommended as a program flow graph decomposition algorithm. Implementation of the decomposition techniques could help in better software comprehension and can be used in the development of some software reusability tools. | |
