Algorithmen für hierarchisches Layout

Dieser Artikel wurde aufgrund von inhaltlichen Mängeln auf der Qualitätssicherungsseite der Redaktion Informatik eingetragen. Dies geschieht, um die Qualität der Artikel aus dem Themengebiet Informatik auf ein akzeptables Niveau zu bringen. Hilf mit, die inhaltlichen Mängel dieses Artikels zu beseitigen und beteilige dich an der Diskussion! (+)
Begründung: Das Lemma ist problematisch, da der nichts zu Algorithmen sagt. Evtl. wäre das unter Hierarchisches Layout besser aufgehoben. Oder ganz woanders? Auch inhaltlich lässt sich das Thema des Artikels sicher noch etwas verständlicher/konkreter fassen. --Zinnmann d 11:34, 29. Okt. 2008 (CET)

Die Entwicklung von Algorithmen für hierarchisches Layout ist ein Themengebiet der Informatik und beschäftigt sich mit der Definition von Berechnungsvorschriften zum Layout und Zeichnen hierarchischer Graphen. Die Berechnung des Layouts und das Zeichnen der Graphen kann statisch (das Layout wird in einem Durchlauf berechnet und gezeichnet) oder dynamisch (es wird ein Start-Layout berechnet und in mehreren Durchläufen optimiert und gezeichnet) erfolgen.

Grundlagen

zufälliger hierarchischer Graph mit 4 Äquivalenzklassen

In seiner reinen Form ist der hierarchische Graph ein gerichteter Graph und hat eine Quelle (Knoten ohne eingehende Kanten) sowie mehrere Senken (Knoten ohne ausgehende Kanten). Die zwischen Quelle und Senke liegenden Knoten können abhängig von Ihrer Entfernung von der Quelle in Äquivalenzklassen unterteilt werden.

Layoutansätze

Um die Charakteristik eines hierarchischen Graphen herauszuarbeiten bieten sich zwei Ansätze für das Layout, also die Anordnung der Knoten und Kanten des Graphen zueinander, an.

Eiskristall

als Eiskristall dargestellter Graph mit 4 Äquivalenzklassen

Ein hierarchisches Layout als Eiskristall ermöglicht viele unterschiedliche konkrete Ausprägungen bei i. d. R. geringem Flächenverbrauch gegenüber einem Layout als Baum, kann aber keine Ordnung zwischen Knoten derselben Äquivalenzebene darstellen.

Bei diesem Layoutansatz steht die Quelle im Mittelpunkt und alle Knoten einer Äquivalenzklasse haben den gleichen Abstand vom Knoten der übergeordneten Äquivalenzklasse. Die konkrete Ausprägung des Layouts unterscheidet sich einerseits dadurch, ob

• alle Kanten im Graph die gleiche Länge aufweisen,
• alle Kanten zu Knoten einer definierten Äquivalenzebene die gleiche Länge aufweisen, aber alle Kanten zu Knoten der untergeordneten Äquivalenzebene eine andere, untereinander wieder gleiche Länge aufweisen oder
• alle Kanten im Graph eine unterschiedliche Länge aufweisen

und andererseits dadurch, ob

• Knoten einer untergeordneten Äquivalenzebene nur von der Quelle weg angeordnet werden oder
• in jeder beliebigen Richtung angeordnet werden.

Der einfachste statische Algorithmus für Eiskristall-Layout berechnet die Anordnung der Knoten auf konzentrischen Kreisen um die Quelle. Er ermittelt das Gewicht jedes Knotens anhand der Anzahl der mit ihm verbundenen Knoten aller untergeordneten Äquivalenzebenen. Dieses Gewicht ist dann Maß für den Winkel, den der Knoten auf dem seiner Äquivalenzebenen zugeordneten konzentrischen Kreis beansprucht. Sowohl die Berechnung des Gewichts der Knoten als auch das Zeichnen von Knoten und Kanten wird durch rekursive Methodenaufrufe realisiert. Für das Zeichnen muss darüber hinaus ein Startwinkel festgelegt werden.

Implementierung

Die folgende Klasse gibt ein Beispiel für die Implementierung einer Node-Klasse in C#, anhand derer man die Funktionsweise gut nachvollziehen kann.

public class GraphNode
{
    public const Int32 NodeRadius = 10;                        // Draw node as point, use radius = 10.

