Главная » XSLT » Создание графического представления деревьев

1

Задача

Требуется представить иерархическую структуру данных в виде дерева.

Решение

В этом разделе мы рассмотрим два разных алгоритма рисования дерева. Есть и более сложные, но эти дают вполне приемлемые результаты.

Если бы дерево было сбалансированным, то нарисовать его было бы просто; надо лишь разделить имеющее горизонтальное пространство на количество узлов на каждом уровне, а вертикальное – на число уровней1. К сожалению, реальные деревья не всегда симметричны. Поэтому алгоритм должен учитывать ширину каждой ветви.

Первый способ требует лишь одного прохода по дереву. Однако для этого придется включить в результирующий SVG-файл посторонние атрибуты, необхо­димые только для служебных целей. Мы поместим эти атрибуты в отдельное про­странство имен, чтобы исключить конфликты с атрибутами SVG:

<?xml version="1.0" encoding="UTF-8"?> <xsl:stylesheet

<!– версия 1.1 объявлена не действующей, но Saxon поддерживает ее –>

<!– ради xsl:script. –>

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="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/2 0 01/REC-SVG-2 0 010904/DTD/ svg10.dtd"/>

<!– Эти параметры управляют линейными характеристиками дерева и его узлов –>

<xsl:variable name="width" select="5 0 0"/> <xsl:variable name="height" select="5 0 0"/> <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"/>

<svg width="{$width}" height="{$height}">

<!– Запоминаем поддерево этого узла в переменной –> <xsl:variable name="subTree">

<xsl:apply-templates/> </xsl:variable>

<!— maxPos — это максимум из двух самых отдаленных координат X и Y –> <!– при рисовании узла –> <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)"/>

<!– Масштабируем дерево, так чтобы все узлы оказались в области рисования –>

<g transform="scale({$maxDim div ($maxPos + 1)})">

<!– Пользуйтесь функцией exsl:node-set($subTree) –>

<!– если ваш процессор XSLT поддерживает только версию 1.0 –>

<xsl:copy-of select="$subTree/g/*"/> </g>

</svg>

</xsl:template>

<!– Шаблон сопоставляется со всеми нелистовыми узлами —> <xsl:template match="*[*]">

<xsl:variable name="subTree">

<xsl:apply-templates/> </xsl:variable>

<!— По горизонтали узел располагается так, чтобы он был центрирован –> <!– над своими потомками –> <xsl:variable name="thisX"

select="sum($subTree/*/@tree:THISX)

div count($subTree/*)"/>

<xsl:variable name="maxX" select="$subTree/*[last( )]/@tree:MAXX"/>

<!— По вертикали узел располагается на своем уровне —> <xsl:variable name="thisY"

select="($vertSpace + $nodeHeight) * count(ancestor-or-self::*)"/>

<xsl:call-template name="emath:max">

<!– Пользуйтесь функцией exsl:node-set($subTree) –> <!— если ваш процессор XSLT поддерживает только версию 1.0 —> <xsl:with-param name="nodes" select="$subTree/*/@tree:MAXY"/> </xsl:call-template> </xsl:variable>

<!– Помещаем родителя, его детей и соединители в группу –> <!– Включаем в эту группу также служебные атрибуты для передачи –> <!– информации вверх по дереву –>

<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"/>

<!– Рисуем соединительную линию между текущим узлом и его потомками — >

<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>

<!– Копируем SVG поддерева –> <xsl:copy-of select="$subTree"/> </g>

</xsl:template>

<!– Этот шаблон сопоставляется с листовыми узлами –> <xsl:template match="*">

<!— По горизонтали листовые узлы располагаются с учетом количества —> <!– предшествующих листовых узлов –> <xsl:variable name="maxX"

select="($horzSpace + $nodeWidth) *

(count(preceding::*[not(child::*)] ) + 1) "/>

Можно было бы с помощью выражения count(ancestor-or-self::*) каждый раз вычислять уровень. Но проще и эффективнее передавать уровень в качестве дополнительного параметра:

<!– По вертикали узел располагается на своем уровне –> <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>

<!– Переопределить в импортирующей таблице стилей, если желательно –> <!– изменить стиль рисования соединительных линий –> <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>

<!– Прямая соединительная линия — это кратчайший путь от середины –> <!– нижней стороны родителя до середины верхней стороны потомка —> <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>

<!– Прямоугольная соединительная линия — это состоящий только из –> <!– горизонтальных и вертикальных отрезков кратчайший путь от –> <!– середины нижней стороны родителя до середины верхней стороны –> <!– потомка — >

<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"/>

<!– вертикальный отрезок, отходящий от родителя –> <line x1="{$xParent + $widthParent div 2}" y1="{$yParent + $heightParent}" x2="{$xParent + $widthParent div 2}" y2="{$midY}"

style="stroke: black; stroke-width:0.1;"/> <!– средний горизонтальный отрезок –>

<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;"/>

<!– вертикальные отрезки, идущие к потомкам –> <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>

Эта таблица стилей рисует структуру произвольного XML-документа в виде дерева. На рис. 11.15 показан результат ее применения в простому входному XML-файлу.

Рис. 11.15. Структура XML-документа, преобразованная в SVG

Первый алгоритм располагает родительские узлы посередине относительно множества их дочерних узлов. В результате для несбалансированных деревьев корневой узел оказывается не в центре. Следующий алгоритм несколько лучше, поскольку решает проблему смещения по горизонтали и не засоряет SVG посто­ронними атрибутами. Однако для него требуется два прохода по дереву:

<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="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/2 0 01/REC-SVG-

2 0 010 90 4/DTD/svg10.dtd"/>

<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="/">

<!– Ha пеpвoм пpoxoде входной документ кoпиpyется с добавлением –> <!– служебных aтpибyтoв –>

<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)"/>

