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.
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>
<?XML VERSION="1.0"?>
<!DOCTYPE GTS SYSTEM "GTS.DTD">
<gts>
<rule id="r0">
<lhs>
<graph>
<node id="n0"/>
<node id="n1"/>
<edge id="e0" source="n0" target="n1"/>
<edge id="e1" source="n0" target="n1"/>
</graph>
</lhs>
<rhs>
<graph>
<node id="n2"/>
<node id="n3"/>
<edge id="e2" source="n2" target="n3"/>
</graph>
</rhs>
<map>
<nodemap from="n0" to="n2"/>
<nodemap from="n1" to="n3"/>
<edgemap from="e0" to="e2"/>
<edgemap from="e1" to="e2"/>
</map>
</rule>
</gts>
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.
<!ATTLIST edge source IDREF
#REQUIRED
&
nbsp;
target IDREF #REQUIRED>
by
<!ATTLIST edge source IDREFS #REQUIRED
&
nbsp;
target IDREFS #REQUIRED>
<!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>
<!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*)>
<!ELEMENT attr EMPTY>
<!ATTLIST attr name CDATA #REQUIRED
&
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.
<!ATTLIST node type CDATA #IMPLIED>
<!ATTLIST edge type CDATA #IMPLIED>
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:
<!ATTLIST node type IDREF #IMPLIED>
<!ATTLIST edge type IDREF #IMPLIED>
<!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.