    public List<GraphNode> Children = new List<GraphNode>();   // Every node circa  have 0..N child nodes.
 
    public Int32 Level;                                        // Define the level of equivalence.
    public Int32 Weight;                                       // Store the aggregated weight.

    private GraphNode()                                        // Prevent default constructor calls.
    { ;   }
 
    public GraphNode(Int32 level)                              // Initializing constructor.
    { Level = level; }

    public Int32 CalculateWeight()                             // Calculate weight recusrively.
    {   if (Children.Count == 0)                Weight = 1;
        else                                    Weight = 0;
 
        foreach (GraphNode child in Children)   Weight += child.CalculateWeight();
 
        return Weight;
    }
 
    private Int32 X(Graphics g, double angle, double radius)   // Calculate x-posiotion on concentric circle.
    {   return (Int32)((g.VisibleClipBounds.Width)  / 2 + Math.Cos(angle) * radius * Level); }

    private Int32 Y(Graphics g, double angle, double radius)   // Calculate y-posiotion on concentric circle.
    {   return (Int32)((g.VisibleClipBounds.Height) / 2 + Math.Sin(angle) * radius * Level); }

    public void DrawEqualAngle(Graphics g, double radius, double start, double share, Rectangle parent)
    {   Brush     brush;
        Pen       pen;
        Double    angle;
        Rectangle rect;

        angle = start + Weight * share / 2;                    // Calculate angle of this node.
        rect = new Rectangle(X(g, angle, radius) - NodeRadius, // Calculate position of this node.
                             Y(g, angle, radius) - NodeRadius,
                             NodeRadius * 2, NodeRadius * 2);

        foreach (GraphNode child in Children)                  // Draw child nodes.
        {   child.DrawEqualAngle(g, radius, start, share, rect);
            start += share * child.Weight;
        }

        brush = new SolidBrush((Level == 1 ? Color.DarkBlue : 
                                (Level == 2 ? Color.DarkGreen : Color.DarkRed)));
        pen = new Pen(brush);

        g.DrawLine(pen, parent.Left + parent.Width / 2,        // Draw this node's connection to parent.
                   parent.Top + parent.Height / 2,
                   rect.Left + rect.Width / 2, rect.Top + rect.Height / 2);
        g.FillEllipse(brush, rect);                            // Draw this node.

        pen.Dispose();
        brush.Dispose();
    }
}

Die folgende Methode gibt ein Beispiel für die Implementierung des vollständigen Zeichnens in C#, wobei die Methoden der Node-Klasse für die Berechnung des Gewichtes und das Zeichnen aufgerufen werden.

    private void PaintEqualAngle()
    {   Int32 totalWeight = 0;
        Double startAngle = 0;
        Graphics g;
        Brush brush;
        Rectangle rect;

        foreach (GraphNode node in Graph)                       // Calculate maximum weight.
            totalWeight += node.CalculateWeight();

        g = this.CreateGraphics();
        brush = new SolidBrush(BackColor);
        g.FillRectangle(brush, g.VisibleClipBounds);            // Clear background.
        brush.Dispose();

        rect = new Rectangle((Int32)((g.VisibleClipBounds.Width) / 2) - GraphNode.NodeRadius,
                             (Int32)((g.VisibleClipBounds.Height) / 2) - GraphNode.NodeRadius,
                             GraphNode.NodeRadius * 2, GraphNode.NodeRadius * 2);

        foreach (GraphNode node in Graph)                       // Draw child nodes.
        {   node.DrawEqualAngle(g, Math.Min(g.VisibleClipBounds.Width, g.VisibleClipBounds.Height) / 7,
                                startAngle, Math.PI * 2 / totalWeight, rect);
            startAngle += Math.PI * 2 / totalWeight * node.Weight;
        }

        brush = new SolidBrush(Color.Black);
        g.FillEllipse(brush, rect);                             // Draw root.
        brush.Dispose();
        g.Dispose();
    }

Baum

als strenger Baum dargestellter Graph mit 4 Äquivalenzklassen

Ein hierarchisches Layout als Baum ermöglicht die Darstellung einer Ordnung zwischen Knoten derselben Äquivalenzebene (z. B. durch horizontale oder vertikale Anordnung), beansprucht aber i. d. R. mehr Fläche als ein Layout als Eiskristall.

