XML is the appropriate format for semistructured data, that is, data with a natural tree structure. Trees are a special form of graphs, and a dialect of XML called GraphML now exists that provides a standard set of tags for describing them. To visualize or draw the graph we can use another XML dialect called SVG, or Scalable Vector Graphics.

SVG is a language for describing two-dimensional graphics and graphical applications and is a dialect of XML. In this article we discuss the representation of tree-structured data using XML and GraphML. We visualize the data using SVG and transform the data between the various XML documents using Extensible Stylesheet Language Transformations (XSLT).

Introduction
A graph is simply a collection of nodes and edges and may be directed or undirected. In the case of a directed graph, an arrow connects the source to the target; for an undirected graph there is no arrow, only a line. A tree is a special case of a graph: there are no closed loops or circuits but all the nodes are connected. XML documents satisfy this definition and thus exhibit a natural tree structure. Examples of trees include decision trees, concept maps, and the structure of hydrocarbon molecules.

The structure of a tree is shown in Figure 1. The rectangles are the nodes and the edges are the lines connecting the nodes. Node A is a source and targets nodes B, C, and D; similarly, source node D targets nodes E and F.

The tree in Figure 1 can be represented in XML by a series of tags as shown in Figure 2. The nodes of the tree become tags in XML.

Alternatively, we can use a standard format like GraphML to illustrate a tree. In GraphML the tree shown in Figure 1 becomes the listing in Figure 3.

The "graph" element is the root element and the "edgedefault" attribute determines globally whether the graph is directed or undirected. Each edge element may contain an attribute called "directed" or "undirected" and has the values "true" or "false". Setting the attribute "directed" to "false" or setting the attribute "undirected" to "true" overrules the global setting.

The advantage of a standard format is that quite often a free viewer is available to render it in some fashion. If no free viewer is available, we may visualize the data by transforming it into SVG and using Internet Explorer. A free plug-in for SVG in Internet Explorer is available from Adobe. Apart from the need to render a document or visualize it, you may still wish to transform a local XML document into another form for the purpose of exchanging it over the Web. This is best done in some accepted standard format, and XSLT is one way of accomplishing this. Christophe Jolif has discussed some alternative ways to make the XML-to-SVG transformation.

Case Study: Subject Prerequisites
To illustrate, we’ll use a mostly fictional example that could be taken from the subject catalog of any college or university. Subjects are generally taken in some set order; that is, the prerequisites must be done first. Listing 1 shows the prerequisites in XML format, as well as the post-requisites for each subject (Listings are available at www.sys-con.com/xml/sourcec.cfm). The root element is <subjects>, and all the necessary information about each subject is included as a child element of it. What we have not shown is the schema in the form of a separate DTD or XSD document that details the rules for the tags. For example, in each <subject-prerequisite> element there can be only one <subject> child element and there would be limits on how many prerequisites and post-requisites each subject could have. Since the schema is not germane to our discussion, we have not included it.

By working XML we mean an XML document that conforms to a schema that is being used locally within a particular organization. A local dialect is not necessarily used outside the organization. To exchange data like this with another university, it would be advantageous if a common data format existed. This could take the form of a shared dialect with a publicly available and fixed schema.

Transformation to a Standard Format
What we are describing is a two-step process for making the transformation from the input XML document to the output SVG document. The intermediate format we are using is GraphML, which is a potential industry standard. There is another advantage to doing things this way: the overall XSLT transformation is simplified if it is broken down into two transformations. It would be hard to find a simpler XML dialect than GraphML, and its use as the intermediate considerably simplifies the XPath expressions used. These can become quite complicated; indeed XPath is generally considered one of the more difficult aspects of XML and any scheme to simplify its use is a plus.

The transformation from the working XML document, Prerequisites.xml, is accomplished by the XSLT Stylesheet XMLtoGrML.xslt, shown in Listing 2.

GraphML
The application of the stylesheet XMLtoGrML.xslt on the input XML file produces the GraphML document, GrML.xml, shown in Listing 3. A GraphML document may contain any number of <graph> elements. Each must include a mandatory "edgedefault" attribute that determines globally whether the graph is directed or undirected. A <graph> element can contain <node> and <edge> elements in any order.

GraphML was designed to represent both basic and specialized graphs. A specialized graph would require additional information in the form of data elements that describe layout and graphics. GraphML consists of a core component that describes the basic graph structure. The main elements of it are shown in Figure 3. The extension mechanism allows additional data specific to one graph to be included. In this article we will make use of the simpler aspects of GraphML.

Transformation to SVG
Both GraphML and SVG are standard file formats. A general-purpose XSLT stylesheet can now be written that will transform the GraphML into SVG. This is another advantage of using a two-step process. The last step involves the design of a stylesheet that need not be altered. Rather than reinvent the wheel, we have chosen to adapt an excellent XSLT stylesheet program written by Christophe Jolif, shown in Listing 4. This is another good reason for working with standard formats: chances are that somebody has already written a good program for you.

