Comparison between XML to SVG Transformation Mechanisms

The GraphML use case

Christophe Jolif
Software Architect
ILOG S.A.
France
cjolif@ilog.fr
http://www.ilog.com

Biography

Christophe Jolif is a Software Architect mainly working on the ILOG JViews Component Suite, the ILOG Java technology based visualization framework. He has been working for ILOG since 1997 and is the company representative to the SVG (Scalable Vector Graphics) W3C Working Group since 1999. He has been involved in several SVG related developments including the SVG import and export features of the ILOG JViews Graphics Framework and the Batik project at Apache.


Abstract


This paper compares some of the possibilities that exist to visualize data from a given XML format inside an SVG user agent, taking the example of GraphML a format for describing graphs; that is, a set of nodes connected by edges. After describing the different alternatives to transform the XML to SVG , it concludes on the advantages and drawbacks of the different solutions and how several of them can be mixed to overcome their limitations.


Table of Contents


GraphML and SVG in a nutshell
GraphML to SVG using XSLT
     Portable XSLT
     Extended XSLT
GraphML to SVG using Java Transformation
GraphML inside the SVG using SVG extension mechanisms
     Batik Extension Mechanism
     Rendering Custom Content Mechanism
Conclusion
Footnotes
Acknowledgements
Bibliography

As XML (eXtensible Markup Language) formats become more and more widespread, a web developer has a high probability of using XML at both extremities of his development workflow. If he needs rich display on his client he will use SVG , an XML grammar for vector graphics, for building the web user interface to his business data. The data themselves will probably be provided through an XML document using a business oriented XML grammar. Taking as an example the workflow monitoring or modeling business, the data could be provided using the BPML (Business Process Modeling Language) XML language that would be translated to SVG in order to display the workflow as a graph on the end user web client.

The purpose of this paper is to present to developers the alternatives they have when transforming business XML data to SVG for their presentation to the end user. In order to avoid sticking to a particular industry (such as the workflow one), which would require in-depth explanation of its language, a more abstract XML format will be used that is able to describe graphs, that is a set of nodes connected by edges (and thus able to represents workflows): the GraphML format. GraphML could easily be seen as a kind of intermediary format in-between the workflow XML document and the final SVG document. On the contrary of a lot of conversions from one XML grammar to another one, these two examples ( BPML and GraphML) are particularly interesting use cases because they are not straightforward transformations, they require more than a mapping from one format's XML elements to the other one's. For example, BPML (or GraphML) only provides information about the workflow (or graph) structure and not the positioning or visual representation of the workflow activities (or graph nodes). This means that the conversion will have to take this into account and organize the activities (or nodes) on the screen such that they are presented in a usable manner to the end user without being able to get that information from the original data.

GraphML and SVG in a nutshell

GraphML was first introduced during the 2000 Graph Drawing Symposium and later specified in [GraphML] . It is described as an XML-based comprehensive and easy-to-use file format for graphs. It provides an advanced set of structural properties to describe graphs including directed or undirected graphs, hyper and nested graphs. A typical GraphML file will contain a set of nodes and edges defining a graph:

<graph edgedefault="directed">
  <desc>GraphML sample</desc>
  <node id="n1"/>
  <node id="n2"/>
  <node id="n3"/>
  <node id="n4"/>
  <edge source="n1" target="n2"/>
  <edge source="n1" target="n3"/>
  <edge source="n2" target="n4"/>
  <edge source="n2" target="n4" directed="false"/>
</graph>

The root element is the 'graph' element that accepts an edgedefault attribute. This attribute can be set to directed or undirected values. When edges are directed, as in the example above, it means that they are oriented. The contents of the 'graph' element is made of four nodes defined by 'node' elements and four edges defined by 'edges' elements. The edges define their source and target nodes by referencing IDs of the nodes. The directed attribute on a particular 'edge' allows to override the global property set on the 'graph' element.

GraphML also provides a set of elements to specify additional data on GraphML elements. This aspect of GraphML will not be developed here, but theoretically this could be leveraged to add data inside the GraphML that would give hints to the transformation process.

The SVG language, specified by [SVG 1.1] , allows to describe two-dimensional vector and mixed vector/raster graphics in XML . That is why it is a good candidate for displaying the graphical representation of a GraphML graph. There are several possibilities for representing the graph described above in SVG , one of them being the following SVG fragment:

<defs>
  <marker id="arrow" refX="5" refY="5" markerUnits="userSpaceOnUse" markerWidth="10" markerHeight="10" orient="auto">
    <path fill="black" d="M0 0 10 5 0 10z" />
  </marker>
</defs>
<g id="n1">
  <rect x="10" y="-100" width="100" height="100" fill="silver" />
  <text x="45" y="-40" style="font-size:24;font-weight:bold">N1</text>
</g>
<g id="n2">
  <rect x="130" y="-100" width="100" height="100" fill="silver" />
  <text x="165" y="-40" style="font-size:24;font-weight:bold">N2</text>
</g>
<g id="n3">
  <rect x="10" y="20" width="100" height="100" fill="silver" />
  <text x="45" y="80" style="font-size:24;font-weight:bold">N3</text>
</g>
<g id="n4">
   <rect x="130" y="20" width="100" height="100" fill="silver" />
   <text x="165" y="80" style="font-size:24;font-weight:bold">N4</text>
