Baumdiagramme erzeugen

(Auszug aus "XSLT Kochbuch" von Sal Mangano)

Problem

Sie möchten die hierarchische Struktur Ihrer Daten als Baum darstellen.

Lösung

Dieser Abschnitt stellt zwei verschiedene Algorithmen für die Darstellung von Bäumen vor, von denen keiner als der ausgefeilteste verfügbare Algorithmus gilt, aber beide führen zu brauchbaren Ergebnissen.

Wenn alle Bäume, die Sie jemals darstellen müssten, ausgeglichen wären (oft sagt man auch balanciert), dann wäre die Darstellung von Bäumen ein Leichtes, weil Sie auf jeder Ebene nur den horizontal verfügbaren Raum durch die Anzahl der Knoten und den vertikalen Raum durch die Anzahl der Ebenen teilen müssten. (Tatsächlich müssen Sie durch die Anzahl der Knoten + 1 teilen, sonst machen Sie einen sogenannten »Zaunpfahlfehler«, engl. »fencepost error«, bei dem Sie um eins daneben liegen.) Leider sind die Bäume, die Ihnen im wirklichen Leben begegnen werden, nicht ganz so symmetrisch. Deswegen brauchen Sie einen Algorithmus, der die Breite aller Äste berücksichtigt.

Bei der ersten Methode erfolgt nur ein Durchgang über den Baum. Um sie aber durchführen zu können, müssen einige fremde Attribute aus Buchführungsgründen ins resultierende SVG eingebettet werden. In diesem Beispiel werden diese Attribute in einem Namensraum gesetzt, damit es zu keinem Konflikt mit SVG-spezifischen Attributen kommt:

<?xml version="1.0" encoding="UTF-8"?>
<!-- version 1.1 ist erloschen, aktiviert aber in Saxon die Eigenschaft xsl:script. -->
<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/2001/REC-SVG-20010904/DTD/svg10.dtd"/>
  <!-- Diese Parameter steuern die Ausdehnung des Baums und seiner Knoten -->
  <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}">
      <!-- Halte den Unterbaum dieses Knotens in einer Variablen fest -->
      <xsl:variable name="subTree">
        <xsl:apply-templates/>
      </xsl:variable>
      <!-- maxPos ist das Maximum der entferntesten X- oder Y-Koordinate, die beim Rendern eines Knotens benutzt wird. -->
      <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)"/>
      <!-- Wir skalieren den Baum, damit alle Knoten ins Koordinatensystem passen. -->
      <g transform="scale({$maxDim div ($maxPos + 1)})">
      <!-- Verwenden Sie exsl:node-set($subTree), falls Ihr XSLT-Prozessor die Version 1.0 hat. -->
        <xsl:copy-of select="$subTree/g/*"/>
      </g>
    </svg>
  </xsl:template>
  <!-- Das passt auf alle Knoten, die keine Blätter sind. -->
  <xsl:template match="*[*]">
    <xsl:variable name="subTree">
      <xsl:apply-templates/>
    </xsl:variable>
    <!-- Positioniere diesen Knoten horizontal abhängig von der mittleren Position seiner Kindknoten -->
    <xsl:variable name="thisX" select="sum($subTree/*/@tree:THISX) div count($subTree/*)"/>
    <xsl:variable name="maxX" select="$subTree/*[last( )]/@tree:MAXX"/>
    <!-- Positioniere diesen Knoten vertikal abhängig von seiner Tiefe -->
    <xsl:variable name="thisY" select="($vertSpace + $nodeHeight) * count(ancestor-or-self::*)"/>
    <xsl:variable name="maxY">
      <xsl:call-template name="emath:max">
        <!-- Verwenden Sie exsl:node-set($subTree), falls Ihr XSLT-Prozessor die Version 1.0 hat. -->
        <xsl:with-param name="nodes" select="$subTree/*/@tree:MAXY"/>
      </xsl:call-template>
    </xsl:variable>
    <!-- Wir platzieren den Elternknoten und seine Kindknoten sowie die Verbindungen in eine Gruppe. Außerdem fügen wir zur Gruppe ein paar Verwaltungsattribute hinzu, um im Baum Information nach oben weitergeben zu können. -->
    <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"/>
      <!-- Zeichne eine Verbindungslinie zwischen dem aktuellen Knoten und dessen Kindknoten -->
      <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>
      <!-- Kopiere das SVG des Unterbaums -->
      <xsl:copy-of select="$subTree"/>
    </g>
  </xsl:template>
  <!-- Das passt auf alle Blattknoten -->
  <xsl:template match="*">
    <!-- Positioniere Blattknoten horizontal abhängig von der Anzahl der vorherigen Blattknoten -->
    <xsl:variable name="maxX" select="($horzSpace + $nodeWidth) * (count(preceding::*[not(child::*)] ) + 1)"/>

