An Interactive Graph Theory System

The medium of computer graphics provides a capability for dealing with pictures in man-machine communication. Graph Theory is used to model relationships which are represented by pictures and is therefore an appropriate discipline for the application of an interactive computer graphics system. Previous efforts to solve Graph Theoretic problems by computer have usually involved specialized programs written in a symbolic assembly language or algebraic compiler language. In recent years, graphics equipment with processing power has been commercially available for use as a remote terminal to a large central computer. Although these terminals typically include a small general purpose computer, the potential of using one as programmable subsystem has received little attention. These motivations have led to the design and implementation of an interactive graphics system for solving Graph Theoretic problems. The system operates on an IBM 7040 with a DEC-338 graphics terminal connected by voice-grade telephone line. To provide effective response times, computing power is appropriately divided between the two machines. The remote computer graphics terminal is controlled by a special-purpose executive program. This executive includes an interpreter of a command language oriented towards the control of existence and display of graphs. Several interactive functions such as graph drawing and editing are available to a user through light button and pushbutton selection. These functions which are local to the terminal are programmed in a mixture of the terminal computer\u27s machine language and the interpreted command language. For more significant computational requirements the central computer is used, but response time for interactive operation is then diminished. In order to overcome the speed of the telephone link, the central computer may call upon a program at the terminal as a subroutine. Based on the mathematical terminology used to define graphs, a high level language was developed for the specification of interactive algorithms. A growing library of these algorithms provides routines to aid in the construction and recognition of various types of graphs. Other routines are used for computing certain properties of graphs. Graphs may be transformed by some routines with respect to both connectivity and layout. Any number of graphs my be saved and later restored. A programmer using the terminal as an alphanumeric console may call upon the programming features of the system to develop new interactive algorithms and add them to the library. Programs may also be created for the display terminal, using the central computer for assembly. Examples of system use which are presented include finding a shortest path between any pair of vertices in a weighted directed graph, determining the maximally complete subgraphs of an arbitrary graph, interpreting a graph as a Mealy model of a finite state machine, and laying out a tree for aesthetic presentation