A XML Specification for Grrr Programs

Contribution to the University of Paderborn GT Exchange Formats Meeting

Peter Rodgers

Computing Laboratory
University of Kent

Below is an XML DTD and worked example to show how a Grrr program might be stored in an form that allows conversion to other graph transformation systems. This is GRXL draft version 0.1.

Grrr Home Page

A major consideration in the design of this specification was depth and consistency verses shallow readability. The XML DTD grammar forces each level to be explicitly marked up. For full extensibility and generality in the DTD this entails a large amount of markup for each graph transformation system stored. The alternative is to take a much shallower approach, as given here, where the important attributes are included explicitly in the ATTLIST at the highest reasonable level. This implies that any extra user defined attributes can only be included at a different conceptual level by using the attr element, and also that there is a degree of redundancy in the grammar definition. However, the shallow approach taken here allows for easier understanding of the resultant XML, and helps hand coding and editing.

 There are some clear advantages to using XML: tools, parsers, stability and visiblity. However, as a method for storing graph transformation information XML has some deficiencies. XML is a system for linear text markup, and as such storing graph and other structure information is not well catered for. Firstly, the notion of inheritance needs to be explicitly defined by a tree of links. Secondly, it does not contain a concept of constraints, not even implied via a typing system. So, for instance it is not possible to ensure that edges reference nodes in the same graph. Thirdly, XML markup is not very concise and where the grammar depth is great the storage overhead is significant.


 grxl.dtd


<!ELEMENT grxl (attr*, nodetype*, edgetype*, hostgraph*, transformation*)>
<!ATTLIST grxl
  id ID #IMPLIED>

<!ELEMENT nodetype (attr*)>
<!ATTLIST nodetype
  id ID #REQUIRED
  parent IDREF #IMPLIED
  shape CDATA #IMPLIED
  height CDATA #IMPLIED
  width CDATA #IMPLIED>

<!ELEMENT edgetype (attr*)>
<!ATTLIST edgetype
  id ID #REQUIRED
  parent IDREF #IMPLIED
  directed (true | false) "true">

<!ELEMENT hostgraph (attr*, node*, edge*)>
<!ATTLIST hostgraph
  id ID #REQUIRED>

<!ELEMENT transformation (attr*, rewrite*)>
<!ATTLIST transformation
  id ID #REQUIRED>

<!ELEMENT rewrite (attr*, lhsgraph, rhsgraph)>
<!ATTLIST rewrite
  id ID #REQUIRED>

<!ELEMENT lhsgraph (attr*, node*, edge*)>
<!ATTLIST lhsgraph
  id ID #REQUIRED>

<!ELEMENT rhsgraph (attr*, node*, edge*)>
<!ATTLIST rhsgraph
  id ID #REQUIRED>

<!-- match allows morphisms to be encoded -->

<!ELEMENT node (attr*)>
<!ATTLIST node
  id ID #REQUIRED
  type IDREF #IMPLIED
  match IDREF #IMPLIED
  label CDATA #IMPLIED
  xpos CDATA #IMPLIED
  ypos CDATA #IMPLIED
  variable (true | false) "false"
  negative (true | false) "false">

<!ELEMENT edge (attr*)>
<!ATTLIST edge
  id ID #REQUIRED
  type IDREF #IMPLIED
  match IDREF #IMPLIED
  begin IDREF #REQUIRED
  end IDREF #REQUIRED
  label CDATA #IMPLIED
  variable (true | false) "false"
  negative (true | false) "false">

<!-- attr has both a singleton attribute, plus attrelement to allow collections -->

<!ELEMENT attr (attrelement)*>
<!ATTLIST attr
  name CDATA #REQUIRED
  value CDATA #IMPLIED>

<!ELEMENT attrelement EMPTY>
<!ATTLIST attrelement
  name CDATA #REQUIRED
  value CDATA #IMPLIED>


Example: AddAge.xml


Host Graph


Transformation AddAge
The following XML codes the above program:

AddAge.xml

<?xml version = "1.0"?>

<!DOCTYPE grxl SYSTEM "grxl.dtd">

<grxl>

<nodetype
  id = "Top">
</nodetype>

<nodetype
  id = "Trigger"
  parent = "Top"
  shape = "rectangle"
  height = "20"
  width = "30">
