Open Collections

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

The Ggram System : an interactive graphics system for Graph Manipulation Humphreys, Robert Douglas 1974

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Notice for Google Chrome users:
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.

Item Metadata

Download

Media
831-UBC_1974_A6_7 H84.pdf [ 4.71MB ]
Metadata
JSON: 831-1.0051763.json
JSON-LD: 831-1.0051763-ld.json
RDF/XML (Pretty): 831-1.0051763-rdf.xml
RDF/JSON: 831-1.0051763-rdf.json
Turtle: 831-1.0051763-turtle.txt
N-Triples: 831-1.0051763-rdf-ntriples.txt
Original Record: 831-1.0051763-source.json
Full Text
831-1.0051763-fulltext.txt
Citation
831-1.0051763.ris

Full Text

THE GGRAM SYSTEM: INTERACTIVE GRAPHICS SYSTEM FOR GRAPH MANIPULATION by R. Doug Humphreys B.Sc. , U n i v e r s i t y of B r i t i s h Columbia, 1972 A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE CF MASTER OF SCIENCE i n the Department of COMPUTER SCIENCE we accept t h i s t h e s i s as conforming to the reguired standard The U n i v e r s i t y of B r i t i s h Columbia October 1974 In p r e s e n t i n g t h i s t h e s i s i n p a r t i a l f u l f i l m e n t o f t h e r e q u i r e m e n t s f o r an a d v a n c e d d e g r e e a t t h e U n i v e r s i t y o f B r i t i s h C o l u m b i a , I a g r e e t h a t t h e L i b r a r y s h a l l make i t f r e e l y a v a i l a b l e f o r r e f e r e n c e a n d s t u d y . I f u r t h e r a g r e e t h a t p e r m i s s i o n f o r e x t e n s i v e c o p y i n g o f t h i s t h e s i s f o r s c h o l a r l y p u r p o s e s may be g r a n t e d by t h e H e a d o f my D e p a r t m e n t o r by h i s r e p r e s e n t a t i v e s . I t i s u n d e r s t o o d t h a t c o p y i n g o r p u b l i c a t i o n o f t h i s t h e s i s f o r f i n a n c i a l g a i n s h a l l n o t be a l l o w e d w i t h o u t my w r i t t e n p e r m i s s i o n . D e p a r t m e n t o f The U n i v e r s i t y o f B r i t i s h C o l u m b i a V a n c o u v e r 8, C a n a d a D a t e i i ABSTRACT The design and implementation of an i n t e r a c t i v e graphics system f o r graph manipulation are discussed. The a c t i v a t i o n f c r such a system i s examined, and the relevant l i t e r a t u r e i s described and evaluated. A number of ways to improve and extend the system are presented. The system provides the basic graph drawing operations cf adding, d e l e t i n g , l a b e l i n g , and changing both v e r t i c e s and edges. Also included are a number of graph manipulation operations which, among ether t h i n g s , allow a user to subdivide edges, as s o c i a t e v e r t i c e s , reverse the d i r e c t i o n cf a r c s , move v e r t i c e s about the screen, cr even move whole graphs about the sc teen. A f a c i l i t y i s provided whereby the screen can te di v i d e d i n t o as many as four regions, thus a l l o w i n g users t c d i s p l a y more than one graph at a time. Graphs can be saved on disk and l a t e r restored. The image on the graphics screen can te e a s i l y p l o t t e d t c obtain a hard copy of graphs. A few routin e s which perform graph-theoretic operations have teen implemented. Among these are a rou t i n e f o r f i n d i n g the minimum and maximum degrees of a graph, and a routine f c r f i n d i n g the blocks, cutnodes, and bridges cf a graph. Moreover, the system i s designed to allow users to add t h e i r own ro u t i n e s . i i i TABLE OF CONTENTS CHAPTER I - GRAPHICS AND GRAPH THEORY 1 1.1 INTRODUCTION 1 1.2 MOTIVATION 2 1.2.1 Research 3 1.2.2 Education 4 1.2.3 A p p l i c a t i o n s 5 1.3 RELEVANT LITERATURE 5 1.3.1 Graphics Systems For Graph Theory 6 1.3.2 Other Relevant Berk 8 CHAPTER I I - SYSTEM DESIGN 11 2.1 SYSTEM ORGANIZATION 11 2.2 SCREEN DESIGN 14 2.2.1 Menu 14 2.2.2 Regions 17 2.2.3 Message Area 17 2.2.4 Vertex And Edge Counts 18 2.3 FACILITIES 18 2.3.1 General F a c i l i t i e s 18 2.3.2 Graph Drawing F a c i l i t i e s 22 2.3.3 Graph-theoretic Operations 24 2.4 GENERAL CONSIDERATIONS 25 2.4.1 Free-hand Edges 25 2.4.2 M u l t i p l e Edges 26 2.4.3 Loops 26 i v CHAPTER I I I - IMPLEMENTATION 27 3.1 PROGRAMMING LANGUAGES 27 3.1.1 Choice Of Implementation Language 27 3.1.2 E f f e c t Of Implementation Language On The System 31 3.2 HARDWARE CONFIGURATION AND SOFTWARE SUPPORT 32 3.2.1 The Adage Graphics Terminal 33 3.2.2 The GRAPH Supervisor Program 33 3.2.3 E f f e c t Of Hardware And Software On The System 34 3.3 DATA STRUCTURES 37 3.3.1 I n t e r n a l Representation Of Graphs 37 3.3.2 Shadow Bu f f e r 44 3.3.3 Scratch Buf f e r 47 3.4 OVERVIEW OF THE PROGRAM 48 CHAPTER IV - IMPROVEMENTS AND EXTENSIONS 50 4.1 IMPROVING THE EXISTING SYSTEM . 50 4.2 EXTENSIONS 51 4.3 SUMMARY 57 BIBLIOGRAPHY 59 APPENDIX I - USER»S GUIDE 61 LIST OF FIGURES 1 < » The F i e l d s i n a GRAPH Record 38 2 « > The F i e l d s i n a VERTEX Record 39 3 * • The F i e l d s i n an EDGE Record 40 4 * • The F i e l d s i n an EDGEDES Record 41 5 « » The F i e l d s i n an CONSPT Record 41 6 « • The Link S t r u c t u r e of a Small Graph 43 1 < » The Screen When the System i s Running 62 8 « » The DRAW and FUNCTIOH Menus 69 9 < • The E f f e c t of SUBDIVIDE EDGE 87 10 « » The E f f e c t of REMOVE DEGREE 2 VERTEX 88 11 < • The E f f e c t of ASSOCIATE VERTICES 90 12 < » The E f f e c t of PERMUTE LABELS 95 13 • The E f f e c t of PERMUTE COORDS 96 14 i » The E f f e c t of BLOCKS/CUTNODES/BRIDGES 98 ACKNOWLEDGMENT: v i I would l i k e to express my s i n c e r e a p p r e c i a t i o n t c Dr. Abbe Mowshowitz, not only f o r h i s valuable help during the course of t h i s work, but a l s o f o r h i s guidance during the past few years. I would a l s o l i k e to thank Dr. J.M. Kennedy f o r h i s h e l p f u l suggestions f o r improving t h i s t h e s i s . CHAPTER I - GRAPHICS AND GRAPH THEORY 1 l i J INTRODUCTION The growing importance of gr a p h i c s i n computer s c i e n c e i s c e r t a i n l y not s u r p r i s i n g . Most people who have seen g r a p h i c s t e r m i n a l s i n o p e r a t i o n can a t t e s t tc t h e i r e f f e c t i v e n e s s i n pr e s e n t i n g v i s u a l i n f o r m a t i o n . For t h i s reason, many g r a p h i c s systems f o r p a r t i c u l a r a p p l i c a t i o n s have been developed. What i s s u r p r i s i n g , however, i s t h a t i t appears t h a t l i t t l e work has been done i n developing g r a p h i c s systems f o r s o l v i n g graph-t h e o r e t i c problems. The most n a t u r a l way to present a graph f o r someone's i n s p e c t i o n i s by means of a diagram. Most people are l i k e l y to p r e f e r a diagram r a t h e r than an adjacency m a t r i x 1 , f o r example. Thus a g r a p h i c s t e r m i n a l i s w e l l s u i t e d f o r d i s p l a y i n g graphs. T h i s t h e s i s d e s c r i b e s the design and implementation of the GG RAM system, an i n t e r a c t i v e Graphics system f c r GRAph »For g r a p h - t h e o r e t i c terms not e x p l i c i t l y d e f i n e d here, see Harary [ 9 ] . 2 Manipulation. The system i s designed t c allow a user t c draw and manipulate graphs conveniently and g u i c k l y . I t provides the basic operations of adding, d e l e t i n g , l a b e l i n g , and changing both v e r t i c e s and edges, as w e l l as a few s p e c i a l operations such as "subdivide edge" and " a s s o c i a t e v e r t i c e s " . A number of f a c i l i t i e s of general u t i l i t y are al s o provided. These include commands for d i v i d i n g the screen i n t o as many as four re g i o n s , p l o t t i n g the image on the screen, and saving graphs cn d i s k and l a t e r r e s t o r i n g them. Furthermore, a few graph- t h e o r e t i c algorithms have been implemented, and the system i s designed i n such a way as to allow users to e a s i l y add t h e i r own r o u t i n e s . I i i MOTIVATION There are at l e a s t three reasons f o r developing a graphics system f o r manipulating graphs. F i r s t , a properly designed system could be u s e f u l t c graph theory researchers. Second, such a system could help i n the teaching of graph thecry. And t h i r d , such a system could be used f o r s o l v i n g s p e c i f i c c l a s s e s of r e a l - w o r l d problems. 3 1 * 2^1 Research A graphics system f o r manipulating graphs could be used i n i t s s i m p l e s t form f o r i n v e s t i g a t i n g the p r o p e r t i e s of graphs. For example, a user could t e s t f o r isomorphism between two graphs by d i s p l a y i n g them both and then manipulating one to t r y to make i t look l i k e the other. or a user might t r y t c see i f a graph i s planar by t r y i n g to manipulate the graph so as to remove a l l edge-crossings. These operations make d i r e c t use of the i n t u i t i o n and experience of the user to help solve the problem. The e f f e c t i v e n e s s of such procedures could be increased by prov i d i n g the user with f a c i l i t i e s f c r saving and l a t e r r e s t o r i n g graphs. Thus, the o r i g i n a l graph and s e l e c t e d intermediate r e s u l t s could be saved, a l l o w i n g the user t c back up i f necessary. But while such procedures might be u s e f u l , they are c l e a r l y l i m i t e d i n what they can accomplish. What a system f o r graph manipulation r e a l l y needs i s a means for users to add t h e i r own r o u t i n e s . I f t h i s were p o s s i b l e , a user c c u l d t a i l o r the system to meet h i s (or her) p a r t i c u l a r needs. For example, a user i n t e r e s t e d i n planar graphs might implement an e x i s t i n g a l g orithm that t e s t s f o r p l a n a r i t y . Moreover, he cculd use the system to t e s t new algorithms. Research using a graph manipulation system need not be r e s t r i c t e d to graph theory i t s e l f . The importance cf graph theory stems p a r t l y from i t s s i d e range of a p p l i c a b i l i t y to r e a l - w o r l d problems (for example, see [ 2 0 ] ). There i s no reason why these problems c o u l d not be a t t a c k e d with the help of a g r a p h i c s system. I2.2..2 Education An i n t e r a c t i v e g r a p h i c s system f o r graph manipulation has g r e a t p o t e n t i a l f o r e d u c a t i o n . An annoying t h i n g about l e a r n i n g graph theory i s the seemingly endless number of d e f i n i t i o n s and concepts which must be learned b e f o r e more i n t e r e s t i n g problems are c o n s i d e r e d . A graph manipulation system c c u l d make l e a r n i n g such t h i n g s somewhat more e n j o y a b l e . In a d d i t i o n , a graph manipulation system, by i t s nature, would be very e f f e c t i v e f o r i l l u s t r a t i n g concepts. F c r example, the concept of a cutnode could be i l l u s t r a t e d by a c t u a l l y s e e i n g what happens when a vertex i s removed from a graph. Such a procedure i s much more e f f e c t i v e than, say, a blackboard demonstration simply because of i t s g r e a t e r speed and v i s u a l impact. As i s the case with r e a s e a r h , the e d u c a t i o n a l p o t e n t i a l cf a graph manipulation system i s not l i m i t e d to graph theory. Teachers i n other d i s i p l i n e s c o u l d use such a system to i l l u s t r a t e concepts/which can be formulated i n terms of graphs. For i n s t a n c e , a p r o b a b i l i s t might use i t to demonstrate c e r t a i n c h a r a c t e r i s t i c s of Markov c h a i n s . 5 l i 2 A 3 A £ £ l i c a t i o n s A g r a p h m a n i p u l a t i o n s y s t e m c o u l d a l s o be u s e d s i m p l y as a p r o b l e m s o l v e r . For example, a u s e r might implement a r o u t i n e t o f i n d a c r i t i c a l p a t h i n a n e t w o r k , and t h e n use t h i s r o u t i n e t o s o l v e r e a l p r o b l e m s . The a d v a n t a g e i n u s i n g a g r a p h i c s s y s t e m f o r t h i s i s t h a t i n p u t i s i n t h e f o r m o f a d i a g r a m o f t h e g r a p h , r a t h e r t h a n some o t h e r r e p r e s e n t a t i o n . T h i s would l i k e l y be v e r y h e l p f u l , e s p e c i a l l y s i n c e the u s e r c o u l d a l s o use t h e s y s t e m t o d e v e l o p t h e model. A g r a p h i c s s y s t e m c c u l d a l s c make c h a n g i n g t h e model e a s i e r . I J L J RELEVANT LITERATURE A l t h o u g h g r a p h t h e o r y seems l i k e a n a t u r a l a p p l i c a t i o n f o r a g r a p h i c s s y s t e m , t h e r e a p p e a r t o be few r e p o r t s c f s u c h a p p l i c a t i o n s i n t h e l i t e r a t u r e . Some work t h a t has t e e n done i s d e s c r i b e d below. F i r s t , t h e work which i s d i r e c t l y r e l a t e d t o g r a p h m a n i p u l a t i o n s y s t e m s i s e xamined. T h i s i s f o l l o w e d by a s h o r t d i s c u s s i o n o f i n d i r e c t l y r e l a t e d work. 6 l i l i l Gra£hics Systems f o r Grap_h Theory Two systems of sp e c i a l i n t e r e s t to the present study were developed by Wolfberg [20] and Maguire [12], Only a general description of each i s presented i n this section as an in d i c a t i o n of the nature and scope of the work. Mere detailed comments appear i n Chapter I I , where these systems are considered i n r e l a t i o n to the GGRAM system. A large part of Wclfberg's study encompasses the design and implementation of support systems to control the various devices on which the system runs, as well as consideration of programming languages for use on these devices. Of primary intere s t here, however, are the system's f a c i l i t i e s as far as graph theory i s concerned. The system provides a "complete graph drawing and editing f a c i l i t y " [20, p. 27]. Vertices and edges may be added, deleted, labeled, or changed. Vertices can have eight d i f f e r e n t shapes (including n u l l ) , and vertices and edges can be dimmed or blinked. A l i g h t pen and menu are used to choose p a r t i c u l a r operations. The system allows users to save any number of graphs and l a t e r restore selected ones. "A l i b r a r y of graph-thecretic algorithms i s maintained so users may apply certain i n t e r a c t i v e algorithms to ar b i t r a r y graphs. Other algorithms aid in construction or recognition of p a r t i c u l a r types of graphs" [20, P. 27]. 7 Graphs are drawn on what Wolfberg c a l l s the "paper". One of the more interesting features of his system i s the a b i l i t y to look at the paper through various sizes of windows. The largest window i s the same s i z e as the paper. Three other smaller windows e x i s t . As the windows become smaller, the v i s i b l e portion of the graph also becomes smaller, but the graph i n t h i s area i s magnified. In other words, a user can zoom i n on a pa r t i c u l a r area of a graph. Wolfberg's system i s very comprehensive in terms of the f a c i l i t i e s i t offe r s . It i s , however, sometimes cumbersome in i t s method of drawing graphs. More w i l l be said about t h i s in Chapter I I . Maguire [ 12] has developed "An Interactive System for Displaying Linear Graphs" c a l l e d the GSYM (Graph Symmetry) System. It i s a system " e s p e c i a l l y designed for working on the problem of generating displays of graphs" [12, p. 11, which allows a user to "create, manipulate, and display graphs" [12, p. 1], Graphs are composed of v e r t i c e s , edges, and arrows. A useful feature of this system i s that vertices and edges can be assigned properties. For example, edges i n a network might be assigned capacities. This feature i s independent cf labeling. System operations are i n i t i a t e d by choosing, with a l i g h t pen, one of a number of options which the system displays. Again the basic operations are adding, deleting, labeling, and changing vertices and edges. Individual vertices, edges, and 8 arrows, or even a whole graph, can be moved about the screen. Graphs can be saved and r e s t o r e d , and GSYM provides f o r the a d d i t i o n of us e r - w r i t t e n r o u t i n e s . Perhaps the most i n t e r e s t i n g part of GSYM i s the way graphs are stored and d i s p l a y e d . The author s t a t e s : GSYM graphs are defined using a three-dimensional co-ordinate system ... An edge i s dis p l a y e d on the screen as a s t r a i g h t l i n e j o i n i n g the x and y co-ordi n a t e s of the Ca r t e s i a n (x,y,z) co-ordinates of i t s e n d - v e r t i c e s . This three-dimensional C a r t e s i a n r e p r e s e n t a t i o n i m p l i e s that the user must be able to ro t a t e the graph i n order to see more than j u s t one face of the graph [ 1 2 , p. 1 4 ] . The GSYM system o f f e r s a f a i r l y complete set cf f a c i l i t i e s to the user. There are a few d e s i r a b l e f a c i l i t i e s , however, which have not been included. Moreover, l i k e the previous system, the GSYM system has a somewhat awkward procedure f o r drawing graphs. This i s mentioned f u r t h e r i n Chapter I I . Other Relevant Work Di G i u l i o and Tuan [ 7 ] have developed a graphics system to draw and manipulate systems a n a l y s i s networks. These networks are e s s e n t i a l l y d i r e c t e d graphs used to represent p r o j e c t scheduling problems, flows i n networks, and so f o r t h . Although t h e i r work encompasses both graphics and graph theory, i t i s incl u d e d here r a t h e r than i n the previous s e c t i o n because i t i s extremely s p e c i a l i z e d , Using t h e i r system, systems a n a y l s i s networks may be drawn at a graphics ter m i n a l with a j o y s t i c k and 9 a l i g h t pen. Graphs are stored as adjacency matrices and manipulations are performed using these matrices. Operations which can be appli e d to graphs in c l u d e union, i n t e r s e c t i o n , and a few others. The system i s o r i e n t e d towards d i s p l a y i n g graphs, and i t a u t o m a t i c a l l y generates diagrams of graphs from t h e i r adjacency matrices. An algorithm i s presented f c r d i s p l a y i n g a c y c l i c d i r e c t e d graphs i n such a way that a l l arrows point more or l e s s i n one d i r e c t i o n and l i n e - c r o s s i n g s are minimized. A number of programming languages f o r graph theory have been developed by various people. These languages tend tc be extensions of an e x i s t i n g language which enable graph-theoretic operations to be expressed n a t u r a l l y and conveniently. c r e s p i -R e g h i z z i and Morpurgo [ 6 ] have extended ALGOL 60 to i n c l u d e operations on graphs such as a d d i t i o n and d e l e t i o n of v e r t i c e s , the union of two graphs, or the i n t e r s e c t i o n of two graphs, new data types are a l s o provided f o r four d i f f e r e n t c l a s s e s cf graphs. P r a t t and Friedman [16] have developed a programming language extension f c r processing d i r e c t e d graphs. This extension i s formulated i n terms of the semantics cf c e r t a i n p r i m i t i v e operations which operate on graphs. I t i s not designed to be embedded i n a s p e c i f i c language, although an example of an embedding i n LISP i s presented. Another grap h - t h e o r e t i c language has been developed by Rheinboldt et a l . [ 1 8 ] . I t i s an extension of ALGOL 60 f o r 10 " d e s c r i b i n g and implementing graph a l g o r i t h m s of the type a r i s i n g i n a p p l i c a t i o n s " [ 1 8 , p. 220 ], A s i m i l a r language has been developed by King [ 1 1 ] . fie has extended FORTRAN to i n c l u d e f a c i l i t i e s t o perform graph-t h e o r e t i c o p e r a t i o n s . 11 CHAPTER I I - SYSTEM DESIGN In t h i s chapter an attempt i s made to j u s t i f y the design cf the GGRAM system by cons i d e r i n g those f e a t u r e s which are d e s i r a b l e i n an i n t e r a c t i v e graphics system f c r graph manipulation. F i r s t , system o r g a n i z a t i o n i s discussed. Then screen layout i s considered, and the reasons f c r cheesing c e r t a i n system f a c i t l i t i e s are looked a t . F i n a l l y , a number of general c o n s i d e r a t i o n s are examined. Throughout the d i s c u s s i o n the GGRAM system i s compared to the two s i m i l a r e x i s t i n g systems which were described i n Chapter I, Section 1.3.1. Fcr parts of t h i s chapter, readers may f i n d i t h e l p f u l to r e f e r to f i g u r e 7, a p l o t of the screen while the system i s running. 2 i l SYSTEM ORGANIZATION The GGRAM system has been implemented wi t h i n the framework of what might be c a l l e d a t y p i c a l hardware c o n f i g u r a t i o n ( c f . [20, p. 6] ). The graphics f a c i l i t y c o n s i s t s cf a graphics (CRT) t e r m i n a l driven by a general purpose graphics computer. Various input devices, such as a l i g h t pen, pushbuttons, and v a r i a b l e c o n t r o l d i a l s , are attached to the graphics t e r m i n a l . The graphics computer i s connected to a 12 l a r g e main computer by way of a communication l i n e . Associated with the graphics t e r m i n a l , but connected to the main computer, i s a normal (CRT) t e r m i n a l . Programs being run at t h i s (normal) t e r m i n a l are allowed to communicate with the graphics computer using the communication l i n e . When designing a system using such a c o n f i g u r a t i o n , a number of de c i s i o n s must be made. One of the most important d e c i s i o n s i s how to d i v i d e the computing duties between the graphics computer and the main computer. This d e c i s i o n can be in f l u e n c e d by many f a c t o r s , i n c l u d i n g the desired response time, time c o n s t r a i n t s , cost c o n s t r a i n t s , or the scope of the work, to name a few. In most graphics systems there are c e r t a i n f u n c t i o n s which can be handled l o c a l l y by the graphics computer. Fcr example, i n a graph manipulation system information about the layout of di s p l a y e d graphs, and changes to t h i s layout, can be handled i n t h i s way (see [20, p.21 ] ). This approach, however, n e c e s s i t a t e s the implementation of a s p e c i a l supervisor program f o r the graphics computer. But the development of such a supe r v i s o r program i s u s u a l l y only necessary i f communication with the main computer i s too slow f o r a p a r t i c u l a r a p p l i c a t i o n . Thus, f o r s p e c i a l a p p l i c a t i o n s l i k e computer animation i t may be necessary to perform l c c a l processing i f frames cannot be received from the main computer at a high enough r a t e . On the other hand, graph manipulation r e g u i r e s only that the 13 communication time be reasonable (see [13] ). In the GGRAM system a l l computing i s done i n the main computer. A general purpose graphics supervisor [ 4 ] i s used at the graphics computer to d i s p l a y images on the graphics screen, read the pushbuttons and d i a l s , and detect l i g h t pen h i t s (see al s o Chapter III) . S p e c i a l r o u t i n e s [ 5 ] are provided to communicate with the graphics supervisor. Within the main computer the GGRAM system i s d i v i d e d i n t o components i n a s t r a i g h t f o r w a r d and perhaps obvious marner. One important component i s the graph data area which contains the i n t e r n a l r e p r e s e n t a t i o n of graphs. information from t h i s component i s used by d i s p l a y r o u t i n e s to cons t r u c t images to be sent to the graphics computer. A group of c o n s t r u c t i o n r o u t i n e s are used f o r changing these s t r u c t u r e s . The remainder of the system c o n s i s t s or rou t i n e s which roughly f a l l i n t o three c a t e g o r i e s : c o n t r o l r o u t i n e s , command r o u t i n e s , and u t i l i t y r o u t i n e s . At the top l e v e l , c o n t r o l r o u t i n e s communicate with a user to determine what operation i s de s i r e d . When an operation i s s p e c i f i e d , the c o n t r o l r o u t i n e s c a l l the command ro u t i n e (s) necessary to accomplish the operation. C e r t a i n u t i l i t y r o u t i n e s are a l s c a v a i l a b l e to perform s p e c i a l f u n c t i o n s . 14 2^ .2 SCREEN DESIGN The method of presentation of inf o r m a t i o n to a user i s u s u a l l y very important i n a graphics system. Some of the methods which seem appropriate to a graph manipulation system are described i n t h i s s e c t i o n . Perhaps the most e f f e c t i v e way f o r a user t c c o n t r o l the operation of a graphics system, i n most cases, i s by way of a menu. This u s u a l l y means that a l l the operations t h a t are p o s s i b l e at a given time are displayed on the graphics screen and a user chooses the des i r e d operation with a l i g h t pen. Generally the menu i s f r e q u e n t l y changed, depending cc the st a t e of the system. Wolfberg and Maguire both use t h i s approach. Another approach i s t o use a s t a t i c menu, t h a t i s , a l l system f a c i l i t e s are always d i s p l a y e d . With t h i s approach, i t may not be p o s s i b l e to i n i t i a t e some dis p l a y e d operations at a given point i n time. Both approaches have t h e i r drawbacks. The f i r s t method i s sometimes u n s a t i s f a c t o r y when a user i s f r e q u e n t l y changing between operations, e s p e c i a l l y i f there are many choices i n each s t a t e . One problem i s that i t can take too l o n g , r e l a t i v e to a user's speed of thought, to d i s p l a y a new menu. A s i m i l a r problem i s encountered with the GGRAM system when the v a r i a b l e menu i s changed. Users might a l s o be d i s t r a c t e d by the v i s u a l 15 readjustment needed f o r a new menu. Part c f the reason f c r t h i s i s t h a t a new menu must be d i s p l a y e d s u f f i c i e n t l y f a r from the l o c a t i o n where the l i g h t pen may remain a f t e r p o i n t i n g at a pr e v i o u s menu [20, p.172], On the other hand, a s t a t i c menu a l s o presents problems. Since a l l o p e r a t i o n s are always d i s p l a y e d , the amount of i n f o r m a t i o n may d i s t r a c t (or even confuse) a user. A novice may have to search f o r the o p e r a t i o n he wants. Furthermore, a user must be aware of which o p e r a t i o n s are a l l o w a b l e a t a given p c i n t i n time. Of these two approaches, the f i r s t i s unacceptable f c r the GGRAM system because i t would slow down the graph drawing process too much. There are simply too many opt i o n s t c make a c o n t i n u a l l y changing menu f e a s i b l e . The second method, t h e r e f o r e , i s the method t h a t i s used. T h i s i s net as bad as i t might appear at f i r s t , f o r two reasons. F i r s t , both the o b j e c t i o n s to t h i s approach become l e s s important as a user becomes more f a m i l i a r with the system. And second, the menu can be designed i n such a way as to help the user f i n d o p e r a t i o n s and know which are a v a i l a b l e a t each poin t i n time. At a l l l e v e l s the menu i s d i v i d e d i n t o l o g i c a l s e c t i o n s . T h i s helps a user f i n d the command he i s l o o k i n g f o r . At the top l e v e l are the f i x e d and v a r i a b l e menus. The f i x e d menu c o n t a i n s commands of gen e r a l u t i l i t y . The v a r i a b l e menu can c o n t a i n one of two menus: the draw menu or the f u n c t i o n menu. The draw menu c o n t a i n s commands f o r drawing and a l t e r i n g graphs, 16 while the f u n c t i o n menu contains commands f o r i n i t i a t i n g graph-t h e o r e t i c algorithms. The v a r i a b l e menu can be changed using a command i n the f i x e d menu. This menu roust be changed i n t h i s way because there i s not enough room on the screen t c allow both the draw and f u n c t i o n menus to be dis p l a y e d at the same time. A s o l i d d i v i d i n g l i n e across the menu serves to p h y s i c a l l y separate the f i x e d and v a r i a b l e p o r t i o n s . There i s a l s o a l o g i c a l o r dering w i t h i n each menu. C l o s e l y r e l a t e d commands, such as the commands f o r saving and r e s t o r i n g graphs, are d i s p l a y e d on the same l i n e . The draw menu i s f u r t h e r subdivided i n t o s e c t i o n s by two dashed d i v i d i n g l i n e s . The top s e c t i o n contains commands f o r changing the appearance of v e r t i c e s and edges. The middle s e c t i o n contains the vertex and edge prototypes which show what v e r t i c e s and edges w i l l look l i k e when added to a graph. The bottom s e c t i o n contains commands f o r a c t u a l l y drawing and a l t e r i n g graphs. Some important commands are dis p l a y e d i n lar g e l e t t e r s . T his not only serves to emphasize these commands, but a l s o helps to o r i e n t a user by pr o v i d i n g "landmarks". C e r t a i n commands, such as "add", can be a p p l i e d to both v e r t i c e s and edges. So, ins t e a d of c l u t t e r i n g the screen by d i s p l a y i n g both an "add vert e x " and "add edge" command, a s i n g l e ADD command i s di s p l a y e d . A square t c the l e f t of ADD i s f o r adding edges; a sguare to the r i g h t i s f o r adding v e r t i c e s . Since there are a number of commands of t h i s type, two columns of squares are 17 formed. The l e f t column, i n l i n e with the edge prototype, i n i t i a t e s operations on edges; the r i g h t column, i n l i n e with the vertex prototype, i n i t i a t e s operations on v e r t i c e s . 2.. 2_.2 Regions The system allows the screen t o be broken i n t o as many as four regions. There are two major reasons f o r al l o w i n g t h i s . F i r s t , i t i s often u s e f u l to be able to v i s u a l l y compare a number of graphs. For example, a user may want to determine by i n s p e c t i o n whether or not two graphs are isomorphic; or he may want to see a graph before and a f t e r an operation such as a s s o c i a t i n g v e r t i c e s i s performed. Second, a user may want to draw two or more graphs i n p a r a l l e l . A number of d i f f e r e n t yet r e l a t e d graphs might be drawn i n t h i s way. 2J._2.J_3 Message Area A narrow area at the bottom . of the screen, c a l l e d the message area, i s reserved f o r messages to the user. A separate area i s a l l o c a t e d f o r t h i s f u n c t i o n to emphasize the messages and a l s o to prevent messages from i n t e r f e r i n g with graphs di s p l a y e d on the screen. Messages are bl i n k e d to make them even more n o t i c e a b l e . 1 8 2±2J± Vertex and Edge Counts As a convenience to the user, f o r each graph on the screen the number of v e r t i c e s and edges are displayed toward the lower l e f t corner of the regio n . This i s information that i s fr e q u e n t l y wanted. I t a l s o serves as a double-check when drawing s p e c i f i c graphs by a l l o w i n g a user to make sure that a l l d e s i r e d components have been drawn. 2 i J FACILITIES In t h i s s e c t i o n the reasons f o r i n c l u d i n g c e r t a i n f a c i l i t i e s i n the system are examined. The three subsections correspond to the f i x e d menu, the draw menu, and the f u n c t i o n menu, r e s p e c t i v e l y . D e t a i l e d d e s c r i p t i o n s of the i n d i v i d u a l commands can be found i n Appendix I . General F a c i l i t i e s Since the menu does net change, a user needs some way to t e l l when the system i s expecting i n p u t . An i n d i c a t o r which b l i n k s when the system i s ready serves t h i s purpose. To make t h i s i n d i c a t o r h i g h l y v i s i b l e , i t i s placed at the top of the menu and di s p l a y e d i n la r g e c h a r a c t e r s . A command i s necessary to change how the screen i s d i v i d e d i n t o regions. In the GGRAM system eight p o s s i b l e patterns are 1 9 allowed, with the number of regions being e i t h e r one (one c h o i c e ) , two (two c h o i c e s ) , three (four c h o i c e s ) , or four (one c h o i c e ) . This provides a high degree of f l e x i b i l i t y f c r d i s p l a y i n g graphs. Two commands are s u p p l i e d t o set the v a r i a b l e menu. The system i s designed i n such a way t h a t , should the f u n c t i o n menu become f u l l from the a d d i t i o n of u s e r - w r i t t e n r o u t i n e s , a d d i t i o n a l menus can be added. Another command changes the system i n t o keyboard mode1. In keyboard mode, the keyboard rather than the l i g h t pen i s used to c o n t r o l the system. This mode i s provided f o r three reasons. F i r s t , some people simply prefer typing to using the l i g h t pen. Second, i t can be used t o r a p i d l y i n i t i a t e a group cf commands. This could be used, f o r example, t c change a number of system d e f a u l t s at the beginning of a run. To do t h i s , the appropriate commands would be put i n t o a f i l e , and then t h i s f i l e used as input to the system. The f i l e could be kept and used each time the system i s run. T h i r d , keyboard mode all o w s the system to be used even i f the l i g h t pen hardware becomes ino p e r a b l e . Both Wolfberg and Maguire have s i m i l a r f a c i l i t i e s . Holfberg d i s p l a y s a number or a l e t t e r beside each menu item. Typing t h i s character i s equivalent t c choosing the item with *Keyboard mode has not yet been implemented i n the GGRAM system. 20 the l i g h t pen 2. Maguire has implemented what he c a l l s "macro mode", i n which the keyboard i s used f o r communication with the GSIM system. A "help" command^ i s supplied to a c t as an i n t e r a c t i v e user's guide. When t h i s command i s a c t i v a t e d , the user i s asked a s e r i e s of questions to determine what informa t i o n i s de s i r e d . T h i s f e a t u r e i s most u s e f u l when a user gets i n t o t r o u b l e or fo r g e t s something while running the system. The system allows a user to change various g l o b a l parameters. A l l parameters, of course, have d e f a u l t s , but a user may wish to change some of these. For example, unless otherwise s p e c i f i e d , the system places l a b e l s at a d e f a u l t ( r e l a t i v e ) l o c a t i o n , but t h i s l o c a t i o n can be changed i f de s i r e d . The system allows users to s e l e c t i v e l y d i s p l a y l a b e l s . This means that seme l a b e l s that are defined may not be di s p l a y e d . Some graphs may be more readable when vertex and edge l a b e l s are not displayed simultaneously. A user may want to erase a l l l a b e l s f o r some reason, wolfberg's system has a s i m i l a r feature which allows l a b e l s to be defined but not 2 T h e OBC graphics system r u l e s out implementing keyboard mode i n t h i s way because i t i s set up to read from only one device at a time. "The "help" command has not yet been implemented i n the GGBAM system. 21 d i s p l a y e d . An obviously u s e f u l feature f o r a graph manipulation system to have i s the a b i l i t y to produce a hard copy of a p a r t i c u l a r graph. For t h i s reason a command i s included i n the GGRAM system f o r producing a p l o t of the whole screen. Another obviously u s e f u l f e a t u r e i s an a b i l i t y to save and l a t e r r e s t o r e graphs. Commands f o r these two fu n c t i o n s are a l s o included i n the GGRAM system. The graph t i t l i n g f e a t u r e of the GGRAM system a l l c w s a user to annotate graphs with a t i t l e up to f o r t y characters long. This i s most u s e f u l when r e s t o r i n g graphs t h a t have been saved. I t i s also convenient to be able to t i t l e a graph f o r d i s p l a y purposes. A user, however, i s never forced to t i t l e a graph, even i f the graph i s to be saved. This i s u n l i k e both Wolfberg and Maguire, who i n s i s t a graph be t i t l e d before i t i s saved. The system maintains a l i s t of graphs that have been defined to i t ( e i t h e r by drawing of r e s t o r i n g ) . Thus, commands to d i s p l a y and rub out graphs are necessary to c o n t r o l which graphs are dis p l a y e d . A command i s sup p l i e d which a l l o w s a user to move graphs between regions. This i n v o l v e s rubbing out the graph and then r e - d i s p l a y i n g i t i n the new region. The system a u t o m a t i c a l l y prevents a p a r t i c u l a r i n t e r n a l 22 copy of a graph from being displayed i n more than cne r e g i c n . I f t h i s were allowed, i t weald create havoc i f the graphs were a l t e r e d . Sometimes, though, the same image i s desired i n more than one r e g i o n . To do t h i s , d i s t i n c t i n t e r n a l copies must be made and the copies displayed i n the other regions. A graph d u p l i c a t i n g command i s provided f o r t h i s purpose. I t i s c l e a r l y d e s i r a b l e t o allow a user to cancel (where possible) an ope r a t i o n . A command i n the menu serves t h i s purpose when the GGRAM system i s reading from the graphics t e r m i n a l . A user can a l s o c a n c e l when the system i s expecting input from the keyboard. This i s accomplished by entering the current contents of a g l o b a l parameter which i s i n i t i a l l y "CANCEL", but i t can be changed i f d e s i r e d . 2^ 3^ .2 Graph Drawing F a c i l i t i e s I t i s very u s e f u l f o r d i s p l a y purposes to allow the p h y s i c a l c h a r a c t e r i s t i c s of v e r t i c e s and edges to be v a r i e d . Thus, the GGRAM system a l l o w s v e r t i c e s and edges to be normal i n t e n s i t y or bold f a c e , s o l i d or dashed. The s i z e and shape (number of sides) of v e r t i c e s can al s o be changed. In order t h a t a user can a c t u a l l y see what the v e r t i c e s and edges that he w i l l draw w i l l look l i k e , an edge prototype and vertex prototype are d i s p l a y e d i n the menu. This procedure i s somewhat f a s t e r than the one employed by Wolfberg. He al l o w s the appearance of v e r t i c e s and edges tc be 23 v a r i e d , but they are always i n i t i a l l y created with the same c h a r a c t e r i s t i c s , A user can then change them i f d e s i r e d . Maguire does not provide f o r v e r t i c e s and edges t c vary i n appearance. The edge prototype a l s o serves as a convenient i n d i c a t i o n as t o whether or not the system i s i n d i r e c t e d mode. In t h i s mode, a l l edges that are drawn are considered to be d i r e c t e d . When the system i s i n d i r e c t e d mode, the edge prototype i s dis p l a y e d with an arrow, The systems of both s c l f b e r g and Maguire reguire a user to add an arrow to an e x i s t i n g edge i n order to make i t i n t o a d i r e c t e d edge. Thus, two operations are necessary to draw such an edge. This seems to be an unnecessary waste of e f f o r t . The standard graph drawing o p e r a t i o n s , of course, are provided i n the GGRAM system. These allow both v e r t i c e s and edges to be added, d e l e t e d , l a b e l e d , c r changed. A number of s p e c i a l g r a p h i c a l operations are provided, some of which are r e l a t e d to p a r t i c u l a r g raph-theoretic concepts. Homeomorphisms between graphs can be v i s u a l l y i n v e s t i g a t e d using f e a t u r e s which allow an edge to be subdivided, and a vertex of degree two to be removed. A command f o r a s s o c i a t i n g v e r t i c e s allows users to perform elementary homomorphisms on s e l e c t e d graphs. Directed graphs can be manipulated using commands which reverse the d i r e c t i o n c f an a r c , and change an undirected edge 24 i n t o a d i r e c t e d edge, or v i c e versa. A graph's layout can be changed by moving v e r t i c e s around the screen or even moving the whole graph. 2±3±3 Gra£h-theoretic Operations Only four graph-theoretic r o u t i n e s have been implemented to date. Their s e l e c t i o n depended on personal preference and time c o n s t r a i n t s , and they are cnly mentioned here f o r completeness. The f i r s t i s a r o u t i n e f o r determining the minimum and maximum degreees i n a graph. I f the graph i s d i r e c t e d , both the minimum and maximum indegrees and the minimum and maximum outdegrees are determined. Another r o u t i n e w i l l permute the vertex l a b e l s cf a s e l e c t e d graph, while a t h i r d routine w i l l permute vertex coordinates. The l a t t e r r o u t i n e i s p a r t i c u l a r l y u s e f u l f o r t e s t i n g f o r and demonstrating isomorphism. The f i n a l r o u t i n e w i l l f i n d the blocks, cutncdes, and bridges of an a r b i t r a r y graph. I t a l s o f i n d s a spanning t r e e , i f one e x i s t s . The algorithm used i n t h i s r o u t i n e i s due to Read [ 17]. 25 2 A4 GENERAL CONSIDERATIONS Three general c o n s i d e r a t i o n s which are important t c a graph manipulation system are discussed i n t h i s s e c t i o n . These are curved edges, m u l t i p l e edges, and loops. Za.Ha.1 free-hand Edges The a b i l i t y to draw bent or curved edges i s e s s e n t i a l to a t r u l y f l e x i b l e graph-drawing system. For t h i s reason, the GGRAM system a l l o w s a user to draw edges which are made up of any number of l i n e segments, rather than a s t r a i g h t l i n e between v e r t i c e s . These edges are e a s i l y drawn using the t r a c k i n g p a t t e r n and the l i g h t pen. Wolfberg allows a user to bend edges, but i t appears that only one bend i s allowed. Maguire allows " l i g h t pen edges" to be drawn. These edges are temporary curved replacements f o r e x i s t i n g s t r a i g h t edges. C n f o r t u n a t e l y , these edges disappear when a graph i s rot a t e d w i t h i n the three-dimensional space i n which the graph i s defined. A f t e r such a r o t a t i o n , a l l l i g h t pen edges must be re-drawn. 26 la-lsl. M u l t i p l e Edges Whenever a m u l t i p l e edge i s drawn, the GGRAM system d i s p l a y s a warning message t c the user. This i s done because i t i s p o s s i b l e to draw one of a p a i r of m u l t i p l e edges cn top of the other, i n which case the p a i r looks l i k e a s i n g l e edge. A warning i s p a r t i c u l a r l y important i f a user program causes a m u l t i p l e edge, since such an occurence could e a s i l y go unnoticed by the user. But i t i s even q u i t e easy to u n i n t e n t i o n a l l y draw a m u l t i p l e edge with the l i g h t pen. Maguire's system does not check f o r m u l t i p l e edges. He leaves i t up to the user to not i c e t h e i r e x i s t e n c e . Wolfterg does not seem to i n d i c a t e whether or not m u l t i p l e edges are checked f o r or even allowed i n h i s system. 2 ..4 ..3 Loops Loops are allowed by the GGRAM system under the proviso that they be free-hand edges. Otherwise the edge could not be seen. wolfberg allows loops, but they are always the same shape and must have e i t h e r an east, west, north, or south o r i e n t a t i o n . This seems l i k e an unnecessary r e s t r i c t i o n . Maguire does not i n d i c a t e i f loops are allowed i n h i s system. 27 CHAPTER I I I - IMPLEMENTATICH This chapter i s a d i s c u s s i o n of the implementation cf the GGRAM system. F i r s t , the c r i t e r i a used to decide on the implementation language are discussed, and the e f f e c t s of t h i s choice on the system are examined. The hardware c o n f i g u r a t i o n and software support are then described, and t h e i r e f f e c t s cn the system are considered. Next, the major data s t r u c t u r e s used by the system are described. F i n a l l y , an overview cf the program i s presented. 3*. 1 PROGRAMMING LANGUAGES £ifii£J§ cf Iffi£lementation Language Most of the program i s w r i t t e n i n AIGCLW, There are also about a dozen routi n e s w r i t t e n i n FORTRAN, and one routine w r i t t e n i n 360 ASSEMBLER. There are a number of c o n s i d e r a t i o n s which led t c the choice of ALGOLW as the primary implementation language. F i r s t i s the requirement that a s t r u c t u r e d data type be a v a i l a b l e to use f o r the i n t e r n a l r e p r esentation of graphs. The 28 r e p r e s e n t a t i o n chosen makes extensive use of p o i n t e r s (see EATA STRUCTURES below), and would be extremely cumbersome i f implemented by means cf a r r a y s . The ALGOLW record [1 ] i s a o n e - l e v e l s t r u c t u r e d data type c o n s i s t i n g of a number of f i e l d s which can be of d i f f e r e n t (simple) types. Records are pointed to by reference v a r i a b l e s . C l o s e l y r e l a t e d t o s t r u c t u r e d data types, and equa l l y important i n terms of t h i s implementation, i s the requirement that dynamic storage a l l o c a t i o n be a feature of the language. This i s not only e s s e n t i a l f o r record a l l o c a t i o n , but i s a l s o u s e f u l f o r array a l l o c a t i o n . In f a c t , dynamic array a l l o c a t i o n i s used guite often i n the system. A t h i r d requirement i s that a convenient and e f f i c i e n t i n t e r f a c e must e x i s t (or be po s s i b l e ) between the implementation language and FORTRAN. In p a r t i c u l a r , the language must be able to c a l l FORTRAN r o u t i n e s and accept returned values from these r o u t i n e s , and a l s o must be able to handle FORTRAN arrays. The reason f o r t h i s i s that the l i b r a r y r o u t i n e s supplied f c r use with the Adage Graphics Terminal [ 5 ] e i t h e r are w r i t t e n i n FORTRAN or use FORTRAN c a l l i n g conventions. Furthermore, these r o u t i n e s often have arrays as parameters. To c a l l FORTRAN r o u t i n e s from A1GCIW, one simply d e c l a r e s an e x t e r n a l procedure and s p e c i f i e s that FORTRAN c a l l i n g conventions are to be used [ 8 ] . A ro u t i n e declared i n t h i s way 29 i s used i n an ALGOLW program i n the same way as a normal ALGOLW procedure. The i n t e r n a l r e p r e s e n t a t i o n of AIGCIW (cne-dimensional) arrays i s e x a c t l y the same as the FORTRAN r e p r e s e n t a t i o n , and so arrays do not present a problem. Two other requirements are a l s o of some importance. F i r s t , the language should be known, or e a s i l y learned, by people who might use the system. Second, the language should be e f f i c i e n t both i n terms of program development and program usage, t h a t i s , i t should have an e f f i c i e n t compiler which produces e f f i c i e n t code. These two points are important p r i m a r i l y because the system i s intended to be used, i n part , as a research t o o l . Researchers who know the implementation language w i l l be able to modify or extend the system t o meet t h e i r own p a r t i c u l a r needs. I f the system i s expensive to run, researchers w i l l be discouraged from using i t . Furthermore, since a s i g n i f i c a n t p o r t i o n of research i n graph theory r e l a t e s to algorithm development, the compiling e f f i c i e n c y of the language must a l s o be acceptable. Those who are not f a m i l i a r with ALGOLW but who know ALGOL 60, P L / I , FORTRAN, or a s i m i l a r language, should not have any tr o u b l e l e a r n i n g ALGOLW. Furthermore, i t i s r e l a t i v e l y e f f i c i e n t both at compile time and run time. There are also s e v e r a l requirements which, although net e s s e n t i a l , nevertheless make programming e a s i e r . F i r s t , the language should have reasonable s t r i n g handling f a c i l i t i e s . 30 This allows easy manipulation of graph t i t l e s , l a b e l s , messages, and so on. Second, the language should be r e c u r s i v e . This a l l o w s a few f a c i l i t i e s to be provided which would be d i f f i c u l t i n a non-recursive language. For example, the execution of commands i s c o n t r o l l e d by lar g e CASE statements, and i t i s sometimes convenient to be able to c a l l these CASE statements r e c u r s i v e l y . Such i s the case when a c e r t a i n command i s to be executed while s t i l l executing another command. This i s dene, f o r i n s t a n c e , when the appearance of one of the prototypes i s to be changed while "add vertex" i s s t i l l a c t i v a t e d . F i n a l l y , the language should be easy t c write i n . There are many language f e a t u r e s that could be considered i n t h i s regard, many cf which are simply personal preference. However, some features that could be inc l u d e d are a block s t r u c t u r e , the existence cf IF-THEN-ELSE, WHILE, and CASE statements, and the a b i l i t y to use long (and meaningful) i d e n t i f i e r s . Three languages other the ALGOLW were s e r i o u s l y considered as the primary implementation language: PL/I, LISP, and FORTRAN. FORTRAN was r e j e c t e d almost immediately since the only two requirements i t meets are that i t " i n t e r f a c e s to FORTRAN" and i t i s known by many people. LISP was considered somewhat more s e r i o u s l y , e s p e c i a l l y i n l i g h t of the f a c t that a LISP i n t e r f a c e to the Adage Graphics Terminal has already been w r i t t e n . As w e l l as meeting most of the requirements mentioned abcve, LISP al s o provides e x c e l l e n t debugging f a c i l i t i e s , and allows a user to e a s i l y modify e x i s t i n g r o u t i n e s and wri t e new cnes without 31 having to re-compile. LISP was r e j e c t e d , however, mainly because of i t s i n e f f i c i e n c y and i t s lack of widespread appeal to the c l a s s of users f o r whom the system was designed. Both PL/I and ALGOLS met a l l the c r i t e r i a described abcve; however, the PL/I compiler i s somewhat l e s s e f f i c i e n t than the ALGOLW compiler. Moreover, although PL/I i s easy to write i n , i t does not have the consistency and inherent s i m p l i c i t y of ALGOLW; and despite the f a c t t h a t l i n k a g e to FORTRAN from PL/I i s p o s s i b l e , i t i s subject to s p e c i a l r u l e s that are, at the very l e a s t , a nuisance. Thus, ALGOLW was chosen over PL/I f o r the implementation of the system. 3*1.8.2 E f f e c t of Implementation Language on the System The version of ALGOLW adopted by the Computing Centre of the U n i v e r s i t y of B r i t i s h Columbia [ 8 ] c e r t a i n l y i s net p e r f e c t . Although the language i t s e l f i s e x c e l l e n t , the implementation i s i n many ways poor. Most of the problems have to do with s i z e l i m i t a t i o n s of one s o r t cr another. These l i m i t a t i o n s have had a number of e f f e c t s on system development. The r e s t r i c t i o n that "the data area f c r each ERCCIBOBE or BEGIN block with d e c l a r a t i o n s i s l i m i t e d to 4096 bytes" [10, p. 30] has meant tha t any large arrays must be handled i n FORTRAN. This i n v o l v e s s e t t i n g up the arrays i n COMMON blocks and w r i t i n g FORTRAN r o u t i n e s (which can be c a l l e d from ALGCLW) to manipulate the ar r a y s . The "shadow b u f f e r " and the " s c r a t c h b u f f e r " are 32 handled i n t h i s way (see below). The r e s t r i c t i o n that "only 255 d i f f e r e n t procedures or BEGIN blocks with d e c l a r a t i o n s are allowed by the compiler" [10, p. 28] has meant that a number of r e l a t e d procedures have o f t e n been combined i n t o one l a r g e r procedure i n order to save procedure c a l l s . For example, a procedure c a l l e d DELETE_ITEM does the work of DELETE_VEBTEX and DEIETE_EDGE. This l i m i t a t i o n , of course, has hampered e f f o r t s to write a t r u l y s t r u c t u r e d program, and a l s o p a r t i a l l y r e s t r i c t s f u t u r e expansion of the system. A t h i r d r e s t r i c t i o n that has a f f e c t e d the program i s that "the t o t a l amount of machine code and constants f c r any PROCEDURE or other BEGIN block with d e c l a r a t i o n s must be l e s s than 8192 bytes" [10, p. 30]. This has made i t necessary to s p l i t a few procedures that are too la r g e . For example, CONSTRUCT_DRAW_MENU was s p l i t i n t o CONSTRUCT_DRAW_MENU1 and C0NSTRUCT_DRAW_MENU2. 3 A2 HARDWARE CONFIGURATION AND SOFTWARE SUEPOBT Two important i n f l u e n c e s on the design of a graphics system are the hardware that i s a v a i l a b l e and the software that i s su p p l i e d ( i f any) f o r use with t h i s hardware. This aspect of the design of the GGRAM system i s discussed i n t h i s s e c t i c n . 33 3*2*1 SkS Adage Graphics Terminal The GGRAM system i s implemented on an Adage Corporation Model 10 Graphics Terminal, which i s connected to a general purpose graphics computer. An IBM 3270 Display S t a t i o n next to the graphics t e r m i n a l i s connected to an IEM 370/168, and programs being run from the 3270 can communicate with the graphics t e r m i n a l . The normal mode of operation i s f o r a program being run at the 3270 to generate data which i s t r a n s m i t t e d to the graphics computer for d i s p l a y . Refer to reference [ 4 ] f o r more d e t a i l s . 3*2 A2 The GRAPH Sup.er.isgr Program When the GGRAM system i s running, l o c a l c o n t r o l of the graphics t e r m i n a l i s handled by the GRAPH* supervisor program [ 4 ] , A number of FORTRAU-caliable r o u t i n e s [5] have been w r i t t e n to allow users to communicate with t h i s s upervisor program. The supervisor program d i s p l a y s an image on the graphics screen by continuously scanning a 6000 word d i s p l a y b u f f e r . Each word i n the d i s p l a y b u f f e r contains an i n s t r u c t i o n . These i n s t r u c t i o n s i n c l u d e ones f o r moving the l i g h t beam to a c e r t a i n p o i n t , "drawing" the beam to a c e r t a i n p o i n t , c o n t r o l l i n g dashing and s c a l i n g , enabling or d i s a b l i n g the l i g h t pen, and so *from g r a p h i c s , not graph theory. 34 f o r t h . To produce an image on the graphics screen s p e c i a l r o u t i n e s must be used to produce words which are properly formatted f o r the d i s p l a y b u f f e r . one r o u t i n e i s used f o r c o n t r o l words (e.g. i n t e n s i t y ) , another i s used f o r draws and moves, and a t h i r d i s used f o r t e x t . This i n f o r m a t i o n i s put i n t o an array as an image i s being b u i l t up. When a group of i n s t r u c t i o n s i s ready to be t r a n s f e r r e d to the d i s p l a y b u f f e r , a r o u t i n e i s c a l l e d to carry out the t r a n s f e r . Another routine i s supplied to detect pushbutton depressions and l i g h t pen h i t s , and read the d i a l s . li . 2 ^ 3 E f f e c t of Hardware and Software on the System As f a r as the a c u t a l program i s concerned, the hardware and s u p p l i e d software have i n some ways d i c a t a t e d the design of c e r t a i n i n t e r n a l s t r u c t u r e s . For example, the methcd of r e t u r n i n g the l o c a t i o n of a l i g h t pen h i t suggests the n e c e s s i t y of s t r u c t u r e s l i k e the "shadow b u f f e r " and the " s c r a t c h b u f f e r " (see below). A l s o , i n order to erase an image from the screen, the system must know the l o c a t i o n , i n the d i s p l a y b u f f e r , cf the i n s t r u c t i o n s that are producing t h a t image. Thus, f o r each item t h a t might be erased, the system must keep track of a s t a r t i n g and ending l o c a t i o n . This has meant that such values are kept f o r v e r t i c e s , edges, l a b e l s , and various other displayed o b j e c t s . The only major problem with the graphics t e r m i n a l , at l e a s t 35 as f a r as t h i s implementation i s concerned, i s that a character generator i s not i n c l u d e d . This means that a l l characters must be generated by software as a s e r i e s of short l i n e s . Characters generated i n t h i s way tend to re q u i r e a r e l a t i v e l y large number of d i s p l a y i n s t r u c t i o n s . Since the system menu c o n s i s t s i n l a r g e part of c h a r a c t e r s , the d i s p l a y b u f f e r contains a s i g n i f i c a n t number of d i s p l a y i n s t r u c t i o n s even before any graphs are drawn. T h i s , combined with the f a c t that the Adage uses a refreshed screen, causes the screen to begin t c f l i c k e r when la r g e graphs are drawn. In f a c t , the s i z e l i m i t of graphs seems to depend more on t h i s f a c t o r than on other f a c t o r s such as memory a v a i l a b i l i t y ; the f l i c k e r becomes too o b j e c t i o n a b l e long before the d i s p l a y buffer becomes f u l l . For users who can stand the f l i c k e r , the s i z e l i m i t f o r graphs i s very reasonable. The l a r g e s t graph a c t u a l l y drawn to date contained 200 v e r t i c e s and 100 edges. An approximate upper bound on the s i z e of undirected and unlabeled graphs i s im p l i e d by the i n e q u a l i t y (3+s)? + (3+e) E < 3500, where V i s the number cf v e r t i c e s , E i s the number of edges, s i s the average number of s i d e s to a vertex, and e i s the average number of edge s e c t i o n s i n an edge. So, f o r example, i f v e r t i c e s were drawn as t r i a n g l e s (s=3) and a l l edges were drawn as one s t r a i g h t l i n e between v e r t i c e s (e=1), then i t would be p o s s i b l e to draw a graph with 300 v e r t i c e s and 425 edges! 36 This l i m i t i s reduced co n s i d e r a b l y i f l a b e l s are i n c l u d e d , s i n c e , as mentioned above, characters tend to r e g u i r e a large number of d i s p l a y i n s t r u c t i o n s . A f u r t h e r reduction i s encountered i f d i r c t e d edges (with arrows) are considered. For example, i f a l l v e r t i c e s and edges i n a graph are l a b e l e d (and d i s p l a y e d ) , and there are an average of twc characters per l a b e l , and we assume that v e r t i c e s are t r i a n g l e s and edges are d i r e c t e d but not free-hand, then a graph with 60 v e r t i c e s and 74 edges could be drawn. System response time i s u s u a l l y e x c e l l e n t , and i s even very good when the operating system i s busy. This allows graphs to be drawn and manipulated very q u i c k l y , e s p e c i a l l y by users f a m i l i a r with the system. The GGRAM system i s r e l a t i v e l y expensive to use, but not e x c e s s i v e l y expensive. During a t y p i c a l one hour run a user can expect that about 32 per cent of the cost w i l l be f c r connect time, 2 per cent f o r s i g n i n g on to the operating system and loading the system, and 66 per cent f c r CPU time and memory usage. The a c t u a l cost cf preparing and p l o t t i n g f i g u r e 7, f o r example, was 18 computer d o l l a r s . This can be compared with a cost of 12 computer d o l l a r s f o r compiling the system i t s e l f . 3 7 3*3 DATA STRUCTURES There are three important data s t r u c t u r e s w i t h i n the system. They are the i n t e r n a l r e p r e s e n t a t i o n of graphs, the shadow b u f f e r , and the s c r a t c h b u f f e r . 3_i3_il I n t e r n a l Representation of Graphs The most important s t r u c t u r e s , cf course, are those s t r u c t u r e s used f o r s t o r i n g graphs. There are f i v e types of record c l a s s e s a s s o c i a t e d with graphs. Figures 1 through 5 shew the contents of each record type and what the f i e l d s are used f o r . At the top l e v e l i n the s t r u c t u r e i s the GRAPH record, which contains g l o b a l information about the graph such as the t i t l e , the number of v e r t i c e s , and so on. I t also contains a po i n t e r to a l i s t of VERTEX records. Each VERTEX record contains information l o c a l to the vertex as w e l l as three p o i n t e r s t c i n c i d e n t edges: the undirected edges, the i n d i r e c t e d edges, and the o u t d i r e c t e d edges (c.f. [ 1 2 ] ) . These p o i n t e r s , however, do not point d i r e c t l y to EDGE records, but i n s t e a d point to EDGEDES (edge d e s c r i p t o r ) records. Since each edge i s connected to two (net n e c e s s a r i l y d i s t i n c t ) v e r t i c e s , i t would be wasteful to have two copies cf a l l the info r m a t i o n f o r each edge. Having two copies would also complicate changing an edge. Therefore, a VERTEX points tc a l i s t of EDGEDES records, and each EDGEDES record i n turn points to i t s a ssociated EDGE. Each EDGEDES record a l s o has a p c i n t e r 38 INTEGER GNUM STRING (40) GTITLE INTEGER NVERTICES INTEGER NEDGES INTEGER NDIREDGES INTEGER NLOOPS INTEGER NHULTEDGES LOGICAL CHANGED INTEGER LABDISP INTEGER CODNTER REFERENCE (VERTEX) VLIST REFERENCE (GRAPH) NEXTGRAPH REFERENCE (GRAPH). LASTGRAPH INTEGER TSTART INTEGER TEND graph number graph t i t l e no. of v e r t i c e s no. of edges no. of d i r e c t e d edges no. of loops no. of m u l t i p l e edges changed? f l a g l a b e l d i s p l a y i n d i c a t o r ( l a b e l mode) count of components po i n t e r to vertex l i s t p o i n t e r to next graph i n graph l i s t p o i n t e r to previous graph i n graph l i s t s t a r t of t i t l e i n b u f f e r end of t i t l e i n b u f f e r Figure 1 - The F i e l d s i n a GRAPH Record 39 INTEGER VNUM STRING (8) VLABEL INTEGER DEGREE REFERENCE (EDGEDES) DNEDGES INTEGER INDEGREE REFERENCE (EDGEDES) INEBGES INTEGER OOTDEGREE REFERENCE (EDGEDES) OUTEDGES REAL VINTENSITY LOGICAL VSOLID INTEGER VSHAPE REAL VSIZE REAL XVER REAL YVER REAL XVLAB REAL YVLAB REFERENCE (VERTEX) NEXTVERTEX REFERENCE(VERTEX#GRAPH) LASTVERTEX REFERENCE (VERTEX) DOPTEHP INTEGER VSTART INTEGER VEND INTEGER VLSTART INTEGER VLEND vertex number vertex l a b e l degree pointer to l i s t of undirected edges indegree p o i n t e r to l i s t of i n d i r e c t e d edges outdegree po i n t e r to l i s t of ou t d i r e c t e d edges i n t e n s i t y s o l i d (or dashed)? shape (no. of sides) s i z e ("radius") x-coordinate of vertex y-coordinate of vertex r e l a t i v e x-coordinate of l a b e l r e l a t i v e y-coordinate of l a b e l p ointer to next vertex i n vertex l i s t p o inter to previous vertex i n vertex l i s t (points back to GRAPH i f f i r s t VERTEX i n l i s t ) " s c r a t c h " f i e l d used by c e r t a i n commands s t a r t of vertex i n buffer end of vertex i n b u f f e r s t a r t of l a b e l i n bu f f e r end of l a b e l i n bu f f e r Figure 2 - The F i e l d s i n a VERTEX Record 40 INTEGER ENDM STRING (8) ELABEL INTEGER ETYPE REAL EINTENSITY LOGICAL ESOLID INTEGER NCONSPTS REFERENCE (CONSPT) CONSLIST REAL XELAB REAL YELAB REFERENCE(EDGEDES) POSDES REFERENCE (EDGEDES) NEGDES INTEGER ESTART INTEGER EEND INTEGER ELSTART INTEGER ELEND edge number edge l a b e l edge type i n t e n s i t y s o l i d (or dashed)? no. of c o n s t r u c t i o n points pointer to l i s t of c o n s t r u c t i o n points r e l a t i v e x-coordinate of l a b e l r e l a t i v e y-coordinate of l a b e l p o i n t e r to p o s i t i v e edge d e s c r i p t o r pointer to negative edge d e s c r i p t o r s t a r t of edge i n buf f e r end of edge i n buf f e r s t a r t of l a b e l i n buf f e r end of l a b e l i n b u f f e r Figure 3 - The F i e l d s i n an EDGE Record 41 REFERENCE (EDGE) EPTR REFERENCE (VERTEX) VPTR REFERENCE(EDGEDES) NEXTDES REFERENCE (EDGEDES) LASTDES poi n t e r to edge pointer to other adjacent vertex pointer to next edge d e s c r i p t o r i n the l i s t p o inter to previous edge d e s c r i p t o r i n the l i s t Figure 4 - The F i e l d s i n an EDGEDES Record REAL XCONS REAL ICONS REFERENCE (CONSPT) NEXTCONSPT x-coordinate of c o n s t r u c t i o n point y-coordinate of c o n s t r u c t i o n point p o i n t e r to next c o n s t r u c t i o n point i n the l i s t Figure 5 - The F i e l d s i n a CONSPT Record 42 to the second i n c i d e n t vertex. The EDGE records contain information l o c a l to edges, i n c l u d i n g the edge l a b e l , the edge type (undirected or d i r e c t e d ) , and so on. I f the edge i s a free-hand edge, then the EDGE record a l s o contains a p o i n t e r to a l i s t cf CONSPT (c o n s t r u c t i o n point) records. Each CCKSPT record i n t h i s l i s t simply contains the coordinates of one of the intermediate p o i n t s i n the free-hand edge. Figure 6 shows the complete l i n k s t r u c t u r e f c r a small graph. A l l GRAPHS that have been defined t c the system are kept on the "graph l i s t " . There are two ways to put a GRAPH on the graph l i s t : by using RESTORE or by simply s t a r t i n g t c draw i n a blank r e g i o n . The system keeps track of which graphs have been changed (a new graph i s considered to be changed), since these are the graphs a user w i l l l i k e l y consider saving at the end of a run. Graphs i n the system are stored as i f they had been drawn i n a u n i t square. When they are displayed they are scaled according to the s i z e of the appropriate region. The i n t e r n a l coordinates of vertex l a b e l s are r e l a t i v e t o the centre cf the ver t e x ; the i n t e r n a l coordinates of edge l a b e l s are r e l a t i v e to G R A P H V E R T E X ! fj£KTVegT£)C L/\ST.pgs V E R T E X 2 EDGEDES E P T K EPT« Pospes BD&E OUTCJOES OWS LXST KteXTGowSPT C.OMSPT COMSPT -]/' NULL PblMTER. F i g u r e 6 - The Lin k S t r u c t u r e of a Small Graph 4 4 the middle 2 of the edge. 3^3*2 Shadow Buffer The image on the graphics t e r m i n a l ' s screen i s produced from a 6000 word d i s p l a y buffer (or d i s p l a y program) which i s contained i n the graphics computer connected to the graphics t e r m i n a l . This d i s p l a y program c o n s i s t s of i n s t r u c t i o n s f o r moving the l i g h t beam, enabling and d i s a b l i n g dashing, enabling and d i s a b l i n g the l i g h t pen, and so f o r t h . Thus, to produce a p a r t i c u l a r image on the graphics screen, the appropriate i n s t r u c t i o n s must be i n s e r t e d i n t o t h i s b u f f e r . When a l i g h t pen " h i t " i s detected by the graphics t e r m i n a l , the value that i s returned to the system i s the index i n the d i s p l a y b u f f e r cf the vector that was being drawn when the h i t occurred, so, i n order to be able to t e l l what has been h i t , the system must somehow keep track of what i s i n each b u f f e r l o c a t i o n . Furthermore, i t i s d e s i r a b l e t c have a convenient method of f i n d i n g holes i n the b u f f e r , that i s , seguences of elements which are not being used. The shadow bu f f e r serves both these purposes. The shadow b u f f e r i s a s e r i e s of three p a r a l l e l a r r a y s , each of length 6001 ( l c g i c a l index 0 to 6000). They are implemented i n FOBTBAN s i n c e ALGOLW w i l l not support arrays t h i s 2 r e f e r to the LABEL command d e s c r i p t i o n i n Appendix I . 45 long. The f i r s t array holds the type of the e n t i t y , the second holds the number of the e n t i t y , and the t h i r d holds a pointer (where one e x i s t s ) to the e n t i t y . The f o l l o w i n g t a b l e shows the contents of the arrays f o r each e n t i t y type: | ENTITY | hole (button) 3 f i x e d menu item v a r i a b l e menu item CANCEL regi o n mark vertex edge vertex l a b e l edge l a b e l message misc. TYPE | NUMBER < 0 1 2 3 4 5 6 7 8 9 10 999 (see below) button nc. item no, item no. 0 region no. region no. region no. regio n no. region no. 0 0 | PCINTER (see below) NULL NULL NULL NULL NULL pointer t c VERTEX poi n t e r to EDGE pointer tc VERTEX pointer t c EDGE NULL NULL So, for example, i f a l i g h t pen h i t occurs at l o c a t i o n 500 i n the d i s p l a y b u f f e r , and i f l o c a t i o n 500 i n the type array c o n t a i n s 6 and l o c a t i o n 500 i n the number array contains 2, then we know that a vertex d i s p l y e d i n region two i s the e n t i t y that was h i t . Moreover, l o c a t i o n 500 i n the po i n t e r array contains a po i n t e r to that VERTEX. Holes i n the bu f f e r are tr e a t e d i n a s p e c i a l way. The f i r s t element of a hole holds the f o l l o w i n g i n f o r m a t i o n : the type i s the negative of the length of the hole; the number i s 3 l o g i c a l element 0 of the b u f f e r i s used to communicate inf o r m a t i o n about buttons. 46 the index of the s t a r t of the next hole; and the p c i n t e r i s the index of the s t a r t of the previous hole. A l l other elements of the hole are set to zero. Thus, the holes are connected together by way of a doubly l i n k e d l i s t . I n i t i a l l y the l i s t simply c o n s i s t s cf cne entry which i s 6000 elements long. Hhen a hole of a p a r t i c u l a r length i s needed, the l i s t i s scanned and the f i r s t hole which i s long enough i s used. I f the hole i s longer than i s needed, a new sho r t e r hole i s created. As holes are used and created i n t h i s way, the b u f f e r e v e n t u a l l y becomes fragmented. T h i s fragmentation i s minimized, however, i n the f o l l o w i n g way: when a new hole i s created (by the d e l e t i o n of an edge, f o r example), the system checks t c see i f a hole already e x i s t s e i t h e r i n f r o n t of or f o l l o w i n g the new hole. I f e i t h e r or both of these holes are present, a l l cf the holes are combined i n t o cne large hole. I f the system cannot f i n d a hole of the appropriate s i z e when i t needs one, then i t simply terminates execution. The system i s designed i n such a way th a t the b u f f e r can be co m p a c t i f i e d , and i n f a c t the dummy procedure COHEACTlFY e x i s t s and i s c a l l e d i n the system. As i t turns cut, though, a c o m p a c t i f i c a t i o n has never been needed, and so CCHPACTIFY has not been implemented. 47 l i l . . 3 Scratch B u f f e r The s c r a t c h b u f f e r i s used to temporarily hold data t h a t w i l l e v e n t u a l l y be sent t c the d i s p l a y and shadow b u f f e r s . The sc r a t c h b u f f e r i s a set of four p a r a l l e l arrays cf length 5 0 0 . L i k e the shadow b u f f e r , i t i s implemented i n FCRTBAN. As an image to be displayed i s being constructed, i n f o r m a t i o n i s put i n t o the s c r a t c h b u f f e r . One array holds the words that w i l l be sent to the d i s p l a y b u f f e r ; the other three arrays hold the type, number, and pointer that w i l l be sent to the shadow b u f f e r . For example, when a vertex i s tc be di s p l a y e d the f o l l o w i n g i n s t u c t i o n s are put i n t o the f i r s t array of the s c r a t c h b u f f e r : set i n t e n s i t y ; enable l i g h t pen; enable dashed l i n e s i f a dashed ver t e x ; move to the s t a r t of the ver t e x ; draw each s i d e of the vert e x ; and d i s a b l e dashed l i n e s i f a dashed v e r t e x . The appropriate type, number, and pointer are put i n the corresponding elements of the other three a r r a y s . At t h i s point the image i s ready to be t r a n s f e r r e d to the d i s p l a y b u f f e r , so an appropriate hole i s found and the t r a n s f e r i s made. At the same time the contents of the other arrays are t r a n s f e r r e d to the shadow bu f f e r . 48 3ii» OVERVIEW OF THE PROGRAM The s t r u c t u r e of the program i s qu i t e s t r a i g h t f o r w a r d . At the top l e v e l i s a d r i v e r r o u t i n e which simply i n i t i a l i z e s the g l o b a l v a r i a b l e s , s e t s up the screen, and then goes i n t o a loop which f i r s t determines the c o n t r o l mode ( l i g h t pen or keyboard), and then c a l l s the appropriate r o u t i n e . Looping continues u n t i l the system i s stopped. At the present time, only l i g h t pen mode i s implemented. The r o u t i n e which handles t h i s mode reads the graphics screen and then waits u n t i l a command i s s p e c i f i e d . When one i s s p e c i f i e d , the appropriate r o u t i n e i s c a l l e d . I t should be noted t h a t , whenever the graphics screen i s read, care must be taken not to accept i n v a l i d or unwanted input. Therefore, the l i g h t pen mode c o n t r o l routine w i l l not do anything unless a command i s s p e c i f i e d . Aside from a number cf u t i l i t y r o u t i n e s , the remainder of the program i s made up p r i m a r i l y of ro u t i n e s f o r the i n d i v i d u a l commands. There are a l s o a group of ro u t i n e s associated with d i s p l a y i n g and c o n s t r u c t i n g graphs. These i n c l u d e r o u t i n e s f o r s c a l i n g graphs f o r d i s p l a y i n a p a r t i c u l a r r e g i o n , and r o u t i n e s f o r adding v e r t i c e s and edges to the i n t e r n a l graph s t r u c t u r e s , among others. The program l i s t i n g has not been included with t h i s t h e s i s because i t i s too long. I t i s a v a i l a b l e on request from the 49 Department of Computer Science of The U n i v e r s i t y of E r i t i s h Columbia. 50 CHAPTER IV - IMPROVEMEMTS AND EXTENSIONS The primary goal throughout the development of the GGRAM system has been to provide a system f o r q u i c k l y and conveniently drawing and manipulating graphs. Although t h i s goal has been achieved, there are s t i l l a number of refinements which could be made to improve the system's performance. Some cf these improvements are mentioned below. Bore i m p o r t a n t l y , though, there are a number of ways the system could be extended i n order to i n c r e a s e i t s usefulness. Some of these extensions are also discussed below. IMPROVING THE EXISTING SYSTEM An annoying c h a r a c t e r i s t i c of the system i s that an ob j e c t i o n a b l e f l i c k e r develops on the screen as graphs are drawn. As mentioned i n Chapter I I I , t h i s i s made worse than i t might be because the menu needs a large number of d i s p l a y i n s t r u c t i o n s . One way t o delay the onset of f l i c k e r i n g i s to reduce the number of characters i n the menu. This could be done by simply a b b r e v i a t i n g commands. For example, DUPLICATE might become DUP. This would have an a d d i t i o n a l advantage. I f names i n the menu were shortened, then the width of the menu area 51 could be decreased, r e s u l t i n g i n a l a r g e r drawing area. Abbreviated commands, of course, would compound the problems of l e a r n i n g t o use the system. To overcome t h i s , i t would be f a i r l y easy to allow two forms of the menu, one abbreviated and one not. I f the abbreviated menu were the d e f a u l t , the system could allow the user to change to the f u l l menu u s i n g , say, the SET command. Another s l i g h t l y annoying system c h a r a c t e r i s t i c i s that when REPEAT i s on, an a c t i v a t e d menu item must be e x p l i c i t l y turned o f f before a new item i s a c t i v a t e d . I t would be n i c e r i f the act of choosing a new command i m p l i c i t l y released the repeat s t a t u s of any other command which happened to be a c t i v a t e d . This would speed up the graph drawing process s l i g h t l y . U A 2 EXTENSIONS There are two d i s t i n c t problems which a system f o r "graph theory" might be concerned with. One i s graph manipulation, and t h i s i s the problem at which the GGBAM system i s aimed. An e q u a l l y important problem i s the automatic d i s p l a y cf a r b i t r a r y a b s t r a c t l y defined graphs. An a b s t r a c t l y defined graph i s one where l o g i c a l connections of v e r t i c e s are defined, but layout i s not. For inst a n c e , an adjacency matrix represents an a b s t r a c t l y defined graph. As mentioned i n Chapter I , however, the most n a t u r a l way to present a graph to a person i s by way of a 52 diagram. I t would be convenient, t h e r e f o r e , to be able to produce a s u i t a b l e diagram from an a b s t r a c t d e f i n i t i o n cf a graph. Of course, the question immediately a r i s e s as tc j u s t what the p r o p e r t i e s of a " s u i t a b l e " graph are. One common c r i t e r i o n used i s that such a graph should have a minimum cf edge-c r o s s i n g s . But the layout of v e r t i c e s i n i t s e l f can be important. For example, many b i p a r t i t e graphs are best d i s p l a y e d as two rows of v e r t i c e s , not n e c e s s a r i l y with edge-c r o s s i n g s minimized. The i m p l i c a t i o n , then, i s that the automatic d i s p l a y of of a r b i t r a r y graphs i s a d i f f i c u l t problem. But how could a f a c i l i t y f o r a u t o m a t i c a l l y d i s p l a y i n g graphs be embedded i n , or combined with, a graph manipulation system? For c e r t a i n c l a s s e s of graphs, such as c y c l e s or complete graphs, a simple generation algorithm could be devised and simply added as a new system command. The only input needed f o r such commands would be the number of v e r t i c e s d e s i r e d . For more complicated graphs, the system would f i r s t have t c have a f a c i l i t y f o r e n t e r i n g the a b s t r a c t graphs. This would be r e l a t i v e l y easy to provide. a l s o , since the most s u i t a b l e diagramatic r e p r e s e n t a t i o n of a graph depends on i t s p r o p e r t i e s , there must be a way t o determine the p r o p e r t i e s cf a given (abstract) graph. This would i n v o l v e providing property recognizers f o r a l a r g e number of p r o p e r t i e s , but such rec o g n i z e r s would be easy to incorporate i n t o a graph 5 3 manipulation system. I t i s an open question as to where to proceed from t h i s p o i n t . Perhaps the most s t r a i g h t f o r w a r d way, but not n e c e s s a r i l y the best, would be to implement a number of algorithms f o r d i s p l a y i n g c e r t a i n s p e c i f i c c l a s s e s of graphs, an a b s t r a c t graph to be displayed could then be passed t c each i n t u r n . Each would t e s t to see i f the graph belonged to i t s c l a s s and, i f so, would process the graph. Of course, something would have to be done i f the graph did net f i t i n t o any of the c l a s s e s f o r which a d i s p l a y algorithm e x i s t e d . an u n s o p h i s t i c a t e d system might simply r e j e c t the graph. Whatever the approach, though, i t does not seem l i k e l y that many d i f f i c u l t i e s would be encountered i n c o r p o r a t i n g automatic graph d i s p l a y f a c i l i t i e s i n t o a graph manipulation system, assuming the graph-theoretic problems could be overcome. a f t e r a l l , the automatic d i s p l a y r o u t i n e s would simply be programs operating on some s o r t of an i n t e r n a l r e p r e s e n t a t i o n , l i k e l y a matrix. One important reason f o r combining graph manipulation and graph d i s p l a y f a c i l i t i e s i n t o one system i s that the twc would complement each other. Fcr example, a user might want to draw a graph which i s "almost" a complete twenty vertex graph. In a combined system, he could a u t o m a t i c a l l y d i s p l a y a complete twenty vertex graph and then use the manipulation f a c i l i t i e s to change the graph s l i g h t l y . On the other hand, a user might draw 54 a rough v e r s i o n of a graph, and then use the graph d i s p l a y f a c i l i t i e s to generate a neater v e r s i o n . A number of p o s s i b l e extensions concern the a d d i t i o n of us e r - w r i t t e n r o u t i n e s to a graph manipulation system. The a b i l i t y to add new ro u t i n e s i s c r u c i a l to a f l e x i b l e system. The GGRAM system, as w e l l as the systems of Wolfberg [ 2 0 ] and Maguire [ 1 2 ] , a l l provide t h i s f a c i l i t y a t a very low l e v e l . T his simply i n v o l v e s a l l o w i n g a user t o l i n k a new routine i n t o the system by re-compiling some or a l l of the system. No debugging f a c i l i t i e s , except perhaps a command f o r dumping graph s t r u c t u r e s , are provided. An important extension to a graph manipulation system wculd be a set of comprehensive f a c i l i t i e s f o r debugging u s e r - w r i t t e n r o u t i n e s . Many f a c i l i t i e s of t h i s type can be envisioned. one i s t h a t a user might be provided with a means of scanning i n t e r n a l s t r u c t u r e s ( l i k e graphs) i n a way more f l e x i b l e than a simple dump. Of course, with a graphics system a displayed image can be a good i n d i c a t o r f o r t e l l i n g whether cr net a p a r t i c u l a r r o u t i n e i s working. Often, however, the exact cause of t r o u b l e cannot be pinpointed by l o o k i n g at the image. Another extremely u s e f u l debugging f a c i l i t y would be the p r o v i s i o n of an i n t e r p r e t e r f o r the language i n which the system i s implemented. With such a f a c i l i t y , a user could i n t e r p r e t (rather than compile and execute) new r o u t i n e s , and gain the associated advantages. These advantages in c l u d e the prospect of 55 b e t t e r run-time d i a g n o s t i c s , and the a b i l i t y to dynamically a l t e r r o u t i n e s without having to re-compile. Of course, the a d d i t i o n of such a f a c i l i t y would be a major p r o j e c t i n i t s own r i g h t . One way to make i t mere convenient to add u s e r - w r i t t e n r o u t i n e s i s to make the i n t e r n a l design of the system as transparent as p o s s i b l e t c the user. This can be done by p r o v i d i n g a set of appropriate (w e l l chosen) system r o u t i n e s to perform graph-theoretic and u t i l i t y f u n c t i o n s . Another way i s to extend the implementation language to include graph-theoretic operations and s t r u c t u r e s . This i s what wolfberg [20] has done i n h i s graphics system. Other language extensions, without graphics, have a l s o been developed [11,18,16,6]. The extensions which f o l l o w are more s p e c i f i c i n nature than the previous ones. These are m o d i f i c a t i o n s which could be made, without too much t r o u b l e , to increase system performance. At the moment, only one of the s i x t e e n pushbuttons at the graphics t e r m i n a l i s used. I t would be convenient i f the remaining buttons could be defined to be equivalent tc an a r b i t r a r y menu item. In ether words, pushing such a button would have the same e f f e c t as h i t t i n g the associated menu item with the l i g h t pen. The "add vertex" and "add edge" commands are prime candidates f o r such a f e a t u r e . Another improvement could be made by providing a r o u t i n e 56 f o r the input of characters using the l i g h t pen rather than the keyboard. Thus, when a t i t l e or l a b e l i s t c be entered, a "keyboard" could be displayed on the screen and the l i g h t pen used to choose p a r t i c u l a r c h a r a c t e r s . This would be p a r t i c u l a r l y u s e f u l with the e x i s t i n g hardware because the keyboard i s p h y s i c a l l y s i t u a t e d to the r i g h t of the user. This means that right-handed users must put down the l i g h t pen and reach over to enter a l a b e l or t i t l e . N a t u r a l l y t h i s i s a nuisance i f i t i s necessary to repeat i t more than a few times. I t would a l s o be d e s i r a b l e i f a r o u t i n e were w r i t t e n to smooth free-hand edges. This idea could be extended by p r o v i d i n g an i n t e r n a l switch which could be turned cn cr e f f . When on, a l l free-hand edges would a u t o m a t i c a l l y be smoothed when drawn. One of the i n t e r e s t i n g f e a t u r e s of the system developed by Maguire [12] i s the a b i l i t y to a s s o c i a t e property l i s t s with v e r t i c e s and edges (see Chapter I ) , The number and types of these p r o p e r t i e s can be changed dynamically as the system runs. This f e a t u r e can be p a r t i a l l y simulated with l a b e l s , but such an approach e s s e n t i a l l y l i m i t s a component to cne property. Numerical l a b e l s on arcs c c u l d be converted to numbers to be used as c a p a c i t i e s i n networks, f o r example. But the a b i l i t y to a s s o c i a t e a number of p r o p e r t i e s with a vertex or an edge would s i g n i f i c a n t l y improve the system f o r c e r t a i n a p p l i c a t i o n s . F i n a l l y , i t i s i n t e r e s t i n g to consider whether or not a 57 f a c i l i t y analogous to R c l f b e r g ^ "windows" [ 2 0 ] (see also Chapter I) would be worthwhile implementing. I t appears that i t would be worthwhile f o r at l e a s t two reasons. F i r s t , the a b i l i t y to look at a magnified p o r t i o n of a graph can be very u s e f u l . I t can, f o r example, l e t users draw l a r g e , d e t a i l e d graphs which would be d i f f i c u l t otherwise. This c c u l d be done by drawing a number of hi g h l y magnified subgraphs which would then be combined to form the t o t a l graph. Second, windowing could serve to reduce the e f f e c t of screen f l i c k e r by a l l o w i n g users to d i s p l a y only the p o r t i o n of a graph which i s i n use. This, again, would be u s e f u l f c r l a r g e graphs. i b J SUMMARY In t h i s study the design and implementation of an i n t e r a c t i v e graphics system f o r graph manipulation have been examined. The p r i n c i p a l aim of the system i s to f a c i l i t a t e the drawing and manipulation of graphs. To t h i s end, a comprehensive graph drawing c a p a b i l i t y i s provided. This i n c l u d e s the bas i c operations of adding, d e l e t i n g , l a b e l i n g , and changing both v e r t i c e s and edges. Also i n c l u d e d are a group of graph manipulation operations. These operations, among ether t h i n g s , allow a user t c subdivide edges, a s s o c i a t e v e r t i c e s , reverse the d i r e c t i o n of a r c s , move v e r t i c e s about the screen, or even move whole graphs about the screen. 5 8 A f a c i l i t y i s provided whereby the screen can be div i d e d i n t o as many as four regions, thus a l l o w i n g users t c d i s p l a y more than one graph at a time. Graphs can be saved on disk and l a t e r restored. The image on the graphics screen can be e a s i l y p l o t t e d to obtain a hard copy of graphs. A number of r o u t i n e s which perform graph-thecretic operations have been implemented. Among these are a ro u t i n e to f i n d the minimum and maximum degrees of a graph and a routine to f i n d the blo c k s , cutnodes, and bridges of a graph. Moreover, the system i s designed t o allow users to add t h e i r own r o u t i n e s . 59 BIBLIOGRAPHY [ 1 ] Bauer, H. R. ; et a l . , ALGOLS Programming Manual, Univ. of Newcastle Upon Tyne Computing Laboratory, 1970. [ 2 ] C h o i t , M.D. (ed.). The MTS Commands Manual, Univ. of B r i t i s h Columbia Computing Centre, 1970. [ 3 ] Coulthard, W.J., Operator's Manual f o r the Adage Graphics Terminal, Univ. cf B r i t i s h Columbia Computing Centre, 1970. [ 4 ] Coulthard, W.J., A Simple I n t e r a c t i v e Graphics Package, Univ. of B r i t i s h Columbia Computing Centre, 1971. [ 5 ] Coulthard, W.J. ; DeKleer, J . , Basic Communications Package for the Adage Graphics Terminal, Univ. of E r i t i s h Columbia Computing Centre, 1971. [ 6 ] C r e s p i - R e g h i z z i , S.; Mcrpurgo, R., A language f o r t r e a t i n g graphs, Comm^ A^C^M^ 13, 5 (May 1970), 319-323. [ 7 ] Di G i u l i o , H, A.; Tuan, P.L., A graph manipulator f o r on-l i n e network p i c t u r e p r o c e s s i n g , Proc. AFIPS 1969 FJCC, 387-398.. [ 8 ] Dixon, M.R., ALGOLS Compilers, Univ. of B r i t i s h Columbia Computing Centre, 1971. [ 9 ] Harary, F., Graph Theory, Addison-Wesley, Reading, Massachusetts, 1969. [10] Higginson, M., Extensions to ALGOLW, Tech. Report TR73-19, Dept. of Computing Science, Univ. of A l b e r t a , 1973. 60 [11] King, C.A., A graph-theoretic programming language, i n Graph Theory and Computing, by B.C. Read (ed.), Academic Press,~New York, 1972. [12] Maguire, R.B., The GSYM System: An I n t e r a c t i v e System f o r Di s p l a y i n g Linear Graphs, Tech. Report CS-73-24, Univ. of Waterloo, 1973. [13] M i l l e r , R.B., Response time i n man-computer c o n v e r s a t i o n a l t r a n s a c t i o n s , Proc., AFIPS J 9 6 8 FJCC, 267-277. [14] Newman, W.M.; S p r o u l l , R.F., P r i n c i p l e s of I n t e r a c t i v e Computer Graphics, McGraw-Hill7~New~York, *1973. [15] Osborne, E.J., Using MTS from the IBM 3270 Display S t a t i o n , Univ. of B r i t i s h Columbia Computing Centre, 1973. [16] P r a t t , T.W.; Friedman, D.P., A language extension f o r graph processing and i t s formal semantics. Comm. A.CM. 14, 7 (July 1971) , 460-467. [17] Read, R.C, Teaching graph theory to a computer, i n Recent Progress i n Combinatorics, by W.T. Tutte (ed.), Academic Press,~New York, 1969. [18] Rheinboldt, W.C; B a s i l i , V.R. ; Mesztenyi, C.K., On a programming language f o r graph al g o r i t h m s , EIT J.2, (1972), 220-241. [19] Smith, L.B., A survey cf i n t e r a c t i v e g r a p h i c a l systems f o r mathematics, Commuting Surveys 2, 4 (Dec. 1970), 261-301. [20] Wolfberg, M.S., An I n t e r a c t i v e Graph Theory System, Doctoral D i s s e r a t i o n , Univ. of Pennsylvania, 1969. APPENDIX I - USER'S GUIDE 61 INTRODUCTION This Guide presupposes f a m i l i a r i t y with MTS [ 2 ] , the 3270 t e r m i n a l [ 1 5 ] , the Adage graphics t e r m i n a l [ 3 ] , and the GRAPH supe r v i s o r program f o r the Adage graphics t e r m i n a l [ 4 ] , The system can be run by i s s u i n g the f o l l o w i n g MTS command: SSOURCE HUMP:GRAPH The message READY, which appears at the top of the menu, begins b l i n k i n g when the system i s ready. Users sould note t h a t the GRAPH sup e r v i s o r program may have to be loaded i n t o the graphics computer before running the system. Refer to reference [ 3 ] f o r d e t a i l s . Users who wish to experiment with the system without f i r s t r eading a l l of the ma t e r i a l that f o l l o w s i n t h i s Guide are advised to read the i n t r o d u c t o r y remarks and the f o l l o w i n g command d e s c r i p t i o n s : READY, STOP, RUB OUT, CANCEL, A l t , DELETE, and REPEAT. With t h i s minimal amount of information a user should be able to draw graphs, erase graphs, and stop when f i n i s h e d . SCREEN LAYOUT Figure 7 shows what the Adage screen looks l i k e when the system i s running, i n c l u d i n g some sample graphs. The l a r g e s t p o r t i o n of the screen i s the drawing area . This i s the area where graphs are a c t u a l l y drawn. i n the f i g u r e , the drawing area has been d i v i d e d i n t o three regions by using the REGIONS command. In i t s i n i t i a l s t a t e , the drawing area i s not d i v i d e d , t h a t i s , i t i s simply t r e a t e d as one, large r e g i o n . The s i z e cf the regions can be v a r i e d by changing the region i n t e r s e c t i o n p o i n t . This i s one cf the f u n c t i o n s of the SET command. One of the regions on the screen i s considered to be the current region or current area. When there i s only cne re g i o n , then t h a t r e g i o n , of course, i s the current area. When the drawing area i s d i v i d e d i n t o two or more re g i o n s , the current area i s surrounded by bold face l i n e s . The current area i s used by c e r t a i n f u n c t i o n s when a p a r t i c u l a r region must be s p e c i f i e d . For example, when RUB OUT i s a c t i v a t e d , the graph i n the current area i s erased. 62 DRAWING-AREA lN)T6RSeCTIOW POIMT P A T T E R N M A R K RERDY RESIBN5<D BB a B HUB HET8BBRD mp 3 TCP SET vara ase PLOT iflVE BE3TBRE TITLE CWPH D I 9 P L A T RUB OUT DUPLICATE HOC CRNCEL RESET D BOLD • „ D • • DR5HED • a mm. a V D D a D FED D DELETE D LRBEL D UfWSE REPEfiTl SUBDIVIDE ED6E REMWE DEGREE Zl H9S0CIHTE VERTICES REVERSE PRC UH01R <—> DIR LOCK M VERTU LOW OH 6RFH>H VERTU MESSAGE MORmAL. F C £ E - H ^ W J > EDG-E E3X*E P R O T O T Y P E (videcren MOVE ) V E R T E X P R O T O T Y P E F i g u r e 7 - The Screen When the System i s Running 63 When there are two cr more regions, a region number or £§2i2S !§£]£ appears i n the top r i g h t corner of each region. The region mark i s used both to change the current area and to s p e c i f y a p a r t i c u l a r region f o r c e r t a i n commands. To change the cur r e n t area, a user simply " h i t s " , with the l i g h t pen, the region mark of the region which i s d e s i r e d . The r i g h t hand s i d e of the screen i s reserved f c r the menu. The upper part of the menu area contains the f i x e d menu. This menu does not change as the system operates. I t i n c l u d e s commands t h a t are of general u t i l i t y , such as PLOT (for p l o t t i n g the screen) and SAVE and RESTORE (for saving graphs cn disk and l a t e r r e s t o r i n g them). The lower part of the menu area i s f o r the v a r i a b l e menu. The v a r i a b l e menu can be changed so that i t con t a i n s e i t h e r the draw menu or the f u n c t i o n menu. As i t s name i m p l i e s , the draw menu i n c l u d e s commands f o r drawing and a l t e r i n g graphs, i n c l u d i n g such things as adding and d e l e t i n g both v e r t i c e s and edges. The f u n c t i o n menu contains commands f o r invoking graph-theoretic algorithms. These, f o r example, i n c l u d e a command f o r determining the maximum and minimum degrees of a graph, and a command f o r f i n d i n g the b l o c k s , cutnodes, and bridges of a graph. The v a r i a b l e menu can be changed using the DRAW cr FUNCTION commands which appear i n the f i x e d menu. Menu items t h a t are i n e f f e c t or i n use are di s p l a y e d i n bold f a c e . At the bottom of the screen i s a narrow area c a l l e d the Message area. This area i s used f o r d i s p l a y i n g i n s t r u c t i o n s , warnings, e r r o r messages, and so on. When the system i s s t a r t e d , the drawing area i s empty except f c r the t r a c k i n g p a t t e r n , which appears i n the centre of the screen. The t r a c k i n g p a t t e r n i s a set of three c o n c e n t r i c octagons with a dot i n the centre. This pattern can be moved around the screen using the l i g h t pen. When the l i g h t pen touches one of the l i n e s on the perimeter of one cf the octagons, the pattern w i l l move i n that d i r e c t i o n . The system can determine where the centre of the pattern i s at any given time, and thus the t r a c k i n g pattern i s a convenient means to i n d i c a t e such things as the l o c a t i o n s of v e r t i c e s . As graphs are drawn, a user w i l l n o tice numbers appearing near the lower l e f t corner of the regions. The leftmost number i s the number of v e r t i c e s . The second number i s the number of edges. For d i r e c t e d graphs t h i s number in c l u d e s a count cf two f o r each undirected edge i n the graph. I f there are no edges, t h i s number does not appear. A t h i r d number, enclosed i n parentheses, appears f o r d i r e c t e d graphs. This number i s a count of the number of undirected edges. I t i s blank i f there are no undirected edges. 64 I/O METHODS There are two devices with which a user communicates with the system: the Adage graphics t e r m i n a l i t s e l f , and the IEM 3270 t e r m i n a l which i s set up as an i n t e r f a c e between the graphics t e r m i n a l and the operating system, The primary output device i s , of course, the screen of the graphics t e r m i n a l , A small amount of info r m a t i o n a l s c appears from time to time on the 3270 screen. Most of the input t c the system i s supplied by way of the l i g h t pen. Some i n p u t , however, i s s u p p l i e d with pushbuttons and d i a l s connected to the Adage, and the keyboard connected to the 3270. Since the system cannot read from both devices at the same time, a user must be able to t e l l where the system i s expecting input from. When the system i s expecting input from the l i g h t pen (or the pushbuttons) the READY at the top of the menu s t a r t s b l i n k i n g . On the other hand, when input i s expected from the 3270 keyboard, a b l i n k i n g message i s d i s p l a y e d on the Adage screen and a message i s also displayed on the 3270 screen. I t . i s d e s i r a b l e to be able to issue a " c a n c e l " i n d i c a t i o n at both devices. This i s u s e f u l , f o r example, when a user changes h i s mind a f t e r i n i t i a t i n g an operation. The cancel i n d i c a t i o n f o r input from the Adage i s the menu item CANCEL, at the bottom of the f i x e d menu. To i s s u e a cancel i n d i c a t i o n at the 3270, a user must enter the current contents cf the parameter CANCELSTRING. I n i t i a l l y t h i s i s "CANCEL", but i t can be changed with the SET command. PROTOTYPES Since the p h y s i c a l appearance of v e r t i c e s and edges can be v a r i e d , a user should be able to see e a s i l y j u s t what t h e i r c u r r e n t c h a r a c t e r i s t i c s are. Fcr t h i s reason, a vertex prototype and an edge prototype are displayed i n the draw menu (see f i g u r e 7). These prototypes r e f l e c t the c u r r e n t s e t t i n g s of the i n t e n s i t y , dashing, and s i z e parameters associated with v e r t i c e s and/or edges. V e r t i c e s and edges drawn cn the screen w i l l look l i k e the prototypes. As explained below i n the command d e s c r i p t i o n s , v e r t i c e s and edges can be normal i n t e n s i t y , bold f a c e , dashed, or dashed and bold. Furthermore, the s i z e and shape of v e r t i c e s can be v a r i e d . The edge prototype a l s o serves to i n d i c a t e whether or not the system i s i n d i r e c t e d mode. In d i r e c t e d mode, a l l edges tha t are drawn are considered to be d i r e c t e d edges (or a r c s ) . The edge prototype i s a b i s t a b l e s w i t c h . I f h i t with the l i g h t pen when i n undirected mode, the prototype w i l l change i n t o a d i r e c t e d edge and the system w i l l go i n t o d i r e c t e d mode; i f h i t 65 when i n d i r e c t e d mode, the prototype w i l l change back to an u n d i r e c t e d edge and the system w i l l r e t u r n to undirected mode. DIALS It i s d e s i r a b l e t o allow the user c o n t r o l over the r e l a t i v e i n t e n s i t y between normal and b o l d f a c e . T h i s i s accomplished using the v a r i a b l e c o n t r o l d i a l s . D i a l A (top l e f t ) c o n t r o l s normal i n t e n s i t y ; d i a l D (top r i g h t ) c o n t r o l s bold f a c e . So, i f d i a l A i s "turned up", a l l v e r t i c e s and edges cf normal i n t e n s i t y w i l l i n c r e a s e i n i n t e n s i t y . D i a l D does the same f o r bold face v e r t i c e s and edges. I f v e r t i c e s or edges do not appear on the screen when expected, i t may be because the d i a l s are s e t too "low", I t i s advised t h a t they be turned f u l l y c l o c k w i s e i n i t i a l l y , and then a d j u s t e d as d e s i r e d . DRAWING GRAPHS In order t o get a f l a v o u r as to how the system i s used, the f o l l o w i n g d e s c r i p t i o n i s i n c l u d e d t o i n d i c a t e how a graph i s drawn. In p a r t i c u l a r , the steps necessary to draw a graph l i k e the one i n r e g i o n 3 of f i g u r e 7 are d e s c r i b e d . Of course, the " f e e l " of the system can only be experienced by a c t u a l l y using i t [20, p. 172]. The f i r s t step i s to draw the v e r t i c e s . S i n c e a number of v e r t i c e s are to be drawn, REPEAT i s a c t i v a t e d by h i t t i n g i t with the l i g h t pen (at which time i t changes to b o l d f a c e ) . When REPEAT i s on, c e r t a i n commands ( i n c l u d i n g "add vertex") repeat u n t i l e x p l i c i t l y turned o f f . Now, by a c t i v a t i n g the s m a l l sguare to the r i g h t of ADD (underneath the vertex p r o t o t y p e ) , the system i s put i n t o "add v e r t e x mode". At t h i s p o int, to add v e r t i c e s the t r a c k i n g p a t t e r n i s simply moved to p o s i t i o n s where v e r t i c e s are d e s i r e d and the draw b u t t o n 1 pressed. The number of s i d e s i n a v e r t e x can be decreased by h i t t i n g the "-" to the l e f t of SHAPE, and can be i n c r e a s e d by h i t t i n g the "+" to the r i g h t . The second step i s to draw the edges. To dc t h i s , "add v e r t e x " must f i r s t be turned o f f by h i t t i n g i t again with the l i g h t pen. Note that REPEAT remains on. "Add edge" can then be a c t i v a t e d using the square to tha l e f t of ADD (underneath the edge p r o t o t y p e ) . To draw the normal edges, the procedure i s to f i r s t h i t a "from" vertex (a b l i n k i n g c r o s s w i l l be d i s p l a y e d at the c e n t r e of the v e r t e x ) , and then h i t a " t o " vertex. When both v e r t i c e s have been s p e c i f i e d , the edge i s drawn. To draw *The draw button i s i n i t i a l l y button 1, a t the fop l e f t c o r n e r . 66 the free-hand edge, a "from" vertex i s f i r s t s p e c i f i e d i n the normal way. Each edge s e c t i o n can then be drawn by moving the t r a c k i n g p a t t e r n i n t u r n t o each i n t e r m e d i a t e p o i n t and p r e s s i n g the draw button. The edge i s completed by s p e c i f y i n g a " t o " vert e x . Dashed edges can be drawn a f t e r f i r s t h i t t i n g the small sguare t o the l e f t of DASHED, above the edge prototype. A user who i s f a m i l i a r with the system could draw t h i s graph i n about one minute. COMMANDS IN THE FIXED MENU • READY Purpose: To i n d i c a t e that the system i s ready to accept input (from the Adage) . D e s c r i p t i o n : When READY i s b l i n k i n g , the system i s waiting f o r input from the Adage. T h i s means t h a t a l i g h t pen h i t or a button depression w i l l be d e t e c t e d , but that keyboard i n p u t w i l l not be detected. READY w i l l appear with c o n s t a n t i n t e n s i t y when the system i s not waiting f o r Adage in p u t . 67 • REGIONS Purpose: To change how the drawing area of the screen i s di v i d e d i n t o regions. D e s c r i p t i o n : The drawing area can be d i v i d e d i n t o one, twc, three, or four regions by choosing one of the patterns that appear on the menu immediately to the r i g h t of REGIONS. Fcr example, the screen can be d i v i d e d i n t o two regions e i t h e r v e r t i c a l l y or h o r i z o n t a l l y . When there are twc cr more reg i o n s , the region number (or region mark) i s displayed i n the top r i g h t corner of the regio n , and the current area i s o u t l i n e d i n bold face. To change how the screen i s d i v i d e d , a user simply cheeses a new pattern with the l i g h t pen. When t h i s i s done, a l l graphs being d i s p l a y e d are rubbed out, and new region l i n e s are drawn. The system then r e - d i s p l a y s , on region one, the graph ( i f any) which was i n the current area when the new pat t e r n was chosen. The coordinates of the p o i n t of i n t e r s e c t i o n cf the h o r i z o n t a l and v e r t i c a l d i v i d i n g l i n e s are system parameters which can be changed using the SET cost Band. The de f a u l t l o c a t i o n i s the centre of the drawing area. • DRAW-FUNCTION Purpose: To put the system i n t o e i t h e r draw or f u n c t i o n uenu mode, th a t i s , t o set the v a r i a b l e menu. D e s c r i p t i o n : When the system i s i n draw mode, the draw menu i s displayed i n the v a r i a b l e menu area; s i m i l a r l y , when the system i s i n f u n c t i o n mode, the f u n c t i o n menu i s di s p l a y e d . To change to one of these modes a user simply a c t i v a t e s e i t h e r DRAW or FUNCTION. The draw menu contains f a c i l i t i e s f o r drawing and a l t e r i n g graphs. For example, "add vert e x " , "delete edge", and "reverse a r c " are included i n t h i s menu. 68 The f u n c t i o n menu c o n t a i n s f a c i l i t i e s f o r a p p l y i n g g r a p h -t h e o r e t i c a l g o r i t h m s t o a g i v e n g r a p h . These o p e r a t i o n s i n c l u d e s u c h t h i n g s a s p e r m u t i n g t h e v e r t e x l a b e l s o f a g r a p h and f i n d i n g t h e minimum and maximum d e g r e e s c f a g r a p h . F i g u r e 8 shows t h e menu i n b o t h draw and f u n c t i c n mode. • KEY BOARD 2 P u r p o s e : To p u t t h e s y s t e m i n t o k e y b o a r d mode. D e s c r i p t i o n : In k e y b o a r d mode, a u s e r communicates w i t h t h e s y s t e m u s i n g t h e k e y b o a r d r a t h e r t h a n t h e l i g h t pen. A l l r e g u l a r f a c i l i t i e s o f t h e s y s t e m a r e a v a i l a b l e i n k e y b o a r d mode t h r o u g h t h e use o f t y p e d commands. • HELP 3 P u r p o s e : To s u p p l y a u s e r w i t h i n f o r m a t i o n a b o u t t h e s y s t e m . D e s c r i p t i o n : When HELP i s a c t i v a t e d , t h e u s e r i s a s k e d a s e r i e s o f q u e s t i o n s t o d e t e r m i n e what i n f o r m a t i o n i s d e s i r e d . So, f o r example, i f a u s e r wants t o know how t h e EUPLICATE command works, HELP w i l l s u p p l y t h e n e c e s s a r y i n f o r m a t i o n . 2KEYB0ARD has n o t been i m p l e m e n t e d . 3 H E L P has n o t been i m p l e m e n t e d . READY RECISNSSD • B B B ED03 ~ DRRV FUNCTIDN KEYBOARD HELP STOP SET LABELS •• f L l L H a t L 3 UE3TCX EDGE PLOT SAVE RESTORE TITLE CRfiPH DISPLHY RU3 OUT DUPLICATE N3VE CANCEL RESET O BOLD D „ D O D DASHED D • NORMAL a — o _1»W£.t. • ROD • • DELETE O • LABEL O • CHANSE D REPEAT SUBDIVIDE EDGE REMOVE DE6REE 2 VERTEX ASSOCIATE VERTICES REVER9E HRC UNDIfl <—*• DIR VOCK DN VERTEX LOCK ON GRAPH READY RE6ICN5*D ID B B B HJLB DRAW FUNCTION KEYBOARD HELP STOP SET L R 8 E L 3 VEBTEJt EDGE PLOT SflVE RESTORE TITLE CRfiPH DISPLAY RU8 OUT DUPLICATE MOVE CANCEL GO MIN/MAX DEGREE PERMUTE LABELS PERMUTE COORDS gLaoM^cuTNiJoes/BRioeea Figure 8 - The DRAW and FUNCTICN Menus 70 - STOP Purpose: To stop the system. D e s c r i p t i o n : When STOP i s a c t i v a t e d , the system f i r s t asks f o r co n f i r m a t i o n . I f co n f i r m a t i o n i s re c e i v e d , the system does some "bookkeeping" associated with p l o t s and then execution i s terminated. I f the stop i s not confirmed, the system w i l l continue as i f nothing happened. • SET Purpose: To change various system parameters. D e s c r i p t i o n : When SET i s a c t i v a t e d , the names of a number cf system parameters are displayed on the screen. The l i g h t pen i s then used to choose the parameter to be changed. With one exception, the system then p r i n t s the current value of the parameter on the 3270 screen, and waits f c r the user to input a new value at the keyboard. I f at t h i s point the user enters "DEFftOLT" or "#", the parameter w i l l be set to i t s d e f a u l t value. The f o l l o w i n g l i s t contains those parameters which can be changed using SET. Unless otherwise i n d i c a t e d or i m p l i e d , the d e f a u l t values are expressed i n "normalized screen u n i t s " , that i s , i n r e l a t i o n to a u n i t (one inch) square. These values w i l l be s c a l e d a p p r o p r i a t e l y when a graph i s displayed on a p a r t i c u l a r region. XSCREEN/YSCBEEN ( d e f a u l t : centre of drawing area) These are the coordinates of the point of i n t e r s e c t i o n of the v e r t i c a l and h o r i z o n t a l d i v i d i n g l i n e s . The s e t t i n g of these parameters i s d i f f e r e n t from the s e t t i n g of the other parameters. 71 For these parameters, the new values are net typed at the keyboard, but instead the t r a c k i n g pattern i s used to l o c a t e the new i n t e r s e c t i o n p o i n t , Tc accomplish t h i s , the word "PATTERN" (or a b b r e v i a t i o n " E " ) i s used when the system asks f o r a new value. Thus, to set XSCREEN/YSCREEN a user inputs "DEFAULT" (or "#") i f the d e f a u l t l o c a t i o n i s d e s i r e d , cr "PATTERN" (or "P") i f the t r a c k i n g pattern l o c a t i o n i s desi r e d . When XSCREEN and YSCREEN are changed, a l l graphs on the screen are rubbed out, and the graph which was i n the current area i s re - d i s p l a y e d i n region one. ARRLEN ( d e f a u l t : 0 .02) This parameter helps determine the s i z e of the arrows used to show the o r i e n t a t i o n of d i r e c t e d edges ( a r c s ) . ARRLEN (arrow length) i s the length of the p r o j e c t i o n of the arrow's s i d e onto the associated arc. ARRWID (def a u l t : 0 .01) This parameter helps determine the s i z e cf the arrows used to show the o r i e n t a t i o n of d i r e c t e d edges ( a r c s ) . ARRWID (arrow width) i s the length of the p r o j e c t i o n of the arrow's s i d e onto a l i n e perpendicular t c the associated a r c . CANCELSTRING ( d e f a u l t : "CANCEL") The value of t h i s parameter i s used to cancel a operation when the system i s reading from the keyboard. I f , f o r example, the system i s waiting f o r a user to enter a graph t i t l e , then by en t e r i n g the current value cf CANCELSTRING the operation w i l l be c a n c e l l e d , and the graph's t i t l e w i l l be unchanged. I f a user wishes t c use "CANCEL" as a t i t l e or l a b e l , then CANCELSTRING can be changed t c allow t h i s . CANCELSTRING can be any non-blank character s t r i n g of length l e s s than or equal t o 8. LABDIS ( d e f a u l t : 1.0) This i s the length (in inches) that i s used to determine whether or not the d e f a u l t p o s i t i o n i s used 72 f o r l a b e l s . When l a b e l i n g a vertex or an edge, i f the t r a c k i n g p a t t e r n i s l e s s than IABDIS inches frcm the l a b e l i n g point* then the l a b e l i s placed at the centre of the t r a c k i n g p a t t e r n . Cn the other hand, i f the t r a c k i n g p a t t e r n i s more than LABDIS inches frcm the l a b e l i n g point (cr i n a d i f f e r e n t r e g i o n ) , then the l a b e l i s placed at the d e f a u l t l o c a t i o n . The d e f a u l t l o c a t i o n i s determined using the parameters XLAELOC and YLABLOC, which can al s o be changed using SET (see below) . XLABLOC ( d e f a u l t : -0.025) This parameter i s the r e l a t i v e x-coordinate of the d e f a u l t l a b e l l o c a t i o n (see a l s o the parameter LABDIS). I t i s added to the x-coordinate of the vertex or edge l a b e l i n g point t c obtain the x-coordinate of the (lower l e f t corner of the) l a b e l . YLABLOC ( d e f a u l t : 0.015) This parameter i s the r e l a t i v e y-coordinate of the d e f a u l t l a b e l l o c a t i o n (see a l s o the parameter LABDIS). I t i s added to the y-cccrdinate cf the vertex or edge l a b e l i n g point to obtain the y-coordinate of the (lower l e f t corner of the) l a b e l . LABEL HT (d e f a u l t : 0.15) This i s the height ( in inches) of l a b e l s t h a t are displayed cn the screen. DRABBUT ( d e f a u l t : 1) This parameter i s the number of the "draw button". I t can be any value from 1 to 18 i n c l u s i v e . The draw button i s used f o r two purposes. F i r s t , i t i s the button that i s depressed when i n "add vertex" mode to i n d i c a t e that a vertex should be drawn at the t r a c k i n g pattern l o c a t i o n . Second, i t i s used i n "add •The l a b e l i n g point of a vertex i s the centre cf the vertex; the l a b e l i n g point of an edge i s the "middle" cf the edge. Refer to the LABEL command d e s c r i p t i o n f o r a more d e t a i l e d explanation. 73 edge" mode to i n d i c a t e that a free-hand edge i s being drawn. (Note: the f o o t switches are t r e a t e d as "buttons" 17 and 18.) READWAIT ( d e f a u l t : 75) This parameter c o n t r o l s the delay between reads of the Adage screen. I t i s expressed as an i n t e g r a l number of 1/300's of a second. Thus the d e f a u l t wait i s 75/300 = 0.25 seconds. Every time the system attempts to read from the Adage screen, i t f i r s t performs a wait c a l c u l a t e d using EEADWAIT. This prevents m u l t i p l e l i g h t pen h i t s which can occur i f a user a c c i d e n t a l l y holds the l i g h t pen to an item too long. VINCREMENT ( d e f a u l t : 0.05) This i s the amount by which the s i z e cf the vertex prototype i s incremented or decremented when the SIZE command i s used i n draw mode. PLOTSIZE ( d e f a u l t : 10.0) This parameter i s the s i z e (in inches) of any p l o t s t h a t are produced. The p l o t s are scaled so that the enc l o s i n g sguare i s PLOTSIZE X PLOTSIZE inches. The d e f a u l t i s the a c t u a l s i z e of the image as i t appears on the graphics screen. Error Messages: INVALID REGION - TRY AGAIN Attempt to move (XSCREEN,YSCREEN) out of the drawing area. INVALID PARAMETER - TRY AGAIN An i n v a l i d parameter of some s o r t has been i n p u t . The p o s s i b i l i t i e s are: a r e a l number instead of an i n t e g e r , or v i c e versa; an attempt to set CANCELSTRING to blank; an attempt to set DRAWBUT to a number out of the a l l o w a b l e range. 74 > LABELS Purpose: To s e l e c t i v e l y d i s p l a y the l a b e l s of the graph i n the curr e n t area. D e s c r i p t i o n : When LABELS i s a c t i v a t e d , the l a b e l s on the graph i n the current area are displayed according to the current " l a b e l mode". The l a b e l mode i s one of NONE, ALL, VERTEX, cr EDGE. The l a b e l mode can be changed by a c t i v a t i n g one of the menu items which appear immediately t c the r i g h t cf LABELS. The i n i t i a l l a b e l mode i s ALL. Labeling with NONE a c t i v a t e d w i l l cause a l l displayed l a b e l s ( i f any) t c be rubbed out. Labeling with ALL w i l l cause a l l l a b e l s to be di s p l a y e d . To d i s p l a y only vertex l a b e l s VERTEX i s used, and to d i s p l a y only edge l a b e l s EDGE i s used. When a graph i s labeled i n t h i s way, an i n t e r n a l i n d i c a t o r a s s o c i a t e d with that graph i s changed t o correspond with the current l a b e l mode. This then becomes a property of that graph, and i f the graph i s , say, rubbed cut and then l a t e r r e - d i s p l a y e d , the dis p l a y e d image w i l l r e f l e c t the new l a b e l mode. « PLOT Purpose: To p l o t the image which appears cn the Adage screen. D e s c r i p t i o n : When PLOT i s a c t i v a t e d , a " p l o t f i l e " i s prepared f o r l a t e r entry i n t o the operating system's p l o t gueue. PLOT can be a c t i v a t e d as many times a des i r e d during a p a r t i c u l a r run of the system. on each a c t i v a t i o n , an exact ccpy cf the Adage screen ( i n c l u d i n g menu) i s " p l o t t e d " . (The t r a c k i n g p a t t e r n i s not included i n p l o t s . ) When the system i s stepped (see STOP) a l l p l o t s f o r that 75 run are a u t o m a t i c a l l y sent t c the plo t queue. • SAVE Purpose: To save the graph i n the current area i n a disk f i l e . D e s c r i p t i o n : When SAVE i s a c t i v a t e d , the system responds by asking the user f o r the name of the f i l e i n which the graph i s tc be saved. I f the attempt to open t h i s f i l e i s s u c c e s s f u l , the system saves the graph i n the current area i n that f i l e . As many graphs as desired can be saved i n a p a r t i c u l a r f i l e . A graph need net have a t i t l e i n order to be saved, but the presence of a t i t l e sometimes makes r e s t o r a t i o n e a s i e r . Error Messages: NO GRAPH IN CUBBENT REGION FILE SPECIFIED DOES NOT EXIST CANNOT OPEN FILE - RETURN CODE nn The attempt t c open the f i l e was unsuccessful. The re t u r n code can be used t o determine the exact cause. WARNING: NOT A SEQUENTIAL FILE I f the f i l e i s not a s e q u e n t i a l f i l e then new data put i n t o the f i l e w i l l be overwritten r a t h e r than appended. Thus, i f graphs are added to a l i n e f i l e t h at already contains graphs, the o l d graphs w i l l be p a r t i a l l y or t o t a l l y destroyed, and therefore are l o s t . I f a l i n e f i l e i s s p e c i f i e d , the system w i l l ask f c r confirmation cf the SAVE. I f the user confirms the SAVE, the s p e c i f i e d l i n e f i l e w i l l be used; i f not. 76 the SAVE w i l l be c a n c e l l e d . FILE SPECIFIED IS FULL The saved graph w i l l be incomplete i s t h i s case. ERROR IN WHITE - RETURN CODE IS nn This i s caused by an e r r o r c o n d i t i o n occuring i n the HTS WRITE r o u t i n e . The r e t u r n code can be used to determine the exact cause. » RESTORE Purpose: To r e s t o r e one or more graphs that have been saved i n a disk f i l e . D e s c r i p t i o n : When RESTORE i s a c t i v a t e d , the system responds by asking the user f o r the name of a f i l e from which r e s t o r a t i o n w i l l take place. I f t h i s f i l e i s opened s u c c e s s f u l l y , the user i s asked t o enter a request. RESTORE operates i n cne of three request modes: " a l l " , " s e l e c t " , or " t i t l e " mode. To r e s t o r e i n a l l mode the request should be the word "ALL" (or a b b r e v i a t i o n "A"). I f t h i s request i s entered, then a l l graphs i n the s p e c i f i e d f i l e are r e s t o r e d . They are not dis p l a y e d on the screen immediately, but in s t e a d are brought i n t o the system and can l a t e r be dis p l a y e d using DISPLAY. To r e s t o r e i n s e l e c t mode, the request "SELECT" (cr "S") i s used. In s e l e c t mode, f o r each graph i n the s p e c i f i e d f i l e the user i s queried as to whether of not that graph should be r e s t o r e d . For each graph, the graph t i t l e i s displayed (or the graph number i f the graph does not have a t i t l e ) , as w e l l as three choices: "CANCEL", "RESTORE", and "IGNORE". If CANCEL i s chosen, then r e s t o r a t i o n steps and the system begins w a i t i n g f o r a new command. I f BESTGRE i s chosen then the graph i s restored (but not d i s p l a y e d ) , and i f IGNORE i s chosen then the graph i s not re s t o r e d . For both RESTORE and IGNORE the system w i l l continue l o c k i n g f o r graphs i n the f i l e a f t e r taking the appropriate a c t i o n . 77 I f the request i s not "ALL", "A", "SELECT", or "S" then the system assumes i t i s a graph t i t l e . In t h i s case the s p e c i f i e d f i l e i s searched f o r the f i r s t graph with that t i t l e , and i f such a graph i s found i t i s restored and then dis p l a y e d i n the current area. Whenever a graph i s restored i t s number and t i t l e are pr i n t e d on the 3270 screen. Error Messages: FILE SPECIFIED DOES NOT EXIST CANNOT OPEN FILE - BETDEN CODE IS nn The attempt to open the f i l e was uns u c c e s s f u l . The re t u r n code can be used to determine the exact cause. WARNING: FIRST RECORD IN FILE NOT A GRAPH This probably i n d i c a t e s that a f i l e has a c c i d e n t a l l y been s p e c i f i e d which does not contain saved graphs. When t h i s warning occurs the system asks the user whether or not he or she wishes to continue. UNEXPECTED RECORD TYPE - ERROR RETURN UNEXPECTED EOF - ERROR RETURN Unexpected e n d - c f - f i l e . LENGTH INCOMPATIBILITY - ERROR RETURN A record was read that was the c o r r e c t type but the i n c o r r e c t length. SYSTEM I/O ERROR - ERROR RETURN nn This i s caused by an e r r o r c o n d i t i o n cccuring i n one of the MTS I/O r o u t i n e s . The retur n code "nn" can be used to determine the exact cause. 78 • TITLE GRAPH Purpose: To t i t l e the graph i n the cu r r e n t area. D e s c r i p t i o n : When TITLE GRAPH i s a c t i v a t e d , the user i s asked to enter a t i t l e a t the keyboard. A t i t l e can be up to 40 characters i n l e n g t h . TITLE GRAPH can a l s o be used to replace an e x i s t i n g t i t l e . • DISPLAY Purpose: To d i s p l a y a graph i n the cu r r e n t area. D e s c r i p t i o n : When DISPLAY i s a c t i v a t e d , the system responds by d i s p l a y i n g a l i s t of the t i t l e s of the graphs which have been defined to the system, (If a graph does not have a t i t l e , i t s number i s displayed.) The user then uses the l i g h t pen to choose one of the graphs which i s then di s p l a y e d i n the current area. Graphs which have been introduced i n t o the system by drawing (as opposed to i n t r o d u c t i o n by RESTORE) and graphs which have been re s t o r e d but a l t e r e d , are i n d i c a t e d by an a s t e r i s k ("*") to the l e f t of t h e i r name. These are the graphs which a user may be i n t e r e s t e d i n saving at the end of a run. Error Messages: NC GRAPHS TO BE DISPLAYED No graphs have been defined to the system. THAT GRAPH IS ALREADY DISPLAYED A p a r t i c u l a r graph can only be dis p l a y e d i n one region 79 on the screen. I f the same image i s d e s i r e d i n two or more regions then DUPLICATE should be used. • BUB OUT Purpose: To rub out the graph i n the cur r e n t area. D e s c r i p t i o n : When RUB OUT i s a c t i v a t e d , the graph i n the current area ( i f any) i s rubbed out. A graph that i s rubbed cut i s not destroyed, and can be re - d i s p l a y e d using DISEIAY. * DUPLICATE Purpose: To d u p l i c a t e both the i n t e r n a l s t r u c t u r e and the image of the graph i n the current area. D e s c r i p t i o n : When DUPLICATE i s a c t i v a t e d , the system responds by asking "ON WHICH REGION?". The user then i n d i c a t e s a region by choosing a region mark with the l i g h t pen. I f the region s p e c i f i e d i s not the current r e g i o n , then DUPLICATE proceeds to make a d i s t i n c t i n t e r n a l copy of the graph, and then d i s p l a y s the copy i n the s p e c i f i e d r e g i o n . • MOVE Purpose: To move the graph i n the cur r e n t area to another region. D e s c r i p t i o n : When MOVE i s a c t i v a t e d , the system responds by asking "TO WHERE?". The user then i n d i c a t e s a region by choosing a region mark with the l i g h t pen. 80 I f the region s p e c i f i e d i s not the current r e g i o n , then the graph i n the current r e g i o n i s rubbed out and r e - d i s p l a y e d i n the s p e c i f i e d region. • CANCEL Purpose: To cancel an opera t i o n when the system i s reading from the Adage screen. D e s c r i p t i o n : I f CANCEL i s a c t i v a t e d when the system i s waiting f o r input from the Adage screen, then ( i f possible) the system w i l l c a ncel the current operation and re t u r n to i t s previous s t a t e . U sually t h i s previous s t a t e i s the s t a t e of waiting f o r a new command. COMMANDS IN THE DRAW MENU • BESET Purpose: To r e s e t the vertex and edge prototypes to t h e i r d e f a u l t c h a r a c t e r i s t i c s . D e s c r i p t i o n : When RESET i s a c t i v a t e d , the vertex and edge prototypes are rese t to t h e i r d e f a u l t i n t e n s i t i e s and dashing i s turned o f f . The vertex prototype i s a l s o r e s e t to i t s d e f a u l t s i z e and shape. 81 m BOLD-DASHED-NORMAL Purpose: To change the i n t e n s i t i e s and dashing of the vertex and edge prototypes. D e s c r i p t i o n : The s m a l l squares t c the l e f t of BOLD, DASHED, and NORMAL are used to change the edge prototype; the sguares t c the r i g h t are used to change the vertex prototype. For example, the square to the l e f t of BOLD i s used t c change the edge prototype t c bold face. The two boxes on the extreme l e f t and the extreme r i g h t ("between" BOLD and CASHED) w i l l change the appropriate prototype to dashed bold face. Thus, the i n t e n s i t i e s and dashing of the two prototypes can be changed independently using the squares. The prototypes can also be changed simultaneously by a c t i v a t i n g the words "BOLD", "DASHED", and "NORMAL"., So, f o r example, i f "BOLD" i s a c t i v a t e d , then both the prototypes are changed to bold face. • SIZE Purpose: To change the s i z e of the vertex prototype. D e s c r i p t i o n : When the "-" to the l e f t of SIZE i s a c t i v a t e d , the s i z e of the vertex prototype i s decreased by the parameter VINCREMENT; when the >•+" to the r i g h t of SIZE i s used, the s i z e i s increased by VINCREMENT. The parameter VINCREMENT can be changed using SET. 82 • SHAPE Purpose: To change the shape of the verte x prototype. D e s c r i p t i o n : When the "-" to the l e f t of SHAPE i s a c t i v a t e d , the number of s i d e s of the vertex prototype i s decreased by 1; when the "+" t o the r i g h t of SHAPE i s used, the number of s i d e s i s i n c r e a s e d by 1, The number of s i d e s i s not allowed to go below 3 or above 9 . • ADD Purpose: To add v e r t i c e s and edges to graphs on the screen. D e s c r i p t i o n : When the box to the r i g h t of "ADD" i s a c t i v a t e d , the system i s ready to add v e r t i c e s ; when the box to the l e f t i s a c t i v a t e d , the system i s ready t c add edges. To add a ve r t e x , the user simply moves the t r a c k i n g p a t t e r n to the d e s i r e d p o s i t i o n and presses the draw button ( i n i t i a l l y button 1, at the top l e f t c o r n e r ) , A vertex which looks l i k e the vertex prototype i s then c r e a t e d , added to the graph i n the a p p r o p r i a t e r e g i o n , and d i s p l a y e d . To add an edge, the user f i r s t s p e c i f i e s a "from" v e r t e x . When t h i s i s done, a b l i n k i n g c r o s s i s d i s p l a y e d at the ce n t r e of the vertex. The user i s then expected t c e i t h e r s p e c i f y a " t o " vertex c r press the draw button. I f a vertex i s s p e c i f i e d , then an edge which locks l i k e the edge prototype i s c r e a t e d , added to the graph i n the a p p r o p r i a t e r e g i o n , and d i s p l a y e d . The edge w i l l be a s t r a i g h t l i n e between the c e n t r e s of the two s p e c i f i e d v e r t i c e s . Sometimes, however, a s t r a i g h t edge i s not s u i t a b l e , but i n s t e a d a "curved" edge i s d e s i r a b l e . Such an edge, a "free-hand edge", can be drawn using the draw button and 83 the t r a c k i n g p a t t e r n . I f the system has had a "from" vertex s p e c i f i e d to i t , then i f the draw button i s depressed a s e c t i o n c f an edge i s drawn from the "from" vertex to the centre cf the t r a c k i n g pattern. The t r a c k i n g pattern can be moved and the draw button depressed again, i n which case another s e c t i o n of an edge i s added, t h i s time from the end of the l a s t s e c t i o n t o the new l o c a t i o n of the t r a c k i n g p a t t e r n . As many s e c t i o n s as desired can be added i n t h i s way. The process i s terminated by s p e c i f y i n g a " t o " vertex as the second end of the f i n a l edge s e c t i o n . I f the system i s i n d i r e c t e d mode when an edge i s drawn, the edge w i l l be a d i r e c t e d edge with i t s t a i l at the "from" vertex and i t s head a t the " t o " vertex. E r r o r Messages: TRACKING PATTERN NOT IN A REGION (vertex) WRONG REGION (edge) The "from" vertex and the " t o " vertex must be i n the same region. Also, free-hand edges cannot cr o s s region boundaries. LOOP MOST BE A FREE-HAND EDGE (edge) When the "from" and " t o " v e r t i c e s are the same vertex, the edge must be free-hand (otherwise the edge cannot be seen). WARNING - MULTIPLE EDGE (edge) This message appears whenever a m u l t i p l e edge i s drawn. This i s done because i t i s p o s s i b l e t c draw m u l t i p l e edges which are impossible to d i s t i n g u i s h (that i s , the second i s drawn "on top" cf the f i r s t ) . 8*4 • DELETE Purpose: To delete v e r t i c e s and edges from graphs on the screen. D e s c r i p t i o n : When the box to the r i g h t of "DELETE" i s a c t i v a t e d , the system i s ready t c delete v e r t i c e s ; when the box to the l e f t i s a c t i v a t e d , the system i s ready to delete edges. To delete a vertex cr an edge the user simply h i t s the des i r e d object with the l i g h t pen. When a vertex i s delet e d , then a l l i n c i d e n t edges are a l s o deleted. • LABEL Purpose: To l a b e l v e r t i c e s and edges. D e s c r i p t i o n : When the box t o the r i g h t of "LABEL" i s a c t i v a t e d , the system i s ready to l a b e l v e r t i c e s ; when the box to the l e f t i s a c t i v a t e d , the system i s ready to l a b e l edges. At t h i s point the user h i t s e i t h e r a vertex or an edge with the l i g h t pen, and a b l i n k i n g cross i s displayed a t the " l a b e l i n g p o i n t " (see below). The system then asks the user to "ENTER LABEL AT KEYBOARD", and reads the l a b e l (up to 8 c h a r a c t e r s ) . The l a b e l i s then disp l a y e d . Labels can be p o s i t i o n e d e x p l i c i t l y or a d e f a u l t l o c a t i o n can be used. The parameter LABDIS c o n t r o l s t h i s f e a t u r e . I f the t r a c k i n g pattern i s l e s s than LABDIS inches ( i n i t i a l l y 1 inch) from the l a b e l i n g point then the l a b e l i s placed at the centre of the t r a c k i n g p a t t e r n . I f , however, the t r a c k i n g pattern i s more than LA EEIS inches from the l a b e l i n g p o i n t , or i n a d i f f e r e n t r e g i o n , then the l a b e l i s placed at the d e f a u l t l o c a t i o n . The r e l a t i v e coordinates of the d e f a u l t l a b e l l o c a t i o n are the parameters XLABLOC and YLABLOC. LABDIS, XLAEIOC, and YLABLOC a l l can be changed using SET. Refer tc the d e s c r i p t i o n of SET f o r more d e t a i l s . The " l a b e l i n g p o i n t " i s the point r e l a t i v e t c which l a b e l s are both s t o r e d i n the i n t e r n a l r e p r e s e n t a t i o n and 85 d i s p l a y e d . The l a b e l i n g point of a vertex i s the centre of the vertex. The l a b e l i n g p o i n t of an edge i s the "middle" of the edge. For simple edges (edges which are one s t r a i g h t l i n e between two v e r t i c e s ) the middle i s simply the geometric mid-point of the l i n e . For free-hand edges, the middle i s determined by f i n d i n g an edge s e c t i o n which i s "roughly e g u i d i s t a n t " frcm the i n c i d e n t v e r t i c e s , and then using the mid-point of that s e c t i o n as the middle. • CHANGE Purpose: To change the appearance of v e r t i c e s and edges. D e s c r i p t i o n : Hhen the box to the r i g h t of "CHANGE" i s a c t i v a t e d , the system i s ready t o change v e r t i c e s ; when the bcx to the l e f t i f a c t i v a t e d , the system i s ready to change edges. To change a vertex or an edge, the desired object i s h i t with the l i g h t pen. The appearance of the vertex or edge i s then changed to look l i k e the appropriate prototype. • HEP EAT Purpose: To allow automatic r e p e t i t i o n of va r i c u s system f u n c t i o n s . D e s c r i p t i o n : A l l system commands and f u n c t i o n s normally execute only once before c o n t r o l i s returned t c the tcp l e v e l cf the system. By enabling REPEAT, however, c e r t a i n commands can be made to a u t o m a t i c a l l y repeat. The commands a f f e c t e d are those i n the lowest s e c t i o n cf the draw menu (below the lower dashed d i v i d i n g l i n e ) . These commands w i l l continue to repeat u n t i l they are e x p l i c i t l y turned o f f . To turn o f f a menu item that i s being repeated, a user must h i t e i t h e r REPEAT, CANCEL, or the menu item i t s e l f . I f REPEAT i s h i t , REPEAT i s al s o turned o f f . Only cne command can be i n use at one time, so i f the system does not respond to an attempt to turn on a p a r t i c u l a r command, i t 86 may be because another command i s being held on by B1PEflT. The one exception to t h i s r u l e i s that the prototypes can be adjusted while "add edge", "add vertex", "change edge", or "change vertex" i s turned on. m SUBDIVIDE EDGE Purpose: To subdivide an edge by c r e a t i n g a new vertex i n the middle of the edge. D e s c r i p t i o n : When SUBDIVIDE EDGE i s a c t i v a t e d , the system waits f o r an edge to be s p e c i f i e d with the l i g h t pen. When an edge i s chosen, the edge i s replaced with two new edges and a new vertex i n the way i n d i c a t e d by f i g u r e 9 . Directed edges can also be subdivided, with the obvious r e s u l t . • BEHOVE DEGREE 2 VERTEX Purpose: To remove a vertex of degree 2 and add an edge between the two v e r t i c e s t o which i t was connected. D e s c r i p t i o n : When REMOVE DEGREE 2 VERTEX i s a c t i v a t e d , the system waits f o r a vertex to be s p e c i f i e d with the l i g h t pen. When a vertex i s chosen, the vertex and i t s two i n c i d e n t edges are de l e t e d , and an edge i s added between the two v e r t i c e s to which the deleted vertex was connected. Refer to f i g u r e 10 f o r some examples. Error Messages: VERTEX MUST BE DEGREE 2 This message appears whenever the vertex chosen i s not acceptable, i n c l u d i n g such cases as a vertex with two i n p o i n t i n g a r c s . F i g u r e 9 - The E f f e c t o f SUBDIVIDE EDGE F i g u r e 10 - The E f f e c t c f REMOVE DEGREE 2 VERTEX 89 • ASSOCIATE VERTICES Purpose: To a s s o c i a t e two v e r t i c e s , that i s , tc perform an elementary homomorphism. D e s c r i p t i o n : When ASSOCIATE VERTICES i s a c t i v a t e d , the system waits f o r the user to s p e c i f y the f i r s t vertex. When t h i s i s dene, a b l i n k i n g cross i s displayed at the centre of the vertex. The user then must s p e c i f y a second vertex. When t h i s second vertex i s s p e c i f i e d , the f i r s t vertex i s deleted ( i n c l u d i n g i n c i d e n t edges) and edges are added sc that the second vertex i s adjacent to a l l v e r t i c e s that were adjacent to the f i r s t vertex. M u l t i p l e edges are not created during t h i s o p e r a t i o n , so i f both the f i r s t vertex and the second vertex are adjacent to the same t h i r d v ertex, only one edge remains i n the f i n a l graph. I f two edges must be combined, and one of the edges i s d i r e c t e d while the other i s undirected, then the r e s u l t i n g edge w i l l be undirected. I f both edges are d i r e c t e d , and they have opposing d i r e c t i o n s , then the r e s u l t i n g edge w i l l be undirected, and a warning message w i l l be displayed along with a b l i n k i n g cross cn the edge i n question. Figure 11 shows some examples of the r e s u l t s cf a s s o c i a t i n g v e r t i c e s . E r r o r Messages: WRONG REGION The v e r t i c e s to be associated must be i n the same graph. SAME VERTEX The v e r t i c e s t c be as s o c i a t e d must be d i s t i n c t . CANNOT ASSOCIATE ADJACENT VERTICES NOTE EDGES CHANGED TO UNDIRECTED F i g u r e 11 - The E f f e c t o f ASSOCIATE VERTICES 91 A l l undirected edges which r e s u l t e d from a p a i r cf op p o s i t e l y d i r e c t e d m u l t i p l e edges are i n d i c a t e d by a b l i n k i n g cross. • REVERSE ARC Purpose: To reverse the d i r e c t i o n of an a r c . D e s c r i p t i o n : When REVERSE ARC i s a c t i v a t e d , the system waits f o r the user to s p e c i f y an arc. When t h i s i s done, the o r i e n t a t i o n of the arc i s reversed. E r r o r Messages: THAT EDGE IS HOT DIRECTED • UNDIR <--> DIR Purpose: To change an undirected edge i n t o a d i r e c t e d edge, and vice versa. D e s c r i p t i o n : When UNDIR <—> DIR i s a c t i v a t e d , the system waits f o r an edge to be s p e c i f i e d , I f the edge i s undirected, i t i s changed to d i r e c t e d ; i f d i r e c t e d , i t i s changed to undirected. 92 • LOCK ON VERTEX Purpose: To move a vertex to a new l o c a t i o n . D e s c r i p t i o n : When LOCK ON VERTEX i s a c t i v a t e d , the system waits f c r the user to s p e c i f y a vertex to be moved. when a vertex i s chosen, i t i s moved to the current l o c a t i o n of the t r a c k i n g p a t t e r n . Of course, a l l cf i t s i n c i d e n t edges are al s o r e -drawn. Error Messages: WRONG REGION A vertex cannot be moved to a d i f f e r e n t region. • LOCK ON GRAPH Purpose: To move a whole graph to a new l o c a t i o n . D e s c r i p t i o n : When LOCK ON GRAPH i s a c t i v a t e d , the system waits f c r the user to s p e c i f y a vertex. When a vertex i s chosen, that vertex i s moved to the current l o c a t i o n of the t r a c k i n g p a t t e r n , and a l l other v e r t i c e s i n that graph are moved the same r e l a t i v e distances i n the x - d i r e c t i c n and the y-d i r e c t i o n . No part of the graph w i l l be moved out of the con t a i n i n g r e g i o n . E r r o r Messages: WRONG REGION The s p e c i f i e d vertex cannot be moved to a d i f f e r e n t r e g i o n . 9 3 COMMANDS IN THE FUNCTION MENU • GO Purpose: To s i g n a l the s t a r t of c e r t a i n operations. D e s c r i p t i o n : Some operations use GO as a s i g n a l to continue t c the next s t e p . For example, when permuting l a b e l s (see PERMUTE LABELS below), the f i r s t step i s to enter a permutation. When t h i s i s done, GO i s a c t i v a t e d and the l a b e l s are a c t u a l l y permuted. • MIN/MAX DEGREE Purpose: To determine the minimum and maximum degrees of a graph. D e s c r i p t i o n : When MIN/MAX DEGREE i s a c t i v a t e d , the system determines and d i s p l a y s the minimum and maximum degrees of the graph i n the current area. I f the graph i s d i r e c t e d , both the minimum and maximum indegree and the minimum and maximum outdegree are di s p l a y e d . E r r o r Messages: NO GRAPH IN THE CURRENT AREA GRAPH HAS NO VERTICES GRAPH HAS NO EDGES - ALL DEGREES ARE ZERO 94 - PER BUTE LABELS-PERMOTE COORDS Purpose: To permute vertex l a b e l s or vertex coordinates. D e s c r i p t i o n : When PERMUTE LABELS or PERMUTE COORDS i s a c t i v a t e d , the system waits f c r a c y c l i c permutation to be entered. The l a b e l s or coordinates w i l l be changed according t c t h i s permutation. To enter a permutation, the user simply chooses a number cf v e r t i c e s with the l i g h t pen. As each vertex i s chosen, i t s sequence number i n the permutation i s displayed as a b l i n k i n g number adjacent to the vertex. V e r t i c e s can appear i n the permutation only once. I f a vertex i s chosen a second time, an e r r o r message i s generated, unless the vertex has the highest sequence number. In t h i s l a t t e r case the vertex i s removed from the permutation, thus a l l o w i n g a user to back up. When the permutation i s complete, the user must h i t GO with the l i g h t pen, at which time e i t h e r l a b e l s cr coordinates w i l l be permuted, depending on the type of permutation i n e f f e c t . Examples of the e f f e c t of PERMUTE LABELS and EEBMUTE COORDS are shown i n f i g u r e s 1 2 and 1 3 . Error Messages: MUST SPECIFY AT LEAST TWO VERTICES There must be a t l e a s t two v e r t i c e s i n the permutation. WRONG REGION A l l the v e r t i c e s must be i n the same graph. VERTEX ALREADY IN PERMUTATION PERMUTE CANCELLED F i g u r e 1 2 - The E f f e c t of PERMUTE LABELS F i g u r e 1 3 - The E f f e c t of PERMUTE COORDS 97 A l l v e r t i c e s i n the permutation have been "removed". • BLOCKS/CUTNODES/BRIDGES Purpose: To determine and d i s p l a y the of the graph i n the current found, i f one e x i s t s , D e s c r i p t i o n : When BLOCKS/CUTNODES/BRIDGES i s a c t i v a t e d , the system w i l l perform i t s c a l c u l a t i o n s on the graph i n the current area. When completed, the d i f f e r e n t p a r ts of the graph w i l l be i n d i c a t e d as f o l l o w s : cutnodes w i l l be bold face v e r t i c e s ; bridges w i l l be bold face edges; blocks w i l l be these edges l a b e l e d with the same l a b e l ; a spanning tree ( i f any) w i l l be i n d i c a t e d by edges of normal i n t e n s i t y (in a d d i t i o n to the b r i d g e s ) . A l l other v e r t i c e s w i l l be of normal i n t e n s i t y and a l l other edges w i l l be dashed. Figure 14 shows an example cf the a p p l i c a t i o n of BLOCKS/COTNODES/BRIDGES. The algorithm used f o r t h i s o peration i s taken frcm [ 1 7 ] . E r r o r Messages: NO GRAPH IN THE CURRENT AREA GRAPH HAS NO EDGES blocks, cutnodes, and bridges area. A spanning tree i s al s o F i g u r e 14 - The E f f e c t o f BLOCKS/CUTNODES/BRIDGES 99 INDEX TO COMMANDS ADD 82 ASSOCIATE VERTICES 89 ELOCKS/CUTNODES/BRIDGES 97 BOLD 81 CANCEL 80 CHANGE 85 DASHED 81 DELETE 84 DISPLAY 78 DRAW 67 DUPLICATE 79 FUNCTION 67 GO 93 HELP 68 KEYBOARD 68 LABEL 84 LABELS 74 LOCK ON GRAPH 92 LOCK ON VERTEX 92 MIN/MAX DEGREE 93 MOVE 79 NORMAL 81 PERMUTE COORDS 94 PERMUTE LABELS 94 PLOT 74 READY 66 REGIONS 67 REMOVE DEGREE 2 VERTEX 86 REPEAT 85 RESET 80 RESTORE 76 REVERSE ARC 91 RUB OUT 79 SAVE 75 SET 70 SHAPE 82 SIZE 81 STOP 70 SUBDIVIDE EDGE 86 TITLE GRAPH 78 UN DIR <--> DIR 91 

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            data-media="{[{embed.selectedMedia}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.831.1-0051763/manifest

Comment

Related Items