Sie können count(ancestor-or-self::*) verwenden, um jedes Mal an die Ebene, d.h. die Tiefe im Baum, heranzukommen. Vielleicht möchten Sie aber auch einen Parameter hinzufügen, um die aktuelle Ebene im Baum weiter nach unten zu geben, anstatt sie jedes Mal neu zu berechnen:

    <!-- Positioniere diesen Knoten vertikal abhängig von seiner Tiefe -->
    <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>
  <!-- Überschreiben Sie das im importierenden Stylesheet, wenn Sie gerade oder eigene Verbindungslinien haben möchten. -->
  <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>
  <!-- Gerade Verbindungen nehmen den kürzesten Pfad vom Zentrum des unteren Elternknotenteils zum Zentrum des oberen Kindknotenteils. -->
  <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>
  <!-- Rechteckige Verbindungen nehmen den kürzesten Pfad vom Zentrum des unteren Elternknotenteils zum Zentrum des oberen Kindknotenteils und bestehen nur aus horizontalen und vertikalen Linien. -->
  <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"/>
    <!-- vertikale Linie vom Elternknoten -->
    <line x1="{$xParent + $widthParent div 2}" y1="{$yParent + $heightParent}" x2="{$xParent + $widthParent div 2}" y2="{$midY}" style="stroke: black; stroke-width:0.1;"/>
    <!-- horizontale Linie in der Mitte -->
    <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;"/>
    <!-- vertikale Linien zu den Kindknoten -->
    <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>

Dieses Stylesheet stellt die Struktur eines beliebigen XML-Dokuments als Baum dar. Die folgende Abbildung zeigt das Ergebnis für eine einfache XML-Eingabedatei.

Eine XML-Dokumentstruktur, umgewandelt in SVG

Abbildung: Eine XML-Dokumentstruktur, umgewandelt in SVG.

Der erste Algorithmus erzeugt Bäume, bei denen die horizontale Position von Elternknoten abhängig von der mittleren Position ihrer Kinder ist. Bei unausgeglichenen Bäumen führt das dazu, dass der Wurzelknoten nicht in der Mitte liegt. Der folgende Algorithmus stellt insofern eine leichte Verbesserung dar, als er dieses Versetzungsproblem behebt und das SVG nicht mit fremden Attributen zumüllt. Dafür macht er jedoch zwei Durchläufe über den eingegebenen Baum:

<?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="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="/">
    <!-- 1. Durchgang kopiert die Eingabe mit hinzugefügten Verwaltungsattributen -->
    <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)"/>
    <!-- 2. Durchgang erzeugt 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>
  <!-- Layoutknoten mit Kindknoten -->
  <xsl:template match="node( )[*]" mode="layout">
    <xsl:variable name="subTree">
      <xsl:apply-templates mode="layout"/>
    </xsl:variable>
    <!-- Den Knoten, die keine Blätter sind, wird die Summe der Gewichte ihrer Kindknoten zugewiesen. -->
    <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>
  <!-- Layoutblattknoten -->
  <xsl:template match="*" mode="layout">
    <xsl:variable name="depth" select="count(ancestor-or-self::*) "/>
    <xsl:copy>
      <xsl:copy-of select="@*"/>
      <!-- Blattknoten erhalten das Gewicht 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>
  <!-- Zeichne Knoten, die keine Blätter sind. -->
  <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>
  <!-- Zeichne Blattknoten -->
  <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>
  <!-- Rekursive Routine zum Zeichnen von Unterbäumen. Alloziert horizontalen Raum abhängig vom Gewicht des Knotens. -->
  <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"/>
      <!-- Zeichne Knoten samt Kindknoten in einem eigenen Raumanteil, abhängig vom aktuellen X-Wert und allozierter Breite. -->
      <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>
      <!-- Bearbeite verbleibende Knoten -->
      <xsl:call-template name="drawSubtree">
        <xsl:with-param name="nodes" select="$nodes[position( ) &gt; 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>
  <!-- Code für Verbindungen ausgelassen. Identisch mit vorherigem Stylesheet. -->
</xsl:stylesheet>

Die folgende Abbildung zeigt die mit diesem neuen Algorithmus erstellte Ausgabe für die gleiche XML-Eingabedatei.

Ausgeglichenere Version der XML-Dokumentstruktur, umgewandelt in SVG

Abbildung: Eine ausgeglichenere Version der XML-Dokumentstruktur, umgewandelt in SVG.

Diskussion

Die vorangegangenen Rezepte sind unvollständig, weil sie nur das Skelett des Baums, aber nicht seinen Inhalt darstellen. Eine nahe liegende Erweiterung bestünde darin, zu den Knoten einen Text hinzuzufügen, damit man sie identifizieren kann. Eine solche Erweiterung kann jedoch knifflig sein, da SVG Text nicht automatisch skaliert; und besonders schwierig wird es dann, wenn die Breite eines Knotens sich abhängig vom darin enthaltenen Text ändert. Im Rezept Erweiterungsfunktionen mit Java hinzufügen finden Sie eine Java-Erweiterungsfunktion, die bei der Lösung von Layout-Problemen mit SVG hilfreich sein kann.

Bisher haben Sie alle Knoten im Eingabedokument auf Knoten im SVG-Baum abgebildet. Bei einem realen Problem würden Sie vermutlich die unwichtigen Knoten mit Hilfe von Vergleichsmustern herausfiltern, die spezifischer sind als match="node( )[*]" und match="*".

Falls die Baumstruktur Ihrer Daten nicht exakt von der hierarchischen Struktur im XML modelliert wird, dann müssen Sie eine Vorverarbeitung der Eingabe durchführen, um eine solche Struktur zu erzeugen. Das wäre dann z.B. der Fall, wenn die Eltern-Kind-Beziehung mit Hilfe von Zeigern und Zielknoten ausgedrückt wäre, die in Attributen gespeichert sind.

Die Stylesheets enthalten Code, der zwei Arten von Verbindungen unterstützt. In den Beispielen werden rechtwinklige Verbindungen verwendet. Direkte Verbindungen, wie sie in der folgenden Abbildung zu sehen sind, erhalten Sie durch das Überschreiben von drawConnections, sodass drawStraightConnections aufgerufen wird.

Eine XML-Dokumentstruktur als SVG mit direkten Verbindungen

Abbildung: Eine XML-Dokumentstruktur als SVG mit direkten Verbindungen.

Bei diesen Stylesheets gibt es zwei Probleme in Hinblick auf deren Portabilität. Erstens, verwenden sie eine Java-Erweiterung, um auf die Java-Funktion Math:max zuzugreifen. Diese Funktion kann leicht in XSLT implementiert werden. Da aber SVG-erzeugende Stylesheets oftmals noch weitere Erweiterungsfunktionen benötigen, lässt sich dieses Problem eventuell nicht vermeiden. Das zweite Portabilitätsproblem besteht darin, dass sie die Unterstützung von XSLT 1.1 (einer erloschenen Version) oder höher verlangen, in dem Fragmente von Ergebnisbäumen korrekt als Knotenmengen behandelt werden können. Vielleicht möchten Sie stattdessen lieber den Knotenmengen-Umwandler Ihres XSLT-Prozessors verwenden.

Siehe auch

Wenn Sie mehr über ausgefeilte Algorithmen für das Zeichnen von Bäumen und allgemeineren Graphen lernen möchten, sollten Sie das Buch Graph Drawing: Algorithms for the Visualization of Graphs von Giuseppe Di Battista, Peter Eades, Roberto Tamassia und Ionnis G. Tollis (Prentice Hall, 1999) lesen. Seien Sie aber darauf gefasst, dass es viel anspruchsvolle Mathematik enthält und kein Kochbuch mit Algorithmen in Pseudocode ist.

  

zum Seitenanfang

<< zurück vor >>

 

 

 

Tipp der data2type-Redaktion:
Zum Thema XSLT bieten wir auch folgende Schulungen zur Vertiefung und professionellen Fortbildung an:

Copyright © 2006 O'Reilly Verlag GmbH & Co. KG
Für Ihren privaten Gebrauch dürfen Sie die Online-Version ausdrucken.
Ansonsten unterliegt dieses Kapitel aus dem Buch "XSLT Kochbuch" denselben Bestimmungen, wie die gebundene Ausgabe: Das Werk einschließlich aller seiner Teile ist urheberrechtlich geschützt. Alle Rechte vorbehalten einschließlich der Vervielfältigung, Übersetzung, Mikroverfilmung sowie Einspeicherung und Verarbeitung in elektronischen Systemen.

O'Reilly Verlag GmbH & Co. KG, Balthasarstraße 81, 50670 Köln, kommentar(at)oreilly.de