</nodetype>

<nodetype
  id = "NonExecutable"
  parent = "Top">
</nodetype>

<nodetype
  id = "Data"
  parent = "NonExecutable"
  shape = "oval"
  height = "30"
  width = "30">
</nodetype>

<nodetype
  id = "Information"
  parent = "NonExecutable"
  shape = "oval"
  height = "20"
  width = "30">
</nodetype>

<edgetype
  id = "Function">
</edgetype>

<hostgraph
  id = "Start">
  <attr name = "step" value = "0"></attr>
   <node
      id = "hostn1"
      type = "Trigger"
      label = "AddAge"
      xpos = "60"
      ypos = "20">
    </node>
   <node
      id = "hostn2"
      type = "Information"
      label = "25"
      xpos = "30"
      ypos = "60">
    </node>
   <node
      id = "hostn3"
      type = "Information"
      label = "43"
      xpos = "120"
      ypos = "60">
    </node>
   <node
      id = "hostn4"
      type = "Data"
      label = "Harry"
      xpos = "30"
      ypos = "120">
    </node>
   <node
      id = "hostn5"
      type = "Data"
      label = "Fred"
      xpos = "120"
      ypos = "120">
    </node>
    <edge
      id = "hoste1"
      type = "Function"
      begin = "hostn4"
      end = "hostn2"
      label = "age">
    </edge>
    <edge
      id = "hoste2"
      type = "Function"
      begin = "hostn5"
      end = "hostn3"
      label = "age">
    </edge>
    <edge
      id = "hoste3"
      type = "Function"
      begin = "hostn5"
      end = "hostn4"
      label = "employs">
    </edge>
</hostgraph>
 

<transformation id = "AddAge">
  <rewrite id = "AddAge1">
    <lhsgraph id = "LHS1">
      <node
        id = "n1"
        type = "Trigger"
        label = "AddAge"
        xpos = "30"
        ypos = "30"
        variable = "false">
      </node>
      <node
        id = "n2"
        type = "Data"
        label = "X"
        xpos = "40"
        ypos = "60"
        variable = "true">
        <attr name = "once only" value = "yes"></attr>
      </node>
      <node
        id = "n3"
        type = "Information"
        label = "Y"
        xpos = "100"
        ypos = "30"
        variable = "true">
      </node>
      <edge
        id = "e1"
        type = "Function"
        begin = "n2"
        end = "n3"
        label = "age"
        variable = "false">
      </edge>
    </lhsgraph>

    <rhsgraph id = "RHS1">
      <node
        id = "n11"
        type = "Trigger"
        label = "AddAge"
        xpos = "30"
        ypos = "30"
        variable = "false">
      </node>
      <node
        id = "n12"
        type = "Data"
        label = "X"
        xpos = "40"
        ypos = "60"
        variable = "true">
        <attr name = "once only" value = "yes"></attr>
      </node>
      <node
        id = "n13"
        type = "Information"
        label = "Y"
        xpos = "100"
        ypos = "70"
        variable = "true">
      </node>
      <node
        id = "n14"
        type = "Trigger"
        label = "Add"
        xpos = "110"
        ypos = "20"
        variable = "false">
      </node>
      <node
        id = "n15"
        type = "Information"
        label = "1"
        xpos = "120"
        ypos = "70"
        variable = "true">
      </node>

      <edge
        id = "e11"
        type = "Function"
        begin = "n12"
        end = "n14"
        label = "age"
        variable = "false">
      </edge>
      <edge
        id = "e12"
        type = "Function"
        begin = "n14"
        end = "n13"
        label = "arg1"
        variable = "false">
      </edge>
      <edge
        id = "e13"
        type = "Function"
        begin = "n14"
        end = "n15"
        label = "arg2"
        variable = "false">
      </edge>
    </rhsgraph>
  </rewrite>

  <rewrite id = "AddAge2">
    <lhsgraph id = "LHS2">
      <node
        id = "n21"
        type = "Trigger"
        label = "AddAge"
        xpos = "30"
        ypos = "30"
        variable = "false">
      </node>
    </lhsgraph>

    <rhsgraph id = "RHS2">
    </rhsgraph>
  </rewrite>

</transformation>

</grxl>