Bei diesem Layoutansatz ist eine Richtung (z. B. von Oben nach Unten) vorgegeben, in der sich der Graph ausbreitet. Alle Knoten einer Äquivalenzklasse liegen auf derselben Ebene. Die konkrete Ausprägung des Layouts wird gekennzeichnet durch die Entwicklungsrichtung (horizontal oder vertikal) je Äquivalenzebene.

Der einfachste statische Algorithmus für Baum-Layout berechnet die Anordnung der Knoten auf allen Äquivalenzebenen in derselben, z. B. horizontalen, Entwicklungsrichtung. Er ermittelt das Gewicht jedes Knotens anhand der Anzahl der mit ihm verbundenen Knoten aller untergeordneten Äquivalenzebenen. Dieses Gewicht ist dann Maß für den Anteil, den der Knoten auf der seiner Äquivalenzebenen zugeordneten Entwicklungsrichtung beansprucht. Sowohl die Berechnung des Gewichts der Knoten als auch das Zeichnen von Knoten und Kanten wird durch rekursive Methodenaufrufe realisiert.

Implementierung

Die folgende Methode gibt ein Beispiel einer Implementierung zur Erweiterung der Node-Klasse in C#, anhand derer man die Funktionsweise gut nachvollziehen kann.

    public void DrawHorizontalTree(Graphics g, double distance, double start, double share, Rectangle parent)
    {   Brush brush;
        Pen pen;
        Double position;
        Rectangle rect;

        position = start + Weight * share / 2;                  // Calculate angle of this node.
        rect = new Rectangle((Int32)(position - NodeRadius),    // Calculate position of this node.
                             (Int32)(distance * (Level + 1) - NodeRadius),
                             NodeRadius * 2, NodeRadius * 2);

        foreach (GraphNode child in Children)                   // Draw child nodes.
        {   child.DrawHorizontalTree(g, distance, start, share, rect);
            start += share * child.Weight;
        }

        brush = new SolidBrush((Level == 1 ? Color.DarkBlue : 
                                (Level == 2 ? Color.DarkGreen : Color.DarkRed)));
        pen = new Pen(brush);

        g.DrawLine(pen, parent.Left + parent.Width / 2,         // Draw this node's connection to parent.
                   parent.Top + parent.Height / 2,
                   rect.Left + rect.Width / 2, rect.Top + rect.Height / 2);
        g.FillEllipse(brush, rect);                            // Draw this node.

        pen.Dispose();
        brush.Dispose();
    }

Die folgende Methode gibt ein Beispiel für die Implementierung des vollständigen Zeichnens in C#, wobei die Methoden der Node-Klasse für die Berechnung des Gewichtes und das Zeichnen aufgerufen werden.

    private void PaintHorizontalTree()
    {   Int32 totalWeight = 0;
        Double startWidth = 0;
        Graphics g;
        Brush brush;
        Rectangle rect;

        foreach (GraphNode node in Graph)                       // Calculate maximum weight.
            totalWeight += node.CalculateWeight();

        g = this.CreateGraphics();
        brush = new SolidBrush(BackColor);
        g.FillRectangle(brush, g.VisibleClipBounds);            // Clear background.
        brush.Dispose();

        rect = new Rectangle((Int32)((g.VisibleClipBounds.Width) / 2) - GraphNode.NodeRadius,
                             (Int32)((g.VisibleClipBounds.Height) / 5) - GraphNode.NodeRadius,
                             GraphNode.NodeRadius * 2, GraphNode.NodeRadius * 2);

        foreach (GraphNode node in Graph)                       // Draw child nodes.
        {   node.DrawHorizontalTree(g, g.VisibleClipBounds.Height / 5,
                                    startWidth, g.VisibleClipBounds.Width / totalWeight, rect);
            startWidth += g.VisibleClipBounds.Width / totalWeight * node.Weight;
        }

        brush = new SolidBrush(Color.Black);
        g.FillEllipse(brush, rect);                             // Draw root.
        brush.Dispose();
        g.Dispose();
    }

Anwendungen hierarchischer Layouts

Hierarchische Graphen eignen sich zur Darstellung von Strukturen ohne Zyklen (Rückschleifen und Zusammenführung von Teilpfaden) wie:

• Organigrammen
• Funktionsbäumen
• Syntaxbäumen