Home

The GrGen User Manual

1. rule AddRedundancy s SourceNode t DestinationNode modify emit Source node isu s name Destination node is t name exec x DuplicateNode s amp ConnectNeighbors s x exec DuplicateCriticalEdge exec MaxCapacityIncidentEdge t T emit Redundancy added oO OA JO ow SG W N KH H 44 Rule Set Language CHAPTER 5 TYPES AND EXPRESSIONS In the following sections Ident refers to an identifier of the graph model language see Sec tion 3 1 or the rule set language see Section 4 1 Typeldent is an identifier of a node type or an edge type NodeOrEdge is an identifier of a node or an edge 5 1 Built In Types Besides user defined node types edge types and enumeration types GRGEN NET supports the built in primitive types in Table 5 1 The exact type format is backend specific The LGSPBackend maps the GRGEN NE T primitive types to the corresponding C primitive types Table 5 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 object Contains a NET object Table 5 1 GRGEN NE T built in primitive types Of course you are free to express an implicit type cast by an explicit type cast as well as
2. Requires Java Runtime Environment 1 5 or above Introduction CHAPTER 2 QUICKSTART In this chapter we ll build a GRGEN NET system from scratch You should already have read chapter 1 to have a glimpse of the GRGEN NET system and its components We will use GRGEN NET to construct non deterministic state machines We further show some actual graph rewriting by removing e transitions from our state machines This chapter is mostly about the GRGEN NET look and feel please take a look at the succeeding chapters for comprehensive specifications 2 1 Downloading amp Installing If you are reading this document you probably did already download the GRGEN NET soft ware from our website http www grgen net Make sure you have the following system requirements installed e Java 1 5 or above e Mono 1 2 3 or above on Unix like platforms NET 2 0 or above on Microsoft Windows Unpack the package to a directory of your choice for example into opt grgen and opt ycomp mkdir opt grgen tar xvfj GrGenNET V1_3_1 2007 12 06 tar bz2 mv GrGenNET V1_3_1 2007 12 06 opt grgen rmdir GrGenNET V1_3_1 2007 12 06 Add the opt grgen bin directory to your search paths for instance if you use bash add a line to your home profile file export PATH opt grgen bin PATH Furthermore we create a directory for our GRGEN NET data for instance by mkdir home grgen If you re using Microsoft Windows On Windows make sure you have
3. The graph model consists of zero or multiple type declarations Whereas ClassDeclaration defines a node type or an edge type EnumDeclaration defines an enum type to be used as a 18 Graph Model Language type for a attributes of nodes or edges Like all identifier definitions types do not need to be declared before they are used EnumDeclaration Ident Decl Ident Decl or Defines an enum type An enum type is a collection of so called enum items that are associated with integral numbers each Accordingly a GRGEN NE T enum is internally represented as int see Section 5 1 An enum type and an int are different things but in expressions enum values are implicitly casted to int values see section 5 1 Normally assignments of int values to something that has an enum type are forbidden see section 5 1 Only inside a declaration of an enum type an int value may be assigned to the enum item that is currently declared This also includes the usage of items taken from other enum types because they are implicitly casted to int However items from other enum types must be written fully qualified in this case which e g looks like MyEnum a where MyEnum is the name of the other enum type 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 Consider e g the declaration of the enum item e By implicit cast
4. cast a type to itself According to table 5 2 neither implicit nor explicit casts from int to any enum type are allowed This is because the range of an enum type is very sparse in general For the same reason implicit and explicit casts between enum types are also forbidden Thus enum values can only be assigned to attributes having the same enum type A cast of an enum value to a string value will return the declared name of the enum value A cast of an object value to a string value will return null or it will call the toString method of the NET object Be careful with assignments of objects GRGEN NET does not know your NET type hierarchy and therefore it cannot check two objects for type compatibility e eg enum boolean int float double string object enum boolean int implicit int int float implicit implicit float double implicit implicit implicit string implicit implicit implicit implicit implicit implicit object Table 5 2 GRGEN NET type casts 45 46 Types and Expressions e Allowed x myfloat x myint x mydouble float x myint x mystring string x mybool e Forbidden x myfloat x mydouble and x myint int x mybool MyEnumi MyEnumiType int and MyEnum2 MyEnum2Type MyEnum1 where myenumi and myenum2 are different enum types Unlike an eval part which must not contain assignments to node or edge attributes the declaration of an enum type can contain ass
5. gt There must be at least a node between the edges 4 2 Rules and Tests 29 example 9 For an explanation of the exact induced and dpo pattern modifiers see section 4 5 We define a test SomeCond l test SomeCond 1 2 n SeldomNodeType 3 and execute in GRSHELL grs SomeCond amp SomeRule SomeRule will only be executed if a node of type SeldomNodeType exists For graph rewrite sequences in GRSHELL see Section 6 2 6 ActionSignature Ident Decl Return Types The signature sets the name of a rewrite rule to dentDecl 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 Ident Decl Ident Decl 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 NE T 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 graph element Return Types ee The return types specify edge and node types of graph elements that are returned by the replace modify part If
6. float 45 Fujaba 1 generator 3 graph model 3 15 17 23 27 56 graph model language 15 graph rewrite rules 3 graph rewrite script 3 6 56 61 graph rewrite sequence 31 38 65 77 sraphlet 24 32 34 36 GrGen exe 5 group node 63 GRS see graph rewrite sequence Grshell 3 6 19 53 GrShell script see graph rewrite script GrShell exe 6 homomorphic matching 24 32 host graph 3 33 57 identifier 16 24 imperative see attribute evaluation incident 30 info tag 64 inheritance 15 20 61 int 45 isomorphic matching 32 Kantorowitsch tree 65 Koch snowflake 69 label 55 64 layout algorithm 7 56 69 left hand side 3 33 LGPL 5 LGSPBackend 45 55 65 LHS see left hand side 8 libGr 3 6 19 31 53 match 3 matching strategies 1 modifier 38 modify mode 35 multiplicity see connection assertion NAC see negative application condition name 24 34 59 negative application condition 32 nested transaction see transaction Node 20 node graphlet 25 node type 20 non determinism 31 object 45 order of precedence 47 48 78 organic see layout algorithm orthogonal see layout algorithm parameter 29 55 65 pattern 31 pattern graph 3 24 persistent graph 57 persistent name 54 59 60 pragma see annotation precedence see order of precedence preservation 34 preservation morphism 3 34 primitive types 45 quickstart
7. if 32 include 56 induced 27 32 infotag 64 INDEX inherited 21 is 6l labels 64 layout 56 model 77 modify 35 negative 32 new 56 59 60 node 20 60 61 63 64 nodes 60 num 60 off 64 on 64 only 60 61 63 64 open 57 pattern 77 prio ol quit 55 replace 35 reset 64 return 32 38 rule 27 save 61 select 55 57 64 set 56 63 64 shape 63 show 56 57 60 62 65 strict 57 sub 61 super 61 test 27 textcolor 63 true 41 type 61 typeof 49 undirected 19 using 27 validate 21 57 Non Terminals ActionSignature 29 Assignment 37 AttributeDeclarations 22 83 84 AttributeOverwrite 22 Attribute Type 22 Attributes 59 BoolExpr 46 ClassDeclaration 19 Command 55 ConnectAssertions 21 Constant 49 Constructor 59 Continuation 24 EdgeClass 20 EdgeRefinement 26 EnumDeclaration 18 ExecStatement 37 Expression 46 FloatExpr 48 GraphElement 54 GraphModel 17 GraphRewriteSequence 65 77 Graphlet 24 GraphletEdge 26 GraphletNode 25 IdentDecl 51 Intkzpr 47 NodeCtlass 20 NodeConstraint 21 Parameters 29 53 PatternStatement 32 PrimaryExpr 49 RangeConstraint 21 Replace 35 ReturnStatement 38 ReturnTypes 29 RewriteSequence 40 RewriteTerm 41 Rule 41 RuleDeclaration 27 RuleExecution 41 RuleSet 27 Script 55 SimpleRewriteSequence 78 SimpleTerm 78 SpacedParameters 53 StringExpr 48 TestDeclaration 27 TypeConstraint 50
8. amp amp amp typeof x lt Tn The expression T T2 T3 applied to the type hierarchy on the left side yields only the types T and T1 as valid 5 4 Annotations Identifier definitions can be annotated by pragmas Annotations are key value pairs IdentDecl 5 4 Annotations 51 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 int 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 5 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 52 Types and Expressions CHAPTER 6 GRSHELL LANGUAGE GRSHELL is a shell application of LIBGR It belongs 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 l
9. 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 Typed nodes and edges with multiple inheritance on types Directed multigraphs including multiple edges of the same type Undirected and arbitrarily directed edges will be implemented in version 2 0 Node and edge types can be equipped with typed attributes like structs Connection assertions to restrict the shape of graphs Turing complete language for checking complex conditions 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 2 Introduction Besides SPO three additional modes for the semantics of a rule application can be choosen matching of exact patterns only matching of induced subgraphs only and DPO semantics Attribute conditions including arithmetic operations on the attributes Type conditions including powerful instanceof like type expressions Parameter passing to rules Dynamic patterns with iterative or recursive paths and graphs to be implemented in version 2 0 e The rewrite language supports Attribute re calculation using arithmetic operations on the attributes Retyping of nodes edges a more general version of casts k
10. iff either the first or the second Boolean expression is true m Logical AND and OR Lazy evaluation l Logical AND and OR Strict evaluation Table 5 4 Binary Boolean operators in ascending order of precedence IntExpr PrimaryExpr Kee 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 IntExpr The BinIntOperator is one of the operators in Table 5 5 48 Types and Expressions Bitwise shift left bitwise shift right and bitwise shift right preserving the sign Multiplication integer division and modulo Table 5 5 Binary integer operators in ascending order of precedence FloatExpr PrimaryExpr FloatExpr FloatExpr FloatExpr BinFloatOperator The operator is a simple if then else If the BoolExpr is evaluated to true the operator returns the first FloatExpr otherwise it returns the second Floatkxpr The BinFloatOperator is one of the operators in Table 5 6 Table 5 6 Binary float operators in ascending order of precedence The operator on float values works analogous to the integer modulo operator For instance 4 5 2 3 2 2 StringExpr P rimaryExpr StringExpr StringExpr The operator concatenates two strings 5 3 Ty
11. subtypes EdgeType gt 1 EdgeType gt gt 1 Edge gt lt gt 1 Edge gt or lt 1 Edge 3 1 UEdge gt 7 1 AEdge gt e gt The edge e is bound to As the above table shows edges can be defined and used separately 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 eng D 3 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 Zwou 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 4 2 Rules and Tests Se 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 SE 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 TypeCo
12. E Be mg A e e e Ka S e Y O This toy example yields y i 42 y j 1 ExecStatement The statements emit and exec enhance the declarative rewrite part by imperative clauses That means these statements are executed in the same order as they appear within the rule The execution statements take place after all the rewrite operations are done i e they operate on the modified host graph However attribute values of deleted graph elements are still available for reading The eval statements are executed before the execution statements i e the execution statements work on the recalculated attributes Text Output The emit statement prints a string to stdout See section 5 2 for a description of string expressions 38 Rule Set Language XGRS Execution The exec statement executes a graph rewrite sequence which is a composition of graph rewrite rules See section 4 6 for a description of graph rewrite sequences ReturnStatement Graph elements of the replace modify part can be returned according to the return types in the signature see Section 4 2 ActionSignature 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 4 5 Rule and Pattern Modifiers By default GRGEN NET performs rewriting according to semantics as explained in section 4 4 1 This behaviour can be changed with rule pa
13. 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 yCompP 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 6 2 3 The spe cializations Node and Edge of GraphElement require the corresponding graph element to be a node or an edge respectively We insert a node anonymously and with a constructor see also Section 6 2 3 gt new graph lib lgsp TuringModel d1ll 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 oO Aa NID OD FF W N Hr 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 u assigned to start e k HM D N fF OO 6 2 GRSHELL Commands 55 Persistent names belong to a specific graph whereas variables belong to the current GRSHELL environment Persistent names will be saved save graph see Section 6 2 5 and if you visualize a graph dump
14. 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 4 6 for further information on graph rewrite sequences 32 Rule Set Language PatternStatement hom CO 0 0 The semantics of the various pattern statements are given below Graphlet Graphlets specify connected subgraphs See Section 4 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 5 nodes n1 and n2 may be the same node This is possible because they are of the same type NodeTypeA A 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 p
15. connect specific nodes Moreover the number of outgoing and incoming edges can be constrained see Section 3 1 1 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 6 2 2 validate ConnectAssertions connect NodeConstraint NodeConstraint RangeConstraint 3 2 Type Declarations 21 RangeConstraint Number 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 5 2 See Section 6 2 2 validate for an example Table 3 1 describes the multiplicity definitions Multiple connection assertions are applied by conjunction i e all of them must be fulfilled The arrow syntax is based on the GRGEN NET graphlet specification see Section 4 1 1 The different kinds of arrows distinguish between directed und undirected edges The gt arrow means what you intuitively expect a directed edge directing to a node of the target node type or one of its subtypes The lt gt arrow means a directed edge as well but s
16. elements However the modify part allows for explicit deletion of graph elements by using the delete statement What else can we do We have negative application conditions NACs expressed by negative they prevent rules to be applied if the negative pattern is found We also have boolean conditions expressed by if a rule is only applicable if all such condi tions hold true Note the dot notation to access attributes as in e Trigger The emit statement prints a string to stdout The hom x y and hom x y z statements mean match the embraced nodes homomorphically i e they can but they don t have to actually be matched to the same node within the host graph The eval statement is used to re calculate attributes of graph elements Have a look at the statement y StartFinalState lt x gt in addStartFinalState we retype the node x That means the newly created node y is actually the node x including its incident edges and attribute values except for the node type which is changed to StartFinalState Imagine retyping as a kind of a type cast The created rewrite rules might be considered as rewrite primitives In order to implement more complex functionality we will compose a sequence of rewrite rules out of them For o oo N 9 Om FF O N Hr 11 21 51 2 4 The Rewrite Rules using StateMachine test checkStartState x StartState negative x y StartState test checkDoublet
17. indicates the character sequence for switching from the source state node to the destination state node For the rest of the types we use inheritance keyword extends which works more or less like inheritance in object oriented languages Accordingly the abstract modifier for SpecialState means that you cannot create a node of that precise type but you might create nodes of non abstract subtypes As you can see GRGEN NET supports multiple inheritance and with StartFinalState we have constructed a diamond type hierarchy 2 3 Creating Graphs Let s test our graph meta model by creating a state machine graph We will use the GRSHELL see chapter 6 and for visualization YCoMP To get everything working we need a rule set file too For the moment we just create an almost empty file removeEpsilons grg in the home grgen directory containing only the line 1 using StateMachine Now we could start by launching the GRSHELL and typing the commands interactively This is however in most of the cases not the preferred way We rather create a GRSHELL script say removeEpsilons grs in the home grgen directory Figure 2 2 shows this script Run the script by executing grshell removeEpsilons grs The first time you execute the script it might take a while because GRGEN NET has to compile the meta model and the rule set into NET assemblies The graph viewer YCOMP opens and after clicking the blue layout graph button on the v
18. mR A TERT h Layout Options Hierarchic K gt Do Layout AR Organic ie aren EE ef Select Edge Router L aan gt arin Route Edges AT Ties 1 m ne meem Fold Sub h Q Diagonal tes nm een R pon ea Fold Subgraphs L z a lt i l L a ool Unfold Subgraphs Incremen tal Hierarci hic eu eben une oa ch Fold Selected Compilergrap i edan m mom gt rq 1 Enz Graph Analysis und E L on Next Options Toggle Arrows AOD Next Opt kar mian eg pt teilen geng cen vi J Root 0 Reverse Edges SAN Root 0 ee Sien sam 0 GridNode Edge Classes 2 0 GridNode Lei lian naia ee 103 GridNode Show All Edges WG 103 GridNode el S po ee ee EN ie BS 106 GridNode Reset All Reference Nodes DS 106 GridNode BE kael i nen enon robin re Baia at ios 109 MarkedGridN 109 MarkedGridN 10C MarkedGridN ss 54E GridNode de 10C MarkedGridN E CC ef Sen Mies S108GrdNode T EE gag s Ra magia TT oan sag 111 GridNode 111 GridNode E Br SC 114 MarkedGridN 114 MarkedGridh oe eh eh oo et tt tt 117 GridNode 117 GridNode 11 MarkedGridNc 11 MarkedGridNc zo eo 11A GridNode 11A GridNode eto eae se 11D MarkedGridh 11D MarkedGridN 11F GridNode 11F GridNode S une ed 122 GridNode 122 GridNode 125 GridNode 125 GridNode 128 MarkedGridN 128 MarkedGridN F 12B MarkedGridN 12B MarkedGridN 12E MarkedGridN a 12E MarkedGridN 4 pa age EB 132 MarkedGridN Y 132 MarkedGridN BID
19. node x is bound to GraphletEdge Loupe EREE E EdgeRefinement 26 Rule Set Language EdgeRefinement Hien C A GraphletEdge specifies an edge Anonymous edges are specified by an empty EdgeRe finement clause i e gt lt lt gt or T gt lt T for an edge type T respectively A non empty EdgeRefinement clause allows for detailed edge type specification Type constraints are allowed in the pattern part only see Section 5 3 TypeConstraint The lt gt operator retypes an edge Retyping is allowed in the replace modify part only see Section 4 4 Retyping The different kind of arrow tips distinguish between directed undirected and arbitrary edges see also Section 3 1 1 The arrows gt and lt are used for directed edges with a defined source and target The arrow is used for undirected edges The pattern part allows for further arrow tips namely for arbitrary edges and lt gt for directed edges with undefined direction Note that lt gt is not equivalent to the gt lt statements In order to produce a match for the arrow lt gt it is sufficient that one of the statements gt lt matches If an edge type is specified through the EdgeRefinement clause this type has to correspond to the arrow tips of course Graphlet Meaning e EdgeType gt The name e is bound to an edge of type EdgeType or one of its
20. not write to attributes see also Section 4 4 eval However 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 The keywords arbitrary directed and undirected specify the direction attribute of an edge class and thus its inheritance An arbitrary edge inherits from AEdge it is abstract and neither directed nor undirected A directed edge inherits from Edge An undirected edge inherits from UEdge If you do not specify any of those keywords a directed edge is choosen by default See also Section 3 1 1 NodeClass Ge eene og Om 20 Graph Model Language Defines a new node type Node types can inherit from other node types defined within the same file If the extends clause is omitted NodeType will inherit from the built in type Node Optionally nodes can possess attributes EdgeClass ce f Connect Assertions E 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 A connection assertion specifies that certain edge types should only
21. return types are specified the return statement is mandatory Oth erwise no return statement must occur See also Section 4 4 return 30 Rule Set Language Assume the following test that checks whether the edge e is not incident to x test r e Edge gt x Node negative ze I negative X cez o ND oa FP W N HM If x and e are undefined test r is equivalent to test s test s 1 x Node e Edge gt negative FO xX negative x eg d oO DJ OO FP W HM Hr a oO In particular test s is successful if there is some edge in the host graph that is not incident to x We extend SomeRule Example 5 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 n1 NodeTypeA replace varnode return n5 e1 eval oo Aa N OO FP W N MH oO We do not define varnode within the pattern part because this is already covered by the parameter specification itself 4 3 Pattern Part 3l 4 3 Pattern Part Pattern S PatternStatement B A 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 For an explanation of the pattern modifiers dpo indu
22. specializations of Ident to restrict an identifier to denote a node type an edge type or an enum type respectively 3 1 1 Base Types The GRGEN NET model language has built in types for nodes and edges All nodes have the attribute less built in type Node as their ancestor All edges have the abstract see Section 3 2 attribute less built in type AEdge as their ancestor The AEdge has two non abstract built in children UEdge as base type for undirected edges and Edge as base type for directed edges The direction for AEdge and its anchestors that do not inherit from Edge or UEdge is undefined or arbitrary Because there is the magic of direction linked to the edge base types its recommended to use the keywords directed undirected and arbitrary in order to specify inheritance see Section 3 2 As soon as you decided for directed or undirected edge classes within your type hierarchie you are not able to let anchestor classes inherited from a contradicting base type of course That is no edge may be directed and undirected This is an excpetion of the concept multi inheritance Figure 3 1 shows the edge type hierarchy user defined arbitrary edge classes user defined user defined directed edge classes undirected edge classes N user defined directed edge class n Figure 3 1 Type Hierarchy of GRGEN NET Edges 3 2 Type Declarations GraphModel ClassDeclaration u Enum Declaration l
23. successfully applied to the host graph A false return value means that the pattern was not found in the host graph Graph rewrite sequences can be processed transactionally by using angle brackets lt gt If the return value is false all the related operations on the host graph will be rolled back Nested transactions are supported In order to store return values of rewrite terms and to pass return values of rules to other rules variables can be defined A variable is an arbitrary identifier which is defined by assigning a graph element a boolean value or another variable to it You may use named graph elements of the enclosing rule as read only variables A parameter is alive from its first assignment until the end of the enclosing exec statement 4 6 Extended Graph Rewrite Sequences XGRS 39 Modifier Meaning exact Switches to the most restricitive mode An exactly matched node is matched if all its incident edges in the host graph are specified in the pattern induced Switches to the induced mode where nodes contained in the same induced statement require their induced subgraph within the host graph to be spec ified in order to be matched In particular this means that in general induced a b c differs from induced a b induced b c dpo Switches to DPO semantics This modifier affects only nodes that are to be deleted during the rewrite DPO says roughly spoken that implicit dele tions must not occur
24. the NET 2 0 or above framework installed GRGEN NET does not need to be installed just copy the extracted files to a directory of your choice Add this directory to your search paths via control panel system properties You might rather want to download the zip archive instead of the bz2 archive Execute the GRGEN NET assemblies from a command line window Start Run cmd On Windows NEI the mono prefix is not applicable of course 10 Quickstart 2 2 Creating a Graph Model In the directory home grgen we create a text file StateMachine gm that contains the graph meta model for our state machine By graph meta model we mean a set of node types and edge types which are available for building state machine graphs see chapter 3 Figure 2 1 shows the meta model What have we done You can see two base types State for node class State id int abstract node class SpecialState extends State node class StartState extends SpecialState node class FinalState extends SpecialState node class StartFinalState extends StartState FinalState oO oo ND OD FF WwW N e edge class Transition Trigger string e e N e oO e e O const edge class EpsilonTransition extends Transition Figure 2 1 Meta Model for State Machines state nodes and Transition for transition edges that will connect the state nodes State has an integer attribute id and Transition has a string attribute Trigger which
25. 9 rail diagram 15 re evaluation see attribute evaluation redefine 24 redirecting 26 replace mode 34 replacement graph 3 24 33 return type 29 return value 33 38 retyping 25 26 36 rewrite rule 3 27 RHS see right hand side right hand side 3 33 rule pattern modifiers 38 rule application see application rule set 23 27 64 rule set language 23 scope 25 32 script see graph rewrite script search plan 29 51 67 75 86 search plans 1 sesqui pushout 2 shell see GrShell Sierpinski triangle 69 signature 29 single pushout approach 1 26 34 SPO see single pushout approach 38 spot 3 24 string 45 syntax diagram see rail diagram test 27 30 transaction 38 transaction nested 2 transformation specification 33 Turing complete 71 type cast see retyping 45 type constraint 25 26 50 type expression 24 47 49 type hierarchy 15 17 36 50 type compatible 61 UEdge 17 UML class diagram 47 undefined parameter 29 undefined variables 65 undirected 26 validate 57 variable 54 59 65 Varro s benchmark 1 VCG 7 54 62 working graph 57 XGRS see graph rewrite sequence yComp 7 62 65 yComp jar 65 Deprecated Syntax
26. CA 12C BC 12F BC 132 BC 125 AR The temporary file will be deleted when the application Filename is terminated 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 6 2 GRSHELL Commands 63 dump node NodeType a Je 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 EE 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 met
27. Find H Root gt 0 B 102 CA 103 AB gt 104 BC 10E CA 10F AB 110 BC I 11A CA 11B AB 3 11C BC 126 CA 127 AB 128 BC 12 CA 3 132 CA _ 133 AB 134 BC 3 13 AB 13E CA 13F AB 0O O aKT Figure 7 1 Sierpinski triangle yComp Version 1 3 1 File Edit View Navigate Layout Help Rana e XE L7 Root gt 0 Node1 10 Node gt 16 Nodel 17 Node 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 gt 3A Node _ gt 3B Node 41 Nodel a KE ODAAS8HA lt gt athe K n STE Edge Lo Eda LC Eda WH 170 Edar Ar S4C Edgel SHE EZ an gigas L too Sea lt D annan D 116 E gi 160 daet 4 EZ S2E Edget SSC Edgel 150 E does Aart E a 120 E Zaz 84 Edges 44 Edel S2 E Eae 2 Soer 118 E bet SE Esel Stiel 1 Figure 7 2 Koch snowflake o a nn OD A O N Hr 7 2 Busy Beaver 71 7 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 MBOO 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
28. I Tische 2 00 006 FEO Ree SGD EE HEEB EEE BER ER ES 24 4 2 Rules and Tests 27 4 3 Pattern Part Al 4 4 Replace Modify Part ee a gt 4 4 1 Implicit Definition of the eas Mei ee 34 4 4 2 Specification Modes for Graph Transformation 34 ime COU ee een 35 4 5 Rule and Pattern Modifiers 38 4 6 Extended Graph Rewrite Sequences XGRS 38 5 Types and Expressions 45 9 1 Built In Types 45 9 2 Expressions 46 9 3 Type Related H N 49 5 4 Annotations 50 vil vill GrShell Language 6 1 6 2 6 3 6 4 Building Blocks GRSHELL Commands 6 2 1 Common Commands 6 2 2 Graph Commands 6 2 3 Graph Manipulation Commands 6 2 4 Graph Query Commands 6 2 5 Graph Output Commandes 6 2 6 Action Commands XGRS Graphical Debugger oe 4 LGSPBackend Custom Commands 6 4 1 Graph Related Commands 6 4 2 Action Related Commands Examples T 1 2 Fractals Busy Beaver 2 2 2 2 2 2 ne 7 2 1 Graph Model 7 2 2 Rule Set 2222020 7 2 3 Rule Execution with GRSHELL Deprecated Syntax A 1 Graph Model and Rule Set Language A 2 Graph Rewrite Sequences GRS Bibliography Index 53 53 59 59 56 58 60 61 64 65 65 67 67 69 69 71 71 71 13 TT TT TT ol SE 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 expe
29. Languages C ANSI ISO 9899 1990 1990 Georg Sander VCG visualization of compiler graphs user documentation v 1 30 Technical report Universitat des Saarlandes 1995 Adam M Szalkowski Negative Anwendungsbedingungen fiir das suchprogramm basierte Backend von GrGen 2005 Studienarbeit Universitat Karlsruhe The Mono Team Mono http www mono project com 2007 G Varr A Sch rr and D Varr Benchmarking for Graph Transformation Technical report Department of Computer Science and Information Theory Budapest University of Technology and Economics March 2005 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 yWorks yFiles http www yworks com 2007 Keywords abstract 19 actions 64 65 67 77 add 63 64 arbitrary 19 backend 55 56 bordercolor 63 class 20 clear 57 color 63 connect 21 const 19 custom 58 65 67 debug 56 65 77 def 41 79 delete 36 57 60 directed 19 disable 56 dpo 27 dump 62 64 echo 56 edge 20 60 61 63 64 edges 60 emit 37 enable 56 enum 18 eval 36 exact 27 32 exclude 63 exec 37 exit 55 extends 20 false 41 graph 96 08 61 62 67 group 63 grs 65 77 help 55 hom 32
30. MJW91 R 0z99 ISAI 90 San95 Sza05 Tea07 VSV05 IV VFO06 ly Wo07 Deprecated Syntax 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 info uni karlsruhe de software php id 6 2007 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 html1 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 C standard American National Standard for Programming
31. RSHELL commands immediately before the first script file Instead of a line break use a double semicolon to separate commands Requires NET 2 0 or above or Mono 1 2 3 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 at http www grgen net doc libGr 3n is an increasing number 1 6 The Tools 1 6 4 yComp jar YComP KBG 07 is a graph visualization tool based on YFILES yWo07 It is well integrated and shipped with 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 Usage Usually vYCoMP 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 layout process Depending on the graph size this may take a while m 8 ee yComp Version 1 3 1 tmpgraph0 vcg ee yComp Version 1 3 1 tmpgraph0 vcg File Edit View Navigate BEVIT Help File Edit View Navigate Layout Help Z 2 Z 2 T Bans 26 R Random Rane 26 XDA
32. RewriteSequence This executes the graph rewrite sequence SimpleRewriteSequence See section 4 6 for graph rewrite sequences Additionally to the variable assignment in rule embedded graph rewrite se quences you are also able to assign persistant names to parameters via Variable Text 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 Section 4 2 Parameters 6 3 Graphical Debugger The GRSHELL together with YCOMP build GRGEN NET s graphical debugger Use the debug grs option to trace the rewriting process step by step During execution YCOMP will display every single step The debugger can be controlled by GRSHELL Remember that the modifier before a rule works as break point in a graph rewrite sequence The debug commands are shown in Table 6 1 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 26 step o ut Continue a rewrite sequence until the end of the current loop If the execution is not in a loop at this
33. Sight node class City Size Resident const node class Metropolis extends City River String abstract node class AbandonedCity extends City node class GhostTown extends AbandonedCity edge class Street edge class Trail extends Street edge class Highway extends Street connect Metropolis gt Metropolis Jam boolean false Basic elements of the GRGEN NET graph model language are identifiers to denominate nodes edges and attributes The model s name itself is given by its file name The GR GEN 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 may be annotated See Section 5 4 for annotations of declarations e 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 3 2 Type Declarations 17 NodeType EdgeType Enum Tune These are semantic
34. TypeExpr 49 VarAssignment 42 Variable 42 General Index gm 3 Deprecated Syntax erg 3 6 ers 3 D l 42 56 79 42 79 33 00 19 lt gt 41 54 53 lt number gt 24 lt op gt 31 42 79 59 42 79 amp 42 79 gt ae action see graph rewrite sequence action command 64 AFdge 17 analyzing graph 67 annotation 16 24 50 anonymous 24 34 35 54 API 3 6 application 3 31 arbitrary 17 26 associative 40 79 attribute 22 59 61 64 attribute condition 33 attribute evaluation 36 37 backend 3 45 55 65 backslash 55 binding of names 24 boolean 45 break point 41 built in types see primitive types busy beaver 71 case sensitive 16 23 53 color 54 63 command line 56 comment 53 compatible types see type compatible compiler graph see layout algorithm connection assertion 20 21 57 constructor 54 59 continuation see graphlet debug mode 56 debugger 65 declaration 16 18 31 default graph model 23 default search plan 67 default value 59 A 2 Graph Rewrite Sequences GRS definition 16 50 degree see connection assertion deletion 34 36 determinism see non determinism directed 26 double 45 double pushout approach 1 dumping graph 61 dynamic patterns 2 Edge 17 20 edge graphlet 26 edge type 20 empty pattern 4 31 enum item 18 46 enum type 18 45 evaluation see attribute evaluation
35. Universit t Karlsruhe TH Forschungsuniversitat gegr ndet 1825 Fakultat f r Informatik Institut f r Programmstrukturen und Datenorganisation Lehrstuhl Prof Goos The GRGEN NET User Manual Refers to GRGEN NET Release 1 4 www grgen net Jakob Blomer Rubino Gei Apr l 23 2008 il 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 ili 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 easy to integrate into our compiler inf
36. aie EE Text een 60 GrShell Language Creates a new edge within the current graph between the specified nodes directed towards the second Node Optionally a variable Text is assigned to the new edge If EdgeType 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 6 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 The 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 6 2 GRSHELL Commands 61 Gets the inherited descendant types of Node Type Edge Type ee lJ NodeType attributes Gets the available node edge attribute types If NodeType EdgeType is supplied only at tributes defined in NodeType EdgeType are diplayed The only keyword excludes inherited attributes The show nodes edges attributes command
37. anguage GRSHELL scripts are structured by simple statements separated by line breaks 6 1 Building Blocks GRSHELL is case sensitive A 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 A 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 771 Number Is an int or float constant in decimal notation see also Section 5 1 Parameters u 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 02 54 GrShell Language Variable Identifier of a variable that contains a graph element NodeType Edge Type Identifier of a node type resp edge type defined in the model of the current 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
38. by all means Accordingly nodes going to be deleted due to the rewrite part have to be specified exactly exact semantics in order to be matched Furthermore if you specify two pattern graph elements to be homomorphically matched but only one of them is subject to deletion during rewrite those pattern graph elements will never actually be matched to the same host graph element In contrast to exact and induced this modifier applies neither to a pattern as such nor to a single statement but only to an entire rule See Corradini et al CMR99 for a DPO reference Table 4 3 Semantics of rule and pattern modifiers Host Graph Pattern Rule Effect ac Do fe gt ae tt Produces no match for exact nor induced x node gt y node L Produces three matches for induced x y but no match for exact x y E x node induced x Produces no match O O O eent gt anode gt e ee un i Produces no match in DPO mode C modify delete x because of edge e 40 Rule Set Language Note that we have two kinds of return values in graph rewrite sequences Every rewrite term returns a boolean value indicating whether the rewriting could be successfully pro cessed Additionally rules may return graph elements These return values can be assigned to variables on the fly see example 17 The graph rewrite sequence la b c R amp y z is valid It assigns returned graph elements from rule R to variables b and c an
39. ced and exact see section 4 5 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 declaration See Section 4 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 As a LIBGR user have a look at the following methods of the IAction 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
40. ced by the rule set removeEpsilons grg with the name StateMachineGraph There after we create nodes and edges The colon notation indicates a node or edge type Also note the inplace arrow notation for edges Edge gt resp EdgeType gt As you can see attributes of graph elements can be set during creation with a call like syntax The and notation is due to the fact that we have two kinds of names in the GRSHELL Namely we have shell var ables which we did not use no shell variable is explicitly defined in this script and persistent names that denote a specific graph element Persistent names are set by Identifier on creation and they are accessed by Identifier The quote chars around 1 and 2 are used to type these characters as identifier strings rather than numbers 2 4 The Rewrite Rules We will now add the real rewrite rules to the rule set file removeEpsilons grg The idea is to forward the e transitions one after another i e if we have a pattern like a State EpsilonTransition gt b State e Transition gt c State we forward to a e gt c Af ter all such transitions are forwarded we can remove the e transitions alltogether The com plete rule set is shown in figure 2 4 See chapter 4 for the rule set language reference In detail The rule set file consists of a number of rules and tests each of them bearing a name like forwardTransition Rules contain a pattern expressed as several semic
41. covers types and inherited types This is in contrast to the other show commands where types and subtypes 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 6 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 62 GrShell Language e restoring the persistent names see Section 6 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 6 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 yYComp as executable this may look like yComp Version 1 3 1 tmpgraph0 vcg File Edit View Navigate Layout Help Saai ICE spe HA A FER D Find Next Options Root A 0 AB 102 AB 105 CA 108 AB 10B CA 10E CA 111 CA 114 CA 117 CA 11A CA 11D CA 120 CA 123 BC 126 BC 129 BC 12
42. cted to a node of type NodeType2 by an edge of type EdgeType and binds the names v w and e If v and w are not explicitly marked 4 1 Building Blocks 25 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 ial O ae ne is equivalent to ia ini 2 ni gt DI lies lt jal 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 Example 5 lines 13 to 17 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 Tent Specifies a node of type NodeType with respect to TypeConstraint see Section 5 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 4 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 sf 1 Node x The
43. d the infor mation whether R mached or not to variable a RewriteSequence A graph rewrite sequence consists of several logically linked rewrite terms The modifier flags the following operator to act commutative Usually operands are executed evaluated from left to right with respect to bracketing left associative In contrast the sequences s t u ins lt op gt t lt op gt u are executed evaluated in arbitrary order A sequence can further be executed multiple times The star executes a sequence repeatedly as long as its execution does not fail Such a sequence always returns true The braces let execute a sequence repeatedly as long as its execution does not fail but Number times at most 4 6 Extended Graph Rewrite Sequences XGRS 41 RewriteTerm OO Variable ORG Kaz Rewrite terms are the building blocks of graph rewrite sequences They either act as a rule application or assign a value to a variable A variable in the Variable term must contain a boolean value accordingly A def term is successful if all the the variables are defined RuleExecution LOE OO sz Gase Lal to Rule Ruleldent Variable To The RuleExecution clause applies a single rule or test In case of a rule the first found pattern match will be rewritten Variables and named graph elements from the enclosing rule can be passed The returned graph elements can be assigned t
44. e e3 as well as e A correct solution could make use of edge type information We have to change rule po to generate the edge e with a special type stem And this time we will even keep the stem So let 2 Como die If we apply pa to the modified Hi this leads to 1 6 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 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 You ll find the tools in the bin subdirectory of your GRGEN NET installation 1 6 1 GrGen exe The GrGen exe assembly implements the GRGEN NET generator The GRGEN NET gener ator parses a rule set and its model files and compiles them into NE T assemblies The com piled assemblies form a specific graph rewriting system by interacting with the GRGEN NET backend 6 Introduction Usage mono GrGen exe keep lt dest dir gt use lt existing dir gt debug b lt backend d11 gt o lt output dir gt lt rule set gt rule set is a file containing a rule set specification according to chapter 4 Usually such a file has the suffix erg The suffix erg may be omitted By default GRGEN NET tries to write the compiled assemblies into the same directory as the rule set file This can be changed by the optional parameter output dir Options keep Keep the generated C source files If des
45. e graph elements in 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 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 A 1 Graph rewrite expressions 80 Deprecated Syntax Ass00 Bat05a Bat05b Bat06 BKG07 ICEM 06 ICHHKO6 CMR 99 Dew84 D r95 EHKt 99 Fuj07 IGBG 06 Gei07 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 f r eine Zwischendarstellung im bersetzer bau Master s thesis Universit t 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 Andrea Corradini Hartmut Ehrig Ugo Montanari Leila Ribeiro and Grzegorz Rozenberg
46. e hierarchy graph rather their relation can be arbitrary However if source and destination type have one ore more common super types then the respective attribute values are adopted by the retyped version of the respective node or edge The edge specification as well as ReplaceNode supports retyping In Example 5 node n5 is a retyped node stemming from node n1 Note that conceptually the retyping is per formed after the SPO conform rewrite Assignment Tent Har To ZT Perred 4 4 Replace Modify Part 37 Pattern LHS Replace RHS r L R Meaning Nd y N2 lt x gt r lhs x rhs x Preserve x then retype x from Ni to N2 and bind name y to retyped version of x e El f E2 lt e gt r lhs et rhs e Preserve e then retype e from E1 to E2 and bind name f to the retyped version of e Table 4 2 Retyping of preserved nodes and edges 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 modify eval y i eval y j x IJNode y IJNode delete x eval x i 1 yj Z ya Kaffe E O U co
47. 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 Konig Sesqui pushout rewriting In Corradini et al CEM 06 pages 30 45 A Corradini U Montanari F Rossi H Ehrig R Heckel and M Lowe Alge braic Approaches to Graph Transformation Part I Basic concepts and double pushout approach In Roz99 volume 1 pages 163 245 1999 A K Dewdney A computer trap for the busy beaver the hardest working turing machine Scientic American 251 2 10 12 16 17 8 1984 Heiko Dorr 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 Lowe 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 sl 82 Hac03 IKBG 07 YOU Kro07 IMBOO Mic07 M
48. eed 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 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 12 Examples 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 66 rule readZeroRule s State h RWHead gt tp TapePosition zero gt tp s zero gt wv WriteValue modify delete h wv RWHead gt tp o DJ OO FP W N 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 10 rule readOneRule 11 s State h RWHead gt tp TapePosition one gt tp 12 s one gt wv WriteValue 13 modify 1 14 delete h 15 wv RWHead gt tp 16 17 18 19 rule readEmptyRule 20 s State h RWHead gt tp TapePositi
49. een n1 and n2 only occurs in the pattern and therefore gets deleted See Section 4 4 1 for a detailed explanation of the transformation semantics 4 4 Replace Modify Part 35 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 How might Example 11 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 1 ni e0 Edge gt n2 modify n5 NodeTypeC lt n1 gt n3 e1 EdgeTypeB gt n5 delete e0 eval oO a Nn OD A W N bf 4 4 3 Syntax Replace D G a ReplaceStatement ExecStatement 9 ReturnStatement J Selects whether the replace mode or the modify mode is used Several replace statements describe the transformation from the pattern subgraph to the destination subgraph 36 Rule Set Language ReplaceStatement The semantics of the various r
50. eplace 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 4 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 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 table 4 2 shows how retyping can be expressed both for nodes and edges Retyping differs from a type cast During replacement both of the graph elements are alive Specifically both of them are available for evaluation a respective evaluation could e g look like this eval y b 2 x i 42 f a e a Furthermore the source and destination types need not to be on a path in the directed typ
51. ery right side of the button bar you get a window similiar to figure 2 3 see also section 1 6 4 The graph looks still a bit confusing In fact it is quite normal that YCOMP s automatic layout algorithm needs manual adjustments Quit YCOMP and exit the GRSHELL by typing exit You ll find the source code of this quick start example shipped with the GRGEN NET package in the examples FiniteStateMachine directory 2 3 Creating Graphs Kd graph removeEpsilons StateMachineGraph new StartState S id 0 new FinalState F id 3 new State 1 id 1 new State 2 id 2 new S Transition Trigger a gt 1 new 1 Transition Trigger b gt 2 new 2 Transition Trigger c gt F new S EpsilonTransition gt 2 new 1 EpsilonTransition gt F new S EpsilonTransition gt F o A ND ow A UU N A e e k Hm e N F O show graph ycomp Figure 2 2 Constructing a state machine graph in GRSHELL yComp Version 1 3 4 tmpgraph0 vcg File Edit View Navigate Layout Help Rana Je RNB AAA Er AK ED F FinalState ion Find EpsilonTransition Next Options 5 EpsilonTransition sition Eu Root 1 State ansition 2 State F FinalState ransition S StartState Figure 2 3 A first state machine 11 12 Quickstart This script starts with creating an empty graph of the meta model StateMachine which is referen
52. et 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 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 6 2 6 for further information The resulting graphs should look like Figures 7 1 and 7 2 Be careful The running time increases exponentially in the number of iterations 69 70 Examples yComp Version 1 3 1 File Edit View Navigate Layout Help DanS IC XDAAAAHA lt gt ATH D Fie Ra ms ei A gm d Bas pe A weit I S 3 kt EI N ar A d AA we ll ATM Fu ple
53. ewriting 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 10 on page 31 1 4 What is Graph Rewriting The notion of graph rewriting as understood by GRGEN NET is a method for declaratively specifying changes to 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 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 mor
54. fication of attributes because subtypes inherit the attributes of their super types Note that GRGEN NE T 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 same on all such paths Connection Assertions To specify that certain edge types should only connect specific nodes we include con nection assertions In particular this allows for constraints on the number of outgoing and incoming edges In this chapter as well as in chapter 6 GRSHELL we use excerpts of Example 1 the Map model for illustration purposes 3 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 15 16 Graph Model Language oO a nn OD SG O N r The following toy example of a model of road maps gives a rough picture of the language enum Resident VILLAGE 500 TOWN 5000 CITY 50000 node class
55. from these specifications by GrGen exe and can be used by applications such as GRSHELL Figure 1 2 shows the generation process 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 NE T 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 In this context system is not a CHO like grammar rewrite system but rather a set of interacting software components 1 4 What is Graph Rewriting 3 Ga Y LIBGR C a Y Frontend Compile Time Backend Run Time Graph Model e LC call Graph Rewrite Script grs read generate K Graph Model gm GRGEN NET 3 r Generator sd Java C Rewrite Rewrite Rules Rules grg C Graph Man agement C Figure 1 1 GRGEN NET system components Kro07 referencing read generate gt model3 gm backend dll rules1Model dll model2 gm rulesl grg modell gm Figure 1 2 Generating a graph rewrite system Generating a GRGEN NET graph rewrite system may be considered a preliminary task The actual process of r
56. graph see Section 6 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 6 2 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 Like an operating system shell the GRSHELL al lows you to span a single command over n lines by terminating the first n 1 lines with a backslash Script lt line break gt lt end of file gt 6 2 1 Common Commands Displays an information message describing supported commands Quits GRSHELL If GRSHELL is opened in debug mode a currently active graph viewer such as YCOMP will be closed as well Filename Parameters Selects a backend that handles graph and rule representation Filename has to be a NEI assembly e g lgspBackend d11 Comma separated parameters can be supplied optionally if so the backend must support these parameters By default the LGSPBackend is used 56 GrShell Language List all the parameters supported by the currently selected backend The parameters can be provided to t
57. gt This looks like a boolean expression and in fact it behaves similar The whole expression is evaluated from left to right A rule is successfully evaluated if a match could be found We first check for a valid state machine i e if the host graph contains exactly one start state and no redundant transitions Thereafter we do the actual rewriting These three steps are connected by lazy evaluation ands amp amp i e if one of them fails the evaluation will be canceled We continue by disjunctively connected rules connected by The angle brackets lt gt around the transformation rules indicate transactional processing If the enclosed sequence returns false for some reason all the already performed graph operations will be rolled back That means not all of the rules must find a match The is used to apply the rule repeatedly as long as a match can be found This includes applying the rule zero times Even in this case Rulex is still successful 2 5 Debugging and Output If you execute the modified GRSHELL script GRGEN NET starts its debugger This way you can follow the evaluation of the graph rewrite sequence step by step in YCOMP Just play around with the keys d s and r in GRSHELL the d key lets you follow a single rewrite operation in multiple steps the s key jumps to the next rule and the r key runs to the end of the graph rewrite sequence Finally you should get a graph like the one in figure 2 5 yComp Ver
58. he select backend command Executes the GRSHELL script Filename A 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 eS 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 Tert onto the GRSHELL command prompt Ty CommandLine is an arbitrary text the operating system attempts to execute On a Linux machine you might execute 1 sh c lsul grep stuff 6 2 2 Graph Commands Gen graph Filename Text 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 It s also possible to specify a rule set file as Filename In this case the necessary assemblies will be created on the fly 6 2 GRSHELL Commands 57 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 li
59. ify pattern modifiers for a specific set of nodes Accordingly the list of identifiers for a pattern modifier must not contain any edge identifier See section 4 5 for an explanation of the exact and induced modifiers Keep in mind that using type constraints or the typeof operator might be helpful See Section 5 3 for further information 4 4 Replace Modify Part Besides specifying the pattern a main task of a rule is to specify the transformation of a matched subgraph within the host graph Such a transformation specification defines the transition from the left hand side LHS to the right hand side RHS i e which graph 34 Rule Set Language elements of a match will be kept which of them will be deleted and which graph elements have to be newly created 4 4 1 Implicit Definition of the Preservation Morphism r In theory the transformation specification is done by defining the preservation morphism r In GRGEN NET the preservation morphism r is defined implicitly by using names both in Pattern Graph Rewrite Graph Preservation Morphism r SS ih Rul Match m H Hi Host Graph Result Graph Figure 4 1 Process of Graph Transformation pattern graphlets and replace graphlets 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 in a replace graphlet the denoted graph element will be kept Otherwise the graph element will be deleted By defining a
60. ignments of int values to enum items see sec tion 3 2 The reason is that the range of an enum type is just defined in that context 5 2 Expressions Expression FloatExpr BoolExpr Primary Expr ine eee ee The operator negates a Boolean Table 5 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 5 4 The CompareOperator is one of the following operators These operators are supported by int types and float double types but by implicit casting they can also by used with all enum types String types boolean types and object types 5 2 Expressions A7 support only the and the operators Table 5 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 A is a supertype of B or A and B are identical True iff A is a subtype of B or A and B are identical Table 5 3 Compare operators on type expressions A lt Bcorresponds to the direction of the arrow in an UML class diagram S Logical XOR True
61. l EdgeTypeB gt n5 21 eval n5 a3 n3 al n1 a2 22 L In this chapter we use excerpts of Example 5 SomeRule for illustration purposes 4 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 NE T entities 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 23 24 Rule Set Language 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 dent may be an identifier defined in a graph model see Section 3 1 Ident and IdentDecl differ in their role While IdentDecl is a defining occurrence of an identifier Ident is a using occurrence An dentDecl non terminal can be annotated See Section 5 4 for annotations of declarations As in the GRGEN NET model language see note 3 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 expression
62. lable as long as GRSHELL is running i e when the working graph changes the analysis data is still available but maybe obsolete 6 4 2 Action Related Commands custom actions gen_searchplan Action E 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 default search plan is used For efficiency reasons it is recommended to do analyzing and search plan 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 A search plan is available as long as the current rule set remains loaded Specify multiple rewrite rules instead of using multiple 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 68 GrShell Language CHAPTER 7 EXAMPLES 7 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 EO 5 E0 i 4 Edge b Suge d f d ws twe
63. lback to the state 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 zs H Assign the variable w to v If w is undefined v will be undefined too v 0 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 th
64. moment the complete sequence will be executed r un Continue execution without further stops a bort Cancel the execution immediately Table 6 1 GRSHELL debug commands 6 4 LGSPBackend Custom Commands The LGSPBackend supports the following custom commands Make sure that the path to your yComp jar package is set correctly in the veomp shell script within GRGEN NET s bin directory 66 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 7 1 The graph rewriting sequence is 1 debug xgrs makeFlakei amp beautify amp doNothing amp makeFlake2 amp beautify 1 YCoMP will be opened with an initial graph resulting from grs init as 4 gt gel c s5 Edgel N 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 4 Edgel j 2 E U 5 Edgel 9 Edge2 nea _ C Edge2 3 Edgel T 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 6 4 LGSPBackend Custom Commands 67 6 4 1 Graph Related Commands Analyzes the current working graph The analysis data provides vital information for efficient search plans Analysis data is avai
65. n types enum and primitive types See Section 5 1 for a list of built in primitive types Optionally attributes may be initialized with a constant expression The expression has to be of a compatible type of the declared attribute of course See chapter 5 for the GRGEN NET types and expressions reference The AttributeOverwrite clause lets you overwrite initialization values for attributes of super classes The initialization values are evaluated in the order as they appear in the rule set file The following attribute declarations are illegal because of the order of evaluation of initial ization values CHAPTER 4 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 Attributes 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 using SomeModel 3 rule SomeRule al n1 NodeTypeA 5 n2 NodeTypeA ol hom ni n2 oul gt 122 s n3 NodeTypeB 9 negative 10 n3 el EdgeTypeA gt ni 11 if n3 a1 424n2 a1 12 L 3 negative 14 n4 Node NodeTypeB 15 n3 el EdgeTypeB gt n4 16 if typeof e1 gt EdgeTypeA is replace 19 nd NodeTypeC lt n1 gt 20 n3 e
66. 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 SS SE r lhs crrhs x Preservation SE lhs x Z def r Deletion 2 rhs r ran r Creation XT x T 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 4 1 Definition of the preservation morphism r 4 4 2 Specification Modes for Graph Transformation For the task of rewriting GRGEN NET provides two different modes A replace mode and a modify mode 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 replace graphlet Attribute calculations are no using occurrences In Example 11 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 betw
67. nown from common programming 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 to be implemented in version 2 0 Composing several rules with logical and iterative sequence control called graph rewrite sequences GRS including support for nested transactions Emitting user defined text to stdout during the rewrite steps e The rule application language GRSHELL supports Various methods for creation deletion input output of graphs nodes edges Stepwise and graphic debugging of rule application 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 NEI language of your choice e As of version 2 0 GRGEN NET s functionality will be available as an embedded exten sion to C like embedded SQL 1 3 System Overview Figure 1 1 gives an overview of the GRGEN NE T system components A graph rewrite system is defined by a rule set file grg and zero or more graph model description files gm It is generated
68. nsive matching problem GRGEN applies several novel heuristic optimizations According to Varr s benchmark VSV05 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 taking 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 We also support the double pushout approach DPO for explanation see CMR 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 nor to be partly im plemented by hand GRGEN NET Gei07 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
69. nstraint clause the retype operator lt gt and the allowed arrow tips for edges 4 2 Rules and Tests The structure of a rule set file is as follows RuleSet Ce aa O ur 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 aaa RuleDeclaration TestDeclaration ActionSignature RuleDeclaration exact induced Declares a single rewrite rule such as SomeRule It consists of a pattern part see Section 4 3 in conjunction with its rewrite modify part see Section 4 4 A test has no rewrite specifi cation It s intended to check whether and maybe how many times a pattern occurs see ActionSignature 28 Rule Set Language EXAMPLE 8 Some graphlets Z Noda 6 gt gt ke ek Noder 22 N er E lt cel stem n1 Node e2 Edge gt e3 Edge gt e4 Edge gt eb Edge gt n1 ni gt n2 Node il mmn And some illegal graphlets e Edge u 2 Would affect redirecting of edge e Mae he crea 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 4 3 for further information lt
70. o variables again The operator switches the rule to a test i e the rule application does not perform the rewrite part of the rule but only tests if a match exists The operator is a multi purpose flag In the GRSHELL see chapter 6 it dumps the matched graph elements to stdout in debug mode see section 6 3 it acts as a break point you are also able to use this flag for your own purposes when using GRGEN NET via its API interface see section 1 6 3 The sqare braces introduce a special kind of multiple rule application Every pattern match produced by the will be rewritten Be careful Its semantics is not equal to Rule Instead this operator collects all the matches first before starting rewritings In particular the semantics is unsafe i e one 42 Rule Set Language needs to avoid deleting a graph element that is bound by another match If Rule returns values the values of one of the executed rules will be returned VarAssignment S RewriteSequence cma false Variables can hold graph elements or boolean values Graph elments are initially assigned by the RuleExecution statement An VarAssignment rewrite term ist always true Table 4 4 lists operations of graph rewrite expressions at a glance First execute s afterwards execute t The sequence s t is success fully executed if s or t is successfully executed The same as s t but with lazy evaluation i e if s is successful t will no
71. olon separated pattern statements and a modify part or a rewrite part Tests contain only a pattern they are used to check for a certain pattern without doing any rewrite operation If a rule is applied GRGEN NET tries to find the pattern within a host graph for instance within the graph we created in section 2 3 Of course there could be several matches for a pattern GRGEN NET will choose one of them arbitrarily Figure 2 4 also shows the syntax x NodeType for nodes and e EdgeType gt for Edges which we have already seen in section 2 3 There are also statements like FinalState or EpsilonTransistion gt i e we are searching for a node of type FinalState resp an edge of type EpsilonTransition but we are not assigning these graph elements to a name like x or e above Defining of names is a key concept of the GRGEN NET rule sets names work as connection points between several pattern statements and between the pattern and the replace modify part As a rule of thumb If you want to do something with your found graph element define a name otherwise an anonymous graph element will do fine Also have a look at example 8 on page 28 for additional pattern specifications The difference between a replace part and a modify part is that a replace part deletes every graph element of the pattern which is not explicitly mentioned within its body The modify part in contrast deletes nothing by default but just adds or adjusts graph
72. on empty gt tp 21 s empty gt wv WriteValue 22 modify 1 23 delete h 24 wv RWHead gt tp 25 26 27 28 rule writeZeroRule 29 wv WriteZero rw RWHead gt tp TapePosition value gt tp 30 replace 31 WV rw gt tp zero gt tp 32 Le 33 34 35 rule writeOneRule 36 wv WriteOne rw RWHead gt tp TapePosition value gt tp 37 replace 38 WV rw gt tp one gt tp 39 Le 40 41 42 rule writeEmptyRule 43 wv WriteEmpty rw RWHead gt tp TapePosition value gt tp 44 replace 45 WV rw gt tp empty gt tp 46 Le 47 48 49 rule moveLeftRule 50 wv WriteValue moveLeft gt s State 7 2 Busy Beaver 13 51 wv h RWHead gt tp TapePosition lt r right ltp TapePosition 52 modify 1 53 delete h 54 s RWHead gt ltp 55 56 57 58 rule moveRightRule 59 wv WriteValue moveRight gt s State 60 wv h RWHead gt tp TapePosition r right gt rtp TapePosition 61 modify 62 delete h 63 s RWHead gt rtp 64 65 66 67 rule dontMoveRule 68 wv WriteValue dontMove gt s State 69 wv h RWHead gt tp TapePosition 70 modify 71 delete h ya s RWHead gt tp 73 74 75 76 rule ensureMoveLeftValidRule TT wv WriteValue moveLeft gt State 78 wv RWHead gt tp TapePosition 79 negative 80 tp lt right 81 Le 82 modify 1 83 tp lt right ltp TapePosition empty gt l
73. ource node type and target node type are not determined i e A lt gt B is equivalent to A gt B B gt A The arrow is used for undirected edges For arbitrary edges edges not inheriting from Edge or UEdge a connection assertion must not be specified Note that even though a connection assertion applies to the specified node types including their subtypes subtypes of the declaring edge are not taken into account However you are able to make use of the edge class hierarchy by using the keyword inherited The inherited assertion imports the connection assertions of the dzrect ancestors of the declaring edge This is a purely syntactical simplification i e the effect of using inherited is the same as copying connection assertions from direct ancestors by hand 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 gt 0 must hold Abbreviation for 0 Abbreviation for 1 Abbreviation for n n Abbreviation for 1 Table 3 1 GRGEN NET node constraint multiplicities AttributeDeclarations Expression AttributeOverwrite Attribute Type T Primitivelype 7 EnumTlype 22 Graph Model Language AttributeOverwrite Defines a node or edge attribute Possible types are enumeratio
74. pe Related Conditions 49 PrimaryExpr EEE _ KA Constant eet false 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 5 3 Type Related Conditions TypeExpr T ypeldent A type expression identifies a type and in terms of matching also its subtypes A 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 NodeOrEdge 50 Types and Expressions The following rule will add a reverse edge to a one way street rule oneway a Node x street gt y Node negative y typeof x gt a replace a ck y y typeof x gt a oO o ND a A O N e 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 type 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 ETN T1 Tn if typeof x lt T1 amp
75. phism 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 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 4 Introduction Pattern Graph Rewrite Graph Preservation Morphism r e SSSR Rul Match m H _ Hi Host Graph Result Graph Figure 1 3 Basic Idea of Graph Rewriting 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 U z to the empty host graph As 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 p T gt TODE Because of the uniqueness of the total and totally undefined morphism 1 6 The Tools 5 to H and get the new host graph H1 something like this What happened GRGEN NET has arbitrarily chosen one match out of the set of possible matches because x matches edg
76. rastructure 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 a 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 and imple mentation of GRGEN NE T a
77. ree lines per state and input symbol for updating cell value moving read write head respectively new sA_O WriteOne new sA empty gt sA_O new sA_O moveLeft gt sB new sA_1 WriteOne new sA one gt sA_1 new sA_1 moveLeft gt sD new sB_O WriteOne new sB empty gt sB_O new sB_O moveRight gt sC new sB_1 WriteEmpty new sB one gt sB_1 new sB_1 moveRight gt sE new sC_O WriteEmpty new sC empty gt sC_O new sC_O moveLeft gt sA new sC_1 WriteEmpty new sC one gt sC_1 new sC_1 moveRight gt sB new sD_O WriteOne new sD empty gt sD_O new sD_O moveLeft gt sE new sD_1 WriteOne new sD one gt sD_1 new sD_1 moveLeft gt sH new sE_O WriteOne new sE empty gt sE_O new sE_O moveRight gt sC new sE_1 Write ne Examples 7 2 Busy Beaver 79 s lnew SE one gt sE_1 621 Hew SE_1 moveLeft gt sC Our busy beaver looks like this 0 empty 1 RWHead 6 0ne SE D move Left 3 empty 4 move Left L Bsmt lt 10 move Right 18 moveLeft 18 empty 1B one 13 moveLeft 16 moveLeft 12 empty We have an initial host graph now The graph rewrite sequence is quite straight forward and generic to the Turing graph model Note that for each state the Empty One selection is unambiguous xgrs readOneRule readEmptyRule amp writeOneRule writeEmptyRule amp ensureMoveLeftValidRule en
78. resent in the host graph cf Sza05 N ACS must not be nested N ACS 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 general 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 4 4 Replace Modify Part 33 We specify a node x which is not connected to a node of type BadType x Node negative x 1 7 BadType WS N Because NACs have their own binding using NACs leads to specifications which might look a bit redundant Let s specify a singleton a node of type T which is the only one of this type The following specification is wrong it will never return a match X l negative yT Bw N e Instead we have to specify the complete forbidden pattern inside the NAC This is done by X T negative X viol G rw 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 4 4 Return Values Pattern Modifiers Additionally to modifiers that apply to a pattern as a whole you may also spec
79. ropolis A Ki N 2 Edge 1 Edge S AS _north highway ae af Lo 7 Be A5_south highway E AS_north highway ff ri 3 A rs Karlsruhe metropolis e N S f right side dumped with dump add node metropolis group 64 GrShell Language samp a Lag are 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 NodeType resp Ed de Tune In the following example river and jam are info tags A3 highway jam False m False AN South highway jam True Ba 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 6 2 6 Action Commands XGRS 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 6 3 Graphical Debugger 69 Lists all the rules of the loaded rule set their parameters and their return values Rules can return a set of graph elements actions S pacedParameters 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 6 4 GraphRewriteSequence Simple
80. 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 7 2 1 Graph Model The tape will be a chain of TapePosition nodes connected by right edges A 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 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 75 node class State edge class RWHead node class WriteValue node class WriteZero extends WriteValue node class WriteOne extends WriteValue node class WriteEmpty extends WriteValue edge class moveLeft edge class moveRight edge class dontMove 7 2 2 Rule Set Now the rule set We begin the rule set file Turing grg with 1 using TuringModel We n
81. s Frankfurt not specified gt SY En ee A A N CH Executes a command specific to the current backend If SpacedParameters is omitted a list of available commands will be displayed for the LGSP backend see Sections 6 4 6 2 3 Graph Manipulation Commands Graph manipulation commands alter existing graphs including creating and deleting graph elements and setting attributes 6 2 GRSHELL Commands 59 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 23 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 4 where we use names
82. s See Section 5 3 for the use of type expressions 4 1 1 Graphlets Graphlet GraphletNode sa Continuation A 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 5 line 7 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 n1 gt n2 contains 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 elements see Section 4 3 For instance v NodeTypel e EdgeType gt w NodeType2 selects some node of type NodeTypei that is conne
83. s of Resident VILLAGE and C to int we get the int value 501 which is assigned to E Moreover the semantics is as in C SAI 90 So the following holds RED 0 GREEN 1 BLUE 2 A 2 B 3 C 1 Dr OD and 508 The C like semantics of enum item declarations implies that multiple items of one enum type can be associated with the same same int value Moreover it implies that an enum item must not be used before its definition This also holds for items of other enum types meaning that the items of another enum type can only be used in the definition of an enum item when the other enum type is defined before the enum type currently defined 3 2 Type Declarations 19 ClassDeclaration ae keen 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 Ol VG WwW ND KA We adjust our map model and make city abstract abstract node class City Size int abstract node class AbandonedCity extends City node class Ghost Town extends AbandonedCity You will be able to create nodes of type GhostTown but not of type City or AbandonedCity However nodes of type GhostTown are also of type AbandonedCity as well as of type City and they have the attribute Size hence The keyword const indicates that rules may
84. s 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 NET a pleasant graph rewrite experience We hope you enjoy using GRGEN NET as much as we enjoy de veloping it If you find that any statement in this manual needs improvement we encourage you to contact the maintainer of GRGEN NET rubino ipd uni karlsruhe de Thank you for using GRGEN NET Karlsruhe in July 2007 the authors of GRGEN NET vi CONTENTS 1 Introduction 1 1 1 What is GRGEN NET 1 1 2 Features of GRGEN NET 1 1 3 System Overview 2 1 4 What is Graph E E 3 1 5 An Example 4 1 6 The Tools ee m a eee eee eae er lt 1 6 1 GrGen exe AN e vet ede a de ade 5 Mg Se GYG asdsa en ER a ee a a en 6 Ba DTL ee ee we 6 LOA JOP CC ee ee ee ar eee eee id T 2 Quickstart 9 2 1 Downloading amp Installing 9 2 2 Creating a Graph Model 10 2 3 Creating Graphs 10 2 4 The Rewrite Rules 12 2 5 Debugging and Output 14 3 Graph Model Language 15 3 1 Building Blocks a a ee u ur ee ew amp E sll Te a RR Eee ed 17 3 2 Type Declarations 17 4 Rule Set Language 23 4 1 Building Blocks Pee eeeeteeeeantee eae BO ee oo LL
85. sion 1 3 4 mygraph vcg File Edit View Navigate Layout Help Rans Ie XDA AAA HK AK E K 2 Transition Find Next Options 1 Transition i Root 6 Transition 1 FinalState 2 State F FinalState S StartFinalState 0 Transition Figure 2 5 A state machine without e transitions If everything is working fine you can delete the debug keyword in front of xgrs Maybe you want to save the resulting graph This is possible by typing dump graph mygraph vcg in the GRSHELL GRSHELL writes the graph in mygraph vcg into the current directory Files in VCG format are readable by YCOMP Feel free to browse the examples folder shiped with GRGEN NET and have a look at further capabilities of the software CHAPTER 3 GRAPH MODEL LANGUAGE The key features of GRGEN NET graph models as described by Gei et al GBG 06 KG07 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 GRGEN NET edge types can be directed and undirected Attributes Nodes and edges may 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 speci
86. st of currently available graphs Selects the current working graph This graph acts as host graph for graph rewrite sequences see also Sections 1 4 and 6 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 validate eg 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 58 GrShell Language We reuse a simplified version of the road map model from chapter 3 model Map node class city node class metropolis edge class street edge class highway connect metropolis gt metropolis o ND oa SG W N HM The node constraint on highway requires all the metropolises to be connected by highways Now have a look at the following graph A3 highway A5_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 metropoli
87. sureMoveRightValidRule amp 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 steps he takes about 8 5 seconds On a Pentium 4 3 2Ghz with 2GiB RAM 76 Examples 64 custom graph analyze_graph 65 custom actions gen_searchplan readOneRule readEmptyRule writeQneRule writeEmptyRule ensureMoveLeftValidRule ensureMoveRightValidRule moveLeftRule moveRightRule Let the beaver run xgrs readOneRule readEmptyRule amp writeOneRule writeEmptyRule amp ensureMoveLeftValidRule ensureMoveRightValidRule amp moveLeftRule moveRightRule APPENDIX A DEPRECATED SYNTAX This appendix describes deprecated GRGEN NE T constructs of versions prior to 1 4 The following constructs may or may not work with the current GRGEN NET release Support for such constructs will eventually be terminated A 1 Graph Model and Rule Set Language The graph model and the rule set were previously introduced by keywords GraphModel OT RuleSet These keywords are not used any more The name of a graph model resp a rule set is determinated by its file name In previous GRGEN NET versions the pattern was a syntactical block wi
88. t be executed First execute s afterwards execute t The sequence s amp t is success fully executed if s and t is successful The same as s amp t but with lazy evaluation Le if s fails t will not be executed First execute s afterwards execute t The sequence s t 19 success fully executed if s is successful or t successfully but not both i e this an XOR sequence Execute s transactionally Is Switch the result of s from successful to fail and vice versa lt op gt Flag the operator lt op gt as commutative 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 Rule Switches Rule to a test hRule This is the multi purpose flag when accessed from LIBGR Also used for graph dumping and break points Rule Rewrite every pattern match produced by the action Rule def Parameters Check if all the variables are defined true A constant acting as a successful match false A constant acting as a failed match Let s t u be graph rewrite sequences v w variable identifiers lt op gt l amp amp amp and n No Table 4 4 GRS expressions at a glance 4 6 Extended Graph Rewrite Sequences XGRS 43 EXAMPLE 18 The following example works on a hypothetical network flow We don t define all the rules nor the graph meta model It s just about the look and feel of the exec and emit statements
89. t dir is omitted a subdirectory tmpgrgenn within the current directory will be created The destination directory contains e printOutput txt a snapshot of stdout during program execution e NameModel cs the C source file s of the rule setModell d11 as sembly e NameActions_intermediate cs a preliminary version of the C source file of the rule set s actions assembly This file is for internal debug purposes only e NameActions cs the C source file of the rule setActions dl1 as sembly use Don t re generate C source files Instead use the files in existing dir to build the assemblies debug Compile the assemblies with debug information b Use the backend library backend dil default is LGSPBackend 0 Store generated assemblies in output dir Requires NET 2 0 or above or Mono 1 2 3 or above Java Runtime Environment 1 5 or above 1 6 2 GrShell exe The GRSHELL is a shell application of the LIBGR GRSHELL is 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 6 Usage mono grShell exe C lt commands gt lt grshell script gt Opens the interactive shell The GRSHELL will include and execute the commands in the optional list of grshell scripts usually grs files in the given order The grs suffixes may be omitted Options C Execute the quoted G
90. tes negative x State e Transition gt y State hom x y x doublette Transition gt y if typeof doublette typeof e if typeof e EpsilonTransition e Trigger doublette Trigger rule forwardTransition x State EpsilonTransition gt y State e Transition gt z State hom x y Z negative x exists Transition gt Z if typeof exists typeof e if typeof e EpsilonTransition e Trigger exists Trigger modify x forward typeof e gt z eval forward Trigger e Trigger rule addStartFinalState x StartState EpsilonTransition gt FinalState modify y StartFinalState lt x gt emit Start state x id mutated into a start and final state rule addFinalState x State EpsilonTransition gt FinalState if typeof x lt SpecialState modify y FinalState lt x gt rule removeEpsilonTransition EpsilonTransition gt replace Figure 2 4 Rule set for removing e transitions 13 14 Quickstart instance we don t want to forward just one e transition as forwardTransition would do we want to forward them all Such a rule composing is called graph rewrite sequence see section 4 6 We add the following line to our shell script removeEpsilons grs 1 debug xgrs checkStartState amp amp checkDoublettes amp amp lt forwardTransition addStartFinalState addFinalState removeEpsilonTransition
91. thin a rule RuleDeclaration ActionSignature The current version does not use the pattern keyword but expects the pattern statements to be placed as direct members of the rule block see sections 4 2 4 3 The pattern keyword will be used in GRGEN NE T version 2 0 for a different purpose A 2 Graph Rewrite Sequences GRS The non extended graph rewrite sequence was part of the GRSHELL The extended graph rewrite sequences XGRS are available within the GRSHELL as well as within the rule set language see section 4 6 GraphRewriteSequence SimpleRewriteSequence This executes the graph rewrite sequence SimpleRewriteSequence 17 78 Deprecated Syntax SimpleRewriteSequence a I SimpleRewriteSequence Parameters Parameters Table A 1 lists graph rewrite expressions at a glance The operators hold the following order of precedence starting with the lowest priority 5 amp A 2 Graph Rewrite Sequences GRS 79 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 rol
92. tp 84 Le 85 87 rule ensureMoveRightValidRule 88 wv WriteValue moveRight gt State 89 wv RWHead gt tp TapePosition 90 negative 91 tp right gt 92 Le 93 modify 94 tp right gt rtp TapePosition empty gt rtp 95 96 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 your model and the rule set with GrGen exe see Section 7 1 7 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 i select backend bin lgspBackend d11 o a nn OD A WB N H HM e MH re Hr RR bh Fi k L La kA O o nN DO a FP Go N e O 22 23 24 25 26 27 28 29 30 31 32 33 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 74 new graph lib lgsp TuringModel d11 Busy Beaver select actions lib lgsp TuringActions d11 Initialize tape new tp TapePosition Startposition new tp empty gt tp 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 new sA RWHead gt tp Transitions th
93. ttern modifiers Such modifiers add certain conditions to the applicability of a pattern The idea is to match only parts of the host graph that look more or less exactly like the pattern The level of exactness depends on the choosen modifier A modifier in front of the pattern keyword is equivalent to one modifier statement inside the pattern containing all the specified nodes including anonymous nodes Table 4 3 lists the modifiers with their semantics Example 16 explains the modifiers by small toy graphs Internally all the modifier annotated rules are resolved into equivalent rules in standard SPO semantics The semantics of the modifiers is mostly implemented by NACs In particular you might want to use such modifiers in order to avoid writing a bunch of NACs yourself The number of internally created NACs is bounded by O n for exact and dpo and by O n for induced respectively where n is the number of specified nodes 4 6 Extended Graph Rewrite Sequences XGRS Graph rewrite sequences are an imperative enhancement to the rule set language Graph rewrite sequences are syntactically expressed as expressions similar to boolean expressions Composing an expresiion out of single graph rewrite rules not only yields more complex host graph operations but also determines sort of a control flow by means of evaluation order of the operands Graph rewrite sequences have a boolean return value for a single rule true means the rule was

The GrGen User Manual

Contents

Download Pdf Manuals

Related Search

Related Contents