9.3.1. Problem
You want to show the hierarchical structure of your data as a tree.
9.3.2. Solution
This section presents two different algorithms for rendering a tree. Neither is the most sophisticated algorithm available, but both give reasonable results.
If all the trees you needed to render were balanced, then rendering a tree would be easy because you would need to divide the available horizontal space by the number of nodes at each level and the vertical space by the number of levels. Unfortunately, real-world trees are not as symmetrical. You need an algorithm that considers the breadth of each branch.
The first technique makes only one pass over the tree. However, to accomplish this, it needs to embed foreign bookkeeping attributes into the resulting SVG. This example places these attributes in a namespace to ensure they will not conflict with SVG-specific attributes:
-==-
You can use count (ancestor-or-self::*) to get the level each time. However, you might consider adding a parameter to pass the level down the tree rather than recomputing each time:
-==-
This stylesheet renders the structure of any XML document as a tree. Figure 9-15 shows the result against a simple XML input file.
Figure 15. An XML document structure turned into SVG
The first algorithm yields trees whose parent nodes’ horizontal position is a function of the average position of its children. This causes the root node to be placed off center for unbalanced trees. The following algorithm is a slight improvement because it fixes the skewing problem and does not pollute the SVG with foreign attributes. However, it makes two passes over the input tree:
-==-
Figure 9-16 shows the same input XML rendered with this new algorithm.
Figure 16. A more balanced version of the XML document structure turned into SVG
9.3.3. Discussion
The previous recipes are incomplete because they render only the tree’s skeleton and not any of its content. An obvious extension would add text to the nodes to make them identifiable. This extension can be tricky because SVG doesn’t scale text automatically, and it becomes especially difficult if the width of the boxes change based on the amount of text they contain. See Recipe 12.14 for a Java-extension function that can help solve SVG text-layout problems.
You chose to map all nodes in the input document to nodes in the SVG tree. In a real-life problem, you would probably filter out irrelevant nodes by using match patterns more specific than match="node( )[*]" and match="*".
If the tree structure of your data is not modeled literally by the hierarchical structure of the XML, then you need to preprocess the input to create such a structure. For example, this would be the case if the parent-child structure were encoded as pointers and targets stored in attributes.
The stylesheets have code that support two types of connections. The examples use square connections. Straight connections, shown in Figure 9-17, can be obtained by overriding drawConnections to call drawStraightConnections.
Figure 17. An XML document structure turned into SVG by using straight connections
These stylesheets present two portability issues. First, they use a Java extension to access the Java Math:max function. This function can be implemented easily in XSLT. However, since SVG-generating stylesheets often need other types of extension functions, the problem may be unavoidable. The other portability issue is that they assume support for XSLT 1.1 or higher where the result-tree fragments can be properly treated as node sets. You may wish to use your XSLT processor’s nodes set converter instead.
9.3.4. See Also
To learn more about sophisticated algorithms for drawing trees and more general graphs, consult Graph Drawing: Algorithms for the Visualization of Graphs by Giuseppe Di Battista, Peter Eades, Roberto Tamassia, and Ionnis G. Tollis (Prentice Hall, 1999). Be forewarned that the book is heavy on the mathematical side; it is not an algorithms pseudocode cookbook.
First appeared at O’Reilly’s XML.com.
Sal Mangano has been developing software for over 12 years and has worked on many mission-critical applications, especially in the area of financial-trading applications. Unlike many XML/XSLT developers, he did not approach the technology from the standpoint of the Internet and Web development but rather from the broader need for a general-purpose, data-transformation framework. This experience has given him a unique perspective that has influenced many of the recipes in his book, the XSLT Cookbook. Sal has a Master’s degree in Computer Science from Polytechnic University.
XSLT Cookbook – Critical for converting XML documents, and extremely versatile, the XSLT language nevertheless has complexities that can be daunting. The XSLT Cookbook is a collection of hundreds of solutions to problems that Extensible Stylesheet Language Transformations (XSLT) developers regularly face. The recipes range from simple string-manipulation and mathematical processing to more complex topics like extending XSLT, testing and debugging XSLT stylesheets, and graphics creation with SVG. Recipes can be run directly or tweaked to fit your particular application’s needs more precisely.
