6. Graph Grammars
In AToM3, graph grammars are a way to specify model manipulations.
Graph Grammars can be created visually with the commands under the Transformation
menu. The following is a UML Class Diagram showing the main parts of the
Graph Grammar module in AToM3.
Figure 1: UML Class Diagram of the Graph Grammar module.
Editing graph grammars is done by editing a GraphGrammarEdit
object. In this object you can specify a list of rules (objects of type
GGruleEdit),
and Initial and Final Actions. These actions are specified in Python, and
are evaluated before and after the graph grammar is executed. When you
finish creating a graph grammar and click on Transformation|Generate
code for Transformation, AToM3 generates the following classes:
-
A class which inherits from GraphGrammar.
This class contains the necessary code for the graph grammar to be executed
by a GraphRewritingSys
object.
-
For each rule defined, a class which inherits from GGrule.
These classes contain information about the graphs in LHSs, RHSs, applicability
conditions, etc.
And as stated before, GraphRewritingSys
class is responsible to execute a list of GraphGrammar
objects. That is, GraphGrammarEdit
and GGruleEdit are used
for modelling graph grammars, whereas GGrule,
GraphGrammar
and GraphRewritingSys
are used to execute graph grammars. The structure of these three latter
classes is explained in the following subsections.
6.1 The GraphRewritingSys class
As stated before, the GraphRewritingSys
class is responsible to execute a list of GraphGrammar
objects. Its structure is shown in the next figure:
Figure 2: Structure of the GraphRewritingSys class.
The meaning of the attributes are as follows:
-
parent: A pointer to the ATOM3 instance where
this object is being executed.
-
graph: An object of a child class of ASG,
which contains the model to which the graph grammars are going to be applied.
-
GraphGrammars: The list of graph grammars to be executed. A list of objects
of children classes of the GraphGrammar
class.
-
lastExecutedGG: the index of the graph grammar which is being executed.
-
lastExecutedRule: the index of the rule which was last executed.
-
stepByStep: Flag that indicates if the graph grammar should be executed
stopping after each rule match.
-
executionMode: One of either GraphRewritingSys.SEQ_RANDOM, GraphRewritingSys.SEQ_MANUAL
or GraphRewritingSys.PARALLEL. The value of this flag selects the
way in which a rule is to be applied in case it has made a match in multiple
places in a graph: in a random place, or the user chooses one interactively,
or in all the places which are disjoint.
-
graphics: it should be 0 in the case for example of a graph grammar acting
on a non-visible model.
The meaning of the method is as follows:
-
getCurrentGG: returns the name (a string) of the current graph grammar.
-
getLastRule: returns a string with the name and the priority of the last
executed rule.
-
evaluate: executes each rule of each graph grammar until none of them is
applicable. The arguments are as follows:
-
stepByStep is the flag that indicates if the GraphRewritingSys
should stop after each rule execution, moveEntities is a flag that
indicates if entities should be move according to their relatives positions
in LHSs and RHSs.
-
execute is either GraphRewritingSys.SEQ_RANDOM, GraphRewritingSys.SEQ_MANUAL
or GraphRewritingSys.PARALLEL.
-
graphics is a flag that should be 0 in the case for example of a
graph-grammar acting on a non-visible model.
-
executeRule: Executes current rule on the subgraph subGraph. The
rule to execute can also be given in parameter rule (None or an
instance of a child of GGrule).
-
doStep: This is the main method, which iterates trying to execute a rule
on the graph, until none of them is applicable. Graph grammar rules are
ordered by their priority (from lower to higher numbers), and whenever
a rule makes a match, the GraphRewritingSys
tries the first rule in the sequence again.
6.2 The GraphGrammar class
GraphGrammar class objects
are executed by GraphRewritingSys
objects on graphs (objects of children of the class ASG).
Its structure is shown in the next figure:
Figure 3: Structure of class GraphGrammar.
The meaning of the attributes is as follows:
-
rewritingSystem: A pointer to the GraphRewritingSys
where this object is going to be executed.
-
GGrules: A list of pointers to GGrule
children objects.
The meaning of the methods is as follows:
-
setGraphRewritingSystem: It takes a pointer to a GraphRewritingSys
object (rs) and assigns the self.rewritingSystem attribute as well
as calling the setGraphRewritingSystem method in the GGrule
objects.
-
initialAction and finalAction: are abstract methods which will contain
the Python code for initial and final actions.
6.3 The GGrule class
The GGrule class is the base
for all graph grammar rules defined by the user. Its attributes and its
main methods are shown in figure 4:
Figure 4: Structure of class GGrule.
The meaning of the attributes is as follows:
-
executionOrder: The priority assigned to this rule. A GraphRewritingSys
tries all the rules in sequence ordered by their priority from low to high
numbers.
-
LHS and RHS: Are objects instances of children classes of the the class
ASG.
-
graphGrammar: Pointer to the GraphGrammar
object which contains this rule.
-
graphRewritingSystem: Pointer to the GraphRewritingSys
object that is executing the rule.
The meaning of the methods is as follows:
-
matches: decides if there is a matching between node1 (host graph) and
node2 (L or R hand side of rule) (both of type ASGNode).
-
evaluate: tries to find a matching of the left hand side and graph (type
ASG).
-
condition: Abstract method which will contain a condition that must hold
for the rule to be applicable.
-
action: Abstract method which will contain the action to be performed when
the rule is applied
-
setGraphGrammar: Sets the reference (attribute graphGrammar) to the GG
that is contains the rule
-
getMatched: Given a (LHS) node, returns the matched node corresponding
to the graph identified by idGraph.
6.4 Example
Suppose we have modified the meta-model defined in the previous
example to add a relationship aRel connecting two aTest
entities.These modifications are shown in figure 5.
Figure 5: Adding a relationship to the example in section 1.
Then using the defined formalism we can draw model such as the following:
Figure 6: A simple model specified with the meta-model in figure
5.
As an example of building a graph grammar, we will define one to break
loops between two aTest entities. For this purpose, we just need
one rule with the following left and right hand sides:
Left Hand Side
|
Right Hand Side
|
Figure 7: A simple graph grammar rule to break
loops.
Observe how, in the LHS, when you specify "Any" as the matching
condition for an attribute, and that attribute is being shown in the canvas,
it appears labeled as "<ANY>". In the RHS, you have three posibilities
to assign values to attributes:
-
Specify one just by typing it into the attribute's widget.
-
Copy it from the node with the same label from the LHS by selecting te
appropriate checkbutton. In this case, if the attribute is being shown
in the canvas, it will appear with the label "<COPIED>". We have specified
the attribute aNumber in the nodes of the RHS to be copied, but
they do not appear in the canvas. We have also copied the aString
attrubte of node 3 to be copied.
-
Specify the value using Python code. In this case, if the attribute is
being shown in the canvas, it will appear with the label "<SPECIFIED>".
This is what we have done in the example for the attribute aString
(which is of type ATOM3String).
This is the Python code which calculates the new attribute's value if the
rule gets executed:
n3 = self.getMatched( graphID, self.LHS.nodeWithLabel(3))
return mySelf.aString.toString()+" :: "+n3.aString.toString()
First of all, you have to keep in mind that this method will be added to
a class that AToM3 will generate, and that this class inherits
from GGrule (in fact this is
not what really happens, the method is added 'on the fly' by GGrule directly
from the string you have typed, but for practical matters you can think
of it as a new method). The method is passed the following parameters:
self,
graphID, mySelf, atom3i.Where:
-
graphID is a parameter which identifies the current graph morphism,
you usually will not do anything with it except pass it as parameter to
the method getMatched of GGrule.
-
mySelf is a pointer to the object which you are specifying the code
for.
-
atom3i: is the instance of the ATOM3 class which is executing this
graph grammar.
What the previous Python code does is to search for the node 3, and return
the concatenation of the values of their aString attribute. Notice
that the return value of this method is what is going to be assigned to
the attribute. Other important thing is that we do not want the value of
attribute
aString in node number 3 in LHS, but the value of the
node which has made a match in the host graph. That is why we use the function
getMatched.
When you click on Transformation|Generate code for Transformation
two Python files are generated in our case:
-
The first one contains the class which inherits from GraphGrammar.
This file is named as the name you specified in the dialog window to fill
the GraphGrammarEdit
object. In our example, the file is called loopBreaker.py.
This class builds the list with all the rules in the constructor and has
the methods with the initial and the final action. Both methods receive
graph
as the only parameter, which is the host graph to which the graph grammar
will be executed.
-
The other one contains a class which inherits from GGrule.
We only generate one file as we have only defined one rule in the graph
grammar. The file is named as the name you specified in the rule. In our
case the file is named break_loop.py.
This class creates the LHSs and RHSs graphs in the constructor, and has
two methods which contain the condition and the action. Both methods have
the same signature, for example:
def condition(self, graphID, isograph, atom3i):
Where graphID has the meaning stated before. isograph is
a tuple containing the nodes (children from ASGNode) that compose
the subgraph in the host graph which has made a matching with this rule.
atom3i
is an instance of the ATOM3 class. Note that
no method is generated for the specification in the form of Python code
of attribute values of nodes in RHSs. As explained before, this is done
on the fly directly from the string the user type. Of course this has the
implication that no syntax checking is performed on the code you have entered!.
Note also that when you edit the RHS of a rule, a button appears in the
user interface ("copy LHS") that allows you to copy the current
graph in the LHS. The following figure shows the result of the application
of the previous graph grammar to the model in figure 6:
Figure 8: Result of the application of the previous graph grammar.
Maintained by Juan de Lara.
Last modified 25 July 2002.
Programming