A Simple XML Exchange Format for Graph Transformation

Gabriel Valiente

Technical University of Catalonia
Department of Software

APPLIGRAPH Subgroup Meeting on Exchange Formats for Graph Transformation, Paderborn University, Germany, September 5-6, 2000


The need for a common exchange format for graph transformation based on XML has been a major conclusion of the panel on the perspectives of graph transformation that took place during the Joint APPLIGRAPH and GETGRATS Workshop on Graph Transformation Systems, held in Berlin in March 2000.

Design Goal

Previous proposals evolved from the attempt to store a program for a particular graph transformation system in XML format. While the Berlin Proposal is based on AGG, the Kent Proposal is based on Grrr, and the Koblenz Proposal has a clear PROGRES flavor.

The main design goal of the present Barcelona Proposal is simplicity. As will (hopefully) become clear from the discussion below, taking, say, the minimum common XML data supermodel for all existing graph transformation systems and taking also future graph transformation systems (will ever GRACE get incarnation) as well as future uses into account, is perhaps too ambitious a goal to be reached in the short or mid term. The maximum common XML data submodel for all existing graph transformation systems could be adopted instead, agreeing upon those features (elements and attributes) considered to be essential and leaving out additional features which, although important for particular applications, are not essential from the point of view of software exchange within the graph transformation community.

The XML Data Model

The XML data model proposed as exchange format for graph transformation is described in the sequel in a literate programming style, combining code and documentation.

In its simplest form, a graph transformation system consists of zero or more graphs followed by zero or more graph transformation rules.

<!ELEMENT gts     (graph*, rule*)>

A graph has an optional identifier and consists of a sequence of nodes followed by a sequence of edges.

<!ELEMENT graph   (node*, edge*)>
<!ATTLIST graph   id     ID    #IMPLIED>

A node has a mandatory identifier and an optional label string.

<!ELEMENT node    EMPTY>
<!ATTLIST node    id     ID    #REQUIRED
           & nbsp;      label  CDATA #IMPLIED>

An edge has a mandatory identifier, mandatory references to the source and target node, and an optional label string.

<!ELEMENT edge    EMPTY>
<!ATTLIST edge    id     ID    #REQUIRED
           & nbsp;      source IDREF #REQUIRED
           & nbsp;      target IDREF #REQUIRED
           & nbsp;      label  CDATA #IMPLIED>

A graph transformation rule has an optional identifier and consists of a left-hand side graph, a right-hand side graph, and a map of the former into the latter.

<!ELEMENT rule    (lhs, rhs, map)>
<!ATTLIST rule    id     ID    #IMPLIED>

<!ELEMENT lhs     (graph)>

<!ELEMENT rhs     (graph)>

A map (representing a graph morphism) consists of a sequence of node correspondences followed by a sequence of edge correspondences. Notice that the latter is needed because it cannot always be obtained from the former in a unique way, for instance when dealing with multigraphs or when the notion of subgraph underlying the graph transformation approach is not that of induced subgraph.

<!ELEMENT map     (nodemap*, edgemap*)>
<!ATTLIST map     id     ID    #IMPLIED>

<!ELEMENT nodemap EMPTY>
<!ATTLIST nodemap from   IDREF #REQUIRED
           & nbsp;      to     IDREF #REQUIRED>

<!ELEMENT edgemap EMPTY>
<!ATTLIST edgemap from   IDREF #REQUIRED
           & nbsp;      to     IDREF #REQUIRED>

A Toy Example

The following XML text encodes a sample graph transformation rule using the proposed DTD. Can you figure out what it is supposed to do?

<?XML VERSION="1.0"?>
  <rule id="r0">
    <node id="n0"/>
    <node id="n1"/>
    <edge id="e0" source="n0" target="n1"/>
    <edge id="e1" source="n0" target="n1"/>
    <node id="n2"/>
    <node id="n3"/>
    <edge id="e2" source="n2" target="n3"/>
    <nodemap from="n0" to="n2"/>
    <nodemap from="n1" to="n3"/>
    <edgemap from="e0" to="e2"/>
    <edgemap from="e1" to="e2"/>

It makes a multigraph simple by removing parallel edges. Okay, under a particular approach to graph transformation and under certain application conditions, but in the realm of XML (only | mostly) syntax is dealt with.

Open Questions


Should only multigraphs be encompassed by the XML data model, or also hypergraphs, relations, algebras, ...? The Berlin Proposal covers the CS notion of a hypergraph by a simple extension, namely replacing

<!ATTLIST edge    source IDREF  #REQUIRED
           & nbsp;      target IDREF  #REQUIRED>


           & nbsp;      target IDREFS #REQUIRED>

Deep or Shallow

How shallow should the XML data model be? For instance, the declarations

<!ELEMENT lhs     (graph)>
<!ELEMENT rhs     (graph)>

could be replaced by

<!ELEMENT lhs     (node*, edge*)>
<!ELEMENT rhs     (node*, edge*)>

In the same vein, graph morphisms are represented by node and edge correspondences within a separate element:

<!ELEMENT map     (nodemap*, edgemap*)>
<!ELEMENT nodemap EMPTY>
<!ATTLIST nodemap from   IDREF #REQUIRED
           & nbsp;      to     IDREF #REQUIRED>
<!ELEMENT edgemap EMPTY>
<!ATTLIST edgemap from   IDREF #REQUIRED
           & nbsp;      to     IDREF #REQUIRED>

