Recipe11.3.Creating a Tree Diagram

Recipe 11.3. Creating a Tree Diagram

Problem

You want to show the hierarchical structure of your data as a tree.

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.^[2] Unfortunately, real-world trees are not as symmetrical. You need an algorithm that considers the breadth of each branch.

^[2] Actually, you need to divide by the number of nodes + 1, lest you have a so-called "fencepost" error.

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:

<?xml version="1.0" encoding="UTF-8"?> <xsl:stylesheet    <!-- v. 1.1 is defunct but works in Saxon to enable the -->   <!-- xsl:script feature. -->   version="1.1"    xmlns:emath="http://www.exslt.org/math"    xmlns:xsl="http://www.w3.org/1999/XSL/Transform"   xmlns:tree="http://www.ora.com/XSLTCookbook/ns/tree"   xmlns:Math="java:java.lang.Math"    extension-element-prefixes="Math"    exclude-result-prefixes="Math emath">      <xsl:script implements-prefix="Math"                    xmlns:Math="java:java.lang.Math"                    language="java"                    src="/books/2/765/1/html/2/java:java.lang.Math"/>       <xsl:include href="../math/math.max.xslt"/>       <xsl:output method="xml" version="1.0" encoding="UTF-8" indent="yes"      doctype-public="-//W3C//DTD SVG 1.0/EN"     doctype-system="http://www.w3.org/TR/2001/REC-SVG-20010904/DTD/svg10.dtd"/>       <!-- These parameters control the proportions of the tree -->   <!-- and its nodes -->     <xsl:variable name="width" select="500"/>   <xsl:variable name="height" select="500"/>   <xsl:variable name="nodeWidth" select="2"/>   <xsl:variable name="nodeHeight" select="1"/>   <xsl:variable name="horzSpace" select="0.5"/>   <xsl:variable name="vertSpace" select="1"/>      <xsl:template match="/">      <svg width="{$width}" height="{$height}">         <!-- Capture the subtree of this node in a variable -->     <xsl:variable name="subTree">       <xsl:apply-templates/>     </xsl:variable>         <!--maxPos is the max of the furthest X or Y coordinate used in -->     <!--rendering a node -->         <xsl:variable name="maxPos"                    select="Math:max(number($subTree/g/@tree:MAXX),                           number($subTree/g/@tree:MAXY))"/>     <xsl:variable name="maxDim" select="Math:max($width,$height)"/>         <!--We scale the tree so all nodes will fit in the -->     <!--coordinate system -->     <g transform="scale({$maxDim div ($maxPos + 1)})">         <!-- Use exsl:node-set($subTree) -->     <!-- if your XSLT processor is version 1.0 -->           <xsl:copy-of select="$subTree/g/*"/>                      </g>        </svg>   </xsl:template>            <!-- This matches all non-leaf nodes -->     <xsl:template match="*[*]">        <xsl:variable name="subTree">         <xsl:apply-templates/>     </xsl:variable>        <!-- Position this node horizontally based on the average -->     <!-- position of its children -->     <xsl:variable name="thisX"                           select="sum($subTree/*/@tree:THISX)                                        div count($subTree/*)"/>         <xsl:variable name="maxX" select="$subTree/*[last( )]/@tree:MAXX"/>         <!-- Position this node vertically based on its level -->     <xsl:variable name="thisY"           select="($vertSpace + $nodeHeight) * count(ancestor-or-self::*)"/>         <xsl:variable name="maxY">       <xsl:call-template name="emath:max">         <!-- Use exsl:node-set($subTree) if your XSLT processor -->         <!-- is version 1.0 -->         <xsl:with-param name="nodes" select="$subTree/*/@tree:MAXY"/>        </xsl:call-template>     </xsl:variable>          <!-- We place the parent and its children and the connectors -->     <!-- in a group -->     <!-- We also add bookkeeping attributes to the group as a means of -->     <!--passing information up the tree -->     <g tree:THISX="{$thisX}" tree:MAXX="{$maxX}" tree:MAXY="{$maxY}">       <rect x="{$thisX - $nodeWidth}"                 y="{$thisY - $nodeHeight}"                 width="{$nodeWidth}"                 height="{$nodeHeight}"                 style="fill: none; stroke: black; stroke-width:0.1"/>           <!--Draw a connecting line between current node and its children -->               <xsl:call-template name="drawConnections">            <xsl:with-param name="xParent" select="$thisX - $nodeWidth"/>            <xsl:with-param name="yParent" select="$thisY - $nodeHeight"/>            <xsl:with-param name="widthParent" select="$nodeWidth"/>            <xsl:with-param name="heightParent" select="$nodeHeight"/>            <xsl:with-param name="children" select="$subTree/g/rect"/>       </xsl:call-template>              <!--Copy the SVG of the sub tree -->       <xsl:copy-of select="$subTree"/>     </g>        </xsl:template>      <!-- This matches all leaf nodes -->     <xsl:template match="*">        <!-- Position leaf nodes horizontally based on the number of -->     <!-- preceding leaf nodes -->     <xsl:variable name="maxX"           select="($horzSpace + $nodeWidth) *                   (count(preceding::*[not(child::*)] ) + 1) "/>

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:

    <!-- Position this node vertically based on its level -->     <xsl:variable name="maxY"          select="($vertSpace + $nodeHeight) * count(ancestor-or-self::*) "/>          <g tree:THISX="{$maxX}" tree:MAXX="{$maxX}" tree:MAXY="{$maxY}">       <rect x="{$maxX - $nodeWidth}"                 y="{$maxY - $nodeHeight}"                 width="{$nodeWidth}"                 height="{$nodeHeight}"                 style="fill: none; stroke: black; stroke-width:0.1;"/>     </g>          </xsl:template>       <!-- Override in importing stylesheet if you want -->   <!-- straight or some custom type of connection -->   <xsl:template name="drawConnections">     <xsl:param name="xParent"/>     <xsl:param name="yParent"/>     <xsl:param name="widthParent"/>     <xsl:param name="heightParent"/>     <xsl:param name="children"/>     <xsl:call-template name="drawSquareConnections">       <xsl:with-param name="xParent" select="$xParent"/>       <xsl:with-param name="yParent" select="$yParent"/>       <xsl:with-param name="widthParent" select="$widthParent"/>       <xsl:with-param name="heightParent" select="$heightParent"/>       <xsl:with-param name="children" select="$children"/>     </xsl:call-template>   </xsl:template>       <!-- Straight connections take the shortest path from center -->   <!-- of parent bottom to center of child top -->   <xsl:template name="drawStraightConnections">     <xsl:param name="xParent"/>     <xsl:param name="yParent"/>     <xsl:param name="widthParent"/>     <xsl:param name="heightParent"/>     <xsl:param name="children"/>     <xsl:for-each select="$children">        <line x1="{$xParent + $widthParent div 2}"                 y1="{$yParent + $heightParent}"                 x2="{@x + $nodeWidth div 2}"                 y2="{@y}"                 style="stroke: black; stroke-width:0.1;"/>       </xsl:for-each>   </xsl:template>       <!-- Square connections take the shortest path using only horizontal -->   <!-- and vertical lines from center of parent bottom to center of -->      <!-- child top -->   <xsl:template name="drawSquareConnections">     <xsl:param name="xParent"/>     <xsl:param name="yParent"/>     <xsl:param name="widthParent"/>     <xsl:param name="heightParent"/>     <xsl:param name="children"/>          <xsl:variable name="midY"          select="($children[1]/@y + ($yParent + $heightParent)) div 2"/>          <!--vertical parent line -->     <line x1="{$xParent + $widthParent div 2}"              y1="{$yParent + $heightParent}"              x2="{$xParent + $widthParent div 2}"              y2="{$midY}"              style="stroke: black; stroke-width:0.1;"/>          <!--central horizontal line -->     <line x1="{$children[1]/@x + $children[1]/@width div 2}"              y1="{$midY}"             x2="{$children[last( )]/@x + $children[1]/@width div 2}"              y2="{$midY}"              style="stroke: black; stroke-width:0.1;"/>                   <!--vertical child lines -->     <xsl:for-each select="$children">        <line x1="{@x + $nodeWidth div 2}"                 y1="{$midY}"                 x2="{@x + $nodeWidth div 2}"                 y2="{@y}"                 style="stroke: black; stroke-width:0.1;"/>       </xsl:for-each>        </xsl:template>       </xsl:stylesheet>