<!– Ha втopoм пpoxoде создается 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>

<!– Размещаем узлы вместе с их потомками –> <xsl:template match="node( )[*]" mode="layout"> <xsl:variable name="subTree">

<xsl:apply-templates mode="layout"/> </xsl:variable>

<!— Нелистовым узлам пpисвaивaется вес, paвный сумме весов их детей –>

<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>

<!– Размещаем листовые узлы –> <xsl:template match="*" mode="layout">

<xsl:variable name="depth" select="count(ancestor-or-self::*) "/> <xsl:copy>

<xsl:copy-of select="@*"/>

<!– Листовым узлам присваивается вес 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>

<!– Рисуем нелистовые узлы –>

<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>

<!– Рисуем листовые узлы –> <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>

<!– Рекурсивная процедура для рисования поддерева –>

<!– Распределяет горизонтальное пространство с учетом веса узла –>

<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"/>

<!– Рисуем узел и его детей в выделенной области, –>

<!– основываясь на текущем значении x и вычисленной ширине –>

<!– области –>

<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>

<!– Обрабатываем остальные узлы –> <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>

<!– Код рисования соединительных линий опущен, т.к. не отличается –> <!– от предыдущего примера. –>

</xsl:stylesheet>

На рис. 11.16 показано, как тот же самый входной документ рисуется новым алгоритмом.

Рис. 11.16. Более сбалансированное представление структуры XML-документа

Обсуждение

Предыдущие рецепты не полны, так как позволяют нарисовать только скелет дерева без содержимого. Очевидное улучшение – добавить к узлам дерева текст, чтобы можно было распознать, к чему они относятся. Это не просто, поскольку SVG не масштабирует текст автоматически. Дополнительную сложность вносит тот факт, что ширина прямоугольников становится зависимой от объема размещенного в них текста. См. рецепт 14.14 и написанную на Java функцию расширения, которая по­могает решить проблему размещения текста в SVG.

Мы решили отобразить все узлы входного документа на узлы SVG-дерева. На практике, вероятно, следовало бы отфильтровать ненужные узлы, указав вместо выражений match="node( )[*]" и match="*" другие образцы.

Если структура дерева не должна буквально повторять иерархическую струк­туру XML-документа, то следует выполнить предварительную обработку с целью преобразования структуры.

В таблицы стилей включен код для поддержки двух стилей соединительных линий. В примерах мы пользовались прямоугольными соединениями. Чтобы нари­совать прямые соединения, как показано на рис. 11.17, нужно переопределить drawConnections, так чтобы вызывался шаблон drawStraightConnections.

С точки зрения переносимости в этих таблицах стилей есть две проблемы. Во-первых, в них вызывается написанная на Java функция расширения Math:max. Ее легко можно реализовать и на XSLT. Однако в таблицах стилей для генерации SVG часто бывают нужны и другие расширения, так что в общем случае их использование неизбежно. Вторая проблема – предположение о поддержке спецификации XSLT 1.1 (ныне объявленной недействующей) или более поздней, чтобы фрагменты результирующего дерева можно было корректно рассматривать как наборы узлов. Можно вместо этого воспользоваться теми средствами конвер­тации наборов узлов, которые имеются в доступном вам процессоре XSLT.

Рис. 11.17. Структура XML-документа, преобразованная в SVG с использованием прямых соединений

Peter Eades, Roberto Tamassia, and Ionnis G. Tollis Graph Drawing: Algorithms for the Visualization of Graphs (Prentice Hall, 1999). Но имейте в виду, что она насы­щена нетривиальной математикой; это не просто сборник алгоритмов на псев­докоде.

Мангано Сэл  XSLT. Сборник рецептов. – М.: ДМК Пресс, СПБ.: БХВ-Петербург, 2008. – 864 с.: ил.

По теме:

  • Комментарии

1 комментарий

  1. Laa911 says:

    А есть ли программа которая может автоматически создавать
    1. деревья при вводе праметров дерева по уровням
    2. делать кружочки пропорциоанально сумме в в узле?

    Может есть что то подобное ?