as done in the Berlin Proposal, while they are modeled in the Kent Proposal by optional attributes of nodes and edges:

<!ATTLIST node    match  IDREF #IMPLIED>
<!ATTLIST edge    match  IDREF #IMPLIED>


Regarding layout of graphs, the essential information should include at least the coordinates of the center of each node in a certain coordinate system. Now, further information to be associated to the nodes and edges is restricted only by imagination. For the sake of comparison, the additional information used in LEDA could be encoded as follows:

<!ENTITY % color "( black | white | red | green | blue | yellow | violet |
           & nbsp;        orange | cyan | brown | pink | green2 | blue2 |
           & nbsp;        grey1 | grey2 | grey3 | ivory | invisible )">

<!ENTITY % position "( central_pos | northwest_pos | north_pos | northeast_pos |
           & nbsp;           east_pos | southeast_pos | south_pos | southwest_pos | west_pos )">

<!NOTATION xpm SYSTEM "sxpm">

<!ENTITY algosol         SYSTEM "LEDA/pixmaps/algosol.xpm"         NDATA xpm>
<!ENTITY earth           SYSTEM "LEDA/pixmaps/earth.xpm"        &nb sp;  NDATA xpm>
<!ENTITY leda            SYSTEM "LEDA/pixmaps/leda.xpm"        &nbs p;   NDATA xpm>
<!ENTITY leda_book       SYSTEM "LEDA/pixmaps/leda_book.xpm"       NDATA xpm>
<!ENTITY leda_icon       SYSTEM "LEDA/pixmaps/leda_icon.xpm"       NDATA xpm>
<!ENTITY tintin          SYSTEM "LEDA/pixmaps/tintin.xpm"        &n bsp; NDATA xpm>
<!ENTITY win_icon        SYSTEM "LEDA/pixmaps/win_icon.xpm"        NDATA xpm>
<!ENTITY win_icon1       SYSTEM "LEDA/pixmaps/win_icon1.xpm"       NDATA xpm>
<!ENTITY win_small_icon  SYSTEM "LEDA/pixmaps/win_small_icon.xpm"  NDATA xpm>
<!ENTITY win_small_icon1 SYSTEM "LEDA/pixmaps/win_small_icon1.xpm" NDATA xpm>

<!ATTLIST node position         NMTOKENS #REQUIRED
           & nbsp;   shape            ( circle_node | ellipse_node | square_node | rectangle_node )
           & nbsp;           &nbs p;        "circle_node"
           & nbsp;   width            NMTOKEN "20"
           & nbsp;   height           NMTOKEN "20"
           & nbsp;   color            ( %color; ) "ivory"
           & nbsp;   pixmap           ENTITY #IMPLIED
           & nbsp;   border_color     ( %color; ) "black"
           & nbsp;   border_width     NMTOKEN "1"
           & nbsp;   label_type       ( no_label | user_label | data_label | index_label ) "index_label"
           & nbsp;   user_label       CDATA  #IMPLIED
           & nbsp;   label_position   ( %position; ) "central_pos"
           & nbsp;   label_color      ( %color; ) "black">

<!ATTLIST edge shape            ( poly_edge circle_edge | bezier_edge | spline_edge ) "poly_edge"
           & nbsp;   bends            NMTOKENS #IMPLIED
           & nbsp;   direction        ( undirected_edge | directed_edge | redirected_edge | bidirected_edge )
           & nbsp;           &nbs p;        "directed_edge"
           & nbsp;   width            NMTOKEN "1"
           & nbsp;   color            ( %color; ) "black"
           & nbsp;   style            ( solid | dashed | dotted | dashed_dotted ) "solid"
           & nbsp;   label_type       ( no_label | user_label | data_label | index_label) "no_label"
           & nbsp;   user_label       CDATA #IMPLIED
           & nbsp;   label_position   ( %position; ) "central_pos"
           & nbsp;   label_color      ( %color; ) "black"
           & nbsp;   slider_positions NMTOKENS #IMPLIED>

A general XML data model covering all the features used for representing graphs and graph transformation rules in ( all | most ) existing graph drawing and graph transformation tools, as well as in other applications where graphs are used, seems too ambitious a goal to be reached in the short or mid term. A more pragmatic stance is needed, perhaps agreeing upon a reasonable subset of additional information that could be exchanged.

The solution adopted in the Koblenz Proposal is twofold. On the one hand, any number of attributes may be defined for a node or an edge:

<!ELEMENT node (attr*)>
<!ELEMENT edge (attr*)>
           & nbsp;   value CDATA #REQUIRED>

The same use of attributes is found in the Berlin Proposal and also in the Kent Proposal, in which an attribute is allowed to link to a sequence of further attributes, something that does not seem to be necessary given that always sequences of attributes are used.

On the other hand, in the Koblenz Proposal the use of graph schemata is advocated, although the same structural information could be represented by an extended notion of typing.


The notion of type underlying the Koblenz Proposal could be encoded by an optional string attribute of nodes and edges:


while in the Berlin Proposal and also in the Kent Proposal the type of a node or edge is an optional link to a type element, which associates further attributes with the node or edge. Essentially:

<!ELEMENT nodetype   EMPTY>
<!ATTLIST nodetype   (attr*)>
<!ELEMENT edgetype   EMPTY>
<!ATTLIST edgetype   (attr*)>

While the latter approach allows reuse of common attributes, it requires them to be distinguished and assigned a unique identifier.


Last, but not least, modules are only mentioned in the Berlin Proposal and they are not further considered.