Knots : a measure of program complexity

Graduation date: 1980Most measures of program complexity gauge either textual or\ud control flow attributes of a program. A recent addition to the field\ud of complexity measures, the knot metric, is a function of both these\ud attributes. A knot measurement reflects the degree of control-flow\ud tangle in a program's listing. This thesis discusses and proves four\ud functional properties of the knot measure.\ud 1. Calculation of a program's knot content is fast with respect\ud to the number of branches in a program. A worst-case optimal algorithm\ud for computing knots is quadratic in time and linear in space.\ud 2. The complexity of a program can be reduced by rearranging\ud groups of statements in a manner that retains the program's function\ud yet lowers its knot content. The problem of finding an arrangement with\ud the fewest knots for any arrangement of a program is probably difficult\ud or NP-complete, but approximation methods are fast and often find\ud the minimum knot arrangement.\ud 3. A direct relationship exists between the types of knots in a\ud program text and the structuredness of that program. This leads to an\ud easily testable, sufficient condition for unstucturedness. Thus\ud unstuctured programs may be detected without graphically reducing the\ud control structure to structured programming conventions.\ud 4. An empirical investigation of a set of FORTRAN programs,\ud testing for their knot content, rearrangement characteristics, cyclomatic\ud number, and program length, demonstrates the practicality of the\ud knot measure. Most programs benefited from rearrangement, and a fast,\ud heuristic algorithm was effective in finding a program text ordering\ud with minimal knot content. Furthermore, the knot content of a program\ud is dissassociated from two other measures of complexity, cyclomatic\ud number and program length. Knots must measure some aspect of complexity\ud missed by those measures.\ud Overall, the knot metric is an effective, and efficient means\ud for detecting, reducing, and controlling some attributes of software\ud complexity