Science, Faculty of
Computer Science, Department of
DSpace
UBCV
Ng, William Pak Hung
Master of Science - MSc
University of British Columbia
Web grammars are a general and flexible method for "picture" description in computer graphics. They apply the rewriting procedure typical of string grammars to general directed graphs or "webs". An interactive graphical system is implemented to provide an easy and convenient way to manipulate and specify a web in a natural manner. This project is based on a system implemented by Pat Conroy. The system is written in ALGOLW. The graphical terminal used to display the webs is an Adage Graphical Terminal ( AGT for short ) which is connected to a main computer, an IBM 360/67 by telephone lines. There are instruments such as light-pen, function keys, foot pedals and dials to assist the interaction between the user and the AGT. In this project, a solution to the problem of replacing a subweb by another on the display screen is attemped.
fi' AN INTERACTIVE GRAPHICAL PROGRAM FOR SPECIFICATION AND APPLICATION OF WEB REWRITING RULES by WILLIAM PAK HUNG NG B.S. University of Oregon, 1 9 7 0 A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF SCIENCE i n the Department of Computer Science We accept t h i s thesis as conforming to the required standard. THE UNIVERSITY OF BRITISH COLUMBIA October, 1 9 7 3 In presenting t h i s thesis i n p a r t i a l f ulfilment of the requirements for an advanced degree at the University of B r i t i s h Columbia, I agree that the Library s h a l l make i t freely available for reference and study. I further agree that permission for extensive copying of t h i s thesis for scholarly purposes may be granted by the Head of my Department or by his representatives. I t i s understood that copying or publication of t h i s thesis for f i n a n c i a l gain s h a l l not be allowed without my written permission. Department The University of B r i t i s h Columbia Vancouver 8, Canada ABSTRACT i i Web grammars are a general and f l e x i b l e method f o r " p i c t u r e " d e s c r i p t i o n i n computer graphics. They apply the r e w r i t i n g procedure t y p i c a l of s t r i n g grammars t o general d i r e c t e d graphs or "webs". An i n t e r a c t i v e g r a p h i c a l system i s implemented t o provide an easy and convenient way t o manipulate and s p e c i f y a web i n a n a t u r a l manner. This p r o j e c t i s based on a system implemented by Pat Conroy. The system i s w r i t t e n i n ALGOLW. The g r a p h i c a l t e r m i n a l used t o d i s p l a y the webs i s an Adage Gr a p h i c a l Terminal ( AGT f o r short ) which i s connected t o a main computer, an IBM 3 6 0 / 6 7 by telephone l i n e s . There are instruments such as l i g h t - p e n , f u n c t i o n keys, foot pedals and d i a l s t o a s s i s t the i n t e r a c t i o n between the user and the AGT. In t h i s p r o j e c t , a s o l u t i o n t o the problem of r e p l a c i n g a subweb by another on the d i s p l a y screen i s attemped. i i i TABLE OF CONTENTS Page SECTION 1 : I n t r o d u c t i o n 1 SECTION 2 s D e f i n i t i o n s and Examples 4 SECTION 3 : S p e c i f i c a t i o n of Problems 13 SECTION 4 J Implementation 16 4 . 1 : Data S t r u c t u r e 19 4 . 2 5 The Algorithm 21 4 . 2 . 1 J The Algorithm f o r The Replacement of A Web 30 4 . 2 . 2 : The Algorithm f o r F i n d i n g A p p l i c a b l e Rules 31 4 . 3 : The System 33 4 . 4 : L i m i t a t i o n s of The System 3 ^ SECTION 5 : Conclusions and Summary 37 BIBLIOGRAPHY ^2 APPENDIX A s L i s t i n g of Programmes 4 3 APPENDIX B : How t o Use The Programmes 6 3 i v LIST OF FIGURES Page Figure 1.1 Representation of A Directed Arc 11 Figure 4.1 Data Structure of A Web 21 Figure 4.2 State Diagram 22 Figure 4.3 Flow Diagram For State 1 24 Figure 4.4 Flow Diagram For S p e c i f i c a t i o n of Webs 25 Figure 4.5 Area Occupied By A Web 31 Figure 4.6 Error of Light-Pen Hit 35 Figure 5.1 Web Before Application of A Rule 38 Figure 5.2 Web After Application of A Rule 38 Figure 5.3 A Web of The TTPSN 41 Plate 1 Input The Number of Webs 63 Plate 2 Input The Number of Rules 63 Plate 3 Options i n State 1 64 Plate 4 Input Web Name 64 Plate 5 Options i n The S p e c i f i c a t i o n of Webs 65 Plate 6 Options i n The S p e c i f i c a t i o n of Webs 65 Plate 7 Indicate The Positi o n of A Node 66 Plate 8 Specify From-Node 66 Plate 9 Specify To-Node 67 Plate 10 Input Node Label 67 Plate 11 Rule Numbers t 68 Plate 12 Web Names 68 Plate 13 Left Web 69 Plate 14 Right Web 69 Plate 15 S p e c i f i c a t i o n of Embeddings 70 V Page P l a t e 16 Sp e c i f y A 70 P l a t e 17 Sp e c i f y T 71 P l a t e 18 Specify B 71 P l a t e 19 Specify G 72 P l a t e 20 A p p l i c a t i o n of Web Rewriting Rule 72 P l a t e 21 A p p l i c a t i o n of Web Rewriting Rule 73 P l a t e 22 Choose A p p l i c a b l e Rule 73 vi ACKNOWLEDGEMENTS I am g r e a t l y indebted t o Pr o f e s s o r F r i e d e r Nake f o r h i s suggestion of the t o p i c of t h i s t h e s i s , and f o r a l l h i s help and advice given t o me durin g the p r e p a r a t i o n of t h i s t h e s i s . I a l s o wish t o thank P r o f e s s o r D.A.R. Seeley f o r h i s c r i t i c i s m on the d r a f t form of t h i s t h e s i s . I wish t o express my thankfulness t o the Department of Computer Science of the U n i v e r s i t y of B r i t i s h Columbia f o r the f i n a n c i a l support. 1 1 . INTRODUCTION Much e f f o r t has been devoted, i n the e a r l y s i x t y ' s , t o g e n e r a l i z i n g p i c t u r e d e s c r i p t i o n i n computer graphics; but not u n t i l 1 9 6 9 was a general and f l e x i b l e theory introduced. 1 1 P f a l t z and Rosenfeld a p p l i e d the r e w r i t i n g procedure, t y p i c a l of s t r i n g grammars, to general d i r e c t e d l a b e l l e d graphs or " webs they a l s o introduced the term web grammar f o r t h i s type of grammar. Montanari^, i n 1 9 7 0 , gave a s l i g h t l y d i f f e r e n t but equivalent d e f i n i t i o n of web grammars. The d i f f e r e n c e i s i n the d e f i n i t i o n of embeddings ( see S e c t i o n 2 ). Another piece of work on formal graph languages i s the c o n t e x t - f r e e graph grammars ( CFGG f o r short ) by P a v l i d i s 9 . In a CFGG, the embeddings are not s p e c i f i e d ( see S e c t i o n 2 ). Most of the work has been on the t h e o r e t i c a l s ide so f a r . The use-f u l n e s s of these grammars f o r p r a c t i c a l purposes, such as d e s c r i p t i o n of general data s t r u c t u r e s 0 , s t i l l needs much experimentation;. There e x i s t s a web p a r s i n g program f o r two t e r m i n a l s e r i a l p a r a l l e l networks implemented by Michael B e r k u s 1 ^ and 10 a p i c t u r e p a r s i n g program f o r neuron networks . Both these programs were implemented at the U n i v e r s i t y of Maryland i n 1 9 7 0 . In 1 9 7 2 Pat Conroy implemented an algorithm f o r the d e f i n i t i o n and use of web grammars at the U n i v e r s i t y of 2 B r i t i s h Columbia . This p r o j e c t of Conroy's i s not g r a p h i c a l i n nature. Webs and embeddings are coded i n t o f i x e d formats. There i s no immediate response whenever a web i s a l t e r e d , d u r i n g the process of a p p l y i n g r e w r i t i n g r u l e s . Moreover a user has to l e a r n the i n t e r n a l r e p r e s e n t a t i o n s of webs and embeddings i n order t o input webs and embeddings. Since web grammars dea l w i t h graphs, a g r a p h i c a l system t o work w i t h them would s u r e l y appeal more to users. The main purpose of t h i s p r o j e c t i s t o implement an i n t e r a c t i v e g r a p h i c a l system which provides a n a t u r a l and easy means f o r s p e c i f i c a t i o n of webs and embeddings. This system a l s o r i d s i t s user of the t r o u b l e of l e a r n i n g the i n t e r n a l r e presentations of webs and embeddings. G r a p h i c a l methods are important t o o l s i n a p p l i e d mathematics. Graphs are used i n engineering i n such areas as automatic c o n t r o l , e l e c t r i c networks, and p r i n t e d c i r c u i t s design. Graphs are a l s o very important i n operations research where many problems, such as t r a n s p o r t a t i o n , d i s t r i b u t i o n and t r a f f i c problems, can be modeled and solved by means of graph There are-'other problems,e.g. i n l i g u i s t i c s , that f r e q u e n t l y use graphs; i n programming, flow charts are a l s o forms of graphs. Graphics i s a l s o e s s e n t i a l i n automobile and aeroplan mathematical techniques, yet graphs have the important advan-tage of making the s o l u t i o n of the problem more v i s u a l and more i n t u i t i v e . Therefore, i t i s f e l t t h a t computer graphics can p l a y a very important r o l e i n these areas. Since web grammars are a general and f l e x i b l e theory f o r computer graphics, i t i s important t o i n v e s t i g a t e t h e i r p r a c t i c a l use-f u l n e s s . The goal of t h i s p r o j e c t i s , t h e r e f o r e , not to achieve t h e o r e t i c a l r e s u l t s , but t o provide a system f o r the 3 a p p l i c a t i o n of web r e w r i t i n g r u l e s i n p i c t u r e d e s c r i p t i o n . The l i t e r a t u r e on web grammars w i l l be reviewed b r i e f l y i n S e c t i o n 2 . D e f i n i t i o n s of the necessary terminology ( webs, embeddings, web r e w r i t i n g r u l e s , e t c . ) are a l s o included i n t h i s s e c t i o n , and examples w i l l be given. A rig o r o u s d e f i n i -t i o n of embeddings i s given i n S e c t i o n 2 , since both P f a l t z 11 7 and Rosenfeld's and Montanari's papers l a c k some p r e c i s i o n i n t h i s r e s p e c t . In S e c t i o n 3» the goals f o r the implementation of the system are e x p l i c i t l y given. The various problems that have to be solved i n t h i s p r o j e c t are a l s o s t a t e d , and the reasons f o r the occurence of these problems are given. The d e t a i l e d algorithm f o r t h i s p r o j e c t i s s t a t e d i n Se c t i o n k. The algorithm f o r the problem of replacement of a subweb by another on the d i s p l a y s c r e e n , i s e s p e c i a l l y t r e a t e d . In t h i s s e c t i o n , the data s t r u c t u r e ( i n t e r n a l r e p r e s e n t a t i o n ) of the webs .and-.a general d e s c r i p t i o n of the program are given. There are s p e c i a l key words i n t h i s system, which are explained. The l i m i t a t i o n s of the system are a l s o i n d i c a t e d . In S e c t i o n 5» an example of the two t e r m i n a l s e r i a l p a r a l l e l network i s given. The r e s u l t s and observations a f t e r some t e s t runs w i t h the system are discussed as w e l l as p o s s i b l e f u r t h e r developments and improvements. In Appendix A, there i s a l i s t i n g of the program. In Appendix B, the d e t a i l s of how t o use the system are described. 2. DEFINITIONS AND EXAMPLES In a conventional phrase-structure " s t r i n g grammar"* the "sentences" of the language generated by the grammar are s t r i n g s ; i n a " p i c t u r e grammar" the "sentences" of one language are p i c t u r e s of va r i o u s types. Web grammars generate "sentences" which are d i r e c t e d l a b e l l e d graphs. A d i r e c t e d graph i s a two-tuple G = ( NQ , AQ ) , where NQ i s a f i n i t e s e t , whose elements are c a l l e d the "node" of G and AQ C Ng x N & i s a set of ordered p a i r s whose elements are c a l l e d the " a r c s " of G. A graph H = ( N H , A^ ) i s c a l l e d a subgraph of G = ( NQ , AQ ), i f ( i ) N H C N Q and ( i i ) A H = AQ fl N H x N H i . e . A H c o n s i s t s of ju s t those arcs of AQ whose both endpoints are i n N^. Thus any subset N of NQ defines a unique subgraph, which we c a l l the subgraph on N. A web V/ i s defined as t r i p l e W = ,( G, V, A ), where G= ( NQ , Ag ) i s a d i r e c t e d graph, V i s a f i n i t e set ( the "alphabet" ) whose elements are c a l l e d "symbols", and X i s a f u n c t i o n from N G t o V, x s NQ * V, c a l l e d the " l a b e l l i n g " . A web W = ( G', V , /\' ) i s c a l l e d a subweb of W = . ( G, V, A ) i f and only i f ( i ) G' = ( N R , A ) i s a subgraph of G = * G ( N G , A G ), ( i i ) V C V and ( i i i ) A'(n) = x(n) V n e NQ. , i . e . A' i s the r e s t r i c t i o n of A t o NQ , . A web grammar i s a t r i p l e y = ( V, I, R ), where V i s an alphabet, V = V N U V.j, where V N and V,-p are two d i s j o i n t s e t s , V^ i s the "non-terminal" alphabet and Vrp i s the " t e r m i n a l " alphabet, I i s a set of " i n i t i a l webs" and R i s a set of " r e w r i t i n g r u l e s " . R e w r i t i n g r u l e s of the form « - - - ^ i n s t r i n g grammars are used t o replace one s t r i n g by another. Such a r u l e i s completely determined by s p e c i f y i n g the p a i r of s t r i n g s ( c<, p ). Any s t r i n g co = ykxy which contains <X as a s u b s t r i n g can be immediately r e w r i t t e n as ty^ff. This i s the case because i n a s t r i n g , due t o i t s l i n e a r i t y , the l a s t symbol of ^ can be viewed as being connected t o the f i r s t of cx o r ^ respec-t i v e l y , and the f i r s t symbol of <p as connected t o the l a s t symbol of <x o r p r e s p e c t i v e l y . This l i n e a r o r d e r i n g does not e x i s t f o r general webs and thus r e p l a c i n g part of a web by another one i s more complicated. A web r e w r i t i n g i s not completely determined by j u s t s p e c i f y i n g the p a i r of webs ( 1$ ), more d e f i n i t i o n i s necessary. A subwebcxof a web may connect to the r e s t of the web i n many d i f f e r e n t ways and any node i n the r e p l a c i n g web j$ » may be connected to any number of nodes i n £o - oi . During the process of replacing ex by p we have therefore to specify e x p l i c i t l y how the web y3 has to be connected to oo - ex. a f t e r the deletion of « from w. This s p e c i f i c a t i o n of arcs between /3 and 6o - c* i s c a l l e d the "embedding" of ^ In co . It i s e s s e n t i a l that the d e f i n i t i o n of an embedding i n a rewriting rule must not be dependent upon a p a r t i c u l a r web, 6 j , i n such a manner that would prevent us from replacing any occurence of <* by {3 i n any web that contains o< as a subweb. The d e f i n i t i o n has to be general so that can be replaced by p no matter what <w i s . Before we go ahead to define an embedding l e t us define the l e f t and right neighbourhood of a node i n a web. Let co -( N M , A w , A w ) be a web, then the l e f t neighbouhood of a node n e N w i s the set t L(n) = -[ m € Nco 8 ( m, n ) € A w ], and the r i ght neighbourhood of a node n e N w i s the set» R(n) = [ m € N w : ( n, m ) € A ^ ] . If (X = ( Nc* , AQC , Ac* ) i s a subweb of co , we define the, l e f t and right connect ions' i n ^ of a node n € Noc as the sets: L K(n) = { m e N w - s ( m, n ) € Aco ] , and Ro<(n) = ^ m £ N w - N,x ! ( n, m ) € A w ] respectively. The l e f t connections of i n co i s the set J L(cx) = U L w(n) , and n £ the r i ght connections of oc i n to i s the set: U B n .€ N<* R(oO = R w(n) . I n t h e c a s e o f a s t r i n g grammar we have L(<x") H R(^} = jZf i f (A i s n o t t h e empty s t r i n g . T h i s i s n o t n e c e s s a r i l y t r u e f o r web grammars . As i n d i c a t e d b e f o r e , t h e s p e c i f i c a t i o n o f a r c s b e t w e e n p and co i s t h e embedding o f in oo . L e t us d e f i n e t h e embedding o f ^ i n ^ as i E(|3) = { ( m, n ' ) : m e L{f), n e N ^ ] U { ( n , m ) 5 m € R ( ^ ) , n e N ^ ] . T h i s d e f i n e s how t h e i n s e r t i n g web, /3 , i s c o n n e c t e d t o t h e web, t o . Now we must d e f i n e , f o r e a c h web r e w r i t i n g r u l e , ( <*» {3 > E ) , t h e l e f t and r i g h t c o n n e c t i o n s o f /3 . P f a l t z and 11 R o s e n f e l d a l l o w any l o g i c a l s p e c i f i c a t i o n s f o r t h i s , i . e . t h e d e s c r i p t i o n o f L(^3) and R(^3) c a n depend on any p r e d i c a t e d e f i n e d on co. More s p e c i f i c a l l y , t h e s e p r e d i c a t e s may depend on t h e n o d e s , a r c s and l a b e l s o f c o . They a r e t h e r e f o r e f u n c -t i o n s o f t h e k i n d p : N ^ x N ^ . . . x N w + £ t r u e , f a l s e ] , n a m e l y d e p e n d i n g on any f i n i t e number o f n o d e s ; t h i s i m p l i e s dependency upon a r c s and l a b e l s . O b v i o u s l y t h e s e p r e d i c a t e s s h o u l d be dec idabxLe. I n t h i s p r o j e c t we a l l o w f o r : L (n) = j m 6 L ^ n ' ) s p » , n ' € N * \ and R (n) = | m € R < x ( n ' ) i . p w ( m ) , n ' 6 N ^ ] . F u r t h e r r e s t r i c t i o n s o f embeddings have b e e n s t a t e d by P a v l i d i s ^ . He r e s t r i c t s t h a t | fl N^ | = 1 o r 2 and Nco (1 No< = Nco fi N^ g , i . e . he a l l o w s o n l y s u c h r u l e s w h i c h p e r m i t . c< and t o have 1 o r 2 nodes i n common w h i c h r e m a i n s t a b l e d u r i n g t h e p r o c e s s o f r e w r i t i n g , and t h e s e nodes a r e t h e o n l y c o n n e c t i o n s b e t w e e n t h e webs /3 and °o . S i n c e no f u r t h e r 8 connection between a> and ($ i s allowed, the embedding of each r u l e i s not s p e c i f i e d . A web r e w r i t i n g r u l e can how be defined as a t r i p l e ( cx;, 1$ , E ), where o< and ^ are webs and E i s an embedding of /3. P f a l t z and Rosenfeld define the web r e w r i t i n g r u l e E ) t o be c o n t e x t - s e n s i t i v e i f there e x i s t s a node n of « such tha t - ( [ n ] , V, A(n) ) i s a subweb of fi . I t i s s a i d 11 t o be c o n t e x t - f r e e i f <* has only a s i n g l e node The f o l l o w i n g i s an example of a c o n t e x t - f r e e graph 11 grammar taken from P f a l t z and Rosenfeld's paper i V = { X, x J , I = | x x x X x | , R c o n s i s t s of r u l e s : • • — • »• where X^ and X2 are not new l a b e l s , the s u b s c r i p t s are used f o r i d e n t i f i c a t i o n between the two nodes. E = { ( p, X 1 ) : ( p, X ) € A^} U j ( x2 , p ) t ( x, p ) e A W ] . X X • — • • — X E = [ ( p, X ) s ( p, x ) e A w J u { ( X, p ) : ( X, p ) € A^ j X x . := . ( Ri ) ( Ro ) ( R3 ) 9 E = { ( pv X ) : ( p , X ) € } U j ( x, p ) « ( X, p ) € Aco ] . 11 P f a l t z and Rosenfeld mention contextual conditions , which are the conditions imposed on the context of a web to determine the a p p l i c a b i l i t y of a rewriting r u l e . They do not include the contextual condition i n t h e i r d e f i n i t i o n of web rewriting rules, yet they do use i t i n one of t h e i r examples* Montanari, i n his d e f i n i t i o n of a rewriting rule, defines the contextual condition to be a l o g i c a l function upon the con-text of a web. He defines a web rewriting rule to be a four-tuple ( <X, C, E ), where cX and 3^ are webs, C i s a l o g i c a l function, the contextual condition, and E i s an embedding of fi i n co ; The web rewriting rule i s applicable i f C i s true. Montanari proves that his d e f i n i t i o n of a rewriting rule i s equivalent to that of P f a l t z and Rosenfeld's d e f i n i t i o n i n so f a r as the same webs get produced. Application of a web rewriting rule means e s s e n t i a l l y the same as that of a s t r i n g rewriting r u l e , except that the embedding i s used f o r the linkage of fi to the web co - cX • Use the previously mentioned web grammar ( on page 8 ) as an example. Suppose we have obtained the following web a f t e r applying web rewriting rules f o r some time: x 10 Let us apply Rr,. We f i r s t delete & from the web, oJ , and "break" a l l the arcs that connect cx to to - o< . Then we have: x 00 - oc. = . Next the web, , i s inserted into ^ - <* and we have: X x x The f i n a l step i s doing the embedding. Then we obtain: Let = ( V , I, R ) be a web grammar. Let us define a p a r t i a l order r e l a t i o n ^ * such that ^ -pr*- ^ 2 ^ a n d o n l y i f 6->2 c a n ^e obtained from by the application of a single rewriting of R. Let us further define by to 1 * p 6u i f and only i f there exist co ? , , ... , j- Q m c. J 0 com_]_ such that 1 g 2 2 ^ 3 , . . . , m i . e . c o m can be derived from ^ i n the grammar, Q-.. The language of a grammar ^ i s defined t o be the s e t : L( ) = [ co = ( N, A, A ) : X(n) 6 V T ¥ n £ N and -J i € I such that i — j r* <o ] . The language of the c o n t e x t - f r e e graph grammar given above i s the set of 11 a l l two t e r m i n a l s e r i a l p a r a l l e l networks For the sake of reference, a few terms are discussed. In a r e w r i t i n g r u l e ( y3, E ), o< and p are c a l l e d the l e f t web and the r i g h t web r e s p e c t i v e l y . The host web i s defined t o be the web which i s c u r r e n t l y used f o r the a p p l i c a t i o n of web r e w r i t i n g r u l e s . Since we are working w i t h d i r e c t e d graphs, we need t o know the d i r e c t i o n of an arc which i s represented by an arrow on the d i s p l a y screen. The term from-node i s used t o i n d i c a t e the node at the t a i l of an arrow ( a d i r e c t e d arc ) and the term to-node i n d i c a t e s the node at the head of an arrow ( see Figure 1.1 ) . from-node to-node *. arc r e p r e s e n t a t i o n of a d i r e c t e d arc on the d i s p l a y screen Figure 1.1 For the s p e c i f i c a t i o n of embeddings, we must introduce some more terminology t o describe them i n the program. The coding of the embedding of a r u l e i s described by sets of f o u r - t u p l e s ( A, T, B, C ), where : 12 A contains a l a b e l or where represents "whatever", i . e . whatever the l a b e l i s , T i s a l i t e r a l s t r i n g ; i t contains either 'to' or 'from'; t h i s determines the d i r e c t i o n of arcs, B i s a node of the l e f t web, c* , and C i s a node "of the right web, /3 . For example, take ( ) from page 8 for i l l u s t r a t i o n . . , x x l x 2 ( R t ) . s= . p. E = ( ( p, X1 ) : ( p, X ) e A ] U ( X 2 , p ) I ( X, p ) e A ] . Two sets of ( A, T, B, C ) i s needed to describe:the embedding. They are: ( 'from', X, X^ ), meaning that a l l the from-nodes of X w i l l be fromr-nodes of X^ and ( •*', 'to', X, X 2 ), meaning that a l l the to-nodes of X w i l l be to-nodes of X 2 « 13 3... SPECIFICATION OF PROBLEMS The t o p o l o g i c a l s t r u c t u r e of a graph i s given by the d e s c r i p t i o n of i t s nodes and t h e i r r e l a t i o n s , the a r c s , i n terms of neighbourhood; the d e f i n i t i o n s of d i r e c t e d graphs and webs ( i n S e c t i o n 2 j ) g i v e t h e i r t o p o l o g i c a l s t r u c t u r e s . In a geometrical s t r u c t u r e , a graph i s described i n terms of poi n t s ( nodes ) i n an n-dimensional Euclidean space, u s u a l l y 2-dimensional, interconnected by a system of l i n e s ( arcs ). For a l a b e l l e d graph, associated w i t h each point (if.node ) there i s a l a b e l attached f o r i d e n t i f i c a t i o n . In S e c t i o n 1, we have mentioned the importance of graphs to engineering, a r c h i t e c t u r e , operations research, l i n g u i s t i c s , e t c . , yet the t o p o l o g i c a l s t r u c t u r e of a graph has l i t t l e or no appeal f o r those who d e s i r e t o u t i l i z e graphs f o r s o l v i n g problems, e.g. p r i n t e d c i r c u i t design, s o l v i n g operations research problems by graphs, aeroplane and automobile design. Most people, when t h i n k i n g of graphs, t h i n k i n terms of t h e i r geometrical s t r u c t u r e s . The main purpose of t h i s p r o j e c t i s t o implement an i n t e r a c t i v e graphical.system f o r the s p e c i f i c a t i o n of web and embeddings and f o r the a p p l i c a t i o n of web grammars. A g r a p h i c a l system should enable the user to work on graphs i n a n a t u r a l manner, i . e . as a person working w i t h p e n c i l and paper on the p i c u t r e of a graph would do; the system should a l s o be easy and convenient t o use, and such operations as i n s e r t i o n or d e l e t i o n of a node, an arc or a node l a b e l should be allowed. 14 The implementation of t h i s p r o j e c t u t i l i z e s an i n t e r -a c t i v e graphics device, the Adage G r a p h i c a l Terminal ( AGT ), .for d i s p l a y of webs, commands, i n s t r u c t i o n s and input of webs and embeddings. The AGT provides a l i g h t - p e n , 16 f u n c t i o n keys, 2 foot pedals and 6 d i a l s f o r the i n t e r a c t i o n between user and the computer^ . The AGT d i s p l a y screen i s used as a sheet of blank paper f o r the user t o "draw" webs, i . e . t o s p e c i f y the t o p o l o g i c a l s t r u c t u r e s of webs i n terms of t h e i r geometrical r e p r e s e n t a t i o n s . The l i g h t - p e n i s the most con-venient t o o l t o use, yet due t o i t s l i m i t e d c a p a b i l i t y , d i a l s and f u n c t i o n keys are used i n co-operation w i t h the l i g h t - p e n . During the process of "drawing" webs, the f i d d l i n g around w i t h l i g h t - p e n , d i a l s and f u n c t i o n keys i s very clumsy and time consuming. However, because of the reason j u s t mentioned above t h i s cannot be avoided. I f a web i s used many times as l e f t web or r i g h t web or host web, only one copy of the web i s to '.be i n p u t . This w i l l minimize the time f o r input of webs. Moreover, i t i s a very b o r i n g task f o r the user t o input the same web many times. Since the input of webs i s done by drawing the webs on the d i s p l a y screen, the user does not have to know the i n t e r n a l r e p r e s e n t a t i o n of webs. Throughout the whole program, the AGT screen i s a l s o used as the i n s t r u c t i o n sheet t o show the user what a c t i o n he could or should take and what instruments he should use. During the process of a p p l y i n g r e w r i t i n g r u l e s , the host web i s subject t o change a l l the time, subwebs are deleted and i n s e r t e d . A problem of general importance to computer g r a p h i c s a r i s e s , n a m e l y how t o a c c o m o d a t e t h e u s e r ' s d e s i r e f o r f a s t o r e v e n i m m e d i a t e r e s p o n s e w h i l e p o s i t i o n i n g a n d s c a l i n g t h e new web w h i c h i s r e p l a c i n g a n o l d one. S i n c e a p i c t u r e u s u a l l y c o n t a i n s a c o m p l e x s t r u c t u r e w h i c h i s o f m e a n i n g t o t h e u s e r , one h a s t o k e e p a n a p p r o p r i a t e d a t a s t r u c t u r e up t o d a t e and r e f r e s h t h e s c r e e n a s f a s t a s p o s s i b l e a t t h e same t i m e . Thus t h e p r o b l e m i s how t o m a i n -t a i n a r a p i d l y c h a n g i n g , " r e a d a b l e " p i c t u r e on a v e r y l i m i t e d s p a c e . What p a r t s h o u l d p l a y ? What p a r t s h o u l d p r o c e d u r e s p l a y ? A d i s c u s s i o n o f o u r s o l u t i o n o f t h e p r e s e n t c a s e f o l l o w s i n S e c t i o n 4. 4. IMPLEMENTATION For implementation, the most important problem to be solved i s the i n s e r t i o n of one subweb to replace another one. On display screen, each subweb occupies a c e r t a i n area. Since the deleted subweb w i l l disappear from the display screen, i t i s quite natural to insert the new subweb into the same space the deleted subweb had occupied. The co-ordinates of a l l the nodes of the deleted subweb are known, therefore the problem of where the subweb i s to be placed i s easy to solve. The problem of how the subweb i s to be placed there remains. The co-ordinates of the i n s e r t i n g subweb, /3 , are a l l known, the area occupied by i t may be d i f f e r e n t from that of the deleted subweb, c< . In order to place the i n s e r t i n g subweb into the area the deleted subweb had occupied, we have to scale and displace the i n s e r t i n g subweb. Let us define the x-span of a web, co , to be the d i f f e r -ence between the maximum x co-ordinate value and the minimum x co-ordinate value: Sp„(w) = x - X m i v , ^ x max mm The y-span of a web, c o , i s defined to be the defference between the maximum y co-ordinate and the minimum y co-ordinate value: Sp v(^) = y - y m. • y max mm The x-scaling function, S x , i s defined to be j Sp x(*)/Sp y(/3) i f Spx(o<) / 0 and Spx(/S) 4 0 v k otherwise, where k i s a constant, where e* i s the deleted subweb and p i s the i n s e r t i n g subweb. The y - s c a l i n g function i s defined to be: f Sp y(o<)/Sp y(^) i f Spy(c<) ,1 o and Spy(/3) 4 0 (. k otherwise, where k i s a constant. The x-displacement function D x i s defined to be: D x = x m i n(o0 " x m i n (^ ) , where x in(o<) i s the minimum x co-codinate value of the deleted subweb, cx , and x mj_ n(|3) i s the minimum x co-ordinate value of the i n s e r t i n g subweb, ^ . The y-displacement function D y i s defined to be: D y = y m i n ( o < ) " ymin^>' where ymin(<>0 i s the minimum y co-ordinate value of the deleted subweb, <X , and y . (/3) i s the minimum y co-ordinate value of •'mm / the i n s e r t i n g subweb, ^3 . F i n a l l y , we can define how the i n s e r t i n g subweb, p> , i s to be placed into the host web, £o - <x . The subweb i s inserted conserving i t s o r i g i n a l shape, i . e . the same configuration as i s input. A l l we have to do i s re-defining the co-ordinates of the i n s e r t i n g subweb, ^ , as follows: xnew = s x < x o l d - 0 X ) + D x , y n e w = s y ( y 0 i d " V } + Dy 18 where ( x ^ , j , y n j ) i s the o l d co-ordinate p o i n t , ( x , o l d ''old new y ) i s the new co-ordinate p o i n t and ( 0 „ , 0 ) i s the co-ordinate p o i n t chosen as the o r i g i n of r e f erence. In t h i s p r o j e c t , a rectangle i s used t o describe the area occupied by a web or subweb. The value of k f o r the f u n c t i o n , S x , i s set t o 1 i f e i t h e r Spx(o<) = 0 or Sp^ (/3) = 0; the value of k f o r the f u n c t i o n , S , i s set t o 1 i f e i t h e r sPy(°0 = 0 or Spy(^3) = 0. The co-ordinate p o i n t ( x m i n(«:) , y m^ n((X) ) i s chosen as the p o i n t of o r i g i n of reference f o r the i n s e r t i o n of the subweb, /3 . The x m ^ n , x m a x , ymin and y m Q V of any web are found d u r i n g the process of s p e c i f y i n g the web, but these values f o r the deleted subweb are found d u r i n g the process of a p p l y i n g r e w r i t i n g r u l e s . During t h i s process, we have to search f o r a p p l i c a b l e r u l e s . This i n v o l v e s the problem of matching the l e f t web of each web r e w r i t i n g r u l e t o the subwebs of the host web. Since we assume th a t the l e f t webs of web r e w r i t i n g r u l e s are not very complex, no s p e c i a l a l g o r i t h m i s provided to solve t h i s problem. In t h i s p r o j e c t , the t e s t f o r a p p l i c a b i l i t y of each r u l e i s done by matching the l e f t web, node by node, t o the subwebs of the host web. During the process of matching, the subwebs are determined by the r e l a t i o n s of the l e f t and r i g h t neighbourhood of each node. The algorithm w i l l be given l a t e r . Since the s t r u c t u r e of a graph i s changing a l l the time, i . e . nodes, arcs and l a b e l s are i n s e r t e d and deleted c o n s t a n t l y , 1 9 e s p e c i a l l y d u r i n g the process of r e w r i t i n g , we have t o choose a computer language w i t h the a b i l i t y of dynamic a l l o c a t i o n of storage. Thus, ALGOLW i s chosen f o r t h i s p r o j e c t f o r the f o l l o w i n g reasons: ( i ) I t has the a b i l i t y of dynamic a l l o c a t i o n of data spaces ( the data type RECORD ). ( i i ) I t i s much cheaper t o use on an IBM 3 6 0 / 6 7 than language such as P L / l . 4.1 DATA STRUCTURES During the process of s p e c i f y i n g ( input ) webs, search-i n g through the d i s p l a y b u f f e r i s necessary t o i d e n t i f y each node because whatever i s done t o the web i s i n d i c a t e d on the d i s p l a y screen. For in s t a n c e , i f an arc between two nodes i s t o be created, these nodes have t o be s p e c i f i e d on the d i s p l a y screen. To speed up the searching, each node i s coded by a hash f u n c t i o n on the x co-ordinate value. The hash f u n c t i o n , , used i s : the number x, - 1 0 ^ x ^ 1 0 . Therefore ^ takes the values from 0 t o 1 0 , 0 ^ H 1 ^ 1 0 . During the process of a p p l y i n g r e w r i t i n g r u l e , we have to search f o r a p p l i c a b l e r e w r i t i n g r u l e s . This i n v o l v e s the matching of the l e f t web of each web r e w r i t i n g r u l e to the subwebs of the host web. In doing t h i s , we are matching the node l a b e l s . Matching node l a b e l s one by one i s time consuming. 20 To speed up the matching process, each l a b e l i s assigned a unique p o s i t i v e integer, ( f o r the same node l a b e l , the same integer i s assigned, i . e . i f a node of a web has the l a b e l 'b* and the integer assigned i s 7, then to a node of the same web or to any other web with a node of the same l a b e l *b', the integer 7 i s also assigned ). The hash function, H 2 , i s used on the integer assigned to each node l a b e l . Nodes with the same hash function value are stored i n the same stack. H 2 = R( 1/10 ) where R ( i / l O ) i s the remainder of I divided by 10, I i s the integer'assigned to the node l a b e l concerned. Figure 4.1 gives the structure of a web, Figure 4.1.a i s the header of a web, and the headers of webs are stored in\a stack. Figure 4.1.b gives the structure of a node. In Figure 4.1.a, WEB NAME i s the name of a web f o r i d e n t i f i c a t i o n , i s the hash function on the x co-ordinate values of nodes, H 2 i s the hash function on the node labels, NEXT WEB i s the pointer to the next i n the stack. In Figure 4.1.b, X and Y are the co-ordinates of a node on the graphical display screen, LABEL i s the l a b e l of the node, TO-NODE i s the pointer to a stack which s p e c i f i e s the right neighbourhood of the node, 21 WEB NAME H, NEXT WEB -••nodes -•nodes Y LABEL TO-NODE FROM-NODE NEXT NODE ID I r i g h t •neighbourhood • l e f t neighbourhood ( a ) s t r u c t u r e of headers of webs ( b ) s t r u c t u r e of a s i n g l e node Figure 4.1 FROM-NODE i s the p o i n t e r t o a stack which s p e c i f i e s the l e f t neighbourhood of the node, NEXT NODE i s the p o i n t e r t o the next node i n the stack, which contains nodes w i t h the same hash f u n c t i o n value, ID i s a p o s i t i v e i n t e g e r which i s used i n t e r n a l l y t o i d e n t i f y nodes' w i t h the same l a b e l , I i s a p o s i t i v e i n t e g e r assigned i n t e r n a l l y t o the node l a b e l . 4.2 THE ALGORITHM The a l g o r i t h m i s e s s e n t i a l l y d i v i d e d i n t o three s t a t e s , namely State 1, State 2 and State 3 ( see Figure 4.2). State 22 1 is. the d r i v e r r o u t i n e which governs the flow of the algorithm. State 2 c o n s i s t s of f i v e d i s c r e t e p a r t s , each of these parts performs a c e r t a i n task and i t i s these f i v e p a r t s which c o n s t i t u t e the heart of the system. Some of these p a r t s are f u r t h e r subdivided i n t o other parts which are i n State 3 . State 1 J State 2 J — S t a t e 3 J State diagram Figure 4 . 2 In State 1 , a l l necessary constants are i n i t i a l i z e d . The substates of State 2 are a c c e s s i b l e only from State 1 and they can be entered as many times as the user wants. Substates of State 3 are a c c e s s i b l e only from the corresponding part i n State 2 . The p a r t s i n State 2 define the main tasks that can be achieved i n t h i s system and the parts i n State 3 define the operations a v a i l a b l e f o r the t a s k s . The f i v e p a r ts i n State 2 are as f o l l o w s : ( i ) s p e c i f i c a t i o n of webs, i . e . input of webs by s p e c i f y i n g the geometrical c o n f i g u r a t i o n s , ( i i ) s p e c i f i c a t i o n of r u l e s , i . e . the s p e c i f i c a t i o n of the l e f t webs and the r i g h t webs, ( i i i ) s p e c i f i c a t i o n of the host web, ( i v ) s p e c i f i c a t i o n of embeddings f o r each r u l e and (v) a p p l i c a t i o n of web r e w r i t i n g r u l e s . The algorithm i s as f o l l o w s : 2 3 Step 1 set the number of webs to zero; Step 2 set the number of r u l e s t o zero; Step 3 i n d i c a t e which of the f i v e p a r ts i n State 2 i s t o be entered; Step 4 i f none of the f i v e p a r t s i s i n d i c a t e d then stop; Step 5 evoke the i n d i c a t e d p a r t ; Step 6 go t o step 3« Figure 4 . 3 i l l u s t r a t e s the flow of the a l g o r i t h m i n State 1. Only one of the f i v e p a r ts i n State 2 i s f u r t h e r sub-d i v i d e d i n t o p a r t s i n State 3> i t i s "the part f o r the s p e c i -f i c a t i o n of webs. This has seven d i s c r e t e p a r t s , each of which performs a unique operation on a web. The seven d i s c r e t e p a r t s are as f o l l o w s : ( i ) c r e a t i o n of a node, i . e . i n d i c a t i o n of the p o s i --,v!, ' t i o n of a node on the AGT d i s p l a y screen; a dot w i l l be d i s p l a y e d t o represent the node, ( i i ) c r e a t i o n of a d i r e c t e d a r c , i . e . s p e c i f i c a t i o n of the from-node and the to-node; an arrow w i l l be d i s p l a y e d on the screen t o represent the a r c , ( i i i ) c r e a t i o n of a l a b e l f o r a node, i . e . input a l i t e r a l s t r i n g through the IBM 2 2 6 0 keyboard, ( i v ) d e l e t i o n of a node, i . e . delete a node from the web together w i t h i t s l a b e l and a l l arcs l e a d i n g to and from the node; a l l i n f o r m a t i o n concerning the node w i l l disappear completely, (v) d e l e t i o n of an a r c , 24 i n i t i a l i z a t i o n of constants t , £ decision? «^^stop^) , t , s p e c i f i c a t i o n of webs s p e c i f i c a t i o n of host web , t , s p e c i f i c a t i o n of embeddings , 1 -> application of rules s p e c i f i c a t i o n of rules flow diagram f o r the algorithm for State 1 Figure 4.3 (vi) deletion of a node l a b e l and ( v i i ) s p e c i f i c a t i o n of a new webj t h i s means that the creation of a web i s fin i s h e d , a new web i s to sp e c i f i e d . A l l these parts are accessible only t;hrough the part for specificatdbn:of webs, and ultimately return control to that part i n State 2. Figure 4.4 i l l u s t r a t e s the flow of the C algorithm f o r the s p e c i f i c a t i o n of webs 25 ( ^ r e t u r n ^ create a node create an arc create a node l a b e l ]~ -© £ d e c i s i o n ? J * delete a node J >f S delete an arc - 0 delete a node l a b e l create a new web J >C^ ) flow diagram f o r the algorithm f o r the s p e c i f i c a t i o n of web Figure 4.4 26 The algorithm f o r the s p e c i f i c a t i o n of webs i s as f o l l o w s s Step 1 increase the number of webs by l j Step 2 input the name f o r the web which i s t o be created; set the number of nodes t o 0; Step 3 i n d i c a t e which of the seven p a r t s i n State 2 i s to be entered; Step 4 i f none of these p a r t s i s i n d i c a t e d then r e t u r n ; Step 5 "evoke the i n d i c a t e d p a r t ; Step 6 i f i t i s the seventh part ( create a new web ) then go t o step 1 e l s e go t o step J. The algorithm f o r c r e a t i o n of a node i s as f o l l o w s * Step 1 d i s p l a y the part of the web th a t has already been created; Step 2 i n d i c a t e the p o s i t i o n of the node on the d i s -p l a y screen; Step 3 i n s e r t the node t o the web according t o the hash f u n c t i o n ; Step 4 i n s e r t the node i n t o the d i s p l a y b u f f e r ; Step 5 increment the number of nodes by 1; Step 6 r e t u r n . The algorithm f o r the c r e a t i o n of a d i r e c t e d arc i s as fo l l o w s s Step 1 i f the number of nodes i s greater or equal t o 2 then go t o step 2 e l s e r e t u r n ; Step 2 d i s p l a y the part of the web th a t has already 27 been created; Step 3 i n d i c a t e the from-node; Step 4 i n d i c a t e the to-node; Step 5 i n s e r t the arc i n t o the data s t r u c t u r e ; Step 6 i n s e r t the arc i n t o the d i s p l a y b u f f e r ; Step 7 r e t u r n . The algorithm f o r the c r e a t i o n of a node l a b e l i s as f o l l o w s : Step 1 i f the number of nodes < 1 then r e t u r n ; Step 2 d i s p l a y the part of the web that has already been created; Step 3 i n d i c a t e the node whose l a b e l i s t o be in p u t ; Step 4 input the node l a b e l ; Step 5 i n s e r t the l a b e l i n t o the data s t r u c t u r e ; Step 6 set up the hash f u n c t i o n H 2 f o r the j u s t input node l a b e l ; Step 7 i n s e r t the node l a b e l t o the d i s p l a y b u f f e r ; Step 8 r e t u r n . The algorithm f o r the d e l e t i o n of a node i s as follows;' / Step 1 i f the number of nodes < 1 then r e t u r n ; Step 2 i n d i c a t e the node t o be d e l e t e d . Step 3 delete the node together w i t h i t s l a b e l and arcs l e a d i n g from and t o the node, from the data s t r u c t u r e and the d i s p l a y b u f f e r ; Step k decrement the number of nodes by 1; Step 5 r e t u r n . 28 The a l g o r i t h m f o r t h e d e l e t i o n o f an a r c i s as f o l l o w s : S t e p 1 i f t h e r e i s no a r c e x i s t i n g t h e n r e t u r n ; S t e p 2 d i s p l a y t h e p a r t o f t h e web t h a t has a l r e a d y b e e n c r e a t e d ; S t e p 3 i n d i c a t e t h e a r c t o be d e l e t e d ; S t e p k d e l e t e t h e a r c f r o m t h e d a t a s t r u c t u r e and •/ f r o m t h e d i s p l a y b u f f e r ; S t e p 5 r e t u r n . The a l g o r i t h m f o r t h e d e l e t i o n o f a node l a b e l i s as f o l l o w s : S t e p 1 i f t h e r e i s no node l a b e l e x i s t i n g t h e n r e t u r n ; S t e p 2 d i s p l a y t h e p a r t o f t h e web t h a t has a l r e a d y been c r e a t e d ; S t e p 3 i n d i c a t e t h e node whose l a b e l i s t o be d e l e t e d ; S t e p 4 d e l e t e t h e l a b e l f r o m t h e d a t a s t r u c t u r e and f r o m t h e d i s p l a y b u f f e r ; S t e p 5 r e t u r n . The p a r t f o r t h e s p e c i f i c a t i o n o f a new web s t o r e s t h e c r e a t e d web and t h e n r e t u r n s c o n t r o l t h e c a l l i n g p r o c e d u r e . The a l g o r i t h m f o r t h e s p e c i f i c a t i o n o f r u l e s i s as f o l l o w s : S t e p 1 i f t h e number o f webs < 0 t h e n r e t u r n ; S t e p 2 i n d i c a t e t h e r u l e whose l e f t and r i g h t webs a r e t o be s p e c i f i e d ; S t e p 3 i f none o f t h e r u l e s i s i n d i c a t e d t h e n r e t u r n else set i t o the r u l e number; Step 4 d i s p l a y the web names; Step 5 i n d i c a t e the l e f t web f o r the i - t h r u l e ; Step 6 d i s p l a y the names of webs; Step 7 i n d i c a t e the r i g h t web f o r the i - t h r u l e ; Step 8 s e t v U p a.record f o r the l e f t and r i g h t webs t h e . i - t h r u l e ; Step 9 go t o step 2. The algorithm f o r the s p e c i f i c a t i o n of the host web i as f o l l o w s : i f the number of webs ^ 0 then r e t u r n ; d i s p l a y the web names; i n d i c a t e the host web; set up record f o r the host-web; r e t u r n . The algorithm f o r s p e c i f i c a t i o n of embedding i s as f o l l o w s J Step 1 i f there-is no r u l e e x i s t i n g then r e t u r n ; Step 2 i n d i c a t e the r u l e whose embedding i s t o be s p e c i f i e d ; Step 3 i f no r u l e i s i n d i c a t e d then r e t u r n e l s e s<= i t o the r u l e number; Step 4 s p e c i f y A; Step 5 s p e c i f y T; Step 6 d i s p l a y , the l e f t web of the i - t h r u l e ; Step 7 s p e c i f y B; Step 8 d i s p l a y the r i g h t web of the i - t h r u l e ; Step 1 Step 2 Step 3 Step k Step 5 30 Step 9 s p e c i f y C; Step 10 go to step 2. The algorithm f o r the a p p l i c a t i o n of a web r e w r i t i n g r u l e i s as f o l l o w s : Step 1 d i s p l a y the host web; Step 2 i f no r u l e i s t o be a p p l i e d then r e t u r n ; Step 3 f i n d the a p p l i c a b l e r u l e s ; i f there,are none then r e t u r n ; Step 4 . i n d i c a t e which a p p l i c a b l e r u l e i s t o be a p p l i e d ; Step 5 i n s e r t the newly found copy of the r i g h t w'feb of the i n d i c a t e d a p p l i c a b l e r u l e ; Step 6 delete the subweb isomorphic t o the l e f t web of the i n d i c a t e d a p p l i c a b l e r u l e ; Step ? do the embeddings, then go t o step 2. 4.2.1 THE ALGORITHM FOR THE REPLACEMENT OF A WEB In t h i s p r o j e c t the area occupied by a web or subweb i s described by a rectan g l e ( see Figure 4.5 ). I f cx; i s the deleted web and ^ i s the i n s e r t i n g web, the alg o r i t h m i s as f o l l o w s • f i n d x m i n , x m a x , y m i n and y m a x f o r the web d ; Step 2 c a l c u l a t e Sp x(cx) and Sp v(pO; Step 3 c a l c u l a t e Sp x(|3) and S p y ( ^ ) , ( the x m i n , xmax ' ymin a n d ^max a r e f o u n d d u r i n g the process of s p e c i f y i n g the web , ^3 ); Step 7 Step 8 Step 9 3.1 Step 4 i f either Spx(cx) = 0 or Spx(/5) = 0 then S x = 1 else S x = Sp x( )/Sp x( ; j ; ' ' y v ' . . Step 5 i f either Spy(cX) = 0 or Spy(y3) = 0 then S y = 1 else S y = S p y ( * ) / S p y ( ^ ) j Step 6 calculate D calculate D y; set 0 X = x m i n(o<)j set O y = y, mm Step 10 calculate the new x and y co-ordinates for the i n s e r t i n g web, /3 ; 4 B, B 3 / B C the rectangle ( 1,2,3»4 ) defines the area occupied by the subweb .(J-A,B",'B, B ) Figure 4.5 4.2.2 THE ALGORITHM FOR FINDING APPLICABLE RULES Before being able to apply a rewriting rule, we have to search for an applicable r u l e ; t h i s involves the matching of the l e f t web of each rule to the subwebs of the host web. For l e f t webs that are not very complex, no s p e c i a l algorithm i s needed. The matching i s done by matching the nodes of the l e f t web to the nodes of the host web. Nodes are stored i n stacks, a l l nodes of the same web with the same hash function value Hp w i l l be stored i n the same stack. The algorithm . 32 i s as f o l l o w s : Step 1 set i = 1 ; Step 2 s t a r t w i t h the f i r s t node of the l e f t web of the i - t h r u l e ; Step 3 i f the stack c o n t a i n i n g the nodes of the host web w i t h same hash f u n c t i o n ( H 2 ) value i s empty then go t o step 1 2 ; Step 4 search down the stack; Step 5 i f no match then go t o step 1 2 ; Step 6 i f the l e f t neighbourhood of the node of the l e f t web matches any subset of the l e f t neighbourhood of the node of the host web, then go to step 8 ; Step 7 i f there are nodes l e f t i n the stack ( of the host web ) then go t o 10 else go t o step 1 2 ; Step 8 i f the r i g h t neighbourhood of the node of the l e f t web matches any subset of the r i g h t nieghbourhood of the node of the host web then go t o step 1 1 ; Step 9 i f there i s no node l e f t i n the stack ( of the host web ) then go t o step 1 2 ; Step 10 continue searching down the stack ( of the host web ) and go t o step 5» Step 11 i f there i s a node l e f t i n the l e f t web then get the next node and go t o step 3 else go t o step 1 3 ; Step 12 i f there i s no other r e w r i t i n g r u l e then r e t u r n e l s e set i •'•= i + 1 and go t o step 2 ; 33 Step 13 store the value of i i n a stack which i n d i c a t e s the a p p l i c a b l e r u l e s , go t o step 12. 4 . 3 THE SYSTEM There are c e r t a i n key words that need explanation f o r running t h i s system. During the run, there are commands and i n s t r u c t i o n s d i s p l a y e d on the AGT ( Adage G r a p h i c a l Terminal ) d i s p l a y screen. At a l l stages the user i s i n s t r u c t e d about what kind of instruments are t o be used. ( see Appendix B ). There are four i n s t r u c t i o n s which r e q u i r e the use of the IBM 2260 d i s p l a y t e r m i n a l keyboard. A l l these i n s t r u c t i o n s c o n t a i n the key word 'input'; they are as f o l l o w s : ( i ) 'input the number of webs': an i n t e g e r number s p e c i f y i n g the maximum number of webs f o r the run i s t o be input ( see P l a t e 1 i n Appendix B ), ( i i ) 'input the number of r u l e s ' ; an i n t e g e r number s p e c i f y i n g the maximum number of web r e w r i t i n g r u l e s f o r the run i s t o be input ( see P l a t e 2 i n Appendix B ), ( i i i ) 'input web name': a s t r i n g of characters w i t h i n double quotes, the web name f o r the web which i s t o be s p e c i f i e d , i s t o be input ( see P l a t e 4 i n Appendix B ), ( i v ) 'input l a b e l ' : a s t r i n g of character w i t h i n double quotes, the name of the node j u s t i n d i c a t e d , i s t o be inp u t . 34 For the c r e a t i o n of a node, two d i a l s are used t o i n d i c a t e on the AGT d i s p l a y screen the p o s i t i o n of the node to be created ( see P l a t e 7 )• The d i a l s c o n t r o l the p o s i -t i o n s of two c r o s s - h a i r which are perpendicular t o each other, the h o r i z o n t a l l i n e gives t h e x co-ordinate value and the v e r t i c a l l i n e gives the y co-ordinate value. A f u n c t i o n key i s used t o i n d i c a t e that the p o s i t i o n s of the c r o s s - h a i r s are s e t . Whenever the i n s t r u c t i o n 'use f u n c t i o n key 1 or 2' appears on the screen ( see P l a t e 8 and 9 ), there i s always a sm a l l square e n c l o s i n g a node. The node i s the f i r s t one i n the d i s p l a y b u f f e r . The enclosed node i s the c u r r e n t l y a c t i v e node and the user can act on i t , e.g. the user can i n d i c a t e t h a t the node i s the to-node or the from-node of an arc or that the node i s t o be de l e t e d . A press of f u n c t i o n key 1 means that the enclosed i s the des i r e d one, and a press of f u n c t i o n key 2 w i l l make the square jump t o enclose the next node i n the d i s p l a y b u f f e r . I f key 1 i s pressed a t r i a n g l e w i l l enclose the j u s t i n d i c a t e d node ( see P l a t e 9 and 10 ). Whenever the i n s t r u c t i o n 'use l i g h t - p e n ' appears i t means that the l i g h t - p e n i s t o be used t o p i c k up items from the menu* tha t appears on the AGT d i s p l a y screen. 4 . 4 LIMITATIONS OF THE SYSTEM The l i g h t - p e n i s the most convenient and n a t u r a l i n s t r u -ment to use, yet the l i g h t - p e n f o r the AGT i s not very accurate. I f we want t o have a l i g h t - p e n h i t on the node A 35 of the web i n Figure 4 . 6 , i t might h i t on the a r c , Ac, or on the a r c , BA. For the g r a p h i c a l package used i n t h i s p r o j e c t , the l i g h t - p e n h i t r e s u l t s i n r e t u r n i n g an i n t e g e r value, i , which i n d i c a t e s t h a t the h i t i s on the i - t h word i n the d i s p l a y b u f f e r . I f the h i t i s on the a r c , Ac, we w i l l have the in t e g e r value p o i n t i n g t o the word which causes a l i n e to be drawn from A t o c on the d i s p l a y screen; t h i s word contains ? 4 the x and y co-ordinate values--" . I f the h i t i s on the arc BA, f o r the same reason j u s t mentioned, we get the co-ordinate of the node, A. This i s the reason why d i a l s and f u n c t i o n deys are used t o compensate f o r the d e f i c i e n c y of the l i g h t -pen. a l i g h t - p e n h i t occur at any point i n s i d e the c i r c l e such th a t the h i t may be on arc Ac or arc BA or on the node A In t h i s system only one arc i s allowed between any two nodes, no m u l t i p l e arcs are a v a i l a b l e . The user connot work w i t h any graph c o n t a i n i n g m u l t i p l e a r c s . A l s o , no graphs c o n t a i n i n g loops are allowed, i . e . w i t h the same node being both the from-node and the to-node of an a r c . No hard copies are a v a i l a b l e . I f the user wants a hard copy of a web, he has t o copy i t down himself or take a photograph of the web. B Figure 4 . 6 36 During the process of s p e c i f y i n g the embeddings of web r e w r i t i n g r u l e s , there i s no i n d i c a t i o n t h a t the embeddings have been s p e c i f i e d c o r r e c t l y . There i s no i n d i c a t i o n of what has been s p e c i f i e d , the user has t o keep t r a c k of t h i s . Therefore, some p r e p a r a t i o n i s necessary before s p e c i f y i n g embeddings, i . e . the user has t o make a copy of the embedd-ings f o r a l l the r u l e s . There i s no way of t e l l i n g which web i s represented by each web name. Therefore, the user somehow has t o keep a record of t h i s i n order t o i d e n t i f y each web d u r i n g the process of s p e c i f i c a t i o n of the host web or of the l e f t web and the r i g h t web of a web r e w r i t i n g . This system contains no "zoom i n " . Therefore the user w i l l not be able t o look at a c e r t a i n part of the host web c l o s e l y and work on t h a t part only. This system does not include the o p t i o n of manual manipulation of a web. The user i s not able t o manipulate a web d u r i n g the run, i . e . no i n s e r t i o n or d e l e t i o n of nodes, arcs or node l a b e l s by the user, other than d u r i n g the process of s p e c i f i c a t i o n of webs, i s p o s s i b l e . The a p p l i c a t i o n of web r e w r i t i n g i s d e s t r u c t i v e . This means tha t a f t e r the a p p l i c a t i o n of a web r e w r i t i n g r u l e there i s no way t o go back one step, i . e . t o o b t a i n the web before a p p l y i n g the r u l e . There i s no record of the sequence of r u l e s a p p l i e d . 37 5 - CONCLUSIONS AND SUMMARY The i n t e n t i o n of t h i s p r o j e c t i s t o provide an i n t e r -a c t i v e , g r a p h i c a l system t o s p e c i f y and work w i t h webs i n an easy, convenient and n a t u r a l manner. The system provides an easy way t o s p e c i f y webs without n e c e s s i t a t i n g knowledge of the i n t e r n a l r e p r e s e n t a t i o n s of web, the user needs only t o concern himself w i t h the geometrical c o n f i g u r a t i o n s of webs. Webs are s p e c i f i e d by "drawing" them on the AGT ( Adage G r a p h i c a l Terminal ) screen. This system can e a s i l y be used by any person, even a non-programmer. In t h i s system there are f i v e main tasks the user can perform, namely: ( i ) s p e c i f i c a t i o n of webs, ( i i ) s p e c i f i c a t i o n of host' web, ( i i i ) s p e c i f i c a t i o n of r e w r i t i n g r u l e s , ( v i ) s p e c i f i c a t i o n of embeddings and (v) a p p l i c a t i o n of web r e w r i t i n g r u l e s . The system provides the c a p a b i l i t y of doing any one of these tasks whenever and as many times as the user wants. Communication between man and machine i s done mostly through the AGT screen. Once the system i s running, the IBM -a 2260 d i s p l a y t e r m i n a l ^ i s h a r d l y used at a l l , except f o r the input of node l a b e l s and web names. To f u r t h e r increase the man-machine i n t e r a c t i o n , the host web i s d i s p l a y e d immediately whenever a r e w r i t i n g r u l e i s a p p l i e d , thus a user knows what-ever happens to the host web at each stage. A f t e r the s p e c i f i c a t i o n of the host web, the l e f t web or the r i g h t web of a r u l e , the i n d i c a t e d web i s d i s p l a y e d on the screen f o r 38 a short while so that the user knows which he has i n d i c a t e d . During the process of the a p p l i c a t i o n of web r e w r i t i n g r u l e s , the host web g e n e r a l l y increases i n s i z e . Due t o the way a subweb i s i n s e r t e d , the host web grows upward and expands from l e f t t o r i g h t . The i n s e r t i n g subweb,^, i n s e r t e d i n a s i m i l a r geometrical c o n f i g u r a t i o n as i s "drawn" on the AGT d i s p l a y screen, may be s m a l l e r i n s i z e . The manner of replacement of one subweb by another i n t h i s system gives r i s e t o the problem of p o s s i b l e c o i n c i d i n g of a r c s . Example, s t a r t w i t h the host web i n Figure 5.1. A f t e r the a p p l i c a t i o n of the r e w r i t i n g r u l e s we get Figure 5 « 2 « I f "the same r u l e i s a p p l i e d again, two arcs ( AN, A )• w i l l c o i n c i d e w i t h each other on the d i s p l a y screen. This problem can be solved i n two wayss ( i ) ;:,allow the r o t a t i o n of arcs and webs and ( i i ) a l l o w curves f o r r e p r e s e n t a t i o n s of arcs d u r i n g the process of i n s e r t i n g of webs. R = ( AN , AN A , E ) ( AN, p ) : ( A, p ) € A web before a p p l i c a t i o n of r u l e R web a f t e r a p p l i c a t i o n of r u l e R A f t e r the i n s e r t i o n of a web i n t o the host web, arcs may c r o s s . This increases the complexity of the host web, and 3 9 a l s o makes i t q u i t e d i f f i c u l t t o determine whether or not there i s a node at the c r o s s i n g p o i n t . In t h i s system, the only way t o d i s t i n g u i s h a node from a c r o s s i n g p o i n t of arcs i s by the existence of a l a b e l f o r each node. To avoid the c r o s s i n g s of arcs we can do one of the f o l l o w i n g : ( i ) the vacant area l e f t by the d e l e t e d subweb, c< , can be expanded i n s i z e t o f i t the i n s e r t i n g web, /3 . This means that at l e a s t part of the host web has t o be re-arranged each time a web r e w r i t i n g r u l e i s a p p l i e d ; ( i i ) the whole web can be re-arranged whenever the t h i n k s i t i s necessary. An algorithm does e x i s t f o r t h i s - ^ . The disadvantage of t h i s way s o l v i n g the problem i s t h a t the geometrical c o n f i g u r a t i o n of the host web i s completely changed. This may not be the c o n f i g u r a t i o n the user wants and he may no longer be able t o recognize the host web. Using an e n c l o s i n g rectangle t o describe the area occupied by a web or a subweb i s not always most ap p r o p r i a t e . A polygon may sometimes be more appr o p r i a t e , yet a polygon may be appropriate f o r one web, and not f o r another. I f we allow t h a t the area of each web i s described by a polygon, the problem of f i n d i n g the most appropriate polygon f o r each web or subweb r e s u l t s . Another problem i s how t o f i t a web des-v' c r i b e d by a d i f f e r e n t polygon, i . e . i f we have an i n s e r t i n g web which i s best described by a pentagon and a deleted subweb which i s best described by a hexagon. 40 There are s e v e r a l f u r t h e r improvements th a t can be seen immediately. They are as f o l l o w s : ( i ) During the searching f o r the a p p l i c a b i l i t y of a web r e w r i t i n g r u l e , search, f o r a l l the subwebs of the host web which are isomorphic t o the l e f t web of the r e w r i t i n g r u l e . Each instance of a p p l i c a b i l i t y i s i n d i c a t e d by an index on the d i s p l a y screen, thus the user knows which subweb corresponds t o which instance of a p p l i c a b i l i t y , and he can i n d i c a t e which instance of a p p l i c -a b i l i t y he wishes to apply. To have an index f o r each subweb increases the complexity and the d i f f i c u l t y of reading what i s on the d i s p l a y screen. ( i i ) This system allows m u l t i p l e arcs between any two nodes and allows graphs w i t h loops. To i n d i c a t e loops curves are used to represent arcs but drawing i s time consuming and i t i s a l s o d i f f i c u l t t o determine what kind of curves w i l l be most app r o p r i a t e . ( i i i ) the system should a l l o w another ta s k , that i s the m o d i f i c a t i o n of webs by the user d u r i n g the run of the system. This should a l l o w f o r the i n s e r t i o n and d e l e t i o n of nodes, arcs and node l a b e l s , and a l s o f o r the displacement of a node or of the whole web. This option i s the same as the o p t i o n f o r the s p e c i f i c a t i o n of webs except f o r these a d d i t i o n a l operations: the displacement of nodes and of webs. ( i v ) To increase the man-machine i n t e r a c t i o n , the use of f u n c t i o n keys and d i a l s should be aban-doned. A b e t t e r g r a p h i c a l package, which w i l l r e t u r n b e t t e r r e s u l t s a f t e r a l i g h t - p e n h i t , i s needed. (v) In t h i s system there i s no "windowing". By "windowing" a part of a web, we t e m p o r a r i l y e l i m i n a t e the other parts of the web i n order to enable enlargement of the s e l e c t e d p a r t , thus to more c l e a r l y see i t s f i n e d e t a i l s . Some equip-ments have hardware "windowing"; software "windowing" i s normally time consuming. ( v i ) The system should be capable of producing hard copies of web at the user's s e l e c t i o n . Since i t i s p o s s i b l e f o r users t o take photographs of the d i s p l a y screen, t h i s option i s not implemented f o r t h i s p r o j e c t . a p i c t u r e of a web of the TTPSN a f t e r a p p l i c a t i o n of web r e w r i t i n g r u l e s Figure 5 . 3 BIBLIOGRAPHY 42 1. Aramaki, I . , Kawabata, T. and Arimoto, K., Automation of E t c h i n g - P a t t e r n Layout C-ACM V o l . 14(11), pp. 720-730, 1971. 2. Conroy, P., A Web Grammar Implementation Program, Department of Computer Science, U n i v e r s i t y of B r i t i s h Columbia, 1972. 3. Coulthard, J . , UBC GRAPH, Computer Centre, U n i v e r s i t y of B r i t i s h Columbia, 1970. 4. Coulthard, J . , UBC BASIC, Computer Centre, U n i v e r s i t y of B r i t i s h Columbia, 1970. 5. D i G i u l i O , H.A. and Tuan, P.L., A Graph Manipulator f o r On-Line Networks, F a l l J o i n t Computer Conference, AFIPS V o l . 35(D pp. 387-398, 1969. 6. E a r l e y , J . , Toward An Understanding of Data S t r u c t u r e , C-ACM V o l . 14(10), pp. 617-627, 1971. 7. Montanari, U.G., Separable Graphs, Planar Graphs and Web Grammars, Information and C o n t r o l V o l . 16, pp. 243-267, 1970. 8. P a v l i d i s , T., Grammatical and Graph Theoretic A n a l y s i s of P i c t u r e s , P r i n c e t o n U n i v e r s i t y 1972. 9. P a v l i d i s , T., Linear and Context-Free Graph Grammar, J-ACM V o l . 19(1), PP H - 2 2 , 1972. 10. P f a l t z , J.L., Web Grammars and P i c t u r e D e s c r i p t i o n , T e c h n i c a l Report 7 O - I 3 8 , U n i v e r s i t y of Maryland, 1970. 11. P f a l t z , J.L. and Rosenfeld, A., Web Grammars, Proceddings J o i n t I n t e r n a t i o n a l Conference on A r t i f i c i a l I n t e l l i g e n c e , Washington D.C., 1969. 12. S p r o u l l , R.F. and Sutherland, I.E., A C l i p p i n g D i v i d e r , F a l l J o i n t Computer Conference, AFIPS 3 3(0. 1968. APPENDIX A COMMENT external procedures declaration; BEGIN PROCEDURE agtdsp(INTEGER ARRAY disp (*); INTEGER VALUE n,loc; BITS VALUE cl e a r ; INTEGER VALUE mode); FORTRAN "agtdsp"; PROCEDURE agtcvt(INTEGER RESULT a; REAL VALUE x,y; INTEGER VALUE d,e); FORTRAN "agtcvt"; PROCEDURE agthit(INTEGER RESULT i v e c t ) ; FORTRAN "agthit"; PROCEDURE fns(BITS ARRAY log (*)); FORTRAN "fns"; PROCEDURE cvtagt(INTEGER VALUE disp; REAL RESULT x,y INTEGER RESULT idraw.ieol); FORTRAN "cvtagt"; PROCEDURE agtext(REAL VALUE x,y,ht; STRING VALUE bed REAL VALUE ang; INTEGER VALUE nc; INTEGER ARRAY a (* INTEGER RESULT nv); FORTRAN "agtext"; PROCEDURE dials(REAL ARRAY d (*)); FORTRAN " d i a l s " ; PROCEDURE message(INTEGER ARRAY a,b,c (*); INTEGER RESULT na,nb,nc; REAL RESULT f , t , s ) ; FORTRAN "mess"; PROCEDURE message1(INTEGER ARRAY a,b,c,d,e (*); INTEGER RESULT na,nb,nc,nd,ne; REAL RESULT x); FORTRAN "messl"; PROCEDURE rtwait(INTEGER VALUE n); FORTRAN "rtwait"; COMMENT main program, set up range f o r arrays; INTEGER total_web,total_rule,noplace,nonot_app, nf _k, nd_f, nf _ke y, no l i ght _p; INTEGER ARRAY light_p (1II150)$ INTEGER ARRAY not_app (li«l?5); INTEGER ARRAY f_k,f_key,place (lu250); INTEGER ARRAY d_f(lt « 3 0 0 ) ; REAL fromc,toe,ask,blank; BEGIN INTEGER ARRAY n_rule (1II175); INTEGER hnr.,hriwebj INTEGER ARRAY n_web (1II250)I me s sage(n_rule,plac e,not_app,nnr,noplac e, 4 4 nonot_aap,fromc,t oc,as k); agtdsp(n rule,nnr,l,# 1,0); READ(total_rule); messagelTn_web,light_p,f_k,d_f,f key,nnweb, no 1 i ght _p, nf _k, nd_f, nf _ke y, b lankj; agtdsp(n_web,nnweb,1,#1,0); READ(total_web) END; BEGIN COMMENT star t of the program; COMMENT a l l o c a t i o n of variables and arrays; INTEGER numnodes,indicator,n_sr,nwh,nft,nolw,nin,nnr,norw, no_web,nmany,no inst,n2,nfromnd,nt ond,num_nod e,nwh_arc, nh,nrn,noarc s,no graph,nolb,no_app,noapp,nail,rule_n,nlw, noweb,patlabel,noall,nt,nl,web_num,lrw,nsr, nrule_num,nlv,no_of_rule; INTEGER ARRAY wh_low,wh up,lft,uft,app_l,app_up,a_lo, a_up,sr_low,sr_up (1:»Zj; INTEGER ARRAY lowerl,upperl ( I t : 6 ) ; INTEGER ARRAY lower2,upper2 (1««8); INTEGER ARRAY uap, lap, r n _ l , rn_p (11 : t o t a l _ r u l e + l ) ; INTEGER ARRAY no_nd,no_arc,no_label (1:stotal_web); INTEGER ARRAY web__l,web_u (1: :total_web+l); INTEGER ARRAY rnum,from_to,tond ( I : . i 5 0 ) ; INTEGER ARRAY fromnd,too_many,1 web,r_web,node_l,wh_arc, in_name,applie,t,in_web,labelv Tl'«100); INTEGER ARRAY all,h,what,same_rule ( l : i l ? 5 ) ; INTEGER ARRAY graph ( 1 I I 2 0 0 ) J INTEGER ARRAY app^r'(1I i250)> INTEGER ARRAY commandl,command2,rule_num (1JS400); INTEGER ARRAY arcs.nolabel ( I 1 1 5 0 0 ) ; INTEGER ARRAY webjn ( 1 I I 1 3 0 0 )I INTEGER ARRAY source (1:»4000); INTEGER ARRAY ndv (1:»total_web,1;:200); INTEGER ARRAY arcv,labv (1«:total_web, 1 :»500); LOGICAL light_pen; STRING ARRAY numeral ( 0 : : t o t a l _ r u l e ) ; REAL xg'16bal,yglobal; REAL ARRAY x_squ,y_squ ( l s : 4 ) ; REAL ARRAY xs,ys ( 1 I I 6 ) J REAL ARRAY xmin,xmax,ymin,ymax (11«total_web); COMMENT record declaration; RECORD table2(STRING l a b e l ; INTEGER plabel,ident; REFERENCE(table2) nextlabel); REFERENCE(table2) labeltable; RECORD insertion(REFERENCE(node) r e f _ i n s e r t ; REFERENCE(insertion) next_insert); REFERENCE(insertion) inserted; RECORD nodse (STRING l n ; REAL xvalue, yvalue; INTEGER pt l a b e l , ndid,node_pos,ll,12; REFERENCE(node_to) pto; REFERENCE (node_from) p f r ; REFERENCE(node) nextnode,nextorder); REFERENCE(node) ARRAY hash(l:»total_web,01tlO); REFERENCE(node) ARRAY order ( 1Jstotal_web,Os» 9 )I RECORD node_to(REFERENCE(node) r e f e r _ t o ; INTEGER arc^pos; REFERENCE(node_to) next_to); RECORD node_from(REFERENCE(node) refer_from; REFERENCE(node_from)next_from); RECORD fortrn(INTEGER p f o r t ; REFERENCE(fortrn) next_fortrn); RECORD webs(STRING name; INTEGER number,index; REFERENCE(fortrn)tarrai; REFERENCE(webs) next_web); REFERENCE(webs) header,host_web; RECORD rule_p(REFERENCE(webs) left_w,right_w); REFERENCE(rule_p) ARRAY rules ( 1: : t o t a l _ r u l e ) ; RECORD. embed(STRING a,b,c,tfa; INTEGER b i d , c i d ; REFERENCE(embed) next_embed); REFERENCE(embed) ARRAY embedd(l::total_rule); RECORD instance(REFERENCE(node) r e f _ i n s t , r _ i n s t ; REFERENCE(instance) next_inst); REFERENCE(instance) ARRAY instances(l::total_web); COMMENT—-internal procedures; PROCEDURE decision; COMMENT to determine whether to input webs, embeddin or rules or to apply production ru l e s ; BEGIN INTEGER i ; agtdsp(commandl,nl,1,#1,0); indicator:=nl+l; i :=choose(lowerl,upperl,commandl,6); CASE i OF BEGIN BEGIN COMMENT—input of webs; initial_web; decision END; BEGIN COMMENT s p e c i f i c a t i o n of webs: to indicate l e f t and right webs for each rule; input_rule; decision END; BEGIN COMMENT s p e c i f i c a i t i o n of host web; INTEGER j,jk,k; REFERENCE(webs) r e f e r ; agtdsp(web_N,no_web,1,#1,0); j : = 1 ; agtdsp(h,nh,no_web+l,#0,0); refer:=header; indicator:=no_web+nh+l; k:=choose(web_l,web_u,web_n,no_web); jk:=noweb+l-k; con(source,h,ndv(jk,*),arcv(jk,*),labv(jk,*), nsr,nh,no_nd(jk),no_arc(jk),no_label(jk)); agtdsp(source,nsr,l,# 1 , 0 ); rtwait ( 3 0 0 ) ; WHILE j-=k DO BEGIN refer<s=next_web ( r e f e r ) ; j:=j+l END; a r r a i ( r e f e r ) : = f o r t r n ( l , a r r a i ( r e f e r ) ) ; host_web:=re_set(refer); decision END; BEGIN COMMENT s p e c i f i c a t i o n of embeddings; embeddings; decision END: 46 BEGIN COMMENT a p p l i c a t i o n of production r u l e s ; appry; d e c i s i o n END; BEGIN COMMENT—-finish; INTEGER n t ; INTEGER ARRAY t ( l n 5 0 ) j agtext(0.,-9.5».5,"good luck",0.,9»t,nt); a g t d s p ( t , n t , l , # l , 0 ) ; rtwait(lOOO) END END END; PROCEDURE i n i t i a l _ w e b ; COMMENT to i n i t i a l i z e a web and a l l the necessary v a r i a b l e s ; IF web_num ••^t.>=total_web THEN BEGIN agtdsp(too_many,nmany,l,#l,0); rtwait(lOO) END ELSE BEGIN STRING web_name; web_num:=web num+1; nograph:=0; nolb:=0; noarcs»=0; xmin(web_numTs=ll.; xmax(web_nura):=-ll.; ymin(web_num)s+11.; ymax(web_num):=-ll.; FOR ii=0 u n t i l 10 DO hash(webjnum.'Ji) :=null; FOR i:=0 u n t i l 9 DO order(web_num„i):=null; agtdsp(in_web,min,l,#l,0); READ(web_name); numnodes «=0; header:=webs(web_name,0,web_num,null,header); input_webs END; PROCEDURE input_webs; COMMENT s p e c i f i c a t i o n of a web, the a c t i o n s that can be taken are c r e a t i o n of a node, an arc or a a l a b e l or d e l e t i o n of a node, an arc or a l a b e l or i n d i c a t i o n another i s to be created or no morei'Web; BEGIN INTEGER k , i ; c on(s ourc e,c ommand 2,graph,arc s,ndlab e l , nsr,n2,nograph,noarcs,nolb); agtdsp(source,nsr,1,#1,0); i n d i c a t o r : = n s r + l ; ks=choose(lower2,upper2,command2,8); CASE k OF BEGIN BEGIN COMMENT c r e a t i o n of a node; INTEGER i ; REAL x,y; con(source,place,graph,arcs,ndlabel, n s r , n p l l a c e,nograph,noarc s,nolb); agtdsp(source,nsr,1,#1,0); agtdsp(d_f,nd_f,nsr*l,#0,0); d i a l a n d f n s ( x , y ) ; IF xmin(web_num) x THEN xmin(web_num)»=x; IF xmax(web_num) x THEN xmax(wbe_num)s=x; IF ymin(web_num) y THEN ymin(web_num)»=y; IF ymax(web_num) y THEN ymax(web_num):=y; agtcvt(graph(nograph+1),x,y,0,0); i *=TRUNCATE(ABS x ) ; nograph:=nograph+2; agtcvt(graph(nograph),x,y,1,0); hash(web_num,i)s =node("?",x,y,0,0,nograph+1,0,0, nu l l , n u l l , h a s h ( w e b _ n u m , i ) , n u l l ) ; input_webs END; *+7 BEGIN COMMENT creation of a directed arcs from node (a,b) to node (x,y); REAL a,b,x,y; INTEGER ARRAY temp(l::6); INTEGER k , l , j ; REFERENCE(node) ptra,ptrx,r; IF nograph>l THEN BEGIN c on(sourc e,fromnd,graph,arc s,ndlabe1, nsr,nfromnd,nograph,noarc s,nolb); agtdsp(source,nsr,1,#1,0); indicator:=nsr+l; indicate_node(graph,nograph,a,b); c on (sourc e, t ond, grap., arcs, ndlabe 1, nsr,ntond,nograph,noarcs,nolb); agtdsp(source,nsr,l,#l,0); t r i a n g l e ( a , b ) j indicator:=nsr+5 > indicate_node(graph,nograph,x,y) j k:=TRUNCATE(ABS a); ptra»=hash(web_num,k); searchxy(a,b,ptra,r); 1:=TRUNCATE(ABS x)j ptrx:=hash(web_num,1); searchxy(x,y,tprx,r); arrow(temp,a,b,x,y); pfr(ptrx):=node_from(ptra,pfr(ptrx)); pto(ptra):=node to(ptrx,noarcs+l,pto(ptra)); FOR i:=l UNTIL Z DO arcs(noarcs+i):=temp(i); noarcs:=noarcs+6 END; input_webs END* BEGIN COMMENT creation of a l a b e l for the node at (x,y); REAL x,y; INTEGER j,ns,nt; REFERENCE(node) p t r , r ; INTEGER ARRAY S(1 I I100)I STRING node_label; REFERENCE(table2) r e f e r _ t a b l e ; IF nograph>0 THEN BEGIN con(source,node_l,graph,arcs,ndlabel, nsr,numjnode,nograph,noarcs,nolb); agtdsp(source,nsr,1,#1,0); t r i a n g l e ( x , y ) ; ptr«=hash(web_num,TRUNCATE(ABS x ) ) ; searchxy(x,y,ptr,r); READ(node_label); xs=xvalue(ptr); y«=yvalue(ptr)+0.1 j agtext(x,y,.26,node_label,0.,l6,s,ns) j refer__table »=s_label(node_label, l a b e l t a b l e ) ; ln(ptr)«=node_label; ndid(ptr):=ident(refer_table) j p t l a b e l ( p t r ) : = p l a b e l ( r e f e r _ t a b l e ) j nt :=ptlabel(ptr) REM 10; nextorder(ptr):=order(web_num,nt); order(web_num,nt)i=ptr; ll(ptr):=nolb+l; FOR i*=l UNTIL ns DO ndlabel(nolb+i)s=s(i); nolbs=nolb+ns; 12(ptr):=nolb END: input_web END; BEGIN COMMENT deletion of a node, arcs connecting to i t are also deleted; IF nograph>0 THEN BEGIN INTEGER k , l ; REAL x,y; REFERENCE(node) p t r , r ; c on(s ourc e,node_l,graph,arc s,ndlabe1, 4 8 nsr,num_node,nograph,noarc s , n o l b ) ; a g t d s p ( s o u r c e , n s r , l , # l , 0 ) ; i n d i c a t o r : = n s r + l ; indicate_node(graph,nograph,x,y); ptrt=hash(web_num,TRUNCATE(ABS x ) ) ; rs=ptr; s e a r c h x y ( x , y , p t r , r ) ; delete_node(ptr,graph,arcs,ndlabel, nograph, noarc s, nolb, webjrmm) END j input_webs END; BEGIN COMMENT d e l e t i o n of an a r c ; IF n o a r c s > 0 THEN BEGIN REAL a,b,x,y; REFERENCE(node_to)ptt; REFERENCE(node_from)ptf; REFERENCE(node) p t r , p t s , r ; c on(s ourc e,wh_arc,graph,arc s,ndlab e1, nsr,nwh_arc,nograph,noarcs,nolb); a g t d s p ( s o u r c e , n s r , l , # l , 0 ) ; indicator»=nsr+l; in d i c a t e _ a r c ( a r c s , n o a r c s , a , b , x , y ) ; p t r s=ha'sh(web_num, TRUNCATE(ABS a ) ) ; s e a r c h x y ( a , b , p t r , r ) ; pts:=hash(web_num,TRUNCATE(ABS x ) ) ; s e a r c h x y ( x , y , p t s , r ) ; ptt»=ptt(ptr); WHILE refer_to(ptt)->=pts DO p t t t = n e x t _ t o ( p t t ) ; refer_to(ptt)«=null k:=arc_pos(ptt); noarcs;=noarcs - 6 ; IF k<noarcs THEN FOR i:=k UNTIL noarcs DO a r c s ( i ) : = a r c s ( i+ 6 ) ; p t f : = p f r ( p t s ) ; WHILE r e f e r _ f r o m ( p t f )-=ptr DO pt f s = n e x t _ f r o m ( p t f ) ; r e f e r _ f r o m ( p t f ) : = n u l l ; FOR i i = 0 UNTIL 1 0 DO BEGIN r:=hash(web_num,i); d_a(r,k) END END; input_web END; BEGIN COMMENT—deletion of a node l a b e l ; REAL x,y; REFERENCE(node) p t r , t ; INTEGER k,l,m; IF n o l b > 0 THEN BEGIN c dri(sourc e,node_l,graph,arc s,ndlab e1, nsr,num_node,nograph,noarc s , n o l b ) ; a g t d s p ( s o u r c e , n s r , 1 , # 1 , 0 ) ; i n d i c a t o r i = n s r + 1 ; indicate_node(graph,nograph,x,y); ptrs=hash(web_num,TRUNCATE(ABS x ) ) j s e a r c h x y ( x , y , p t r , r ) ; k * = l l ( p t r ) ; l : = 1 2(ptr)-k+l; nolb : = n o l b - l ; IF k<nolb THEN FOR i;=k UNTIL nolb DO n d l a b e l ( i ) : = n d l a b e l ( i + l ) ; p t l a b e l ( p t r ) s = 0 ; l n ( p t r ) : = " ? " ; FOR i « = 0 UNTIL 1 0 DO r»=hash(wbe_num, TRUNCATE(ABS x ) ) ; d _ l ( r , k , l ) END; input_webs END; BEGIN COMMENT a new web i s t o be created, the current web i s completed, i t i s s t o r e d ; store(nograph,noarcs,nolb,graph,arcs,ndlabel); i n t i a l web END; 49 BEGIN COMMENT no more web t o be created, the current web i s completed, i t i s s t o r e d ; s t ore(no graph,noarc s,nolb,graph,arc s,ndlab e l ) ; set web END END END; PROCEDURE i n p u t _ r u l e s ; COMMENT t o s p e c i f y the l e f t and r i g h r webs f o r r u l e s ; BEGIN INTEGER i , j k , j , k , n t ; REFERENCE(webs) r e f e r ; INTEGER ARRAY t (1::75)5 agtdsp(rule_num,nrule_num,1 ,#1,0); . indicator:=nrule_num+l; i t=choose(rn_l,rn_p,rule_num,total_rule+l); IF i < t o t a l _ r u l e THEN BEGIN no_o f _ r u l e «=no_of_rule+l; agtext(- .5»-8., .25»numeral(i),0,3»t,nt); c on(s ourc e,web_n,rnum,t,l_web,nsr„no_web,nrn,nt,nolw); i n d i c a t o r s = n s r + l ; a g t d s p ( s o u r c e , n s r , l , # l , 0 ) ; k:=choose(web_l,web_u,web n,noweb); jk»=noweb+l-k; con(source,l_web,ndv(jk,*7 , a r c v ( j k , * ) , l a b v ( j k , * ) , n s r , n o l w , n o _ n d ( j k ) , n o _ a r c ( j k ) , n o _ l a b e l ( j k ) ) ; FOR w:=l UNTIL nrn DO source(nsr+w)«=rnum(w); nsr:=nsr+nrn; FOR w:=l UNTIL nt DO source(nsr+w)s=t(w); n s r s=nsr+nt; a g t d s p ( s o u r c e , n s r , l , # l , 0 ) ; rtwait ( 3 0 0 ) ; jx=l; refer:=header; WHILE j =k DO BEGIN refer»=next_web(refer); j'=j+l END; a r r a i ( r e f e r ) s = f o r t r n ( 1 0 , a r r a i ( r e f e r ) ) ; r u l e s ( i ) s = r u l e _ p ( r e f e r , n u l l ) ; c on(s ourc e,web_n,rnum,t,r_web,nsr,no_web,nrn,nt,norw); agtdsp(source,nsr, 1 , # 1 , 0 ); i n d i c a t o r s = n s r + l ; k:=choose (web_l,web__u,web n,no_web); jk:=noweb+l-k; co n ( s o u r c e , r _ w e b , n d v ( j k , * J , a r c v ( j k , * ) , l a b v ( j k , * ) , n s r , n o r w , n o _ n d ( j k ) , n o _ a r c ( j k ) , n o _ l a b e l ( j k ) ) ; FOR i : = l UNTIL nrn DO source(nsr+w)t=rnum(w); nsr s=nsr+nrn; FOR ws=l UNTIL nt DO source(nsr+w):=t(w); nsr »=nsr+nt; agtdsp(source,nsr, 1 , # 1 , 0 ); rtwait ( 3 0 0 ) ; js=l; refer«=header; WHILE j-=k DO BEGIN jt=j+l; refer»=next_web(refer) END; a r r a i ( r e f e r ) : = f o r t r n ( 1 0 ) , a r a i ( r e f e r ) ) ; right_w(rules(i))»=refer; i n p u t _ r u l e s END END; PROCEDURE embeddings; COMMENT s p e c i f i c a t i o n of embedding f o r each r u l e s ; IF no_of_rule> 0 THEN BEGIN INTEGER i , l , r , n t , n _ l , n _ r , k ; INTEGER ARRAY t ( l n 2 0 ) ; INTEGER ARRAY s l , s r (1$:2000); agtdsp(rule_num,nrule_num,1 ,#1,0); i n d i c a t o r s=nrule_num+l; i:= c h o o s e ( r n _ l , r n _ p , r u l e _ n u m , t o t a l _ r u l e ) ; IF i < = t o t a l r u l e THEN 50 IF r u l e s ( i ) - = n u l l THEN BEGIN l:=i n d e x ( l e f t _ w ( r u l e s ( i ) ) ) ; r:=index(right_w(rules(i))); con(sl,l_web,ndv(l,*),arcv(l,*),labv(l,*), n_l,nolw,no_nd(l),no arc(1) ,no l a b e l ( l ) ) ; con(sr,r_web,ndv(r,*7>arcv(r,*T,labv(r,*), n_r,norw,no_nd(r),no_arc(r),no_label(r)); a g t e x t ( 2 . , - 8 . , . 2 5 , n u m e r a l ( i ) , 0 . , 3 , t , n t ) ; FOR i i i = l UNTIL nt DO rnum(nrn+ii)s=t(ii); embedd(i)«=null; find_embed(sl,sr,rnum,n_l,n_r,nrn+nt,i,1,r); embeddings END END; PROCEDURE firid_embed(INTEGER ARRAY s l , s r , r n (*); INTEGER VALUE n l , n r , n r n , i , l , r ) ; COMMENT to specify a l l embeddings f o r the i - t h r u l e ; BEGIN INTEGER k , j , y i d , z i d ; REFERENCE(node) p,rg; REAL v,w; STRING x,y,z,tfx,a name; agtdsp(same_rule,n_sr,l ,#1 ,0j ; agtdsp(rn,nrn,n_sr+l ,#0,0); indicator:=n_sr,+nrn+l; k s=choose(sr_low,sr_up,same_rule,2); IF k-1 THEN BEGIN agtdsp(what,nwh,1,#1,0); agtdsp(rn,nrn,nwh+l,#0,0); indicators=nwh+nrn+l; j j=choose(wh_low,wh_up,wliat,2); IF j=l THEN x:="*" ELSE BEGIN READ(ajname); xi-a_name END: agtdsp(from_to,nft ,1 ,#1,0); indicator:=nft+l; j:=choose(lft,uft,from_to,2 ) ; IF j=l THEN t f x i = M f r o m M ELSE tfx!="to"; agtdsp(sl,nl,1 , # 1 , 0 ); agtdsp(rn,nrn,nl+l , # 0 , 0 ) ; indicator:=nl+nrn+l; indicate_node(ndv(l,*),no nd(l),v,w); p:=hash(l,TRUNCATE(ABS V)7J searchxy(v,w,p,rg); y:=ln(p); yid:=ndid(p); agtdsp(sr,nr,l,#l , 0 ); agtdsp(rn,nrn,nr+l ,#0,0); indicator:=nr+nrn+l; indicate_node(ndv(r,*),no nd(r),v,w); p:=hash(r,TRUNCATE(ABS v)T; searchxy(v,w,p,rg)j zs=ln(p); zid:=ndid(p); embedd(i)s=embed(x,y,z,tfx,yid,zid,embedd(i)); find_embed(sl,sr,rn,nl,nr,nrn,i,l,r) END END; PROCEDURE appry; COMMENT application of production r u l e s ; IF host_web-,=null THEN BEGIN INTEGER j,hostweb; hostweb:=index(host_web); c on(s ourc e,applie,ndv(ho stweb,*),arcv(hostweb,*), labv(hostweb,*),nsr,no_app,no_nd(hostweb), no_arc(hostweb),no_label(hostweb)); agtdsp(source,nsr,1,#1,0); indicator:=nsr+l; j :=choose (app__l,app_up,applie,2); COMMENT i n i a l i z a t i o n & tes t f o r a p p l i c a b i l i t y ; IF j=l THEN BEGIN INTEGER napp,ninst,num_r; INTEGER ARRAY s ( 1 « : 1 5 ) ; LOGICAL applicable; 51 napp:=noapp; ninst:= n o i n s t ; a p p l i c a b l e : = f a l s e ; ismrph FOR l s = l UNTIL t o t a l _ r u l e DO IF instances (l)-.=null THEN a p p l i c a b l e :=true; IF a p p l i c a b l e THEN'BEG IN' COMiyiENT there i s a p p l i c a b l e r e w r i t i n g r u l e s ; INTEGER k,l,j,ct,nt,l,m,numnodes,r_webs,q,n_no, np,r_num,num; INTEGER ARRAY t ( l n l O O ) ; REAL x,y,xle ft,xright,ylow,yupp,xd,yd, x s c a l e , y s c a l e ; x :=-1 .75 ; y : = - 9 . 0 ; c t : = 0 ; COMMENT choose the r u l e t o be a p p l i e d ; nappi=noapp; FOR k:=l UNTIL t o t a l _ r u l e DO IF i n s t a n c e s ( k ) - = n u l l THEN BEGIN x:=x - .?5 ; agtext (x,y,. 25»numeral(k), 0 . , 3, t , n t ) ; FOR f :=1 UNTIL nt DO app_r(napp+f) 8=t ( f ) ; c t s = c t + l ; lap(ct) 8=napp+l; napp«=napp+nt; uap(ct):=napp; «j: = j+l END; con (source ,app r,ndv(hostweb, *) , arcv(hostweb, *')', labv(hostweb,*T,nsr,napp,no_nd(hostweb), no_arc (hostweb) ,no__label(hostweb)); i n d i c a t o r : = n s r + l ; a g t d s p ( s o u r c e , n s r , l , # l , 0 ) ; m»=choose(lap,uap,app_r,ct); num__rs=0; WHILE m>0 DO BEGIN num__r s=num_r+l; IF instances(num_r) = n u l l THEN m»=m-l END; r_webs:=index(right_w(rules(num_r))); x l e f t 8=xmin(r_webs); xright:=xmax(r_webs); ylow:=ymin(r_webs); yupps=ymax(r_webs); x d 8 = x r i g h t - x l e f t ; yds=yupp-ylow; a p p l i c at ion(r_webs,num_r,xleft,xright,ylow, yupp,xd,yd); appry END * ELSE BEGIN agtdsp(not_app,nonot_app,l,# 1 , 0 ) ; rtwait ( 5 0 0 ) END END END; PROCEDURE ismrph; COMMENT t o match the l e f t webs of r e w r i t i n g r u l e s t o the subwebs of the host web; BEGIN INTEGER web_no,web_host,j; LOGICAL i s o m o r p h i c , a l r i g h t ; REFERENCE(node) rule_node,host_node; REFERENCE(node_to) r e f t o r , r e f t o h ; REFERENCE(node_from) r e f f r r , r e f f r h ; FOR i8=1. UNTIL t o t a l _ r u l e DO BEGIN in'st'anc.es ( i ) : = n u l l ; IF" r u l e s ( i ) i = n u l l THEN BEGIN j t=-l; isomorphic 8=true; web_host:=index(host_web); web_no 8 = i n d e x ( l e f t _ w ( r u l e s ( i ) ) ) ; WHILE isomorphic DO BEGIN j*=j+l; IF j>9 THEN isomorphics=false ELSE BEGIN rule_node:=order(web_no,j); WHILE r u l e . n o d e - ^ n u l l DO BEGIN host_node s=order(web_host,j); a l r i g h t s=false; WHILE host node-.=null DO BEGIN 52 IF ln(rule_node)=ln(host_node) THEN BEGIN reftor:=pto(rule_node); alright:=true; WHILE r e f t o r i = n u l l DO BEGIN a l r i g h t J = f a l s e ; reftohs=pto(host_node)j WHILE reftoh-,=null DO BEGIN IF l n ( r e f e r to(reftoh))= l n ( r e f e r _ t o T r e f t o r ) ) THEN BEGIN alright»=true; reftoh:=null; reftori=next_to(reftor) END ELSE reftoh:=next_to(reftoh) END; IF a l r i g h t THEN r e f t o r J = n u l l END; IF a l r i g h t THEN BEGIN reffrr:=pfr(rule_node); WHILE r e f f r ^ = n u l l DO BEGIN alright:=false; reffrhs=pfr(host_node); WHILE reffrh^=null DO BEGIN IF ln(refer_from(reffrh))= I n ( r e f e r _ f r o m ( r e f f r r ) ) THEN BEGIN alright:=true; reffrh:=null; reffrr»=next_from(reffrr) END ELSE reffrhJ=next_from(reffrh) END; IF a l r i g h t THEN r e f f r r : = n u l l END END END; IF a l r i g h t THEN BEGIN1 • instances(i);=instance(host_node, rule_node,instances(i)); host_node»=null END ELSE host_node:=nextorder(host_node) END; IF a l r i g h t THEN rule_node:=nextorder(rule_node) ELSE BEGIN isomorphic:=false; rule_node t=null; instanc e s ( i ) : = n u l l END END END END END END END; PROCEDURE application(INTEGER VALUE r_web,nrule; REAL VALUE xleft,xright,ylpw,yupp,xd,yd); COMMENT continuation of the procedure appry; BEGIN INTEGER np,host,nd,nl,na,ns,nt; REFERENCE(node) p,q,r,w,v,z; REFERENCE(insertion) insrted; INTEGER ARRAY t ( l : : 1 0 0 ) ; REAL x,y; INTEGER ARRAY s ( ' l ss6) ; REAL xlf,xrg,ylw,yup,yscale, xsvale; REFERENCE(table2) pweb; REFERENCE(node_to) nto; REFERENCE(node_from) nf; REFERENCE(instance) pq; REFERENCE(embed) pqr; STRING s t r ; REFERENCE(insertion) insert_node; pq s = instances(nrule); IF pq^=null THEN BEGIN p:=ref inst(pq); xlf t=xvalue(p); xrg:=xvalueTp); ulw:=yvalue(p); yup:=yvalue(p); pq:=next_inst(pq;; WHILE pq-,=null DO BEGIN p s=ref_inst(pq); IF xlf>xvalue(p) THEN x l f :=xvalue (p) ELSE 53 IF xrg<xvalue(p) THEN xrg:=xvalue(p); IF ylw>yvalue(p) THEN ylws=yvalue(p) ELSE IF yup<yvalue(p) THEN yup:=yvalue(p); pqs=next_inst(pq) END END; IF (xd>0) OR (xrg=xlf) THEN xscale8=1 ELSE xscales=(xrg-xlf)/xd; IF (yd=0) OR (yup=ulw) THEN yscalei=l ELSE yscale:=(yup-ylw)/yd; host8=index(host_web); ndj=no_nd(host); nl:=no_label(host); nas=no_arc(host); COMMENT i n s e r t i o n of right web; inserted s=null; FOR i:=l UNTIL 9 DO BEGIN p:=order(r_web,i); WHILE p^=null DO BEGIN x i=xscale*(xvalue(p)-xleft)+xlf; y s=yscale *(yvalue(p)-ylow)+ylw; np:=TRUNCATE(ABS x); order(host,i)s=node(ln(p),x,y,ptlabel(p),ndid(p), nd+ 1,nl+l,0 ,null,null,hash(host,np),order(host,i)); inserted 8=insertion(order(host,i),inserted); hash(host,np)s=order(host,i); agtcvt(ndv(host,nd+1),x,y,0,0) ; nd8=nd+2; agtcvt(ndv(host,nd),x,y,l , 0 ) ; agtext(x,y+.l, . 2 5,ln(p ) , 0 , l 6,t,nt); FOR i i s = l UNTIL nt DO l a b v ( h o s t , n l + i i ) 8 = t ( i i ) ; nls=nl+nt; 1 2(order(host,i))s=nl; ps=nextorder(p) END END; FOR i8=0 UNTIL 9 DO BEGIN ps=order(r_web,i); WHILE p- i=null DO BEGIN qs=order(host,i); s_lanelid(ptlabel(p):jindid(p) ,q,r); ntos=pto(p); WHILE nto-=null DO BEGIN V8=refer to(nto); r8=orderThost,(ptlabel(v) REM 1 0 ) ) ; s_labelid(ptlanel(v),ndid(v),r,w); pto(q)8=npde_to(r,na+l,pto(q)); pfr(r)8=node_from(q,pfr(r)); arrow(s,xvalue(q),yvalue(q),xvalue(r),yvalue(r)); FOR i i s = l UNTIL 6 DO arcv(host,na+ii)8=s(ii); na:=na+6; nto8=next_to(nt0) END; p8=nextorder(p) END END; COMMENT do the embeddings; pqrs=embedd(nrule); WHILE pqr =null DO BEGIN pqs=instances(nrule); WHILE pq-^null DO BEGIN ps=r inst(pq); IF (b(pqr)=ln(p)) AND (bidTpqr)=ndid(p)) THEN BEGIN zs=ref_inst(pq); IF a(pqr)= M*" THEN BEGIN pweb :=labeltable;. WHILE c(pqr)- n=lapel(pweb) DO pweb s=nextlabel(pweb); rs=order(host,(plabel(pweb) REM 1 0 ) ) ; s_labe 1 id (plabe 1 (pweb)c i d (pqr)', r, w); IF tfa(pqr)= , ,to" THEN BEGIN ntos=pto(z); WHILE nto-=null DO BEGIN ws=refer_to(nto); 54 pto(r):=node_to(w,na+l,pto(r)); pfr(w):=node_from(r,pfr(w)); a r r o w ( s , x v a l u e ( r ) , y v a l u e ( r ) , xvalue(w),yvalue*w)); FOR i i : = l UNTIL 6 DO arcv(host,na+ii)«=s(i na:=na+6; nto»=next_to(nto) END END ELSE BEGIN nf»=pfr(z); WHILE n f - = n u l l DO BEGIN ws=refer_from(nf); pfr(r)»=node_from(w,pfr(r)); pto(w)»=node_to(r,na+l,pto(w)); arrow(s,xvalue(w),yvalue(w), x v a l u e ( r ) , y v a l u e ( r ) ) ; FOR i l : = l UNTIL 6 DO a r c v ( h o s t , n a + i i ) : = s ( i i ) ; nas=na+6; nf*=next_from(nf) END END END ELSE BEGIN s t r : = a ( p q r ) ; IF t f a ( p q r ) = " t o " THEN BEGIN nto:=pto(z); WHILE nto-=null DO BEGIN w:=refer_to(nto); IF str=ln(w) THEN BEGIN pto(r)s=node_to(w,na+l,pto(r)); pfr(w):=node_from(r,pfr(w)); a r r o w ( s , x v a l u e ( r ) y v a l u e ( r ) , xvalue(w),yvalue(w)); FOR ii«=l UNTIL 6 DO arcv(host,na+ii)»=s(ii); na»=na+6 END; nto:=next_to(nto) END END ELSE BEGIN nf«=pfr(z); WHILE n f - = n u l l DO BEGIN wj=refer_from(nf); IF s t r ( l n ( w ) THEN BEGIN pfr(r)s=node_from(w,pfr(r)); pto(w)»=node_to(r,na+l,pto(w)); arrow(s,xvalue(w),yvalue(w), x v a l u e ( r ) , y v a l u e ( r ) ) ; FOR i i : = l UNTIL 6 DO a r c v ( h o s t , n a + i i ) : = s ( i i ) ; na«=na+6; nf:=next_from(nf) END END END END; pq:=next_inst(pq) END; pqrs=next_embed(pqr) END; COMMENT d e l e t i o n of l e f t web; pqs=instances(nrule); WHILE pq-=null DO BEGIN p:=ref_inst(pw); deletion_node(p,ndv(host,*),arcv(host,*), l a b v ( h o s t , * ) , n d , n a , n l , h o s t ) ; pq:=next_inst(pq) END; no_arc(host):=na; n o _ l a b e l ( h o s t ) : = n l ; no_nd(host)s=nd; insert_nodes=inserted; WHILE insert_node-=null DO BEGIN ndid(ref_insert(insert_node))«=ident(s_label ( l n ( r e f _ i n s e r t ( i n s e r t _ n o d e ) ) , l a b e l t a b l e ) ) ; i n s e r t j a o d e : = n e x t _ i n s e r t ( i n s e r t _ n o d e ) END END; PROCEDURE con(INTEGER ARRAY s,com,g,ar,nd (*); INTEGER RESULT ns; INTEGER VALUE nc,ng,na,nn); 55 COMMENT t o concatenate the vectors com,g,ar and nd, the r e s u l t i n g v e c t o r i s returned by s; BEGIN FOR i i * 1 UNTIL nc DO s ( i ) : = c o m ( i ) ; ns:=nc; IF ng 0 THEN FOR i s = l UNTIL ng DO s ( n s + i ) s = g ( i ) ; ns s=ns+ng; IF na 0 THEN FOR i : = l UNTIL na DO s ( n s + i ) : = a r ( i ) ; ns s=ns+na; IF nn 0 THEN FOR i«=l UNTIL nn DO s(n s + i ) : = n d ( i ) ; ns »=ns+nn END; PROCEDURE arrow(INTEGER ARRAY s (*); REAL VALUE u,v,x,y); COMMENT draw an arrow from,'(u,v) t o ( x , y ) ; BEGIN REAL a,b,c,d; REAL ARRAY headx,heady ( I n 2 ) ; headx(l):=.2; headx(2)s=.2; heady(1):=.l; heady(2)»=-.l; a g t c v t ( s ( l ) , u , v , 0 , 0 ) ; agtcvt(s(2),x,y,1,0); IF u=x THEN BEG.IN IF x>u THEN BEGIN a:=x-heady(1); b:=x-heady(2); c:=y+headx(l); ds=y+headx(2) END ELSE BEGIN a:=x+heady(1); b:=x+heady(2); c:=y-headx(l); d:=y-headx(2) END END ELSE BEGIN REAL alpha,sinalpha,cosalpha; IF y=v THEN BEGIN IF x>u THEN BEGIN ai=x-headx(l); b:=a; c«=y-heady(l); ds=y-heady(2) END ELSE BEGIN a*=x+headx(l); b«=a; c«=y+yeady(l); dt=y+heady(2) END END ELSE BEGIN alphas=ARCTAN((v-y)/(u-x)); sinalpha:=SIN(alpha); cosalphas=COS(alpha); a«=headx(l)*cosalpha-heady(l)*sinalpha; b t=headx(2)*cosalpha-heady(2)*sinalpha; c t=headx(l)*sinalpha+heady(l)*cosalpha; d «=headx(2)*s inalpha+heady(2)*cosalpha; IF x>u THEN BEGIN a:=a+xj b:=n+x; c:=c+y; d:=y+d END ELSE BEGIN as=x-a; b:=x-b; c:=y-c; d:=y-d END END END; agtcvt (s (3) »a,c, 0,0); agtcvt (s (4),x,yU>0); agtcvt(s(5),b,c,0,0); agtcvt(s(6),x,y,1,0) END; LOGICAL PROCEDURE already(REAL VALUE r ; INTEGER VALUE r i d ; REAL ARRAY 1(8); INTEGER ARRAY i d ( * ) ; INTEGER VALUE i , n ) ; IF i n THEN TRUE ELSE IF ( r * l . ( i ) ) AND ( r i d = i d ( i ) ) THEN FALSE ELSE a l r e a d y ( r , r i d , 1 , i d , i + 1 , n ) ; REFERENCE(webs) PROCEDURE re_set(REFERENCE(webs) value r e f e r ) ; COMMENT t o create a new web f o r the host-web, t h i s procedure i s entered whenever a r u l e which has the same as the host web; BEGIN IF web_num<total_web THEN BEGIN agtdsp(too_many,namny,1,#1,0); rtwait(1000); host web END 56 ELSE BEGIN INTEGER j,k; STRING s; REFERENCE(node) p,ptr,q; REFERENCE(node_to) p t t ; REFERENCE(node_from) p t f ; RECORD table(REFERENCE(node) old,new; REFERENCE(table next); REFERENCE(table) r , z ; FOR i :=0 UNTIL 9 DO order(web_num,i):=null; web_num:=web__num+l; i:=index(refer); s » = " i n t e r n a l " ; s(811):=numeral(web_num)(011); s(9 1):=nuraeral(web_num(l|i); rs=null; header »=webs(s,O,web_num,fortrn(l,null),header); set_web; FOR i:=l UNTIL 10 DO BEGIN ps=hash(j,i); hash(web_num,i) s=null; WHILE p->=null DO BEGIN k:=ptlabel(p) REM 10; hash(web_num,i):=node(ln(p),xvalue(p),yvalue(p), ptalbel(p),ndid(p),node_pos(p), 1 1(p ) , 1 2(p),null, null,hash(web_num,i),order(web_num,k)); order(web_num,k)i=hash(web_num,i); rj=table(p,hash(web_num,i),r); p;=nextnode(p) END END; FOR ii= 0 UNTIL 10 DO BEGIN pi=hash(j,i); ptrs=hash(web_num,i); WHILE n-.=null DO BEGIN ptt:=pto(p); WHILE ptt-,=null DO BEGIN zs=r; p:=refer_to(ptt); WHILE q-=old*(z) DO z:=next(z); pto(ptr):=node_to(new(z),arc_pos(ptt),pto(ptr)); ptt:=next_to(ptt) END; ptf:=pfr(p); WHILE ptf--=null DO BEGIN z s=r;q:=refer_from(ptf); WHILE q- i=old(z) DO zi=next(z); pfr(ptr):=node from(new(z),pfr(ptr)); ptfa=next fromTptf) END; ps=nextnodeTp) END END; xmin(web_num)s=xmin(j); xmax(web_num):=xmax(j); ymin(web_num)s=ymin(j); ymax(web_num):=ymax(j); store(no n d ( j ) , n o _ a r c ( j ) , n o _ l a b e l ( j ) , n d v ( j , * ) , a r c v ( j , * T , l a b v ( j , * ) ) ; header END END; PROCEDURE set_web; BEGIN REFERENCE(webs) web; REAL x,y: INTEGER ARRAY t ( l n l O O ) ; INTEGER n t ; noweb:=0 agtext ( - 6 . , 9 - 5 , . 2 5 ,"web names:",0.,10,web_n,no_web); web:=header; xs=-3 .0; yj= 9 . 5 ; WHILE web-.=null DO BEGIN IF y -5 .0 THEN BEGIN x$=x+4.5; y:=9»5 END; agtext(x,y,.25»name(web),0. , l6,t,nt); FOR i : = l UNTIL nt DO web_n(no_web+i)s=t(i); noweb:=npweb+l; web_l(noweb)s=no_web+l; no_web:=no_web+nt; web_u(noweb):=no_web; web:=next_web(web); y»=y-l.0.END END; PROCEDURE store(INTEGER VALUE no graph,noarcs,nolb; INTEGER ARRAY graph,arcs,ndlabel (*)); 57 COMMENT to store v e c t o r s f o r nodes, arcs and l a b e l s , update ever y t h i n g concerning the current web; BEGIN REFERENCE(node) q; no_nd(web_num):=nograph; no_arc(web_num):=noarcs; no_label(web_num)s=nolb; number(header):=numnodesj FOR i s = l UNTIL nograph DO ndv(web_num,i):=graph(i); FOR i : = l UNTIL noarcs DO arcv(web_num,i):=arcs(i); FOR i s = l UNTIL nolb DO labv(web_num,i):=ndlabel(i) END; REFERENCE(table2) PROCEDURE s_label(STRING VALUE s; REFERENCE(table2) VALUE p o i n t e r ) ; COMMENT t o search i f the l a b e l s i s already e x i s t e d and r e t u r n the reference, i f not, create a record; BEGIN IF p o i n t e r = n u l l THEN BEGIN p a t l a b e l s = p a t l a b e l + l ; l a b e l t a b l e 8 = t a b l e 2 ( s , p a t l a b e l , 1 , l a b e l t a b l e ) ; l a b e I t a b l e END ELSE IF s + l a b e l ( p o i n t e r ) THEN BEGIN i d e n t ( p o i n t e r ) s = i d e n t ( p o i n t e r ) + l ; p o i n t e r END ELSE s _ l a b e l ( s , n e x t l a b e l ( p o i n t e r ) ) END; INTEGER PROCEDURE choose(INTEGER ARRAY low,up,agt (*); INTEGER VALUE n ) ; COMMENT t o choose an element from menu and ret u r n s the value which i n d i c a t e i t s p o s i t i o n i n the d i s p l a y b u f f e r ; BEGIN INTEGER k , i ; INTEGER ARRAY s (1:s6)j REAL x,y,xc,yc; k:=l; a g t d s p ( l i g h t _ p , n o l i g h t _ p , i n d i c a t o r , # 0 , 0 ) ; indicator.s=ihdicat or+nblight j ; a g t h i t ( i ) ; WHILE - ( ( i =low(k)) AND ( i =up(k))) DO k:=k+l; k END; PROCEDURE .s^labe l i d (INTEGER VALUE 1; INTEGER VALUE i d ; REFERENCE(node) VALUE RESULT p t r . p t p ) ; COMMENT t o f i n d out the node w i t h l a b e l 1 and i . d . i d i n the subweb which i s t o be del e t e d ; IF ptr-.=null THEN I F _ ^ ( ( l = p t l a b e l ( p t r ) ) AND ( i d = n d i d ( p t r ) ) ) THEN BEGIN ptp:=ptr; p t r : = n e x t o r d e r ( p t r ) ; s _ l a b e l i d ( l , i d , p t r , p t p ) END; PROCEDURE dialandfns(REAL RESULT x , y ) j BEGIN REAL ARRAY d ( l s : 6 ) ; BITS ARRAY l ( l s s l 8 ) ; f n s ( l ) ; d i a l s ( d ) ; xs=d(4)*10.0; yi=d(l)*10.0 END; PROCEDURE searchxy(REAL VALUE x,y; REFERENCE(node) VALUE RESULT p t r , p r e ) ; COMMENT search f o r the node i n d i c a t o r and returns the reference of the node ( x , y ) ; 58 BEGIN REAL xabs,yabs; IF ptr-.=null THEN BEGIN xabs:=ABS ( x - x v a l u e ( p t r ) ) ; yabs:=ABS ( y - y v a l u e ( p t r ) ) ; IF -.((xabs =.09) AND (yabs =.09)) THEN BEGIN pr,e's=ptr; p t r :=nextnode(ptr); searchxy(x»y»ptr,pre) END END END; PROCEDURE indicate_arc(INTEGER ARRAY agt (*); INTEGER VALUEfn; REAL RESULT s , t , u , v ) ; COMMENT t o i n d i c a t e the a r c ; BEGIN BITS ARRAY l o g (ls»18); INTEGER i,m,nm,id,ie; REAL x,y; INTEGER ARRAY a ( 1 M 2 5 ) ; INTEGER ARRAY temp ( l s : 1 5 ) ; agtdsp(f_k,nf_k,indicator, # 0 , 0 ) ; i n d i c a t o r s = i n d i e a t o r + n f _ k ; log(l)s=#0; i s = l ; WHILE log(l)=#0 DO BEGIN c v t a g t ( a g t ( i ) , s , t , i d , i e ) ; cvtagt (agt ( i + 1 ) , u , v , i d , i e ) ; x t#is*ut*i-33 r y i ^ etH-v) •*; 33 J agtext(x,y, . 2,"0",6. ,l,a,m); x:=(s+u)*.67; ys=(t+v)*.67; agtext(x,y, .2,,,0",0.,l,temp,nm); FOR :3 :=1 UNTIL nm DO a(m+ j ) i=temp( j ) ; ms=m+nm; agtdsp(a,m,indicator,#0,0); f n s ( l o g ) ; r t w a i t ( l O O ) ; is=i+6; IF i n THEN i : = l END END; PROCEDURE indicate_node(INTEGER ARRAY agt (*); INTEGER VALUE n; REAL RESULT x , y ) ; COMMENT t o i n d i c a t e a de s i r e d node, returns i t s p o s i t i o n i n the d i s p l a y b u f f e r ; BEGIN BITS ARRAY l o g ( l i t l 8 ) ; INTEGER i , i d , i e ; REAL ARRAY x_sq,y_sq(l; * 4 )s INTEGER ARRAY square(1:$5); agtdsp(f_k,nf_k,indicator, # 0 , 0 ) ; i n d i c a t o r J = i n d i e a t o r + n f _ k ; log(l)s=#0; i s = l ; WHILE log(l)+#0 DO BEGIN cvtagt (agt ( i ) ,x,y, i d , i e ) ; FOR js=l UNTIL k DO BEGIN x_sq(j)s=x_squ(j)+x; y_sq(j)s=y_squ(j)+y END; ag t c v t ( s q u a r e ( 1 ) , x _ s q ( l ) , y _ s q ( l ) , 0 , 0 ) ; FOR j s=2 UNTIL 4 DO a g t c v t ( s q u a r e ( j ) , x _ s q ( j ) , y _ s q ( j ) , 1 , 0 ) ; agtcvt(square( 5),x_sq( 1),y sq(1),1,0); agtdsp(square,5,indicator,#0,0); f n s ( l o g ) ; rtwait ( 1 0 0 ); is=i+2; IF i n THEN i : = l END END; PROCEDURE dele'te__node (REFERENCE (node) VALUE p t r ; INTEGER ARRAY graph,arcs,ndlabel (*); INTEGER VALUE RESULT nograph,noarcs,nolb; INTEGER VALUE i l ) ; COMMENT d e l e t i o n of node w i t h reference p t r i ptp i s the reference of the previous node; 59 IF nograrjh>0 THEN BEGIN INTEGER k , l ; REFERENCE(node_to) pt r n t . p t r n t f ; REFERENCE(node) pj REFERENCE(node_from) p t r n f , p t r n f f ; kmode_pos(ptr); nograph:=nograph-2; IF k<nograph THEN FOR i:=k UNTIL nograph DO graph(i):=graph(i+2); FOR ji=0 UNTIL 10 DO BEGIN p:=hash(il,h); WHILE p-=null DO BEGIN IF node_pos (p)>k THEN node_post(p):=node_pos(p)-2; p:=nextnode(p) END END; IF ll(ptr)>0 THEN BEGIN k s = l l ( p t r ) ; l:=12(ptr)-k+l; nolbs=nolb-l; IF k<nolb THEN FOR is=k UNTIL nolb DO ndlabel(i)«=ndlabel(i+l) END; ptrnt:=pto(ptr); FOR is=0 UNTIL 10 DO BEGIN p»=hash(il,i); d_l(p,k,l)" END; WHILE ptrnt - r=null DO BEGIN k«=arc_pos(ptrnt); noarcs:=noarcs-6; FOR h:=0 UNTIL DO BEGIN p:=hash(il,h); d_a(p,k) END; IF k<noarcs THEN FOR i:=k UNTIL noarcs DO arcs(i):=arcs(i+6); ptrnf$=pfr(refer t o ( p t r r i t ) ) ; p trnff:=null; WHILE refer_fromTptrnf )->=ptr DO BEGIN p t r n f f *=ptrnf; ptrnf:=next_from(ptrnf) END; IF ptrnff=null THEN p f r ( r e f e r to(ptrnt))»=next_from(ptrnf) ELSE next_fromTptrnff);=next_from(ptrnf); ptrnts=next_to(ptrnt) END; ptrnf:=pfr(ptr); WHILE ptrnf^=null DO BEGIN ptrnt:=pto(refer_from(ptrnf)); ptrntf:=null; WHILE refer_to (ptrnt )-r=ptr DO BEGIN p t r n t f :=ptrnt; ptrnt»=next_to(ptrnt) END; IF ptrntf=null THEN pto(refer_from(ptrnf)):=next_to(ptrnt) ELSE next_to(ptrntf):=next_to(ptrnt); ptrnfs=next_from(ptrnf) END; IF ptr=hash(il,TRUNCATE(ABS xvalue(ptr))) THEN hash(il,TRUNCATE(ABS xvalue(ptr))):=nextnode(ptr) ELSE BEGIN p s=hash(il,TRUNCATE(ABS xvalue(ptr))); WHILE ptr-.=nextnode (p) DO p :=nextnode (p); nextnode(p):=nextnode(ptr) END: IF ptlabel(ptr)-=0 THEN IF p t r - o r d e r ( i l , ( p t l a b e l ( p t r ) REM 10)) THEN o r d e r ( i l , ( p t l a b e l ( p t r ) REM 10)):=nextorder(ptr) ELSE BEGIN p;=order(il,(ptlabe(ptr) REM 10)); WHILE ptr-.=nextorder(p) DO p!=nextorder(p); nextorder(p):=nextorder(ptr) END END; PROCEDURE d_l(REFERENCE(node) VALUE p; INTEGER VALUE k , l ) ; BEGIN IF p-,=null THEN BEGIN 6 0 IF l l ( p ) > k THEN BEGIN l l ( p ) : = l l ( p ) - l ; 1 2 ( p ) » = 1 2 ( p ) - l END; d_l(nextnode(p),k, 1 ) END END; PROCEDURE d_a(REFERENCE(node) VALUE p; INTEGER VALUE k ) ; BEGIN REFERENCE(node_to) p t r n t ; IF p^=null THEN BEGIN p t r n t i = p t o ( p ) ; WHILE p t r n t - = n u l l DO BEGIN IF arc_pos ( p t r n t )>k THEN arc_pos". ( p t r n t ) s=arc r>os(ptrnt)-6; ptrnt:=next_to(ptrntTEND; d_a(nextnode (p)VkX.END END; PROCEDURE COMMANDt COMMENT set up g l o b a l agt v e c t o r s ; BEGIN a g t e x t ( - 2 . , - 9 . , . 2 5 , " l e f t web " , 0 . , 8,l_web,nolw); a g t e x t ( - 2 . , - 9 • , • 2 5 , " r i g h t web",0.,9»r_web,norw); a g t e x t ( - 2 . , - 9 . , . 2 5 , " h o s t web " , 0 . , 8,h,nh); a g t e x t ( - 2 . , - 8 . , . 2 5 , " r u l e " , 0 . , 4 , r n u m , n r n ) ; a g t e x t ( 5 . , - 8 . , . 2 5 » " s a m e rule" ,0 . ,9»same_rule,n_sr); s r _ l o w ( l ) J = 1 ; sr_low ( 2 ):=n_sr+l; s r _ u p ( l ) s = n _ s r ; a g t e x t ( 5 . , - 8 . 7 5 , . 2 5 , " n e x t r u l e " , 0 . , 9 » t , n t ) ; FOR i s = l UNTIL nt DO sa m e _ r u l e ( n _ s r + l ) : = t ( i ) ; n_srs=n_sr+nt; sr_up ( 2 )s=n_sr; a g t e x t ( 5 . , - 8 . , . 2 5 , " w h a t e v e r " ,0 . , 8 , w h a t , n w h ) ; wh_low (1):=1; wh_up ( 1): =nwh; whJLow (2): =nwh+1; a g t e x t ( 5 . , - 9 « » . 2 5 , " s p e c i f i c " , 0 . , 8 , t , n t ) ; FOR i : = l UNTIL nt DO what(nwh+i)s=t(i); nwh s =nwh+nt; wh_up(2):=nwh; a g t e x t ( - 2 . , - 8 . , . 2 5 , " f r o m " , 0 . , 4 , f r o m _ t o , n f t ) ; l f t ( 1 ) i = l i u f t ( l ) : = n f t ; l f t ( 2 ) : = n f t + l ; a g t e x t ( - 2 . , - 9 . , . 2 5 , " t o " , 0 . , 2 , t , n t ) ; FOR i»=l UNTIL nt DO f r o m _ t o ( n f t + i ) s = t ( i ) ; nft:=nft+nt; u f t ( 2 ) ; + n f t END; PROCEDURE menu; COMMENT—set up g l o b a l agt v e c t o r s ; BEGIN a g t e x t ( - 2 . , - 8 . , . 2 5 , " i n p u t web name " , 0 . , l 4,in_web,nin); a g t e x t ( - 2 . , - 8 . , . 2 5 , " c r e a t e : " , 0 . , 7 , c o m m a n d 2 , n 2 ) ; l o w e r 2 ( l ) s= n 2 + l ; a g t e x t ( l . , - 8 . , . 2 5 , " n o d e " , 0 . , 4 , t , n t ) ; FOR i : = l UNTIL nt DO c o m m a n d 2 ( n 2+i)s=t(i); n2:=n2+nt; u p p e r 2 ( l ) s= n 2 ; l o w e r 2 ( 2 ) ! = n 2+l; a g t e x t ( 3 . , - 8 . , . 2 5 , " a r c " , 0 . , 3 , t , n t ) ; FOR i J = 1 UNTIL nt DO c o m m a n d 2 ( n 2+i):=t(i); n2s=n2+nt; u p p e r 2 ( 2 ) : = n 2 ; l o w e r 2 ( 3 ) * = h 2+l; a g t e x t ( 5 . , - 8 . , . 2 5 , " l a b e l " , 0 . , 5 , t , n t ) ; FOR i : = l UNTIL nt DO c o m m a n d 2 ( n 2+i)s=t(i); n2s=n2+nt; u p p e r 2 ( 3 ) :=n2; l o w e r 2 ( 4 ) »l=n2+l; a g t e x t ( - 2 . , - 8 . 7 5 , . 2 5 , " d e l e t e « " , 6 . , ? , t , n t ) ; FOR i : = l UNTIL nt DO c o m m a n d 2 ( n 2+i)s=t(i); n2:=n2+nt; a g t e x t ( 1 . , - 8 . 7 5 , . 2 5 , H n o d e " , 0 . , 4 , t , n t ) ; FOR i : = l UNTIL nt DO c o m m a n d 2 ( n 2+i):=t(i); 61 n2:=n2+ntj u p p e r 2 ( 4 ) : = n 2j l o w e r 2 ( 5 ) : = n 2+l; a g t e x t ( 3 . , - 8 . 7 5 , . 2 5 , " a r c " , 0 . , 3 , t , n t ) ; FOR i:= 1 UNTIL nt DO c o m m a n d 2 ( n 2+i):=t(i); n2?=n2+nt; u p p e r 2 ( 5 ) ; = n 2 ; l o w e r 2 ( 6 ) : = n 2+l; a g t e x t ( 5 . , - 8 . 7 5 , . 2 5 , " l a b e l " , 0 . , 5 , t , n t ) ; FOR i : = l UNTIL nt DO c o m m a n d 2 ( n 2+i)s=t(i); n2:=n2+nt; u p p e r 2 ( 6 ) : = n 2 ; l o w e r 2 ( 7 )s= n 2+l; agtext( 1 . , - 9 • 5 , • 2 5,"new-web",0 . , 7,t,nt); FOR i : = l UNTIL nt DO c o m m a n d 2 ( n 2+i):=t(i); n2:=n2+nt; u p p e r 2 ( 7 )i= n 2 ; l o w e r 2 ( 8 ) : = n 2+l; a g t e x t ( 4 . , - 9 . 5 , . 2 5 , " r e t u r n " , 0 . , 6 , t , n t ) ; n2:=n2+nt; upper2(8):=n2;END; PROCEDURE coramand_menu •COMMENT--set up g l o b a l agt v e c t o r s ; BEGIN a g t e x t ( - 2 . , - 8 . , . 2 5 , " s p e c i f y t " , 0 . , 8 , c o m m a n d l , n l ) ; l o w e r l ( 1 ) : = n l + l ; a g t e x t ( 1 . , - 8 . , . 2 5 , " w e b s " , 0 . , 4 , t , n t ) ; FOR i : = l UNTIL nt DO commandl(nl+i):=t(i); nl:=nl+nt; upperl ( 1):=nl; l o w e r l ( 2 ) : = n l + l ; a g t e x t ( 4 . , - 8 * . , . 2 5 , " r u l e s " , 0 . , 5 , t , n t ) ; FOR i s = l UNTIL nt DO commandl(nl+i):=t(i); nl:=nl+nt; u p p e r l ( 2 ) J = n l ; l o w e r l ( 3 ) : = n l + l ; a g t e x t ( l . , - 8 . 7 5 , . 2 5 , " h o s t w e b " , 0 . , 8 , t , n t ) ; FOR i : = l UNTIL nt DO commandl(nl+i):=t(i); n l i = n l + n t ; u p p e r l ( 3 ) i = n l ; l o w e r l ( 4 ) : = n l + l ; a g t e x t ( 4 . , - 8 . 7 5 , . 2 5 , " e m b e d d i n g s " , 0 . , 1 0 , t , n t ) ; FOR i i = 1 UNTIL nt DO commandl(nl+i)«=t(i); nls=nl+nt; upperl ( 4 ):=nl; lowerl ( 5 ):=nl+i;> a g t e x t ( 1 . , - 9 . 7 2 , . 2 5 , " a p p l y r u l e s " , 0 . , 1 1 , t , n t ) ; FOR i s = l UNTIL nt DO commandl(nl+i)s=t(i); nl:=nl+nt; u p p e r l ( 5 ) s = n l ; l o w e r l ( 6 ) : = n l + l ; a g t e x t ( 4 . , - 9 . 7 5 , . 2 5 , " r e t u r n " , 0 . , 6 , t , n t ) ; FOR i ! = l UNTIL nt DO commandl(nl+i)$=t(i); nls=nl+nt; upperl ( 6 ):=nl; agtext ( 5 « , - 8 . , . 2 5 ,"from-node",0 . , 9 ,fromnd,nfromnd); a g t e x t ( 5 . , - 8 . , . 2 5 , " t o - n o d e " , 0 . , 7 , t o n d , n t o n d ) ; a g t e x t ( 5 • , - 8 . , . 2 5 , " w h i c h node?",0.,11,node_l,num_node); agtext (5 • , - 8 . , . 25»"which arc? V , 0 , , 1-0,wh^arcVnwh^arc); agtext.j ( | . > - 8 ., i20^'apply",O. , 5,applie,ho_app); a p p _ l ( i ) : = 1 ; app_up(1) s =no_app; app_l(2):=no_app+1; agtext ( 5 . , - 9 . , . 2 5 , " r e t u r n " , 0 . , 6 , t * , n t ) ; FOR i s = l UNTIL nt DO a p p l i e ( n o ^ a p p + i ) j = t ( i ) ; no_app:=no_app+nt; app_up(2)t=no_app END; PROCEDURE tr i a n g l e ( R E A L VALUE x , y ) ; BEGIN REAL x s , y s , x t , y t ; INTEGER ARRAY t ( l s : 4 ) ; X S J = X - 0 . 2 ; ys;=y - 0 . 1 ; a g t c v t ( t ( 1 ) , x s , y s , 0 , 0 ) ; xt:=x+ 0 . 2 ; a g t c v t ( t ( 2 ) , x t , y s , 1 , 0 ) ; yts=y+ 0 . 2 5 ; a g t c v t ( t ( 3 ) , x , y t , 1 , 0 ) ; a g t c v t ( t ( 4 ) , x s , y s , 1 , 0 ) ; a g t d s p ( t , 4 , n s r + l , # 0 , 0 ) END; 62 COMMENT main program; COMMENT i n i t i a l i z i n g g l o b a l v a r i a b l e s ; FOR i : = l UNTIL total_web DO BEGIN xmax(i)s= 0 . ; x m i n ( i ) : = 0 . ; ymax(i ) : = 0 . ; ymin(i) : = 0 . "END; p a t l a b e l ; = 0 ; no_of_rule's=0; web_nums=0; l r w s - 1 0 ; header:=null; host_web:=null; FOR i : = l UNTIL 10 r u l e s ) i ) : = n u l l ; l a b e I t a b l e s=null; x_squ(l)» = 0 . 1; y_squ ( 1 ) : = 0 . 1 ; x_squ ( 2 ) : = 0 . 1; y_squ ( 2 ) : = 0 . 1 ; x_squ ( 3 )i= - 0 . 1; y ^ s q u ( 3 ) i= - 0 . 1 ; x_squ(4)J= 0 . 1; y_squ(4)s= - 0 . 1 ; x s ( l ) : = 0 . ; y s ( l ) i = 0 . ; x s ( 2 ) : = - 0 . 5 ; y s ( 2 ) i = 0 . ; x s ( 3 ) » = 0 . ; y s ( 3 ) : = 0 . ; x s ( 4 ) s = - . 2 ; y s ( 4 ) i = . l j X S ( 5 ) J = 0 . ; ys ( 5 ) : = 0.j x s ( 6 ) : = - . 2 ; y s ( 6 ) : = - . l ; BEGIN INTEGER q,k,m,n; IF t o t a l _ r u l e 9 THEN n s = t o t a l _ r u l e ELSE n:=9; FOR j : = 0 UNTIL n DO BEGIN numeral(j)s=" "; numeral(j ) ( 0|l):=code(240+j) END; m:=0; q : = t o t a l _ r u l e DIV 1 0 ; k : = 0 ; WHILE q-=0 DO BEGIN INTEGER j,remain; ks=k+l; m:=m+10; IF q=l THEN remain:=total_rule REM 10 ELSE remain:=9; FOR i : = 0 UNTIL remain DO BEGIN js=m+i; numeral(j)s=" M; numeral( j ) ( 0 11)i=numeral(k) ( 011 ) ; n u m e r a l ( j ) ( 1 | 1 ) i = n u m e r a l ( i ) ( 0 | 1 ) END; q:=q-l END END; FOR i : = l UNTIL t o t a l _ r u l e DO RULES(i):=null; COMMENT s e t t i n g up permanent agt-Idisplay v e c t o r s ; a g t e x t ( 0 . , 0 . , . 2 5 , " t o o many webs",0 . , 1 3 ,too many,nmany); a g t e x t ( - 2 . , - 8 . , . 2 5 » " a p p l i c a b l e r u l e s " , 0 . a p p _ r , n o a p p ) ; a g t e x t ( 0 . , - 8 . , . 2 5 , " i n p u t l a b e l " , 0 . , 1 1 , l a b e l v , n l v ) ; command; menu; command menu; BEGIN INTEGER ARRAY t 7/l : : 1 5 0 ) ; INTEGER ARRAY l p ( 1 : : 2 0 0 ) ; INTEGER nt,np; REAL y; STRING s; y:=9»; a g t e x t ( 0 . , 9 . » . 2 5 , " r u l e number : " , 0 . , 1 2 ,rule_num,nrule_num); FOR i : = l UNTIL t o t a l _ r u l e DO BEGIN a g t e x t ( 4 . , y , . 2 5 , n u m e r a l ( i ) , 0 . , 3 , t , n t ) ; FOR i i : = l UNTIL nt DO ruTe_num(nrule_num+ii)s=t(ii); rn_l(i)s=nrule_num+l; nrule_num:=nrule_num+nt; rn_p(i):=nrule_num; y:=y-1.0 END; a g t e x t ( 2 . , y , . 2 5 , " r e t u r n " , 0 . , 6 , t , n t ) ; r n _ l ( t o t a l _ r u l e + l ) s = n r u l e _ n u m + l ; nrule_num :=nrule4_num+nt; r n _ p ( t o t a l _ r u l e + l ) s=nrule_num:.END; d e c i s i o n END ENDv 63 APPENDIX B The system i s evoked by the f o l l o w i n g statements $RUN CS:ALGOL.O+CSiFORTRAN.0+AGTiBASIC PAR=SIZE=?5P The f i r s t i n s t r u c t i o n appears on the AGP ( Adage G r a p h i c a l Terminal ) d i s p l a y screen i s the one shown on P l a t e 1 . Then p l a t e s w i l l appear on the screen according to the sequence described at the foot of each p l a t e . next comes P l a t e 2 P l a t e 1 next comes P l a t e 3 P l a t e 2 64 l i g h t - p e n i s used to p i c k out the item the user wants, depending on the item picked e i t h e r P l a t e 4, 5, 12 or 20 comes next P l a t e 3 INPUT WEB NfME f o r the s p e c i f i c a t i o n of webs, a s t r i n g of characters i s to be input t o i d e n t i f y webs next comes P l a t e 5 P l a t e 4 the operations llowed f o r the s p e c i f i c a t i o n of webs are shown, depending on the operation wanted, e i t h e r P l a t e 7» 8 , 10, 3 or 4 comes next P l a t e 5 t h i s i s the same as P l a t e 5» except w i t h a part of a web created P l a t e 6 imwm TIC PSHTIBI tr n mn t o i n d i c a t e the p o s i t i o n of a node which i s to be created. P l a t e 7 UK F U C T 1 W W T i n * t o s p e c i f y the from-node of an arc next comes P l a t e 9 P l a t e 8 to s p e c i f y the to-node of the same arc whose from-node i s enclosed by a t r i a n g l e P l a t e 9 previous to t h i s one there i s one p l a t e almost the same as P l a t e 9» except w i t h "which node?" i n place of " t o -node", the node enclosed by the t r i a n g l e i s the node whose l a b e l i s t o be in p u t ; next comes P l a t e 5 P l a t e 10 6 8 f o r s p e c i f i c a t i o n of e i t h e r embeddings or r e w r i t i n g r u l e s , next comes e i t h e r P l a t e 1 2 , 3 or 1 5 , depending on the operation ( i . e . s p e c i f i c a t i o n of r u l e or embeddings ) P l a t e 11 HI f o r s p e c i f i c a t i o n of the l e f t of a r e w r i t i n g r u l e , there comes a s i m i l a r p l a t e f o r the s p e c i f i c a t i o n of r i g h t web or of host web. P l a t e 1 2 P l a t e 13 P l a t e 14 3oth these p l a t e s appear f o r a b r i e f moment a f t e r the l e f t web or the r i g h t web has been s p e c i f i e d , there i a s i m i l a r p l a t e f o r the s p e c i f i c a t i o n the host web mxi i menu 70 the f i r s t p l a t e f o r the s p e c i f i c a t i o n of embeddings, next comes P l a t e 16 P l a t e 15 s p e c i f i c a t i o n of A next comes P l a t e 17 P l a t e 16 USE LlflHT-PEN wot TO p e c i f i c a t i o n of I, next comes P l a t e 18 P l a t e 1 7 p e c i f i c a t i o n of 3 , next comes P l a t e 1 9 P l a t e 18 72 f o r a p p l y i n g web r e w r i t i n g r u l e s , next comes P l a t e 3 or 22 P l a t e 20 this is the message on the lower right corner of Plate Plate 21
Thesis/Dissertation
eng
Computer Science
Vancouver : University of British Columbia Library
For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.
Graduate
An interactive graphical program for specification and application of web rewriting rules
Text