</g>
<polyline style="marker-end:url(#arrow)" points="110-50 130-50" />
<polyline style="marker-end:url(#arrow)" points="60 0 60 20" />
<polyline style="marker-end:url(#arrow)" points="180 0 180 20" />
<polyline points="185 0 185 20" />

That piece of SVG would be rendered by an SVG user agent as:

first.png
The four nodes are represented by the four 'g' elements that contain a rectangle ('rect') and a label ('text'). The edges are represented by the 'polyline' elements that are drawn from their source node to their target node. Directed edges are drawn with an arrow marker for defining the orientation of the edge.

The transformation from the original GraphML file to the SVG file can be split in two main tasks to achieve:

  1. The transformation of 'node' elements to 'g' elements and 'edge' elements to 'polyline' elements with their styling attributes. This transformation fits well the usual stylesheet mechanisms of XSLT (XSL Transformation) and CSS (Cascading Style Sheets) and can be achieved very easily.
  2. The positioning of the nodes and edges to avoid them being displayed on top of each other. This transformation is not so straightforward, because the conversion mechanism will have to determine by itself which are the best (or the good enough) positions for the nodes and the edges. Depending on the type of the graph and on the expected quality of the result, this operation may be compute intensive and may require programming paradigms that are not supported by all transformation mechanisms.

GraphML to SVG using XSLT

When doing transformations from one XML format to another, the first solution that comes to mind is to use the XSLT mechanism defined by a W3C Recommendation ( [XSLT] ).

This section first describes how to transform a simple GraphML example in SVG using portable XSLT . It then explains how XSLT can be extended to simplify the XSLT stylesheet needed for the transformation.

Portable XSLT

If supported by the user agent, it is possible to put a Processing Instruction on top of the SVG file to ask the user agent to pre-process it with an XSLT processor. For example, sending the following file to the user agent will first apply the graphml2svg XSLT stylesheet before displaying the result:

<?xml-stylesheet type="text/xsl" href="graphml2svg.xslt"?>
<graph edgedefault="directed">
  <node id="n1"/>
  <node id="n2"/>
  <node id="n3"/>
  <node id="n4"/>
  <node id="n5"/>
  <edge source="n1" target="n2"/>
  <edge source="n1" target="n5"/>
  <edge source="n1" target="n3"/>
  <edge source="n2" target="n4"/>
</graph>

The XSLT stylesheet can also be applied on the server side, calling the server XSLT processor with the stylesheet and the GraphML file as parameter.