Scalable Vector Graphics
Scalable Vector Graphics is a language for defining graphics; its purpose is to define visual appearance. SVG was created by the W3C to handle vector graphic display and animation in XML. SVG is entirely text based and is editable in text editors. It is easily human readable; for example, a rectangle located at position (450,150) with a width of 100 pixels and a height of 100 pixels is described in code as:

<rect x="450" y="150" width="100" height="100">

JPEG images and GIF files are raster graphics that use bitmaps. Because of this, when a JPEG image or GIF graphic is enlarged the picture becomes fuzzy. SVG, on the other hand, is resolution independent because it uses mathematical statements to describe the image. Due to this vector nature, SVG files can be quite small in size and are easily transported over the Internet. After downloading and expansion the image remains the same in size since the mathematical formulas describing the image do not alter.

SVG works hand-in-hand with other technologies. SVG can exist on its own, be used within an XML document, be referenced from HTML, display JPEG images, and can also utilize JavaScript and Cascading Style Sheets (CSS). With CSS you can extend SVG’s capabilities. Every line, shape, and style property can be controlled and customized. Thus with SVG we can personalize our graphics.

The XSLT program of Listing 4 acts on the GraphML code in Listing 3 to produce the output SVG code of Listing 5. Line 1 is the standard XML declaration. Line 2 shows that the size of the SVG graph produced has been set to have a width of 8 inches and height of 11 inches. This ensures that the SVG graph will fit on a legal-size page.

Applying style to an object, or grouping of objects, is handled by the <g></g>element. This gives developers the option of applying a particular style to an element or associating elements together. Listing 5 shows how to individually apply a style to each rectangle. Figure 4 shows the X-Y coordinate system of a standard SVG document. The default unit of measurement is the pixel and is what we use here. Other popular formats are inches (in), centimeters (cm), and points (pt).

The following code produces the rectangle shown in Figure 4.

<rect x="300" y="150" width="100"
height="100" fill="lightgrey"/>
<text text-anchor="middle" x="350"
y="205">IFSC3000</text>

The top left-hand corner of the rectangle is the point (300,150). The width and height of the rectangle are 100 pixels, and the center of the text "IFSC3000" is anchored to the point (350, 205). We could have chosen the type of font for the text using CSS, but we used the default setting of our XML processor which was XMLSPY.

The XSLT program in Listing 4 transforms the standard GraphML code in Listing 3 into the SVG graph of Figure 5. By recursions through the "node" and "edge" elements of the GraphML program a series of rectangles and lines connecting the rectangles is produced. When the text code in Listing 5 is viewed in the IE browser the SVG graph in Figure 5 is the result. The text code in Listing 5 is a series of rectangles, like the one produced in Figure 4, connected by lines that are created by the line element:

<line x1="250" y1="100" x2="350"
y2="150" style="stroke:black"/>

Once again, the coordinate system is in pixels and is exactly the same as in Figure 4. The above line starts at the point (250,100) and ends at the point (350,150). This line in Figure 5 connects the IFSC4500 rectangle with the IFSC3000 rectangle. The line style stroke is black.

Summary
GraphML is a comprehensive and easy-to-use file format for graphs. Its simple structure makes it convenient to use as an intermediary format between a working XML document and an SVG output document. Both GraphML and SVG are standard file formats, which confers stability on the XSLT stylesheets used in the second step of the transformation. Use of a simple XML dialect like GraphML also confers the advantage of simpler XPath expressions and a simplified design process for the XSLT. Finally, GraphML is a candidate industry standard allowing the intermediary document to be used for data interchange over the Web.

References

Watt, Andrew; Lilley, Chris; et al. SVG Unleashed. Sams Publishing, 2003.

Published Jan. 7, 2004— Reads 17,480 — Feedback 3
Copyright © 2004 SYS-CON Media, Inc. — All Rights Reserved.
Syndicated stories and blog feeds, all rights reserved by the author.

Related Links

▪ Source Code

About Philip Burton
Philip Burton earned his Ph.D. in Mathematical Physics from the University of Queensland in 1996. He is an assistant professor in the Department of Information Science at the University of Arkansas at Little Rock. Philip is a member of the Institute of Electrical and Electronic Engineering (IEEE) Society, the American Mathematics Society (AMS), and the American Physical Society (APS).

About Russel Bruhn
Russel Bruhn earned his PhD in electrical engineering from Washington State
University in 1997. He is an associate professor and chair of the Department of Information Science at the University of Arkansas in Little Rock. His research interests are in the areas of creating innovative curriculum, computers and education, XML and applications of XML with SVG graphics.