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
Bearbeiten
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
BearbeitenUm 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
Bearbeiten
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
BearbeitenDie 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 recursively.
{ 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-position 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-position 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
Bearbeiten
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
BearbeitenDie 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
BearbeitenHierarchische Graphen eignen sich zur Darstellung von Strukturen ohne Zyklen (Rückschleifen und Zusammenführung von Teilpfaden) wie: