A DATA STRUCTURE FOR DIRECTED GRAPHS IN MAN-MACHINE PROCESSING
COMPUTER COMMAND AND CONTROL CO WASHINGTON DC
Pagination or Media Count:
This report describes research in information processing intended for application to man-machine communication processes. In order to allow a computer user to represent some problems more easily, we would like to let him name and define relations between information entities with which he deals, and then manipulate a large number of such relations stored by the computer. A set of statements on the relative desirability of various conditions is an example of a set of relations which the user might want to store and manipulate. The problem is that available representations for such sets of relations tend to be unwieldy and may require a great deal of processing for large numbers of relations. In order to make such a capability available, compact and easily- manipulated internal computer representations for large numbers of the various kinds of two-entity relations must be found. This report describes such a development for one basic logical form of relation, the transitive, anticommutative relation exemplified by precedes, includes, is greater than, and similar phrases. The report describes a method for storing directed graphs of transitive anticommutative relations in a list-structured computer memory. There are three important features of this representation method A method of dividing a graph into a number of strata based on the lengths of paths in the graph, a recursive decomposition technique which produces successively less complex versions of the graph, and a recursive search technique which utilizes the stratification and decomposition to extract information from the graph with a limited amount of processing effort.
- Human Factors Engineering and Man Machine Systems