For a GraphML file similar to the one above (i.e. without nested 'graph' elements), iterating over the nodes and the edges is enough and so the first conversion task (see Paragraph 11 ) can be achieved with a stylesheet such as the following:

    
<xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform" xmlns="http://www.w3.org/2000/svg">
 <xsl:output method="xml" version="1.0" encoding="UTF-8" indent="yes"/>
 <xsl:template match="graph">
   <!-- when finding a 'graph' element, create the 'svg' root and its 'defs' section -->
   <svg>
     <defs>
       <marker id="arrow" refX="5" refY="5" markerUnits="userSpaceOnUse" markerWidth="10" markerHeight="10" orient="auto">
         <path fill="black" d="M0 0 10 5 0 10z"/>
       </marker>
     </defs>
     <!-- for each 'node' create a 'g' element with its contents -->
     <xsl:for-each select="node">
       <g>
         <rect width="100" height="100" fill="silver"/>
         <text style="font-size:24;font-weight:bold">
           <xsl:value-of select="@id"/>
         </text>
       </g>
     </xsl:for-each>
     <!-- for each 'edge' create a 'line' with the arrow if it is a 'directed' edge -->
     <xsl:for-each select="edge">
       <line>
         <xsl:if test="not(@directed='false')">
           <xsl:attribute name="style">marker-end:url(#arrow)</xsl:attribute>
         </xsl:if>
       </line>
     </xsl:for-each>
   </svg>
 </xsl:template>
</xsl:stylesheet>

With this stylesheet version, the style of the nodes and edges is hardcoded in the XSLT , which may be annoying for later modification of the style without changing the structure of the generated SVG . Leveraging the ability to use CSS inside SVG , the XSLT can reference an external CSS file for defining nodes and edges properties, which allows more flexibility for changing the style afterwards:

 <xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform" xmlns="http://www.w3.org/2000/svg">
   <xsl:output method="xml" version="1.0" encoding="UTF-8" indent="yes"/>
   <xsl:template match="graph">
     <!-- first give a CSS reference for the generated SVG -->
     <xsl:processing-instruction name="xml-stylesheet">type="text/css" href="default.css"</xsl:processing-instruction> 
     <svg>
       <defs>
         <marker id="arrow" refX="5" refY="5" markerUnits="userSpaceOnUse" markerWidth="10" markerHeight="10" orient="auto">
           <path class="edge" d="M0 0 10 5 0 10z"/>
         </marker>
       </defs>
       <xsl:for-each select="node">
         <!-- give to the 'g' the node class for styling -->
         <g class="node">
           <rect width="100" height="100"/>
           <text>
             <xsl:value-of select="@id"/>
           </text>
         </g>
       </xsl:for-each>
       <xsl:for-each select="edge">
         <!-- give to the 'line' the edge class for styling -->
         <line class="edge">
           <xsl:if test="not(@directed='false')">
             <!-- if the edge is directed add the directed CSS class -->
             <xsl:attribute name="class">egde directed </xsl:attribute>
           </xsl:if>
         </line>
       </xsl:for-each>
     </svg>
   </xsl:template>
 </xsl:stylesheet>

The contents of the default.css stylesheet to be used with the previous XSLT depends on the exact expected rendering. For the rectangle of the 'node' to be filled with a silver color, the label to use a 24 size font in bold, and the 'edge' to be filled with black:

.node > rect {
  fill:silver;
}
.node > text {
  font-size:24;
  font-weight:bold;
}
.edge {
  fill:black;
}

For the edges that also have the directed CSS class, use an arrow for their marker-end property:

.edge.directed {
  marker-end:url(#arrow);
}

However a more complex XSLT stylesheet is needed for positioning the nodes and edges. Working only on a directed graph representing a single rooted tree (as in the GraphML example above), it is possible to use the following stylesheet (based on the previous one) that implements a naive tree algorithm:

<xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform" xmlns="http://www.w3.org/2000/svg">
  <xsl:output method="xml" version="1.0" encoding="UTF-8" indent="yes"/>

  <!-- for a 'graph' element, creates an 'svg' element -->
  <xsl:template match="graph">
  <!-- first give a CSS reference for the generated SVG -->
    <xsl:processing-instruction name="xml-stylesheet">type="text/css" href="default.css"</xsl:processing-instruction> 
    <svg>
      <!-- defs section for the arrow -->
      <!-- ... -->
      <!-- recurse 'node' elements of the graph to find graph root -->
      <xsl:apply-templates select="node"/>
    </svg>
  </xsl:template>

  <!-- recurse 'node' element to find graph root -->
  <xsl:template match="node">
    <!-- check if the first 'edge' has current 'node' as target -->
    <xsl:apply-templates select="../edge[1]">
       <xsl:with-param name="n" select="."/>
    </xsl:apply-templates>
  </xsl:template>
  
  <!-- check if a 'node' ($n) is a target of the current 'edge' -->
  <xsl:template match="edge">
    <xsl:param name="n">null</xsl:param>
    <!-- if the 'node' is not a target of the current 'edge' -->
    <xsl:if test="not(@target=$n/@id)">
      <!-- advance to the next edge -->
      <xsl:apply-templates select="following-sibling::edge[position()=1]">
        <xsl:with-param name="n" select="$n"/>
      </xsl:apply-templates>
      <!-- if all edges have been queried  -->
      <xsl:if test="not(following-sibling::edge[position()=1])">
        <!-- the 'node' ($n) is the root, create it -->
        <xsl:call-template name="create-node">
          <xsl:with-param name="n" select="$n"/>
        </xsl:call-template>
      </xsl:if>
    </xsl:if>
  </xsl:template>
  
  <!-- transform a 'node' to SVG and recurse trough its children -->
  <xsl:template name="create-node">
    <xsl:param name="n">null</xsl:param>
    <xsl:param name="level">0</xsl:param>
    <xsl:param name="count">0</xsl:param>
    <xsl:param name="edge">null</xsl:param>
    <xsl:param name="x1">0</xsl:param>
    <xsl:param name="y1">0</xsl:param>
    <!-- some helpers -->
    <xsl:variable name="side" select="1-2*($count mod 2)"/>
    <xsl:variable name="x" select="$level*150"/>
    <xsl:variable name="y" select="$y1 - 50+$side*ceiling($count div 2)*150"/>
    <!-- create the 'node' itself and position it -->
    <g class="node">
      <rect x="{$x}" y="{$y}" width="100" height="100"/>
      <text text-anchor="middle" x="{$x+50}" y="{$y+55}">
        <xsl:value-of select="$n/@id"/>
      </text>
    </g>
    <!-- if there is an 'edge' ($edge) draw it -->
    <xsl:if test="$edge!='null'">
      <!-- the 'edge' position goes from previous 'node' position to $n one -->
      <line class="edge" x1="{$x1}" y1="{$y1}" x2="{$x}" y2="{$y+50}">
        <xsl:attribute name="style">marker-end:url(#arrow)</xsl:attribute>
      </line>
    </xsl:if>
    <!-- now that the 'node' is created, recurse to children through edges -->
    <xsl:call-template name="query-edge">
      <xsl:with-param name="edge" select="$n/../edge[@source=$n/@id][1]"/>
      <xsl:with-param name="x1" select="$x+100"/>
      <xsl:with-param name="y1" select="$y+50"/>
      <xsl:with-param name="n" select="$n"/>
      <!-- going to the upper level, increment level -->
      <xsl:with-param name="level" select="$level+1"/>
      <!-- going to the first child, set counter to 0 -->
      <xsl:with-param name="count" select="0"/>
    </xsl:call-template>
  </xsl:template>
  
  <!-- recurse a 'node' ($n) edges to find 'node' children -->
  <xsl:template name="query-edge">
    <xsl:param name="edge">null</xsl:param>
    <xsl:param name="x1">0</xsl:param>
    <xsl:param name="y1">0</xsl:param>
    <xsl:param name="n">null</xsl:param>
    <xsl:param name="level">0</xsl:param>
    <xsl:param name="count">0</xsl:param>
    <xsl:variable name="target" select="$edge/@target"/>
    <!-- if there is an 'edge' -->
    <xsl:if test="$edge!='null'">
      <!-- go down the tree, create the 'node' of the 'edge' target -->
      <xsl:call-template name="create-node">
        <xsl:with-param name="n" select="$edge/../node[@id=$target]"/>
        <xsl:with-param name="level" select="$level"/>
        <xsl:with-param name="count" select="$count"/>
        <xsl:with-param name="edge" select="$edge"/>
        <xsl:with-param name="x1" select="$x1"/>
        <xsl:with-param name="y1" select="$y1"/>
      </xsl:call-template>
      <!-- go to the next 'edge' that has also the 'node' ($n) has source -->
      <xsl:variable name="next-edge" select="$edge/following-sibling::edge[position()=1][@source=$n/@id]"/>
      <xsl:call-template name="query-edge">
       <xsl:with-param name="edge" select="$next-edge"/>
       <xsl:with-param name="x1" select="$x1"/>
       <xsl:with-param name="y1" select="$y1"/>
       <xsl:with-param name="n" select="$n"/>
       <xsl:with-param name="level" select="$level"/>
       <!-- next 'edge', increment counter -->
       <xsl:with-param name="count" select="$count+1"/>
     </xsl:call-template>
    </xsl:if>
  </xsl:template>
</xsl:stylesheet>
    

Running this stylesheet on the GraphML sample returns the following SVG :

<?xml-stylesheet type="text/css" href="default.css"?>
<svg xmlns="http://www.w3.org/2000/svg">
  <defs>
    <marker id="arrow" refX="5" refY="5" markerUnits="userSpaceOnUse" markerWidth="10" markerHeight="10" orient="auto">
      <path class="edge" d="M0 0 10 5 0 10z"/>
    </marker>
  </defs>
  <g class="node">
    <rect x="0" y="500" width="100" height="100"/>
    <text text-anchor="middle" x="50" y="555">n1</text>
  </g>
  <g class="node">
    <rect x="150" y="500" width="100" height="100"/>
    <text text-anchor="middle" x="200" y="555">n2</text>
  </g>
  <line class="edge" x1="100" y1="550" x2="150" y2="550" style="marker-end:url(#arrow)"/>
  <g class="node">
    <rect x="300" y="500" width="100" height="100"/>
    <text text-anchor="middle" x="350" y="555">n4</text>
  </g>
  <line class="edge" x1="250" y1="550" x2="300" y2="550" style="marker-end:url(#arrow)"/>
  <g class="node">
    <rect x="150" y="350" width="100" height="100"/>
    <text text-anchor="middle" x="200" y="405">n5</text>
  </g>
  <line class="edge" x1="100" y1="550" x2="150" y2="400" style="marker-end:url(#arrow)"/>
  <g class="node">
    <rect x="150" y="650" width="100" height="100"/>
    <text text-anchor="middle" x="200" y="705">n3</text>
  </g>
  <line class="edge" x1="100" y1="550" x2="150" y2="700" style="marker-end:url(#arrow)"/>
</svg>

That would be rendered as:

tree.png

Because XSLT does not provide updateable variables and iteration, it is necessary to build recursions for every action that requires to retain and update values from one computation to another. This creates a very complex stylesheet for a limited result. In cases where more complex graphs are involved, such as undirected graphs, cyclic graphs or nested graphs, using portable XSLT would lead to even more complex stylesheets or might even not be powerful enough to achieve the result.

In conclusion, XSLT is a good fit for the first step of the GraphML to SVG transformation mechanism, but shows some limitations when it comes to the positioning of the nodes and edges.

Extended XSLT

Doing the transformation on a server generally allows the developer to use XSLT extensions because it is then possible to rely on a given XSLT processor. Using extensions gives the ability to use portable XSLT for the part of the transformation that fits well with the XSLT paradigm and delegate other transformations to custom XSLT elements or functions that will be coded in another language that is more suitable for these operations.

Consider that the following extended functions have been added to the XSLT processor in the graphml2svg namespace:

It is then possible to re-write the stylesheet as the following:

<xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform" xmlns="http://www.w3.org/2000/svg" xmlns:graphml2svg="http://www.sample.org/graphml2svg" extension-element-prefixes="graphml2svg">  
  <xsl:output method="xml" version="1.0" encoding="UTF-8" indent="yes"/>
  <!-- for a 'graph' element, creates an 'svg' element -->
  <xsl:template match="graph">
    <!-- first give a CSS reference for the generated SVG -->
   <xsl:processing-instruction name="xml-stylesheet">type="text/css" href="default.css"</xsl:processing-instruction> 
    <svg>
      <!-- defs section for the arrow -->
      <!-- ... -->
      <xsl:apply-templates select="graphml2svg:getroot()"/>
    </svg>
  </xsl:template>
  <!-- transform a 'node' to SVG -->
  <xsl:template match="node">
    <xsl:variable name="x1">0</xsl:variable>
    <xsl:variable name="y1">0</xsl:variable>
    <!-- some helpers -->
    <xsl:variable name="level" select="graphml2svg:getlevel()"/>
    <xsl:variable name="count" select="graphml2svg:getindex()"/>
    <xsl:variable name="edge" select="graphml2svg:getedge()"/>
    <xsl:variable name="side" select="1-2*($count mod 2)"/>
    <xsl:variable name="x" select="$level*150"/>
    <xsl:variable name="y" select="$y1 - 50+$side*ceiling($count div 2)*150"/>
    <!-- create the 'node' itself and position it -->
    <g class="node">
      <rect x="{$x}" y="{$y}" width="100" height="100"/>
      <text text-anchor="middle" x="{$x+50}" y="{$y+55}">
        <xsl:value-of select="./@id"/>
      </text>
    </g>
    <!-- if there is an 'edge' ($edge) to draw it -->
    <xsl:if test="$edge!='null'">
      <!-- the 'edge' position goes from previous 'node' position to $n one -->
      <line class="edge" x1="{$x1}" y1="{$y1}" x2="{$x}" y2="{$y+50}">
        <xsl:attribute name="style">marker-end:url(#arrow)</xsl:attribute>
      </line>
    </xsl:if>
    <!-- now that the 'node' is created, go to children -->
    <xsl:apply-templates select="graphml2svg:getchildren()">
      <xsl:with-param name="x1" select="$x+100"/>
      <xsl:with-param name="y1" select="$y+50"/>
    </xsl:apply-templates>
  </xsl:template>
</xsl:stylesheet>
      

This version is clearly more readable and maintainable than the previous version (see Portable XSLT ). The problem of maintainability is exported to the code that will implement the custom functions. Take as an example the Apache Xalan Java processor, for which code may be written in Java, ECMAScript or any scripting language supported by the BSF (Bean Scripting Framework) library (see [XalanExtension] ). Unfortunately, by using these extensions the portability of the stylesheet is broken because it relies on a particular vendor version for plugin extensions to the processor.

GraphML to SVG using Java Transformation

Because the Java language provides several DOM (Document Object Model) implementations, one can rely on their help to do the GraphML to SVG conversion (loading the GraphML in a document, transforming it using DOM API and saving it as SVG ). This transformation alternative is particularly useful if the developer has access to an existing extensible Graph Model and Graph Layout library written in Java. He will then be able to plug it in for performing the positioning part ( Paragraph 12 ) of the transformation.

The example described below goes a little bit further by leveraging the ILOG JViews Component Suite (http://jviews.ilog.com) for doing the conversion. ILOG JViews provides several packages, among which three of them will be used here:

The workflow that the GraphML document will follow is the following:

sdm-workflow.png

The first step is to convert the GraphML file to a file that the SDM engine is able to interpret. The XML grammar that SDM expects as input is very flexible. For this reason, the XSLT that will transform the GraphML file to a valid SDM input is very simple. The stylesheet is just recursively (to allow nested 'graph' elements) copying the 'node' and 'edges' elements. For the 'edge' elements, the name of the source and target attributes are changed to match SDM naming conventions and an isLink attribute is added with a value of true:

<xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
  <xsl:output method="xml" version="1.0" encoding="UTF-8" indent="yes"/>
  <xsl:template match="/">
     <sdm>
       <xsl:apply-templates select="node()"/>
     </sdm>
  </xsl:template>
  <xsl:template match="graph">
      <xsl:apply-templates select="node"/>
      <xsl:apply-templates select="edge"/>
  </xsl:template>
  <xsl:template match="node">
    <xsl:copy>
      <xsl:copy-of select="@id"/>
      <xsl:apply-templates select="graph"/>
    </xsl:copy>
  </xsl:template>
  <xsl:template match="edge">
    <xsl:copy>
      <xsl:attribute name="isLink">true</xsl:attribute>
      <xsl:attribute name="from"><xsl:value-of select="@source"/></xsl:attribute>
      <xsl:attribute name="to"><xsl:value-of select="@target"/></xsl:attribute>
      <xsl:copy-of select="@directed"/>
    </xsl:copy>
  </xsl:template>
</xsl:stylesheet>

The second step is to provide the SDM engine with a CSS-like stylesheet that will help it generate the correct graphical representation for the input file. It is in this SDM stylesheet that the choice of the Graph Layout algorithm to be used for positioning nodes and edges will have to be made:

SDM {
  GraphLayout: Tree;
}

The graphical representation of the node and links and their style are also described:

node {
  class: ilog.views.sdm.graphic.IlvGeneralNode;
  foreground: black;
  fillColor1: silver;
  /** XPath subset can be used to get values from the SDM input file **/
  label: @id;
  labelPosition: Center;
  shapeWidth:100;
  shapeHeight:100;
}

link {
  class: ilog.views.IlvLinkImage;
  oriented: true;
}

Finally, if a particular link has a directed attribute set to false the orientation property is overridden with the false value:

link[directed='false'] { 
  oriented: false;
}

This stylesheet allows the SDM engine to produce an SVG document similar to the one that was generated with the previous conversion mechanisms.

Because the mechanism here relies on an external library for the graph layout, it is possible to transform more complex graphs than a rooted tree. The power of this external library can be used to transform the following example into SVG . This example contains more complex structures, such as cycle, nested graph and unoriented edges, that would not have been correctly transformed by the naive algorithm implemented in XSLT :

<graph edgedefault="directed">
  <node id="n1"/>
  <node id="n2"/>
  <node id="n3"/>
  <node id="n4"/>
  <node id="n5"/>
  <node id="g">
    <graph>
      <node id="n6"/>
      <node id="n7"/>
      <node id="n8"/>
      <edge source="n6" target="n7"/>
      <edge source="n7" target="n8"/>
      <edge source="n8" target="n6"/>
    </graph>
  </node>
  <edge source="n5" target="g"/>
  <edge source="n1" target="n2"/>
  <edge source="n1" target="n5"/>
  <edge source="n1" target="n3"/>
  <edge source="n2" target="n4"/>
  <edge source="n2" target="n4" directed="false"/>
  <edge source="g" target="n4"/>
  <edge source="n3" target="n4"/>
  <edge source="n4" target="n1"/>
</graph>

Which produces the result below by switching the Graph Layout to be used from Tree to Hierarchical in the SDM stylesheet :

sdm-layout.png

GraphML inside the SVG using SVG extension mechanisms

The SVG specification ( [SVG 1.1] ) states that SVG allows inclusion of elements from foreign namespaces anywhere within the SVG content. This explicitly allows the content developer to directly include the GraphML description inside the SVG file. Keeping the example used in the previous sections, this would mean that the GraphML inside the SVG would look like the following:

<svg xmlns:graphml="http://graphml.graphdrawing.org/xmlns/1.0rc">
  <graphml:graph edgedefault="directed">
    <graphml:desc>GraphML sample</graphml:desc>
    <graphml:node id="n1"/>
    <graphml:node id="n2"/>
    <graphml:node id="n3"/>
    <graphml:node id="n4"/>
    <graphml:node id="n5"/>
    <graphml:edge source="n1" target="n2"/>
    <graphml:edge source="n1" target="n5"/>
    <graphml:edge source="n1" target="n3"/>
    <graphml:edge source="n2" target="n4"/>
  </graphml:graph>
</svg>

There are several ways of defining how it will be rendered in SVG . Two possibilities are described below. One relies on a user agent extension mechanism, the other one is under development by the SVG Working Group in the context of the SVG 1.2 specification defined by [SVG 1.2]

Batik Extension Mechanism

The Batik Project at Apache (http://xml.apache.org/batik) is a Java technology based toolkit for applications or applets that want to use images in the SVG format for various purposes, such as viewing, generation or manipulation. One of the components, called the Batik Squiggle Viewer, is aimed at displaying SVG . This component relies on Batik core components that have been designed to be extensible and can understand foreign namespaces.

The Batik documentation extensions chapter ( [BatikExtension] ) explains in detail how to hook an extension into the Batik rendering system. In short, this can be achieved by implementing the Batik BridgeExtension interface and registering it as a service of the Batik application. The implementation of the BridgeExtension will be called when Batik encounters an XML element that belongs to the extension. The Batik Bridge that corresponds to the element and that has been registered for the extension will be called to build what is necessary for the element to be rendered.

In order to keep some portability, this mechanism should be used with the 'switch' element of SVG to provide an alternate version:

<?xml-stylesheet type="text/css" href="default.css"?>
<svg xmlns:graphml="http://graphml.graphdrawing.org/xmlns/1.0rc">
  <switch>
    <graphml:graph edgedefault="directed" requiredExtension="http://graphml.graphdrawing.org/xmlns/1.0rc">
      <!-- GraphML contents -->
    </graphml:graph>
    <g>
      <!-- alternate SVG contents in case the extension is not available -->
    </g>
  </switch>
</svg>

The first line of the SVG file imports the exact same CSS stylesheet as for the XSLT transformation mechanism. This stylesheet will be used to style the nodes and edges. Then the 'switch' element contains two children, one of which has a requiredExtension attribute. If that extension is available, the contents of the GraphML 'graph' element is interpreted by Batik. Otherwise, the alternate contents are used. Because the Batik extensions are coded in Java, there are several ways to proceed in order to acheive the expected rendering result. For this use case, in the same manner as the XSLT , the extended bridges would map the 'graph' element to a 'g', the 'node' elements to 'g' elements with 'rect' and 'text' as children, and the 'edge' elements to 'line' elements.

For the positioning of the created elements, the Java language allows one to go further than XSLT . It provides the ability for the positioning of the elements to be computed by a third-party graph layout algorithm that will be optimized and that will probably provide more capabilities than an XSLT based algorithm. In order to accomplish this, the third-party graph layout library, such as the ILOG JViews Graph Layout library, has to provide an abstract Graph Model that will be implemented on top of the SVG representation of the GraphML (replacing the default implementation build on top of the library native grapher). Once done, the algorithms of the library, instead of querying the default Graph Model, will query this particular implementation and allow the SVG elements to be laid out.

Rendering Custom Content Mechanism

The Working Draft of the SVG 1.2 specification ( [SVG 1.2] ) describes a new addition to the SVG language that is called RCC (Rendering Custom Content) and is well suited for building SVG contents from GraphML contents inside an SVG document.

The RCC framework, that is still under development and its syntax may be subject to changes, is a generic mechanism that allows an SVG user agent to automatically recognize elements in a third-party namespace and perform a transformation of these elements into SVG elements for rendering. The built on the fly SVG elements do not pollute the original document because they are part of a shadow DOM that is not directly exposed to the user. Another important point is that RCC has been designed such that the transformation should be able to happen in both ways. For example, if the user interactively modifies the SVG content, the initial third-party elements may be modified in response. This means that it provides a more dynamic process than the XSLT mechanism.

The example file, using RCC would look like the following :

  <extensionDefs namespace="http://graphml.graphdrawing.org/xmlns/1.0rc">
    <script type="text/ecmascript" xlink:href="graphml2svg.es"/>
    <defs>
      <marker id="arrow" refX="5" refY="5" markerUnits="userSpaceOnUse" markerWidth="10" markerHeight="10" orient="auto">
        <path class="edge" d="M0 0 10 5 0 10z"/>
      </marker>
    </defs> 
    <elementDef name="graph">
      <prototype>    
        <g>
          <refContent/>
        </g>
      </prototype>
      <script ev:event="SVGBindBegin">
        InitGraph(evt.target)
      </script>
    </elementDef>
    <elementDef name="node">
      <prototype>
        <g class="node">
          <rect width="100" height="100"/>
          <text/>
        </g>
      </prototype>
      <script ev:event="SVGBindBegin">
        var text = evt.target.shadowTree.getElementsByTagNameNS(SVG_NS, "text").item(0)
        var label = document.createTextNode(evt.target.getAttributeNS(null, "id"))
        text.appendChild(label)
      </script>
    </elementDef>
    <elementDef name="edge">
      <prototype>
        <line class="edge"/> 
      </prototype>
      <script ev:event="SVGBindBegin">
        evt.target.parentNode.graph.addEdge(evt.target)
        // each time an edge is added (re-)perform the layout
        evt.target.parentNode.graph.performLayout()
      </script>
    </elementDef>
    <elementDef name="desc">
      <prototype>
        <desc>
          <refContent/>
        </desc>
      </prototype>
    </elementDef>
  </extensionDefs>
  <graphml:graph edgedefault="directed">
    <-- The GraphML Contents -->
  </graphml:graph>
</svg>

In order to better show the RCC architecture, the definition of the extension has been included here inside the SVG itself. Of course, the contents of the 'extensionDefs' section could have been externalized and referenced using an xlink:href attribute.

The 'extensionDefs' section is mainly a set of component definitions ('componentDef') that are themselves made of two main parts:

The 'extensionDefs' section also references an external ECMAScript file that contains the code of the functions called in answer to SVGBindBegin events (such as performing the layout). As a matter of comparison with the XSLT file (see Portable XSLT ), the exact same naive tree algorithm is reproduced below in ECMAScript:

var GRAPHML_NS = "http://graphml.graphdrawing.org/xmlns/1.0rc"
var SVG_NS = "http://www.w3.org/2000/svg"

function InitGraph(elt) {
  elt.graph = new Graph(elt)
}

function Graph(elt) {
  this.graph = elt
}

Graph.prototype.performLayout = function() {
  // look for the root element
  var root = this.getRoot()
  // recurse
  if (root != null)
    this.layoutNode(root, 0, 0)
}

Graph.prototype.getRoot = function() {
  var nodes = this.graph.getElementsByTagNameNS(GRAPHML_NS, "node")
  for (var i = 0; i < nodes.length; i++) {
    var node = nodes.item(i)
    if (this.getToEdges(node) == null)
      return node
  }
  return null
}

Graph.prototype.layoutNode = function(elt, level, index, edgeLine) {
  // get the shadow tree of the node  
  var g = elt.shadowTree
  // layout it
  var rect = g.getElementsByTagNameNS(SVG_NS, "rect").item(0)
  var x = level*150
  var dy = (edgeLine != null)?parseFloat(edgeLine.getAttributeNS(null, "y1"))-50:0
  var y = dy + (1-2*(index % 2))*Math.ceil(index / 2)*150
  rect.setAttributeNS(null, "x", x)
  rect.setAttributeNS(null, "y", y)
  var text = g.getElementsByTagNameNS(SVG_NS, "text").item(0)
  text.setAttributeNS(null, "text-anchor", "middle")
  text.setAttributeNS(null, "x", x+50)
  text.setAttributeNS(null, "y", y+55)
  if (edgeLine != null) {
    edgeLine.setAttributeNS(null, "x2", x)
    edgeLine.setAttributeNS(null, "y2", y+50)
  }
  // recurse
  var children = this.getFromEdges(elt)
  var max = (children == null)?0:children.length
  for (var i = 0; i < max; i++) {
    var edge = children[i]
    // get the edge shadow tree
    var line = edge.shadowTree
    // sets its source anchor
    line.setAttributeNS(null, "x1", x+100)
    line.setAttributeNS(null, "y1", y+50) 
    line.setAttributeNS(null, "marker-end", "url(#arrow)")
    // layout the target node
    this.layoutNode(document.getElementById(edge.getAttributeNS(null, "target")), level+1, i, line)
  }
}

Graph.prototype.addEdge = function(elt) {
  var source = document.getElementById(elt.getAttributeNS(null, "source"))
  var target = document.getElementById(elt.getAttributeNS(null, "target"))
  this.addFromEdge(source, elt)
  this.addToEdge(target, elt)
}

Graph.prototype.addFromEdge = function(node, edge) {
  if (node.from == null)
   node.from = new Array
  node.from[node.from.length] = edge
}

Graph.prototype.addToEdge = function(node, edge) {
  if (node.to == null)
   node.to = new Array
  node.to[node.to.length] = edge
}

Graph.prototype.getToEdges = function(node) {
  return node.to
}

Graph.prototype.getFromEdges = function(node) {
  return node.from
}

Unlike in XSLT where only recursion is available, in ECMAScript iteration is also possible and is used when it allows simpler code than recursion. That added to the object oriented programming paradigm and to a more developed mathematical library makes the ECMAScript and RCC combination a mechanism that seems to better fit the nodes and edges positioning step of the transformation (see Paragraph 12 ). However the current lack of XSLT support in the RCC mechanism leads to some verbose DOM code required for setting some values on the prototypes instances (such as the 'text' contents in the SVG that is the id attribute value of the GraphML 'node' element) that may have been easier to write with the XSLT language.

Conclusion

As the table below shows, the first section described two XSLT / CSS oriented mechanisms that are really in line with the first steps of the transformation ( Paragraph 11 ) consisting of translating 'node' and 'edge' GraphML elements to skeletons of SVG elements ( XSLT ) and providing them with their rendering aspect ( CSS ). The last section described two mechanisms that were more in line with the second step of the transformation ( Paragraph 12 ) consisting of positioning these nodes and edges on the SVG canvas, but that also include the CSS capabilities and the ability to have dynamic transformation where the initial XML elements can be modified in response to user interaction on the SVG . Finally, the second section showed how an existing Java library can be leveraged to perform these both steps with success by reusing powerful graph layout algorithms.

GraphML to SVG Styling Method Layout Coding Language XPath Facilities Leverage Java Layout library Fully Standard Portable across SVG viewers Dynamic Transformation
Portable XSLT XSLT based, easy SVG CSS XSLT, complex and limited Yes No Yes Yes No
Extended XSLT XSLT based, easy SVG CSS Extended XSLT, complex Yes No No Yes No
SDM Transformation SDM CSS based, easy SDM CSS Automatic Subset Integrated No Yes Not for SVG output
Batik Extension Requires Java Coding SVG CSS Java, easier than XSLT No Yes No No Possible
RCC Extension Prototype and DOM based CSS ECMAScript, easier than XSLT No Not Portable Yes Yes Possible

Table 1

As expected, none of these mechanisms provides a perfect solution. However, it is possible to mix several of them in order to improve the final result.

For example, even if RCC philosophy would require the graph layout algorithm to be executed on the client in ECMAScript (for portability among the user agents), one can imagine to rely on a user agent that supports the Java language and re-use a Java library instead of coding the algorithm in ECMAScript. Another alternative to reuse an existing graph layout library would be to do most of the RCC transformation process on the client side but to call back the server when the performLayout method is called to ask it to send back nodes and edges positions.

Another improvement that relies more on the SVG Working Group would be the introduction of, at least, a subset of XPath in RCC . This would allow the prototyping mechanism to be a little bit more clever. With XSLT/XPath the following:

<elementDef name="node">
    <prototype>
      <g class="node">
        <rect width="100" height="100"/>
        <text/>
      </g>
    </prototype>
    <script ev:event="SVGBindBegin">
      var text = evt.target.shadowTree.getElementsByTagNameNS(SVG_NS, "text").item(0)
      var label = document.createTextNode(evt.target.getAttributeNS(null, "id"))
      text.appendChild(label)
    </script>
</elementDef>

Would have been written as:

<elementDef name="node">
    <prototype>
      <g class="node">
        <rect width="100" height="100"/>
        <text><xsl:value-of select="@id"/></text>
      </g>
    </prototype>
</elementDef>

Of course, that would not solve the problem of doing the reverse transformation when, for example, the SVG is modified. But it would already simplify the first part of the transformation.

Finally, taking the example of an XML format for describing graphs, it has been shown that the transformation process to SVG can follow a lot of different paths. The developer may choose among those paths depending on different criteria, such as:

Footnotes

  1. Be careful because RCC is still under development and the syntax may change

Acknowledgements

Adrian Vasiliu (ILOG S.A.)

For his help mostly related to graph terminology.

David Zeleznik (ILOG Inc.)

Bibliography

[GraphML]
GraphML Progress Report: Structural Layer Proposal, U. Brandes, M. Eiglsperger, I. Herman, M. Himsolt, and M.S. Marshall, Proc. 9th Intl. Symp. Graph Drawing (GD '01), LNCS 2265, pp. 501-512.
[SVG 1.1]
SVG 1.1 W3C Recommendation, http://www.w3.org/TR/SVG11
[SVG 1.2]
SVG 1.2 W3C Working Draft, http://www.w3.org/TR/SVG12
[XSLT]
XSLT W3C Recommendation, http://www.w3.org/TR/xslt
[XPath]
XPath W3C Recommendation, http://www.w3.org/TR/xpath
[CSS 2.0]
CSS Level 2 Recommendation, http://www.w3.org/TR/REC-CSS2/
[BatikExtension]
Batik Extension Documentation, http://xml.apache.org/batik/extendingBatik.html
[XalanExtension]
Xalan Extension Documentation, http://xml.apache.org/xalan-j/extensions.html

XHTML rendition created by gcapaper Web Publisher v2.0, © 2001-3 Schema Software Inc.