Graph theoretic program complexity measures

Technical Report

Public Deposited

Citeable URL: https://ir.library.oregonstate.edu/concern/technical_reports/zs25xh88b

Descriptions

Attribute Name	Values
Creator	Cook, Curtis R.
Abstract	Recently several simply computed graph theoretic measures of computer program complexity, testing and unstructuredness have been proposed. Most of them are based on a static analysis of the program graph. One of the best known and most widely accepted is the cyclomatic number. Another is the number of knots, or crossings of flow of control arrows in the program text We show that the number of knots is equal to the number of edges in the-overlap graph of the program where each program branch gives rise to an interval. The number of knots is highly dependent on the order of the statements in the program so that equivalent programs could have different values. We show that the two operations of rearranging and replicating program segments can substantially reduce the number of knots and thereby improve the readability and structure of the program. The rearrangement operation is a useful tool in converting "old" Fortran programs into more readable and structured Fortran 77 programs.
Resource Type	Technical Report
Date Issued	1979
Academic Affiliation	Computer Science
Series	Technical report (Oregon State University. Department of Computer Science)
Rights Statement	In Copyright
Publisher	Oregon State University. Department of Computer Science
Peer Reviewed	No
Language	English [eng]

Thumbnail	Title	Date Uploaded	Visibility	Actions
	Cook_Curtis_R_79_20_05.pdf	2022-12-29	Public	Download