Home
The GrGen User Manual
Contents
1. Or OE CSC SO ON E Be mg Rh e e psp AS 6 Y EE modify I eval y i eval y j x IJNode y IJNode delete x eval x i 1 ve x i yi b This toy example yields y i 42 y j 1 CHAPTER 4 TYPES AND EXPRESSIONS In the following sections Ident refers to an identifier of the graph model language see Sec tion 2 1 or the rule set language see Section 3 1 Typeldent is an identifier of a node type or an edge type NodeOrEdge is an identifier of a node or an edge 4 1 Built In Types Besides user defined node types edge types and enumeration types GRGEN NET supports the built in primitive types in Table 4 1 The exact type format is backend specific The LGSPBackend maps the GRGEN NET primitive types to the corresponding C primitive types Table 4 2 lists GRGEN NE T s implicit type casts and the allowed explicit type casts boolean Covers the values true and false int A signed integer with at least 32 bits float double A floating point number with single precision or double precision respec tively string A character sequence of arbitrary length Table 4 1 GRGEN NET built in primitive types Of course you are free to express an implicit type cast by an explicit type cast as well as Cast a type to itself except for enum types The cast operator does never accept an enum type myfloat myint mydouble float myint mystring string mybool is allowed
2. EXAMPLE 8 We define a test SomeCond test SomeCond pattern I n SeldomNodeType al RR W N R and execute in GRSHELL 1 grs SomeCond amp SomeRule SomeRule will only be executed if a node of type SeldomNodeType exists For graph rewrite sequences in GRSHELL see Section 5 2 6 ActionSignature IdentDecl The signature sets the name of a rewrite rule to IdentDecl and optionally names and types of formal parameters as well as a list of return types Parameters and return types provide users with the ability to exchange graph elements with rule This is similar to parameters of procedural languages Parameters Within a rule parameters are treated as predefined graph elements of the pattern Even if a supplied parameter value is undefined it is treated as valid node or edge definition So in any case a graph element of the specified type has to be mapped GRGEN NET assumes the lookup operation for parameters to be in O 1 In case of an undefined parameter value this might lead to bad search plans because GRGEN NET has to actually search for such a eraph element Return Types Bee The return types specify edge and node types of graph elements that are returned by the replace modify part If return types are specified the return statement is mandatory Oth erwise no return statement must occur See also Section 3 4 return 22 Rule Set Language Assume the following test that ch
3. A5_south highway f AS_north highway ff ri eek Y P Karlsruhe metropoli Y S f right side dumped with dump add node metropolis group 46 GrShell Language En a L re AttributeName Declares the attribute AttributeName to be an info tag Info tags are displayed like ad ditional node edge labels The keyword only excludes the subtypes of Node Type resp Ed ge Type In the following example river and jam are info tags A3 highway jam False m False AN South highway jam True Y trail street Specifies whether edge labels will be displayed or not defaults to on dump Reset all style options dump set to their default values 5 2 6 Action Commands GRS An action denotes a graph rewrite rule select actions Filename Selects a rule set Filename can either be a NET assembly e g rules dll or a source file rules cs Only one rule set can be loaded simultaneously show actions 5 2 GRSHELL Commands AT s t Concatenation First execute s afterwards execute t The sequence s t is successfully executed iff s or t is successfully executed s t XOR First execute s Only if s fails i e can not be executed suc cessfully then execute t The sequence s t is successfully executed iff s or t is successfully executed s amp t Transactional AND First execute s afterwards execute t If s or t fails the action will be terminated and a rollback to the s
4. Pattern Graph Rewrite Graph Preservation Morphism r LR Rul Match m H H Host Graph Result Graph Figure 3 1 Process of Graph Transformation GRGEN NET the preservation morphism r is defined implicitly by using names in pattern graphlets and replace graphlets We don not need to care about the the differences of the replace part and the modify part at the moment Remember that to each of the graph elements a name is bound to either user defined or internally defined If such a name is used 26 Rule Set Language in a replace graphlet the denoted graph element will be kept Otherwise the graph element will be deleted By defining a name in a replace graphlet a corresponding graph element will be newly created So in a replace pattern anonymous graph elements will always be created Using a name multiple times has the same effect as a single using occurrence In case of a conflict between deletion and preservation deletion is prioritized If an incident node of an edge gets deleted the edge will be deleted as well in compliance to the SPO semantics Pattern LHS Replace RHS r L R Meaning x T x r lhs e gt rhs Preservation SE lhs x E def r Deletion x T rhs r ran r Creation SE SSES Illegal redefinition of x e T gt e gt x Node Illegal redirection of e x N e E gt y N x e gt r lhs x gt rhs x Deletion of y Hence del etion of e Table 3 1 Definition of the preservation morp
5. s State h RWHead gt tp TapePosition zero gt tp s zero gt wv WriteValue modify I delete h wv RWHead gt tp oO A ND ow A OQ 10 11 We take the current state s and the current cell tp which is implicitly given by the unique RWHead edge and check whether the cell value is zero Furthermore we check if the state has a transition for zero The replacement part deletes the RWHead edge between s and tp and adds it between wv and tp The remaining rules are analogous 12 rule readOneRule 13 pattern 14 s State h RWHead gt tp TapePosition one gt tp 15 s one gt wv WriteValue 16 Le 17 modify I 18 delete h 19 wv RWHead gt tp 20 Le 21 22 23 rule readEmptyRule 24 pattern 25 s State h RWHead gt tp TapePosition empty gt tp 26 s empty gt wv WriteValue 27 28 modify I 29 delete h 30 wv RWHead gt tp 31 Le 32 34 rule writeZeroRule 4 35 pattern I 36 wv WriteZero rw RWHead gt tp TapePosition value gt tp 37 38 replace 39 WV rw gt tp zero gt tp 40 41 43 rule writeDneRule 44 pattern 45 wv Write ne rw RWHead gt tp TapePosition value gt tp 6 2 Busy Beaver 46 47 replace 48 wv rw gt tp one gt tp 49 Le 50 52 rule writeEmptyRule 53 pattern I 54 wv WriteEmpty rw RWHead gt tp TapePosition value gt tp 55 56 replace 57 WV rw gt tp emp
6. 36 45 command line 38 comment 35 compatible types see type compatible compiler graph see layout algorithm connection assertion 12 13 39 constructor 36 41 continuation see graphlet debug mode 38 debugger 49 declaration 10 11 23 default graph model 15 default search plan 49 default value 41 definition 10 34 degree see connection assertion deletion 26 27 determinism see non determinism double 29 dumping graph 43 Dynamic patterns 2 Edge 12 edge graphlet 18 edge type 12 empty pattern 4 23 enum type 11 29 evaluation see attribute evaluation float 29 Fujaba 1 generator 2 graph model 2 9 11 15 19 38 graph model language 9 graph rewrite rules 3 graph rewrite script 2 6 38 43 graph rewrite sequence 23 48 6 2 Busy Beaver graphlet 16 24 25 27 GrGen exe 3 5 group node 45 GRS see graph rewrite sequence GrShell 2 6 12 35 GrShell script see graph rewrite script GrShell exe 3 6 homomorphic matching 16 24 host graph 4 25 39 identifier 10 16 imperative see attribute evaluation incident 22 info tag 46 inheritance 9 12 43 int 29 isomorphic matching 24 Kantorowitsch tree 49 Koch snowflake 53 label 37 46 layout algorithm 7 38 53 left hand side 3 25 LGPL 5 LGSPBackend 29 49 lgspBackend dll 3 37 LHS see left hand side libGr 2 6 12 23 35 LibGr dll 3 6 match 4 matching s
7. i e without their incident nodes Beware of accidentally redirecting an edge The graphlets e Edge gt x Node e gt y Node are illegal because the edge e would have two destinations an anonymous node and y However the graphlets e gt x Node e Edge gt y Node are allowed but the first graphlet e gt is superfluous In particular this graphlet does not identify or create any copies neither if the graphlet occurs in the pattern part nor if it occurs in the replace part You cannot directly express the redirection of edges This a direct consequence of the SPO approach Redirection of edges can be simulated by either deleting and re inserting an edge or more indirect by re typing of nodes 3 2 Rules and Tests 19 Some attempts to specify a loop edge Graphlet Meaning x Node e Edge gt x The edge e is a loop x Node e Edge gt e gt x The edge e is a loop e Edge gt x Node The edge e may or may not be a loop e Edge gt The edge e is certainly not a loop Although both the pattern part and the replace modify part use graphlets there are subtle differences between them These concern the TypeConstraint clause the retype operator lt gt and the scope of defined graph element names Names defined within the pattern part are valid in the pattern part as well as in the replace modify part Names defined within the replace modify part are unknown to the patt
8. such attributes are still writable by LIBGR and GRSHELL directly This property applies to attributes defined in the current class only It does not apply to inherited attributes The const property will not be inherited by subclasses either If you want a subclass to have the const property you have to set the const modifier explicitly NodeClass CE tar ad Om Defines a new node type Node types can inherit from other node types defined within the same file If the extends clause is omitted Node Type will inherit from the built in type Node Optionally nodes can possess attributes EdgeClass a Eet ce i Connect ssertions y Ka AttributeDeclarations D Defines a new edge type Edge types can inherit from other edge types defined within the same file If the extends clause is omitted Edge Type will inherit from the built in type Edge Optionally edges can possess attributes connection assertion specifies that certain edge types should only connect specific nodes Moreover the number of outgoing and incoming edges can be constrained 2 2 Type Declarations 13 It is not forbidden to create graphs that are invalid according to connection assertions GR GEN NET just enables you to check whether a graph is valid or not See also Section 5 2 2 validate ConnectA ssertions connect NodeC 7 NodeConstraint onstraint B NodeConstraint RangeConstraint RangeConstraint ey
9. A connection assertion is denoted as a pair of node types in conjunction with their multiplic ities A corresponding edge may connect a node of the first node type or one of its subtypes source with a node of the second node type or one of its subtypes target The multiplicity is a constraint on the out degree and in degree of the source and target node type respec tively Number is an int constant as defined in Section 4 2 See Section 5 2 2 validate for an example Table 2 1 describes the multiplicity definitions The number of edges incident to a node of that type is unbounded At least n edges must be incident to nodes of that type At least n edges must be incident to nodes of that type but at most m edges may be incident to nodes of that type m gt n must hold Abbreviation for 0 Abbreviation for 1 Abbreviation for n n Table 2 1 GRGEN NET node constraint multiplicities AttributeDeclarations N AttributeType O 14 Graph Model Language Attribute Type T PrimitiveType 7 Enum Type Defines a node or edge attribute Possible types are enumeration types enum and primitive types See Section 4 1 for a list of built in primitive types CHAPTER 3 RULE SET LANGUAGE 1 The rule set language forms the core of GRGEN NET Rule files refer to zero or more graph models and specify a set of rewrite rules The rule language covers the pattern specification and the replace modify specification Attr
10. Adam M Szalkowski Negative Anwendungsbedingungen f r das suchprogramm basierte Backend von GrGen 2005 Studienarbeit Universit t Karlsruhe The Mono Team Mono http www mono project com 2007 Gergely Varr D niel Varr and Katalin Friedl Adaptive graph pattern match ing for model transformations using model sensitive search plans In G Karsai and G Taentzer editors GraMot 2005 International Workshop on Graph and Model Transformations volume 152 of ENTCS pages 191 205 Elsevier 2006 y Works yFiles http www yworks com 2007 Keywords abstract 11 actions 19 46 48 49 51 add 45 46 backend 37 38 bordercolor 45 class 12 clear 39 color 45 connect 13 const 11 custom 40 48 49 51 debug 38 48 def 47 delete 27 39 42 disable 38 dump 44 46 echo 38 edge 12 42 43 45 46 edges 42 enable 38 enum 11 eval 27 exclude 45 exit 37 extends 12 graph 38 40 43 44 49 group 45 grs 48 help 37 hom 24 if 24 include 38 infotag 46 is 43 labels 46 layout 38 model 11 modify 26 negative 24 new 38 41 42 node 12 42 43 45 46 INDEX nodes 42 num 42 off 46 on 46 only 42 43 45 46 open 39 pattern 23 prio 34 quit 37 replace 26 reset 46 return 24 27 rule 19 save 43 select 37 39 46 set 38 45 46 shape 45 show 38 39 42 44 48 strict 39 sub 43 super 43 test 19 textcolor 45 t
11. Parameters exist i e if all the variables are defined true A constant acting as a successful match false A constant acting as a failed match lt Il Let s t u be graph rewrite sequences v w variable identifiers x an identifier of a graph element lt op gt amp and n No Table 5 1 Graph rewrite expressions 48 GrShell Language Lists all the rules of the loaded rule set their parameters and their return values Rules can return a set of graph elements SpacedParameters y Executes an action specific to the current backend If SpacedParameters is omitted a list of available commands will be displayed for the LGSPBackend see Section 5 3 custom actions GraphRewriteSequence SimpleRewriteSequence This executes the graph rewrite sequence SimpleRewriteSequence SimpleRewriteSequence Kg Parameters va Q SimpleRewriteSequence Rule Parameters 5 3 LGSPBackend Custom Commands 49 Table 5 1 lists graph rewrite expressions at a glance The operators hold the following order of precedence starting with the lowest priority amp Graph elements returned by rules can be assigned to variables using Parameters Action The desired variable identifiers have to be listed in Parameters Graph elements required by rules must be provided using Action Parameters where Parameters is a list of variable identifiers For undefined variables see Sect
12. enum type for use as attribute of nodes or edges Like all identifier definitions types do not need to be declared before they are used Enumbeclaration IdentDecl IdentDecl IntExpr Defines an enum type A GRGEN NET enum is internally represented as int see Sec tion 4 1 enum Color red green blue enum Resident village 500 town 5000 city 50000 enum AsInC a 2 b c 1 d e int Resident village c The semantics is as in C SAI 90 So the following holds red 0 green 1 blue 2 a pe NO SO ClassDeclaration NodeClass g EdgeClass p Defines a new node type or edge type The keyword abstract indicates that you cannot instantiate graph elements of this type Instead you have to derive non abstract types to create graph elements The abstract property will not be inherited by subclasses of course abstract const 12 Graph Model Language al RR W N We adjust our map model and make city abstract abstract node class city size int abstract node class abandoned_city extends city node class ghost town extends abandoned city You will be able to create nodes of type ghost town but not of type city or abandoned city However nodes of type ghost town are also of type abandoned city as well as of type city and they have the attribute size hence The keyword const indicates that rules may not write to attributes see also Section 3 4 eval However
13. graph AttributeName Identifier of an attribute Graph Identifies a graph by its name Action Identifies a rule by its name Color One of the following color identifiers Black Blue Green Cyan Red Purple Brown Grey LightGrey LightBlue LightGreen LightCyan LightRed LightPurple Yel low White DarkBlue DarkRed DarkGreen DarkYellow DarkMagenta DarkCyan Gold Lilac Turquoise Aquamarine Khaki Pink Orange Orchid These are the same color identifiers as in VCG YComp files for a VCG definition see San95 GraphElement The elements of a graph nodes and edges can be accessed both by their variable identifier and by their persistent name specified through a constructor see Section 5 2 3 The spe cializations Node and Edge of GraphElement require the corresponding graph element to be a node or an edge respectively EXAMPLE 18 We insert a node anonymously and with a constructor see also Section 5 2 3 gt select backend lgspBackend dll Backend selected successfully gt new graph lib lgsp TuringModel dl1l G New graph G of model Turing created insert an anonymous node it will get a persistent pseudo name gt new State New node 0 of type State has been created gt delete node 0 and now with constructor gt new v State start new node start of type State has been created Now we have a node named start and a variable vu assigned to sta
14. identifiers to denominate types attributes and the model itself The GRGEN NET graph model language is case sensitive Ident IdentDecl A non empty character sequence of arbitrary length consisting of letters digits or under scores The first character must not be a digit Ident and IdentDecl differ in their role While IdentDecl is a defining occurrence of an identifier Ident is a using occurrence An IdentDecl non terminal can be annotated See Section 4 4 for annotations of declarations Ae N The GRGEN NET model language does not distinguish between declarations and definitions More precisely every declaration is also a definition For instance the following C like pseudo GRGEN NET model language code is illegal node class t_node node class t_node Using an identifier before defining it is allowed Every used identifier has to be defined exactly once 2 2 Type Declarations 11 Node Type Edge Type Enum Type These are semantic specializations of Ident to restrict an identifier to denote a node type an edge type or an enum type respectively 2 2 Type Declarations GraphModel IdentDecl T ypeDeclaration The graph model consists of its name dentDecl and type declarations defining specific node and edge types as well as enums TypeDeclaration EnumDeclaration ClassDeclaration u ClassDeclaration defines a node type or an edge type Enumbeclaration defines an
15. layout process This may take a while depending on the graph size r sr eoo yComp Version 1 3 1 tmpgraph0 vcg ee yComp Version 1 3 1 tmpgraph0 vcg File Edit View Navigate EW 14 Help File Edit View Navigate Layout Help 4 7 Z m3 Daat de ESTA Random DEMS d XOGS4RHA gt AtRER Layout Options Hierarchic E r AR Organic Start Layouting pict I fen Select Edge Router Le Se a e vam _ R Ed ER Circular ER EE EE EE EET oute Edges T Tree DI hh ete ets E Di mo en po on fo Fold Subgraphs q Diagonal i Se ke 7 Unfold Subgraphs s incremen tal Hierarci hic eo ee mme em een mmm re Fold Selected Compilergraph u een A Al Find Graph Analysis lai ge p En mn le lb ze En Next Options Toggle Arrows AGD Next Opti e a een mg 13 Root 0 Reverse Edges SQF L Root 0 ears CE 0 GridNode Edge Classes V 0 GridNode eee Se Show All Edges care 103 GridNode 103 GridNode l ie EIES 106 GridNode Reset All Reference Nodes OS 106 GridNode pal Saz on zen 109 MarkedGridN n 109 MarkedGridN 10C MarkedGridN ss 54E GridNode de 10C MarkedGridN een Zum SE oe ps fs e e o ler s lle gier besen 10E GridNode 10E GridNode 111 GridNode 111 GridNode 114 MarkedGridN 114 MarkedGridN on l oot a dts 117 GridNode 117 GridNode 11 MarkedGridNc 11 MarkedGridNc es ee 511A GridNode 11A GridNode e mn 11D MarkedGridh 11D Ma
16. myenum myenum int myfloat mydouble myint int mybool is forbidden sal enum boolean double string enum boolean int int int int float float implicit float double double implicit implicit string string string string string string Table 4 2 GRGEN NET type casts 29 30 Types and Expressions 4 2 Expressions Expression Float Expr Primary Expr BoolExpr Primary Expr peng The operator negates a Boolean Table 4 4 lists the binary operators for Boolean expres sions The operator is a simple if then else If the first BoolExpr is evaluated to true the operator returns the second BoolExpr otherwise it returns the third BoolExpr The BinBool Operator is one of the operators in Table 4 4 The CompareOperator is one of the following Operators lt lt l gt gt These operators are supported by enum types int types and float double types String types and boolean types support only the and the operators Table 4 3 describes the semantics of compare operators on type expressions True iff A and B are identical Different types in a type hierarchy are not identical True iff A and B are not identical True iff A is a supertype of B but A and B are not identical True iff A is a subtype of B but A and B are not identical True iff is a supertype of B or and B are identical True iff A is a subtype of B or A and B are identica
17. o a nn 0 A W N O Furthermore we need states and transitions The machine s current configuration is modeled with a RWHead edge pointing to a TapePosition node State nodes are connected with WriteValue nodes via value edges a moveLeft moveRight dontMove edge leads from a WriteValue node to the next state cf the picture on page 59 node class State edge class RWHead node class WriteValue node class WriteZero extends WriteValue node class WriteDne extends WriteValue node class WriteEmpty extends WriteValue edge class moveLeft edge class moveRight edge class dontMove 6 2 2 Rule Set Now the rule set We begin the rule set file Turing grg with 1 acttons Turing using TuringModel We need rewrite rules for the following steps of the Turing machine 1 Read the value of the current tape cell and select an outgoing edge of the current state 56 Examples 2 Write a new value into the current cell according to the sub type of the WriteValue node 3 Move the read write head along the tape and select a new state as current state As you can see a transition of the Turing machine is split into two graph rewrite steps Writing the new value onto the tape and performing the state transition We need eleven rules Three rules for each step for zero one and empty and two rules for extending the tape to the left and the right respectively 2 rule readZeroRule pattern
18. operators in ascending order of precedence The operator on float values works analogous to the integer modulo operator For instance 452832 StringExpr StringExpr StringExpr The operator concatenates two strings PrimaryExpr eo PER Constant ess Ee true 4 3 Type Related Conditions 39 Number Is an int float or double constant in decimal notation HexNumber Is an int constant in hexadecimal notation starting with Ox Quoted Text Is a string constant It consists of a sequence of characters enclosed by double quotes 4 3 Type Related Conditions TypeExpr Typeldent NodeOrEdge type expression identifies a type and in terms of matching also its subtypes type expression is either a type identifier itself or the type of a graph element The type expression typeof x stands for the type of the host graph element x is actually bound to The following rule will add a reverse edge to a one way street rule oneway 1 pattern I a Node x street gt y Node negative I y typeof x gt a replace ack y y typeof x gt a oO 0 JD OD SG oa N r Rh e jp N e CH Remember that we have several subtypes of street By the aid of the typeof operator the reverse edge will be automatically typed correctly the same type as the one way edge This behavior is not possible without the typeof operator Type Constraint A ty
19. 8 33 type compatible 43 UML class diagram 30 undefined parameter 21 undefined variables 49 validate 39 variable 36 41 49 Varr s benchmark 1 VCG 6 36 44 66 Examples working graph 39 yComp 6 44 49 yComp jar 6 49
20. GRGEN NET YCOMP ships with its own license Although YCOMP is not free software it s free for use in academic and non commercial areas 1 6 1 GrGen exe The GrGen exe assembly implements the GRGEN NET generator The GRGEN NET gen erator parses a rule set and its model files and compiles them into NET assemblies The compiled assemblies interact with the GRGEN NE T backend 6 Introduction Usage mono GrGen exe use lt existing dir gt d lt rule set gt lt output dir gt rule set is a file containing a rule set specification according to chapter 3 Usually such a file has the suffix grg The suffix grg may be omitted By default GRGEN NE T tries to write the compiled assemblies to the directory lib relative to the path of GrGen exe This can be changed by the optional parameter output dir Options d Enable debug output A subdirectory tmpgrgenn within the current direc tory will be created This directory contains e printOutput txt a snapshot of stdout during program execution e NameActions cs the C source file of the rule setActions dll as sembly e NameModel cs the C source file s of the rule setModell d11 assem bly use Don t re generate C source files Instead use the files in existing dir to build the assemblies Requires NET 2 0 or above or Mono 1 2 2 or above Java Runtime Environment 1 5 or above 1 6 2 GrShell exe The GRSHELL is a shell application of the LIBGR GRSHELL i
21. Parameters is omitted a list of available commands will be displayed for the LGSP backend see Sections 5 3 5 2 3 Graph Manipulation Commands Graph manipulation commands alter existing graphs including creating and deleting graph elements and setting attributes 5 2 GRSHELL Commands 41 Constructor A constructor is used to initialize a new graph element see new below A comma separated list of attribute declarations is supplied to the constructor Available attribute names are specified by the graph model of the current working graph All the undeclared attributes will be initialized with default values depending on their type int 0 enum unspecified boolean false float double 0 0 string The is a special attribute name a unique identifier of the new graph element This identifier is also called persistent name see Example 18 This name can be specified by a constructor only Creates a new node within the current graph Optionally a variable Text is assigned to the new node If NodeType is supplied the new node will be of type NodeType and attributes can be initialized by a constructor Otherwise the node will be of the base node class type Node The GRSHELL can reassign variables This is in contrast to the rule language chapter 3 where we use names A EE Text een 42 GrShell Language Creates a new edge within the current graph between the specified nodes di
22. SLF ES gesses JE Edge gi 60 Edge 4 Edge S2E Edge l SSC Edgel S5DE does SF Edel 05 84 Edges 44 Edge I 2 FESGeL ge Scere SIB bet SE Edge Stiel 1 Figure 6 2 Koch snowflake 6 2 Busy Beaver 55 6 2 Busy Beaver We want GRGEN NET to work as hard as a busy beaver Kro07 Dew84 Our busy beaver is a Turing machine that has got five states plus a halt state it writes 1 471 bars onto the tape and terminates MB00 So first of all we design a Turing machine as graph model Besides this example shows that GRGEN NET is Turing complete We use the graph model and the rewrite rules to define a general Turing machine Our approach is to basically draw the machine as a graph The busy beaver logic is implemented by rule applications in GRSHELL 6 2 1 Graph Model Let s start the model file TuringModel gm with 1 model TuringModel The tape will be a chain of TapePosition nodes connected by right edges cell value is modeled by a reflexive value edge attached to a TapePosition node The leftmost and the rightmost cells TapePosition do not have an incoming and outgoing edge respectively Therefore we have the node constraint 0 1 node class TapePosition edge class right connect TapePosition 0 1 gt TapePosition 0 1 edge class value connect TapePosition 1 gt TapePosition 1 edge class zero extends value edge class one extends value edge class empty extends value
23. Universit t Karlsruhe TH Forschungsuniversitat gegrundet 1825 Fakultat fur Informatik Institut fur Programmstrukturen und Datenorganisation Lehrstuhl Prof Goos The GRGEN NET User Manual Refers to GRGEN NET Release 1 0 www grgen net Jakob Blomer Rubino Gei July 2 2007 Technical Report 2007 5 ISSN 1432 7864 11 ABSTRACT GRGEN NET is a graph rewrite tool enabling elegant and convenient development of graph rewriting applications with comparable performance to conventionally developed ones GR GEN NET uses attributed typed and directed multigraphs with multiple inheritance on node and edge types Extensive graphical debugging integrated into an interactive shell com plements the feature highlights of GRGEN NET This user manual contains both normative statements in the sense of a reference manual as well as an informal guide to the features and usage of GRGEN NET 111 1V FOREWORD First of all a word about the term graph rewriting Some would rather say graph trans formation some even think there is a difference between these two We don t see such differences and use graph rewriting for consistency The GRGEN project started in spring 2003 with the diploma thesis of Sebastian Hack under supervision of Rubino Gei At that time we needed a tool to find patterns in graph based intermediate representations used in compiler construction We imagined a tool that is fast expressive and eas
24. al NACs do not care about bindings within the outer scope Nevertheless if you use an identifier that is defined in the outer scope this specifies exactly the graph element the identifier is bound to in the outer scope 3 4 Replace Modify Part 25 We specify a node x with out degree of exactly 2 1 pattern I lt x Node gt negative SS ene Mica y N OO a FP W N Attribute Conditions The Java like attribute conditions keyword if in the pattern part allow for further restriction of the applicability of a rule Return values The return statement is only allowed for tests Otherwise the return statement belongs to the replace part See Section 3 4 Return Values Keep in mind that using type constraints or the typeof operator can be helpful See Sec tion 4 3 for further information 3 4 Replace Modify Part For the task of rewriting GRGEN NET provides two different modes A replace mode and a modify mode 3 4 1 Implicit Definition of the Preservation Morphism r Besides specifying the pattern a main task of a rule is to specify the transformation of a matched subgraph within the host graph The transformation specification defines the transition from the left hand side LHS to the right hand side RHS i e which graph elements of a match will be kept which of them will be deleted and which graph elements have to be newly created In theory this is done by defining the preservation morphism r In
25. ame on all such paths Connection Assertions To specify that certain edge types should only connect specific nodes we include con nection assertions Furthermore the number of outgoing and incoming edges can be constrained In this chapter as well as in chapter 5 GRSHELL we use excerpts of Example 1 the Map model for illustration purposes 2 1 Building Blocks The following syntax specifications make heavy use of syntax diagrams also known as rail diagrams Syntax diagrams provide a visualization of EBNF grammars Follow a path along the arrows through a diagram to get a valid sentence or subsentence of the language Ellipses represent terminals whereas rectangles represent non terminals For further information on syntax diagrams see MMJW91 Extended Backus Naur Form 10 Graph Model Language oO Aa Nn OD FP W N r The following toy example of a model of road maps gives a rough picture of the language model Map enum resident village 500 town 5000 city 50000 node class sight node class city size resident const node class metropolis extends city I river string abstract node class abandoned_city extends city node class ghost town extends abandoned city edge class street edge class trail extends street edge class highway extends street connect metropolis gt metropolis jam boolean Basic elements of the GRGEN NET graph model language are
26. and imple mentation of GRGEN NET as well as the writing of this manual Especially we want to thank Dr Sebastian Hack G Veit Batz Michael Beck Tom Gelhausen Moritz Kroll Dr Andreas Ludwig and Dr Markus Noga Finally all this would not happened without the productive atmosphere and the generous support that Prof Goos provides at his chair We wish all readers of the manual and especially all users of GRGEN NE T a pleasant graph rewrite experience We hope you enjoy using GRGEN NET as much as we enjoy de veloping 16 If you find that any statement in this manual needs improvement we encourage you to contact the maintainer of GRGEN NET rubinoGipd uni karlsruhe de Thank you for using GRGEN NET Karlsruhe in July 2007 the authors of GRGEN NET vi 1 2 3 4 5 CONTENTS Introduction t1 1 2 1 3 1 4 1 5 1 6 What is GRGEN NET Features of GRGEN NET System Overview What is Graph hele An Example The Tools 16 1 Grenene 2 5668 be eee ew ea Ne be Se hs REE Ewe Lo ME vaere EHS SER eG ES d EE NNN ere ee SEE Se a LME NE ee eR ee eee eee AAA Graph Model Language 2 1 PL Building Blocks Type Declarations Rule Set Language 3 1 3 2 3 3 3 4 Building Blocks Rules and Tests Pattern Part Replace Modify Part aa as 3 4 1 Implicit Definition of the een EV DE is ovas 3 4 2 Specification Modes for Graph Transformation EEE 0 cr rasos EE ee Types and Exp
27. ape of graphs e The pattern language supports Plain isomorphic subgraph matching injective mapping Homomorphic matching for a selectable set of nodes edges so that the matching is not injective Attribute conditions including arithmetic operations on the attributes Type conditions including powerful instanceof like type expressions 1 2 Introduction Parameter passing to rules Dynamic patterns with iterative or recursive paths and graphs yet to be imple mented e The rewrite language supports Attribute re calculation using arithmetic operations on the attributes Retyping of nodes edges a stronger version of casts known from common pro gramming languages Creation of new nodes edges of statically as well as dynamically computed types some kind of generic templates Two modes of specification A rule can either express changes to be made to the match or replace the whole match the semantics is always mapped to SPO Returning certain edges nodes for further computations Copying duplicating of elements form the match comparable with sesqui pushout rewriting CHHK06 yet to be implemented e The rule application language GRSHELL supports Composing several rules with logical and iterative sequence control called graph rewrite sequences GRS Various methods for creation deletion input output of graphs nodes edges Stepwise and graphic debug
28. are deleted from m L during rewrite Elements of R not in the image of r are inserted into H all others elements that are mapped by r are retained The outcome of these steps is the resulting graph H In symbolic language H gt HI 1 5 An Example We ll have a look at a small example Graph elements nodes and edges are labeled with and identifier If a type is necessary then it is stated after a colon We start using a special case to construct our host graph an empty pattern always produces exactly one match independent of the host graph So we construct an apple by applying po DER to the empty host graph s the result we get an apple as new host graph H Now we want to rewrite our apple with stem to an apple with a leaflet So we apply Nos Because of the uniqueness of the total and totally undefined morphism 1 6 The Tools 5 to H and get the new host graph Hj something like this What happened GRGEN NET has arbitrarily chosen one match out of the set of possible matches because x matches edge e3 as well as e correct solution could make use of edge type information We have to change rule po to generate the edge ej with a special type stem And this time we will even keep the stem So let mo A If we apply pa to the modified Hj this leads to 16 The Tools All the programs and libraries of GRGEN NET are licensed under LGPL Notice that the YCOMP graph viewer is not a part of
29. are specified or the direction in the type hierarchy is specified explicitly respectively Gets the attribute types and values of a specific graph element GraphElement AttributeName Gets the value of a specific attribute Gets the information whether the first element is type compatible to the second element 5 2 5 Graph Output Commands Dumps the current graph as GRSHELL script into Filename The created script includes e selecting the backend e creating all nodes and edges 44 GrShell Language e restoring the persistent names see Section 5 2 3 but not necessarily using the same commands you typed in during construction Such a script can be loaded and executed by the include command see Section 5 2 1 Filename Dumps the current graph as VCG formatted file into a temporary file Filename specifies an executable The temporary VCG file will be passed to Filename as last parameter Additional parameters such as program options can be specified by Text If you use YCOMP as executable this may look like yComp Version 1 3 1 tmpgraphO vcg File Edit View Navigate Layout Help Ran ICE spe HA A A D Find Next Options Root A 0 AB 102 AB 105 CA 108 AB 10B CA 10E CA 111 CA 114 CA 117 CA S11A CA 11D CA 120 CA 123 BC 126 BC 129 BC 12 CA 12C BC 12F BC 132 BC 135 AR The temporary file will be deleted when the application Filename is term
30. claration See Section 3 1 for a detailed explanation of names and graphlets The application of a rule is not deterministic remember the example of the introduction in Section 1 5 in particular there may be more than one subgraph that matches the pattern Whereas the GRSHELL selects one of them arbitrarily without further abilities to control the selection the underlying LIBGR provides a mechanism to deal with such ambiguities LIBGR allows for splitting a rule application into two steps Find all the subgraphs of the host graph that match the pattern and rewrite one of these matches By returning a collection of all matches the LIBGR retains the complete graph rewrite process under control s a LIBGR user use the following methods of the TAction interface IMatches Match IGraph graph int maxMatches IGraphElement parameters IGraphElement Modify IGraph graph IMatch match In C this might look like IMatches myMatches myAction Match myGraph 1 null 1 get all the matches for int i 0 i lt myMatches NumMatches i d if inspectCarefully myMatches GetMatch i myAction Modify myGraph myMatches GetMatch i break Also notice that graph rewrite sequences introduce a further variant of non determinism on rule application level The lt op gt flag marks the operator lt op gt as commutative i e the execution order of its operands rules is non deterministic See Section 5 2 6 for fu
31. default search plan is used For efficiency reasons it is recommended to do analyzing and search plan Make sure that the path to your yComp jar package is set correctly in the ycomp shell script within GRGEN NET s bin directory 50 GrShell Language We demonstrate the debug commands with a slightly adjusted script for the Koch snowflake from GRGEN NE T s examples see also Section 6 1 The graph rewriting sequence is 1 debug grs makeFlakel beautify doNothing makeFlake2 beautify 1 YCOMP will be opened with an initial graph resulting from grs init as 4 gt gel 3 S5 Edge1 ON 3 Edgel We type d etailed step to apply makeFlake1 step by step resulting in the following graphs SC Edge 3 Edgel 2 gt A Sn 9 Edge2 7 4 Edgel j 2 sAdgespe BONN 5 Edgel 9 Edge2 sine 7 CEdge2 3 Edge1 5 4 Edgel gt I B Edge2 The following table shows the break points of further debug commands entered one after another e makeFlakel beautify doNothing beautify beautify makeFlake2 5 3 LGSPBackend Custom Commands 51 creation during the rewriting procedure Therefore the host graph should be in a stage similar to the final result Indeed there might be some trial and error steps necessary to get an efficient search plan search plan is available as long as the current rule set remains loaded Specify multiple rewrite rules instead of using mu
32. ea Corradini Hartmut Ehrig Ugo Montanari Leila Ribeiro and Grzegorz Rozenberg editors Graph Transformations Third International Conference ICGT 2006 Natal Rio Grande do Norte Brazil September 17 23 2006 Pro ceedings volume 4178 of Lecture Notes in Computer Science Springer 2006 Andrea Corradini Tobias Heindel Frank Hermann and Barbara K nig Sesqui pushout rewriting In Corradini et al CEM 06 pages 30 45 A K Dewdney computer trap for the busy beaver the hardest working turing machine Scientic American 251 2 10 12 16 17 8 1984 Heiko D rr Efficient Graph Rewriting and its Implementation volume 922 of LNCS Springer Verlag New York Inc Secaucus NJ USA 1995 H Ehrig R Heckel M Korff M L we L Ribeiro A Wagner and A Corradini Algebraic Approaches to Graph Transformation Part II Single Pushout A and Comparison with Double Pushout A In Roz99 volume 1 pages 247 312 1999 Fujaba Developer Team Fujaba Homepage http www fujaba de 2007 Rubino Gei Gernot Veit Batz Daniel Grund Sebastian Hack and Adam Sza lkowski GrGen A Fast SPO Based Graph Rewriting Tool In Corradini et al CEM 06 pages 383 397 R Gei GRGEN NET http www grgen net June 2007 Sebastian Hack Graphersetzung f r Optimierungen in der Codeerzeugung Mas ter s thesis IPD Goos 12 2003 Moritz Kroll Michael Beck Rubino Gei Sebastian Hack and Philipp Leif yComp http www inf
33. ecks whether the edge e is not incident to x test r e Edge gt x Node pattern I negative I mer OG negative Re ze oO Aa N OD OD FP O N Hr al If x and e are undefined test r is equivalent to test s test s I pattern I x Node e Edge gt negative ze 0 negative x lt e oO oo ND a FF WwW N bb Rh e ka N e O In particular test s is successful if there is some edge in the host graph that is not incident LO X We extend SomeRule Example 4 with a user defined node to match and we want it to return the rewritten graph elements n5 and e1 rule SomeRuleExt varnode Node Node EdgeTypeB 1 pattern ni NodeTypeA replace varnode oO Aa ND Om SG O N Hr return n5 el eval Rh E A S We don not define varnode within the pattern part because this is already covered by the parameter specification itself 3 3 Pattern Part 23 3 3 Pattern Part Pattern PatternStatement pattern consists of zero or more pattern statements All the pattern statements must be fulfilled by a subgraph of the host graph in order to form a match An empty pattern always produces exactly one empty match This is caused by the uniqueness of the total and totally undefined function Names defined for graph elements may be used by other pattern statements as well as by replace modify statements Like all identifier definitions such names may be used before their de
34. ern part 3 2 Rules and Tests The structure of a rule set file is as follows RuleSet E Ce Oo T est Declaration a RuleDeclaration y A rule set consists of the underlying graph models and several rewrite rules In case of multiple graph models GRGEN NET uses the union of these models In this case beware of conflicting declarations There is no built in conflict resolution mechanism like packages or namespaces for models If necessary you can use prefixes as you might do in C TestDeclaration RetionSianatare KD D RuleDeclaration ale ActionSignature DL Pattern Replace MO Declares a single rewrite rule such as SomeRule It consists of a pattern part see Section 3 3 in conjunction with its rewrite modify part see Section 3 4 test has no rewrite specifi cation It s intended to check whether and maybe how many times a pattern occurs 20 Rule Set Language Some graphlets sledene FE EE EEE ek NOoder 22 ME gt Er E lt el stem ni Node e2 Edge gt e3 Edge gt e4 Edge gt eb Edge gt n l ni gt n2 Node nie fro And some illegal graphlets me ee NNN Would affect redirecting of edge e avse fr e ur Would affect redirecting of edge e x Node negative y Node hom x y Here x must not occur in the hom statement See Section 3 3 for further information lt gt There must be at least a node between the edges 3 2 Rules and Tests 21
35. ging of rule application Graph rewrite sequences that can contain nested transactions yet to be imple mented e Alternatively to GRSHELL you can access the match and rewrite facility through LIBGR In this way you can build your own algorithmic rule applications in a NET language of your choice 1 3 System Overview Figure 1 1 gives an overview of the GRGEN NET system components Table 1 1 shows the GRGEN NET directory structure call Graph Rewrite Applications gt l Es Script grs GRSHELL C Applications read generate LIBGR CH Frontend Compile Time Backend Run Time Graph Model gm Graph Model GRGEN NET er CF G t E Graph Man enerator gt er g Java C Hase l Rewrite gt Rewrite Rules Rules grg CH Figure 1 1 GRGEN NET system components Kro07 1 4 What is Graph Rewriting 3 Contains the NET assemblies in particular GrGen exe the graph rewrite sys tem generator lespBackend dll a GRGEN NET backend LibGr dll the backend APD and the shell GrShell exe lib Contains the GRGEN NET generated assemblies dll specs Contains the graph rewrite system source documents gm and grg Table 1 1 GRGEN NET directory structure A graph rewrite system is defined by a rule set file grg and zero or more graph model description files gm Such a graph rewrite system is generated from these spec
36. he parameters can be provided to the select backend command Executes the GRSHELL script Filename GRSHELL script is just a plain text file containing GRSHELL commands They are treated as they would be entered interactively except for parser errors If a parser error occurs execution of the script will stop immediately e Enables and disables the debug mode The debug mode shows the current working graph in a YCOMP window All changes to the working graph are tracked by YCOMP immediately Sets the default graph layout algorithm to Text If Text is omitted a list of available layout algorithms is displayed See Section 1 6 4 on YCOMP layouters Prints Text onto the GRSHELL command prompt D Cormmandline CommandLine is an arbitrary text the operating system attempts to execute On a Linux machine you might execute 1 sh c ls l grep stuff 5 2 2 Graph Commands CONCEDEN Creates a new graph with the model specified in Filename Its name is set to Text The model file can be either source code e g turing machineModel cs or a NET assembly e g lgsp turing machineModel d11 5 2 GRSHELL Commands 39 Opens the graph Text stored in the backend However the LGSPBackend doesn t support persistent graphs The LGSPBackend is the only backend so far Therefore this command is currently useless Displays a list of currently available graphs Selects the current working graph This graph acts as host gra
37. hism r 3 4 2 Specification Modes for Graph Transformation Replace mode The semantics of this mode is to delete every graph element of the pattern that is not used occur in the replace part keep every graph element that is used and create every additionally defined graph elements Using means that the name of a graph element occurs in a graphlet Attribute calculations are no using occurrences In Example 10 the nodes varnode and n3 will be kept The node n1 is replaced by the node n5 preserving n1 s edges The anonymous edge instance between n1 and n2 only occurs in the pattern and therefore gets deleted See Section 3 4 1 for a detailed explanation of the transformation semantics Modify mode The modify mode can be regarded as a replace part in replace mode where every pattern graph element is added occurs before the first replace statement In particular all the anonymous graph elements are kept Additionally this mode supports the delete operator that deletes every element given as an argument Deletion takes place after all other rewrite operations Multiple deletion of the same graph element is allowed but pointless as well as deletion of just created elements pointless too 3 4 3 Syntax Replace replace R modify eplaceStatement Selects whether the replace mode or the modify mode is used Several replace statements describe the transformation from the pattern subgraph to the destina
38. ibutes of graph elements can be re evaluated during an application of a rule The following rewrite rule mentioned in Gei et al GBG 06 gives a rough picture of the language 1 actions SomeActions using SomeModel 3 rule SomeRule 4 pattern I 5 ni NodeTypeA 6 n2 NodeTypeA 7 hom n1 n2 8 len f 9 n3 NodeTypeB 10 negative I 11 n3 el EdgeTypeA gt n1 12 if n3 a1 42 n2 a1 13 14 negative 15 n4 Node N NodeTypeB 16 n3 el EdgeTypeB gt n4 17 if typeof e1l gt EdgeTypeA 18 Le 19 20 replace I 21 nd NodeTypeC lt n1 gt 22 n3 el EdgeTypeB gt n5 23 eval 24 n5 a3 n3 al n1 a2 25 26 Ss In this chapter we use excerpts of Example 4 SomeRule for illustration purposes Omitting a graph meta model means that GRGEN NET uses a default graph model The default model consists of the base type Node for vertices and the base type Edge for edges 15 16 Rule Set Language 3 1 Building Blocks The GRGEN NET rule set language is case sensitive The language makes use of several identifier specializations in order to denominate all the GRGEN NET entities Ident IdentDecl A non empty character sequence of arbitrary length consisting of letters digits or under scores The first character must not be a digit Ident may be an identifier defined in a graph model see Section 2 1 Ident and IdentDecl differ in their role While IdentDecl is a defining occur
39. ifications by GrGen exe and can be used by applications such as GRSHELL Figure 1 2 shows the generation process referencing read generate gt rules1Model dll model3 gm backend dll model2 gm rulesl grg modell gm specs bin lib Figure 1 2 Generating a graph rewrite system In general you have to distinguish carefully between a graph model meta level a host graph a pattern graph and a rewrite rule In GRGEN NET pattern graphs are implicitly defined by rules i e each rule defines its pattern On the technical side specification docu ments for a graph rewrite system can be available as source documents for graph models and rule sets plain text gm and grg files or as their translated NET modules either C source files or their compiled assemblies dll Generating a GRGEN NE T graph rewrite system may be considered as preliminary task The actual process of rewriting as well as dealing with host graphs is performed by GR GEN NET s backend GRGEN NET provides a backend API the NET library LIBGR For most issues in particular for experimental purposes you might rather want to work with the GRSHELL because of its more convenient interface However GRSHELL does not provide the full power of the LIBGR see also note 6 on page 23 1 4 What is Graph Rewriting The notion of graph rewriting as understood by GRGEN NET is a method for declaratively specifying changes t
40. inated if GRSHELL is still running at this time camp Dumps the current graph in VCG format into the file Filename Visualization Styles The following commands control the style of the VCG output This affects dump graph show graph and enable debug See Section 1 6 4 5 2 GRSHELL Commands 45 dump node NodeType ED ME Sets the color text color border color or the shape of the nodes of type NodeType and all of its subtypes The keyword only excludes the subtypes The following shapes are supported box triangle circle ellipse rhom hexagon trapeze uptrapeze lparallelogram rparallelogram Those are shape names of YCOMP for a VCG definition see San95 Sets the color or text color of the edges of type Edge Type and all of its subtypes The keyword only excludes the subtypes Excludes nodes of type NodeType and all of its subtypes as well as their incident edges from output The keyword only excludes the subtypes i e subtypes of NodeType are dumped dunp add ode NodeType erow Declares NodeType and subtypes of NodeType as group node type All the differently typed nodes that point to a node of type Node Type i e there is a directed edge between such nodes will be grouped and visibly enclosed by the NodeType node The following example shows metropolis ungrouped and grouped Frankfurt metropolis A N N 2 Edge 1 Edge akten AS north highway ae E Lo p P
41. ing the present host graph into account The task of selecting a good search plan is then considered as an optimization problem BKG07 Bat06 For the rewrite step our tool implements the well founded single pushout approach SPO for explanation see EHK 99 For ease of use GRGEN features an expressive specification language and generates pro gram code with a convenient interface In contrast to systems like Fujaba Fuj07 our pattern matching algorithm is fully automatic and does not need to be tuned or partly be imple mented by hand GRGEN NET Got is the successor of the GRGEN tool presented at ICGT 2006 GBG 06 The NET postfix of the new name indicates that GRGEN has been reimplemented in C for the Microsoft NET or Mono environment Mic07 Tea07 1 2 Features of GRGEN NET The process of graph rewriting can be divided into four steps Representing a graph according to a model searching a pattern aka finding a match performing changes to the matched spot in the host graph and finally selecting the next rule s for application We have organized the features of GRGEN NET according to this breakdown of graph rewriting e The graph model meta model supports Directed graphs Typed nodes and edges with multiple inheritance on types Node and edge types can be equipped with typed attributes like structs Multigraphs including multiple edges of the same type Connection assertions to restrict the sh
42. ion 3 2 Parameters Use the debug option to trace the rewriting process step by step During execution YCompP will display every single step The debugger can be controlled by GRSHELL The debug commands are shown in Table 5 2 s tep Execute the next rewrite rule match and rewrite d etailed step Execute a rewrite rule in a three step procedure matching highlighting elements to be changed doing rewriting n ext Ascend one level up within the Kantorowitsch tree of the current rewrite sequence see Example 21 step o ut Continue a rewrite sequence until the end of the current loop If the execution is not in a loop at this moment the complete sequence will be executed r un Continue execution without further stops a bort Cancel the execution immediately Table 5 2 GRSHELL debug commands 5 3 LGSPBackend Custom Commands The LGSPBackend supports the following custom commands 5 3 1 Graph Related Commands Analyzes the current working graph The analysis data provides vital information for efficient search plans Analysis data is available as long as GRSHELL is running i e when the working graph changes the analysis data is still available but maybe obsolete 5 3 2 Action Related Commands custom actions gen_searchplan i Action y Creates a search plan for each rewrite rule Action using a heuristic method and the analyzes data if the graph has been analyzed by custom graph analyze graph Otherwise a
43. it nicely We execute the Sierpinski script by GrShell exe test Sierpinski grs or mono GrShell exe test Sierpinski grs respectively Because both of the scripts are using the debug mode we complete execution by typing r un See Section 5 2 6 for further information The resulting graphs should look like Figures 6 1 and 6 2 Be careful The running time increases exponentially in the number of iterations 53 54 Examples yComp Version 1 3 1 File Edit View Navigate Layout Help DanS IC ADAL ATH D Fie Ra ms ei A pm dy Ban AS i A weit gt A 3 st EI N ar A A pa S ae ATM Fu ple Find H Root 0 B 102 CA 103 AB gt 104 BC 10E CA 10F AB 110 BC I 11A CA 11B AB I 11C BC 126 CA 127 AB 128 BC PY 12 CA 132 CA _ 133 AB 134 BC 13 AB 13E CA 13F AB OOO Calo en Figure 6 1 Sierpinski triangle yComp Version 1 3 1 File Edit View Navigate Layout Help Rana e XE Root gt 0 Node1 10 Node gt 16 Nodel 17 Node gt 18 Node 1 Nodel 21 Nodel 22 Node 23 Node 29 Nodel 2 Nodel 2A Node gt 2B Node gt 31 Nodel gt 32 Node gt 33 Node gt 39 Nodel 3A Node _ 3B Node 41 Nodel PUT a 89254 lt gt athe pd n STE Edge 50 Edge LC Edge I den Speer STO t e oe S4C Edgel SHE Edge IAEA gigas 20 EdgeSce SSE Edge 6 HAZ hipo
44. l Table 4 3 Compare operators on type expressions A lt B corresponds to the direction of the arrow in an UML class diagram 4 2 Expressions 31 Logical XOR True iff either the first or the second Boolean expression is true a Logical AND and OR Lazy evaluation Logical AND and OR Strict evaluation Table 4 4 Binary Boolean operators in ascending order of precedence IntExpr PrimaryExpr i BoolExpr Sr IntExpr KS Int Expr H IntExpr gt BinIntOperator gt IntExpr The operator is the bitwise complement That means every bit of an integer value will be flipped The operator is a simple if then else If the BoolExpr is evaluated to true the op erator returns the first IntExpr otherwise it returns the second ntExpr The BinIntOperator is one of the operators in Table 4 5 Bitwise shift left bitwise shift right and bitwise shift right preserving the sign Table 4 5 Binary integer operators in ascending order of precedence FloatExpr PrimaryExpr FloatExpr BinFloatOperator FloatExpr FloatExpr 32 Types and Expressions The operator is a simple if then else If the BoolEzpr is evaluated to true the operator returns the first FloatExpr otherwise it returns the second FloatExpr The BinFloatOperator is one of the operators in Table 4 6 E Addition and subtraction Multiplication division and modulo Table 4 6 Binary float
45. looks like this SC 0 SC empty gt sC_0 SC 0 moveLeft gt sA SC 1 SC one gt sC_1 sC_1 moveRight gt sB sD 0 sD empty gt sD 0 sD 0 moveLeft gt sE sD 1 sD one gt sD 1 sD 1 moveLeft gt sH sE 0 sE empty gt sE 0 sE 0 moveRight gt sC sk 1 sE one gt sE 1 sE 1 moveLeft gt sC sB 0 moveRight gt sC sB 1 WriteEmpty sB one gt sB 1 sB 1 moveRight gt sE WriteEmpty WriteEmpty WriteOne WriteOne WriteOne WriteOne 16 moveLeft EE 1 RWHead 6 0ne Astate lt 3 empty D move Left 10 move Right 7 moveLeft A moveRight 12 empty 18 move Left 18 empty 13 moveLeft C empty 19 move Left 99 We have an initial host graph now The graph rewrite sequence is quite straight forward and generic to the Turing graph model One 99 selection is unambiguous Note that for each state the Empty 60 Examples grs readOneRule readEmptyRule writeDneRule writeEmptyRule ensureMoveLeftValidRule ensureMoveRightValidRule moveLeftRule moveRightRule 32 We interrupt the machine after 32 iterations and look at the result so far In order to improve the performance we generate better search plans This is a crucial step for execution time With the initial search plans the beaver runs for 1 minute and 30 seconds With improved search plans after the first 32 ste
46. ltiple commands for each rule to improve the search plan generation performance custom actions set max matches Number Sets the maximum amount of possible pattern matches to Number This command affects the expression Rule If Number is less or equal to zero the constraint is reset 92 GrShell Language CHAPTER 6 EXAMPLES 6 1 Fractals The GRGEN NET package ships with samples for fractal generation We will construct the Sierpinski triangle and the Koch snowflake They are created by consecutive rule applications starting with the initial host graphs BR 3 E0 N N 1 E0 5 E0 4 Edge Ki Ze d f d ss tweet D for the Sierpinski triangle resp the Koch snowflake First of all we have to compile the model and rule set files So execute in GRGEN NE T s bin directory GrGen exe specs sierpinski grg GrGen exe specs snowflake grg or mono GrGen exe specs sierpinski grg mono GrGen exe specs snowflake grg respectively If you are on a Unix like system you have to adjust the path separators of the GRSHELL scripts Just edit the first three lines of test Sierpinski grs and test Snowflake grs And as we have the file Sierpinski grs already opened we can increase the number of iterations to get even more beautiful graphs Just follow the com ments Be careful when increasing the number of iterations of Koch s snowflake YCOMP s layout algorithm might need some time and attempts to layout
47. ngs to GRGEN NET s standard equipment GRSHELL is capable of creating manipulating and dumping graphs as well as performing and debugging graph rewriting The GRSHELL provides a line oriented scripting language GRSHELL scripts are structured by simple statements separated by line breaks 5 1 Building Blocks GRSHELL is case sensitive comment starts with a and is terminated by end of line or end of file Any text left of the will be treated as a statement The following items are required for representing text numbers and rule parameters Text May be one of the following e non empty character sequence consisting of letters digits and underscores The first character must not be a digit e Arbitrary text enclosed by double quotes e Arbitrary text enclosed by single quotes Number Is an int or float constant in decimal notation see also Section 4 1 Parameters rd SpacedParameters A In order to describe the commands more precisely the following semantic specializations of Text are defined Filename A fully qualified file name without spaces e g Users Bob amazing file txt or a single quoted or double quoted fully qualified file name that may contain spaces Users Bob amazing file txt 30 36 GrShell Language Variable Identifier of a variable that contains a graph element Node Type Edge Type Identifier of a node type resp edge type defined in the model of the current
48. o a graph This is comparable to the well known term rewriting Normally you use one or more graph rewrite rules to accomplish a certain task GRGEN NET implements an SPO based approach In the simplest case such a graph rewrite rule consists of a tuple L R whereas L the left hand side of the rule is called pattern graph and R the right hand side of the rule is the replacement graph Moreover we need to identify graph elements nodes or edges of L and R for preserving them during rewrite This is done by a preservation morphism r mapping elements from L In this context system is not a CHO like grammar rewrite system but rather a set of interacting software components 4 Introduction Pattern Graph Rewrite Graph Preservation Morphism r e HA M Rul Match m H gt Hi Host Graph Result Graph Figure 1 3 Basic Idea of Graph Rewriting to R the morphism r is injective but needs to be neither surjective nor total Together with a rule name p we have p L gt R The transformation is done by application of a rule to a host graph H To do so we have to find an occurrence of the pattern graph in the host graph Mathematically speaking such a match m is an isomorphism from L to a subgraph of H This morphism may not be unique i e there may be several matches Afterwards we change the matched spot m L of the host graph such that it becomes an isomorphic subgraph of the replacement graph R Elements of L not mapped by r
49. o uni karlsruhe de software php id 6 2007 61 62 Om Kro07 MB00 Mic07 MMJW91 Roz99 SATT 90 San95 Sza05 Tea07 VVE06 ly Wo07 Examples Moritz Kroll and Rubino Gei Developing Graph Transformations with Gr Gen NET In Applications of Graph Transformation with Industrial rele VancE AGTIVE 2007 2007 preliminary version submitted to AGTIVE 2007 Moritz Kroll GrGen NET Portierung und Erweiterung des Graphersetzungssys tems GrGen 5 2007 Studienarbeit Universitat Karlsruhe H Marxen and J Buntrock Old list of record TMs http www drb insel de heiner BB index html 8 2000 Microsoft NET http msdn2 microsoft com de de netframework aa497336 aspx 2007 Andrew B Mickel James F Miner Kathleen Jensen and Niklaus Wirth Pascal user manual and report 4th ed ISO Pascal standard Springer Verlag New York Inc New York NY USA 1991 G Rozenberg editor Handbook of Graph Grammars and Computing by Graph Transformation World Scientific 1999 Herbert Schildt American National Standards Institute International Organiza tion for Standardization International Electrotechnical Commission and ISO IEC JTC 1 The annotated ANSI UC standard American National Standard for Programming Languages C ANSI ISO 9899 1990 1990 Georg Sander VCG visualization of compiler graphs user documentation v 1 30 Technical report Universit t des Saarlandes 1995
50. ontains an anonymous edge thus can be understood as ni 1 Edge gt n2 Names must not be redefined once defined a name is bound to a graph element We use the term binding of names because a name not only denotes a graph element of a graphlet but also denotes the mapping of the abstract graph element of a graphlet to a concrete graph element of a host graph So graph elements of different names are pair wise distinct except for homomorphically matched graph 3 1 Building Blocks 17 elements see Section 3 3 For instance v NodeTypel e EdgeType gt w NodeType2 selects some node of type NodeType1 that is connected to a node of type NodeType1 by an edge of type EdgeType and binds the names v w and e If v and w are not explicitly marked as homomorphic the graph elements they bind to are distinct Binding of names allows for splitting a single graphlet into multiple graphlets as well as defining cyclic structures The following graphlet n1 n2 and n3 are defined somewhere else Haa gt as nl is equivalent to 4022 148 Da 2 alas saul e and ni gt n3 is equivalent to n3 lt n1 of course The visibility of names is determined by scopes Scopes can be nested Names of surrounding scopes are visible in inner scopes Usually a scope is defined by and In contrast to pure syntactic scoping the replace modify part is a direct inner scope of the pattern part In Example 4 lines 14 to 18
51. pe constraint is used to exclude parts of the type hierarchy The operator is used to create a union of its operand types So the following pattern statements are identical SS ES x T T1 e Tn if typeof x lt T1 amp amp amp amp typeof x lt Tn 34 Types and Expressions The expression TN T2 T3 applied to the type hierarchy on the left side yields only the types T and T1 as valid 4 4 Annotations Identifier definitions can be annotated by pragmas Annotations are key value pairs IdentDecl Although you can use any key value pairs between the brackets only the identifier has an effect so far Key Value Type Applies to Meaning node edge Changes the ranking of a graph element for search plans The default is prio 1000 Graph elements with high values are likely to appear prior to graph elements with low values in search plans Table 4 7 Annotations We search the pattern v NodeTypeA e EdgeType gt w NodeTypeB We have a host graph with about 100 nodes of NodeTypeA 1 000 nodes of NodeTypeB and 10 000 edges of EdgeType Furthermore we know that between each pair of NodeTypeA and NodeTypeB there exists at most one edge of EdgeType GRGEN NET can use this information to improve the initial search plan if we adjust the pattern like v prio 10000 NodeTypeA e prio 5000 EdgeType gt w NodeTypeB CHAPTER 5 GRSHELL LANGUAGE GRSHELL is a shell application of LIBGR It belo
52. ph for graph rewrite sequences see also Sections 1 4 and 5 2 6 Though you can define multiple graphs only one graph can be the active working graph Deletes all graph elements of the current working graph resp the graph Graph Deletes the graph Graph from the backend storage q Validates if the current working graph fulfills the connection assertions specified in the cor responding graph model The strict mode additionally requires all the edges of the working graph to be specified in order to get a valid Otherwise edges between nodes without spec ified constraints are ignored 40 GrShell Language We reuse a simplified version of the road map model from chapter 2 model Map node class city node class metropolis edge class street edge class highway connect metropolis gt metropolis 0 ND AQ N PE The node constraint on highway requires all the metropolises to be connected by highways Now have a look at the following graph A3 highway AN South highway AS north highway trail street This graph is valid but not strict valid gt validate The graph is valid gt validate strict The graph is NOT valid CAE city Eppstein highway A3 gt metropolis Frankfurt not specified CAE metropolis Karlsruhe street trail gt metropolis Frankfurt not specified gt RA ee AA N BB Executes a command specific to the current backend If Spaced
53. ps he takes about 8 5 seconds 64 custom graph analyze graph 65 custom actions gen searchplan readOneRule readEmptyRule writeQneRule writeEmptyRule ensureMoveLeftValidRule ensureMoveRightValidRule moveLeftRule moveRightRule Let the beaver run grs readOneRule readEmptyRule writeDneRule writeEmptyRule ensureMoveLeftValidRule ensureMoveRightValidRule moveLeftRule moveRightRule On a Pentium 4 3 2Ghz with 2GiB RAM Ass00 Bat05a Bat05b Bat06 IBKGO7 CEM 06 ICHHKO6 Dew84 D r95 EHKt 99 Fuj07 GBG 06 Gei07 Hac03 IKBG 07 BIBLIOGRAPHY Uwe Assmann Graph rewrite systems for program optimization ACM Transac tions on Programming Languages and Systems TOPLAS 22 4 583 637 2000 Gernot Veit Batz Graphersetzung fur eine Zwischendarstellung im Ubersetzer bau Master s thesis Universitat Karlsruhe 2005 Veit Batz Generierung von Graphersetzungen mit programmierbarem Suchal gorithmus Studienarbeit 2005 Gernot Veit Batz An Optimization Technique for Subgraph Matching Strategies Technical Report 2006 7 Universit t Karlsruhe Fakult t f r Informatik April 2006 Gernot Veit Batz Moritz Kroll and Rubino Gei A First Experimental Evalu ation of Search Plan Driven Graph Pattern Matching In Applications of Graph Transformation with Industrial releVancE AGTIVE 2007 2007 preliminary version submitted to AGTIVE 2007 Andr
54. rected towards the second Node Optionally a variable Text is assigned to the new edge If Edge Type is supplied the new edge will be of type EdgeType and attributes can be initialized by a constructor Otherwise the edge will be of the base edge class type Edge Number Set the attribute AttributeName of the graph element GraphElement to the value of Text or Number Deletes the node Node from the current graph Incident edges will be deleted as well Deletes the edge Edge from the current graph 5 2 4 Graph Query Commands Gets the persistent names and the types of all the nodes edges of the current graph If a node type or edge type is supplied only elements compatible to this type are considered T he only keyword excludes subtypes Nodes edges without persistent names are shown with a pseudo name If the command is specified with num only the number of nodes edges will be displayed sub super 7 sub 5 2 GRSHELL Commands 43 Gets the inherited descendant types of NodeType Edge Type U e lJ NodeType attributes Gets the available node edge attribute types If Node Type Edge Type is supplied only at tributes defined in Node Type Edge Type are diplayed The only keyword excludes inherited attributes The show nodes edges attributes command covers types and inherited types This is in contrast to the other show commands where types and subtypes
55. rence of an identifier Ident is a using occurrence An IdentDecl non terminal can be annotated See Section 4 4 for annotations of declarations As in the GRGEN NET model language see note 2 every declaration is also a definition Using an identifier before defining it is allowed Every used identifier has to be defined exactly ONCE Modelldent Typeldent NodeType Edge Type These are semantic specializations of Ident Typeldent matches every type identifier i e a node type an edge type an enumeration type or a primitive type All the type identifiers are actually type expressions See Section 4 3 for the use of type expressions Graphlet GraphletNode Ven Continuation graphlet specifies a connected subgraph GRGEN NET provides graphlets as a descriptive notation to define both patterns to search for as well as the subgraphs that replace or modify matched spots in a host graph Any graph can be specified piecewise by a set of graphlets In Example 4 line 8 the statement n1 gt n2 is the node identifier n1 followed by the continuation graphlet gt n2 All the graph elements of a graphlet have names The name is either user assigned or a unique internal non accessible name In the second case the graph element is called anony mous For illustration purposes we use a lt number gt notation to denote anonymous graph elements in this document For example the graphlet ni gt n2 c
56. ressions 4 1 4 2 4 3 4 4 Built In Types Expressions Type Related Fe Annotations GrShell Language 9 1 9 2 5 3 Building Blocks GRSHELL Commands Beak Common COMANDOS gt i s kw eee paea ar en D MN oos eee he bl 9 2 3 Graph Manipulation Commande 5 2 4 Graph Query Commands 2 2 CK om nn Dow raph Output Commands sais sss pee kes eR a nd 5 2 6 Action Commands CR LGSPBackend Custom Commands 5 3 1 Graph Related Commands noaoo a m Emm nen Vil O O O ook UNE e o 15 16 19 23 20 20 26 26 29 29 30 39 34 35 39 37 37 38 40 42 43 46 49 viii 5 3 2 Action Related Commande Examples 6 1 Fractals 6 2 Busy Beaver CaL EEN NIOU wee ce eee eee eae ee eee es as Dene SO ee a a ee eS Ghee he eee FE Rew ee we eee nenn 6 2 3 Rule Execution with GRbanpLt a G Bibliography Index 53 93 55 313 55 58 61 03 CHAPTER 1 INTRODUCTION 1 1 What is GRGEN NET GRGEN Graph Rewrite GENerator is a generative programming system for graph rewrit ing For the potentially expensive matching problem GRGEN applies several novel heuristic optimizations According to Varr s benchmark it is at least one order of magnitude faster than any other tool known to us In order to accelerate the matching step we internally introduce search plans to represent different matching strategies and equip these search plans with a cost model tak
57. rkedGridh 11F GridNode 11F GridNode Se 122 GridNode 122 GridNode y rei la EN 125 GridNode 125 GridNode 128 MarkedGridN 128 MarkedGridN eleng LE LE EE a 12B MarkedGridN 12B MarkedGridN 12E MarkedGridN 4 12E MarkedGridN EE 132 MarkedGridh Y 132 MarkedGridh gt gt Requires Java Runtime Environment 1 5 or above Introduction CHAPTER 2 GRAPH MODEL LANGUAGE The key features of GRGEN NET graph models as described by Gei et al GBG 06 KGO7 are given below Types Nodes and edges are typed This is similar to classes in common programming lan guages except for the concept of methods that GRGEN NET nodes and edges don t support Attributes Nodes and edges can possess attributes The set of attributes assigned to a node or edge is determined by its type The attributes themselves are typed too Inheritance Node and edge types classes can be composed by multiple inheritance Node and Edge are built in root types of node and edge types respectively Inheritance eases the specification of attributes because subtypes inherit the attributes of their super types Note that GRGEN NET lacks a concept of overwriting On a path in the type hierarchy graph from a type up to the built in root type there must be exactly one declaration for each attribute identifier Furthermore if multiple paths from a type up to the built in root type exist the declaring types for an attribute identifier must be the s
58. rt 5 2 GRSHELL Commands 37 Persistent names belong to a specific graph whereas variables belong to the current GRSHELL environment Persistent names will be saved save graph see Section 5 2 5 and if you visualize a graph dump graph see Section 5 2 5 graph elements will be labeled with their persistent names Persistent names have to be unique for a graph GraphElement Assigns the variable or persistent name GraphElement to Variable If Variable has not been defined yet it will be defined implicitly As usual for scripting languages variables have neither static types nor declarations 52 GRSHELL Commands This section describes the GRSHELL commands Commands are assembled from basic ele ments As stated before commands are terminated by line breaks Alternatively commands can be terminated by the symbol Script lt end of file gt 5 2 1 Common Commands Displays an information message describing supported commands Quits GRSHELL If GRSHELL is opened in debug mode currently active graph viewers such as YCOMP will be closed as well Filename Parameters Selects a backend that handles graph and rule representation Filename has to be a NET assembly e g 1IgspBackend d11 Comma separated parameters can be supplied optionally If so the backend must support these parameters 38 GrShell Language List all the parameters supported by the currently selected backend T
59. rther information on graph rewrite sequences 24 Rule Set Language PatternStatement hon 9050 The semantics of the various pattern statements are given below Graphlet Graphlets specify connected subgraphs See Section 3 1 for a detailed explanation of eraphlets Isomorphic Homomorphic Matching The hom operator specifies the nodes or edges that may be matched homomorphically In contrast to the default isomorphic matching the specified graph elements may be mapped to the same graph element in the host graph Note that the graph elements must have a common subtype Several homomorphically matched graph elements will be mapped to a graph element of a common subtype In Example 4 nodes n1 and n2 may be the same node This is possible because they are of the same type NodeTypeA name may not occur in multiple hom statements For instance it is illegal to write hom a b hom b c Instead write hom a b c Inside a NAC the hom operator may only operate on graph elements that are either defined or used in the NAC Negative Application Conditions NACs With negative application conditions keyword negative we can specify graph patterns which forbid the application of a rule if any of them is present in the host graph cf Sza05 NACs must not be nested NACs possess a scope of their own Names defined within a NAC do not exist outside the NAC Identifiers from surrounding scopes must not be redefined In gener
60. s capable of creating manip ulating and dumping graphs as well as performing graph rewriting with graphical debug support For further information about the GRSHELL language see chapter 5 Usage mono grShell exe c lt commands gt lt grshell script gt Opens the interactive shell The GRSHELL will execute the commands in grshell script usually a grs file immediately Options c Execute the quoted GRSHELL commands immediately Instead of a line break use a double semicolon to separate commands Requires NET 2 0 or above or Mono 1 2 2 or above 1 6 3 LibGr dll The LIBGR is a NET assembly implementing GRGEN NET s API See the extracted HTML documentation for interface descriptions 1 6 4 yComp jar YComP KBG 07 is a graph visualization tool based on YFILES yWo07 It is well integrated in GRGEN NET but it s not a part of GRGEN NET YCOMP implements several graph layout algorithms and has file format support for VCG GML and YGF among others 3n is an increasing number 1 6 The Tools T Usage Usually YCOMP will be loaded by the GRSHELL You might want to open YCOMP manually by typing java jar yComp jar lt graph file gt The graph file may be any graph file in a supported format YCOMP will open this file on startup Hints Do not use the compiler graph layout algorithm yCOMP s default setting Instead Organic or Orthogonal might be good choices Use the rightmost blue play button to start
61. tate before s amp t is performed lt op gt Flag the operator lt op gt as commutative Usually operands are ex ecuted evaluated from left to right with respect to bracketing left associative But the sequences s t u in s lt op gt t lt op gt u are executed evaluated in arbitrary order S Execute s repeatedly as long as its execution does not fail s n Execute s repeatedly as long as its execution does not fail but n times at most Dump found matches into VCG formatted files for a VCG definition see San95 Every match produces three files within the current directory 1 The complete graph that has the matched graph elements marked 2 The complete graph with additional information about match ing details 3 A subgraph containing only the matched graph elements Rule Rewrite the first found pattern match produced by the action Rule Rule Rewrite every pattern match produced by the action Rule Note This operator is mainly added for benchmark purposes Its semantics is not equal to Rule Instead this operator collects all the matches first before starting rewritings In particular one needs to avoid delet ing a graph element that is bound by another match V W Assign the variable w to v If w is undefined v will be undefined too x Assign the graph element identified by x to the variable v If x is not defined v will be undefined too def Parameters Is successful if all the graph elements in
62. the negative condition uses n3 from the surrounding scope and defines n4 and e1 We may safely reuse the variable name e1 in the replace part GraphletNode Specifies a node of type NodeType with respect to TypeConstraint see Section 4 3 Type Constraint Type constraints are allowed in the pattern part only The is an anonymous node of the base type Node Remember that every node type has Node as super type The lt gt operator retypes a node Retyping is allowed in the replace modify part only see Section 3 4 Retyping Graphlet Meaning x NodeType The name x is bound to a node of type NodeType or one of its subtypes NodeType 1 NodeType E 1 Node X The node x is bound to 18 Rule Set Language GraphletEdge enee GRITO Specifies an edge Anonymous edges are specified by gt or lt resp T gt or lt T for an edge type T For a more detailed specification you can use the inplace notated EdgeRe finement clause Type constraints are allowed in the pattern part only see Section 4 3 TypeConstraint The lt gt operator retypes an edge Retyping is allowed in the replace mod ify part only see Section 3 4 Retyping Graphlet Meaning e EdgeType gt The name e is bound to an edge of type EdgeType or one of its subtypes EdgeType gt 1 EdgeType gt gt 1 Edge gt gt The edge e is bound to As the above table shows edges can be defined and used separately
63. tion subgraph 3 4 Replace Modify Part D How might Example 10 look in modify mode We have to denominate the anonymous edge between n1 and n2 in order to delete it The node varnode should be kept and does not need to appear in the modify part So we have 1 rule SomeRuleExtModify varnode Node Node EdgeTypeB pattern I ni e0 Edge gt n2 modify 1 no NodeTypeC lt n1 gt n3 el EdgeTypeB gt n5 delete e0 eval oO a N OD OD A W N Rh pap H fF CH ReplaceStatement The semantics of the various pattern statements are given below Graphlet Analogous to a pattern graphlet a specification of a connected subgraph Its graph elements are either kept because they are elements of the pattern or added otherwise Names defined in the pattern part must not be redefined in the replace graphlet See Section 3 1 for a detailed explanation of graphlets Deletion The delete operator is only available in the modify mode It deletes the specified pattern graph elements Multiple occurrences of delete statements are allowed Dele tion statements are executed after all other replace statements Multiple deletion of the same graph element is allowed but pointless as well as deletion of just created elements pointless too Attribute Evaluation If a rule is applied then the attributes of matched and inserted graph elements will be recalculated according to the eval statements 28 Rule Set Language Re
64. trategies 1 modify mode 26 multiplicity see connection assertion NAC see negative application condition name 16 25 41 negative application condition 24 Node 12 node graphlet 17 node type 12 non determinism 23 order of precedence 31 32 49 Organic see layout algorithm Orthogonal see layout algorithm parameter 21 37 49 pattern 23 pattern graph 3 16 persistent graph 39 persistent name 36 41 42 pragma see annotation 65 precedence see order of precedence preservation 26 preservation morphism 3 25 primitive types 29 rail diagram 9 re evaluation see attribute evaluation redefine 16 redirecting 18 replace mode 26 replacement graph 3 16 25 return type 21 return value 25 28 retyping 17 18 28 rewrite rule 2 19 RHS see right hand side right hand side 3 25 rule application see application rule set 15 19 46 rule set language 15 scope 17 24 script see graph rewrite script search plan 21 34 49 60 search plans 1 sesqui pushout 2 shell see GrShell Sierpinski triangle 53 signature 21 single pushout approach 1 18 26 SPO see single pushout approach spot 4 16 string 29 syntax diagram see rail diagram test 19 22 transaction nested 2 transformation specification 25 Turing complete 55 type cast see retyping 29 type constraint 18 33 type contraint 17 type expression 16 30 33 type hierarchy 9 2
65. turn Values Graph elements of the replace modify part can be returned according to the return types in the signature see Section 3 2 ActionSignature The return statement must not occur multiple times The graph element names have to be in the same order as the corresponding return types in the signature The named elements must be compatible to the declared type Retyping Retyping enables us to keep all adjacent nodes and all attributes stemming from com mon super types of a graph element while changing its type Retyping differs from a type cast During replacement both of the graph elements are alive Specifically both of them are available for evaluation Furthermore the source and destination types need not to be on a path in the directed type hierarchy graph rather their relation can be arbitrary The edge specification as well as ReplaceNode supports retyping In Example 4 node n5 is a retyped node stemming from node n1 Assignment en JO Mera Expresion Several evaluation parts are allowed within the replace part Multiple evaluation statements will be internally concatenated preserving their order Evaluation statements have impera tive semantics In particular GRGEN NET does not care about data dependencies Eval uation takes place before any graph element gets deleted and after all the new elements have been created You may read and write although this is pointless attributes of graph elements to be deleted
66. ty gt tp 58 59 61 rule moveLeftRule 62 pattern 63 wv WriteValue moveLeft gt s State 64 wv h RWHead gt tp TapePosition lt r right ltp TapePosition 65 Le 66 modify 1 67 delete h 68 s RWHead gt ltp 69 70 I 72 rule moveRightRule 73 pattern I 74 wv WriteValue moveRight gt s State 75 wv h RWHead gt tp TapePosition r right gt rtp TapePosition 76 77 modify 78 delete h 79 s RWHead gt rtp 80 Le 81 83 rule dontMoveRule 4 84 pattern 85 wv WriteValue dontMove gt s State 86 wv h RWHead gt tp TapePosition 87 88 modify 1 89 delete h 90 s RWHead gt tp 91 92 94 rule ensureMoveLeftValidRule 95 pattern 96 wv WriteValue moveLeft gt State 97 wv RWHead gt tp TapePosition 98 negative 99 tp lt right 100 101 102 modify 1 tp lt right ltp TapePosition empty gt ltp 58 Examples 105 107 rule ensureMoveRightValidRule 108 pattern I 109 wv WriteValue moveRight gt State 110 wv RWHead gt tp TapePosition 111 negative I 112 tp right gt 113 114 115 modify I 116 tp right gt rtp TapePosition empty gt rtp 117 Le Have a look at the negative conditions within the ensureMove rules They ensure that the current cell is indeed at the end of the tape An edge to a right left neighboring cell must not exist Now don t forget to compile
67. y to integrate into our compiler infrastructure So far Optimix was the only tool that brought together the areas of compiler construction and graph rewrit ing Ass00 However its approach is to feature many provable properties of the system per se such as termination confluence of derivations and complete coverage of graphs This is achieved by restricting the expressiveness of the whole formalism below Turing completeness Our tool GRGEN in contrast should be Turing complete Thus GRGEN NET provides the user with strong expressiveness but leaves the task of proving such properties to the user To get an prototype quickly we delegated the costly task of subgraph matching to a relational database system Hac03 Albeit the performance of this implementation could be improved substantially over the years we believed that there was more to come Inspired by the PhD thesis of Heiko D rr D r95 we reimplemented our tool to use search plan driven graph pattern matching of its own This matching algorithm evolved over time Sza05 Bat05b Bat05a Bat06 BKG07 and has been ported from C to C KG07 Kro07 In the year 2005 Varr VVF06 independently proposed a similar search plan based approach Though we started four years ago to facilitate some compiler construction problems in the meantime GRGEN NET has grown into a general purpose tool for graph rewriting We want to thank all co workers and students that helped during the design
68. your model and the rule set with GrGen exe see Section 6 1 6 2 3 Rule Execution with GRSHELL Finally we construct the busy beaver and let it work with GRSHELL The following script starts with building the Turing machine that is modeling the six states with their transitions in our Turing machine model select backend bin lgspBackend d11 new graph lib lgsp TuringModel dll Busy Beaver select actions lib lgsp TuringActions d11 Initialize tape new tp TapePosition Startposition new tp empty gt tp o a JO vo A U WD States new sA State A new sB State B new sC State C new sD State D new sE State E new sH State Halt Rh e e pa pao pa psp N On 8 FP W N e O new sA RWHead gt tp GA ka o Transitions three lines per state and input symbol for updating cell value moving read write head respectively N N Rh O 2 N 23 24 new S 0 WriteDne 25 new S empty gt sA_O 26 new S 0 moveLeft gt sB 27 28 new S 1 WriteDne 29 new S one gt sA_1 30 new sA_1 moveLeft gt sD 31 32 new SB 0 WriteDne 33 new SB empty gt sB 0 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 6 2 Busy Beaver new new new new new new new new new new new new new new new new new new new new new new Our busy beaver
69. ype 43 typeof 33 using 19 validate 13 39 Non Terminals ActionSignature 21 Assignment 28 AttributeDeclarations 14 Attribute Type 14 Attributes 41 BoolExpr 30 ClassDeclaration 11 ConnectAssertions 13 Constant 32 Constructor 41 Continuation 16 EdgeClass 12 EdgeRefinement 18 EnumDeclaration 11 63 64 Expression 30 FloatExpr 31 GraphElement 36 GraphModel 11 GraphRewriteSequence 48 Graphlet 16 GraphletEdge 18 GraphletNode 17 IdentDecl 34 IntExpr 31 NodeClass 12 NodeConstraint 13 Parameters 21 35 Pattern 23 PatternStatement 24 PrimaryExpr 32 RangeConstraint 13 Replace 26 ReplaceStatement 27 Return Types 21 RuleDeclaration 19 RuleSet 19 Script 37 SimpleRewriteSequence 48 Simple Term 48 SpacedParameters 35 StringExpr 32 TestDeclaration 19 TypeConstraint 33 TypeDeclaration 11 TypeExpr 33 General Index gm 2 erg 2 6 ers 2 6 1 38 47 47 EE e T O 36 35 lt number gt 16 lt op gt 23 47 41 Pe Ys amp 47 action see graph rewrite sequence action command 46 analyzing graph 49 annotation 10 16 34 Examples anonymous 16 26 36 API 3 6 application 4 23 associative 47 attribute 14 41 43 46 attribute condition 25 attribute evaluation 27 28 backend 2 29 37 48 binding of names 16 boolean 29 built in types see primitive types busy beaver 55 case sensitive 10 16 35 color
Download Pdf Manuals
Related Search
Related Contents
Samsung ST96 用户手册 MANUAL DE INSTALAÇÃO INDUSPARQUET Bedienungsanleitung 取扱説明書 AC Drive User`s Manual p3 u&i hard drive Manual Mode d`emploi User Manual Contents EM220II - Zebra Technologies Corporation LINCOLN ai - Amazon Web Services Copyright © All rights reserved.
Failed to retrieve file