This stylesheet renders the structure of any XML document as a tree. Figure 11-15 shows the result against a simple XML input file.

Figure 11-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:

<?xml version="1.0" encoding="UTF-8"?> <xsl:stylesheet version="1.1"                           xmlns:emath="http://www.exslt.org/math"                           xmlns:xsl="http://www.w3.org/1999/XSL/Transform"                           xmlns:tree="http://www.ora.com/XSLTCookbook/ns/tree"                           xmlns:Math="java:java.lang.Math"                          extension-element-prefixes="Math"                           exclude-result-prefixes="Math emath">                              <xsl:script implements-prefix="Math"                     xmlns:Math="java:java.lang.Math"                     language="java"                      src="/books/2/765/1/html/2/java:java.lang.Math"/>      <xsl:include href="../math/math.max.xslt"/>      <xsl:output method="xml" version="1.0"                      encoding="UTF-8"                      indent="yes"                      doctype-public="-//W3C//DTD SVG 1.0/EN"                      doctype-system="http://www.w3.org/TR/2001/REC-SVG-20010904/DTD/svg10.dtd"/>                        <xsl:variable name="width" select="500"/>   <xsl:variable name="height" select="500"/>   <xsl:variable name="nodeWidth" select="2"/>   <xsl:variable name="nodeHeight" select="1"/>   <xsl:variable name="horzSpace" select="0.5"/>   <xsl:variable name="vertSpace" select="1"/>   <xsl:variable name="strokeWidth" select="0.1"/>      <xsl:template match="/">         <!--Pass 1 copies input with added bookkeeping attributes -->       <xsl:variable name="treeWithLayout">       <xsl:apply-templates mode="layout"/>     </xsl:variable>          <xsl:variable name="maxPos"        select="Math:max($treeWithLayout/*/@tree:WEIGHT *                         ($nodeWidth + $horzSpace),                        $treeWithLayout/*/@tree:MAXDEPTH *                           ($nodeHeight + $vertSpace))"/>                                                            <xsl:variable name="maxDim" select="Math:max($width,$height)"/>          <xsl:variable name="scale" select="$maxDim div ($maxPos + 1)"/>          <!--Pass 2 creates SVG -->       <svg height="{$height}" width="{$width}">       <g transform="scale({$scale})">         <xsl:apply-templates select="$treeWithLayout/*" mode="draw">           <xsl:with-param name="x" select="0"/>           <xsl:with-param name="y" select="0"/>           <xsl:with-param name="width" select="$width div $scale"/>           <xsl:with-param name="height" select="$height div $scale"/>         </xsl:apply-templates>       </g>     </svg>   </xsl:template>      <!--Layout nodes with children -->   <xsl:template match="node( )[*]" mode="layout">     <xsl:variable name="subTree">       <xsl:apply-templates mode="layout"/>     </xsl:variable>          <!--Non-leaf nodes are assigned the sum of their child weights -->     <xsl:variable name="thisWeight"                           select="sum($subTree/*/@tree:WEIGHT)"/>                               <xsl:variable name="maxDepth">       <xsl:call-template name="emath:max">         <xsl:with-param name="nodes"                                     select="$subTree/*/@tree:MAXDEPTH"/>       </xsl:call-template>     </xsl:variable>          <xsl:copy>       <xsl:copy-of select="@*"/>       <xsl:attribute name="tree:WEIGHT">         <xsl:value-of select="$thisWeight"/>       </xsl:attribute>       <xsl:attribute name="tree:MAXDEPTH">         <xsl:value-of select="$maxDepth"/>       </xsl:attribute>       <xsl:copy-of select="$subTree"/>     </xsl:copy>        </xsl:template>      <!--Layout leaf nodes -->   <xsl:template match="*" mode="layout">     <xsl:variable name="depth" select="count(ancestor-or-self::*) "/>     <xsl:copy>       <xsl:copy-of select="@*"/>       <!--Leaf nodes are assigned weight 1 -->       <xsl:attribute name="tree:WEIGHT">         <xsl:value-of select="1"/>       </xsl:attribute>       <xsl:attribute name="tree:MAXDEPTH">         <xsl:value-of select="$depth"/>       </xsl:attribute>     </xsl:copy>   </xsl:template>      <!--Draw non-leaf nodes -->   <xsl:template match="node( )[*]" mode="draw">     <xsl:param name="x"/>     <xsl:param name="y"/>     <xsl:param name="width"/>     <xsl:variable name="thisX"                           select="$x + $width div 2 - ($nodeWidth+$horzSpace) div 2"/>     <xsl:variable name="subTree">       <xsl:call-template name="drawSubtree">         <xsl:with-param name="nodes" select="*"/>         <xsl:with-param name="weight" select="@tree:WEIGHT"/>         <xsl:with-param name="x" select="$x"/>         <xsl:with-param name="y" select="$y + $nodeHeight + $vertSpace"/>         <xsl:with-param name="width" select="$width"/>       </xsl:call-template>     </xsl:variable>     <g>            <rect x="{$thisX}"                 y="{$y}"                width="{$nodeWidth}"                 height="{$nodeHeight}"                 style="fill: none; stroke: black; stroke-width:{$strokeWidth};"/>                       <xsl:call-template name="drawConnections">         <xsl:with-param name="xParent" select="$thisX"/>         <xsl:with-param name="yParent" select="$y"/>         <xsl:with-param name="widthParent" select="$nodeWidth"/>         <xsl:with-param name="heightParent" select="$nodeHeight"/>         <xsl:with-param name="children" select="$subTree/g/rect"/>       </xsl:call-template>              <xsl:copy-of select="$subTree"/>            </g>        </xsl:template>         <!--Draw leaf nodes -->   <xsl:template match="*" mode="draw">     <xsl:param name="x"/>     <xsl:param name="y"/>     <xsl:param name="width"/>     <xsl:variable name="thisX"                           select="$x + $width div 2 - ($nodeWidth+$horzSpace) div 2"/>     <g>       <rect x="{$thisX}"                 y="{$y}"                 width="{$nodeWidth}"                 height="{$nodeHeight}"                 style="fill: none; stroke: black; stroke-width:{$strokeWidth};"/>     </g>   </xsl:template>      <!-- Recursive routine for drawing subtree -->   <!-- Allocates horz space based on weight given to node -->   <xsl:template name="drawSubtree">     <xsl:param name="nodes" select="/.."/>     <xsl:param name="weight"/>     <xsl:param name="x"/>     <xsl:param name="y"/>     <xsl:param name="width"/>          <xsl:if test="$nodes">       <xsl:variable name="node" select="$nodes[1]"/>       <xsl:variable name="ratio" select="$node/@tree:WEIGHT div $weight"/>           <!--Draw node and its children in sub partition of space-->       <!--based on current x and width allocation -->       <xsl:apply-templates select="$node" mode="draw">         <xsl:with-param name="x" select="$x"/>         <xsl:with-param name="y" select="$y"/>         <xsl:with-param name="width" select="$width * $ratio"/>       </xsl:apply-templates>           <!-- Process remaining nodes -->       <xsl:call-template name="drawSubtree">         <xsl:with-param name="nodes" select="$nodes[position( ) > 1]"/>         <xsl:with-param name="weight" select="$weight"/>         <xsl:with-param name="x" select="$x + $width * $ratio"/>         <xsl:with-param name="y" select="$y"/>         <xsl:with-param name="width" select="$width"/>       </xsl:call-template>     </xsl:if>        </xsl:template>     <!-- Elided code for connections. Same as previous stylesheet -->      </xsl:stylesheet>

Figure 11-16 shows the same input XML rendered with this new algorithm.

Figure 11-16. A more balanced version of the XML document structure turned into SVG

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 14.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 11-17, can be obtained by overriding drawConnections to call drawStraightConnections.

Figure 11-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 (now defunct) 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.