Hierarchisches Layout

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen
Dieser Artikel oder Abschnitt bedarf einer grundsätzlichen Überarbeitung. Näheres sollte auf der Dieser Artikel angegeben sein. Bitte hilf mit, ihn zu verbessern, und entferne anschließend diese Markierung.

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.

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

[Bearbeiten | Quelltext bearbeiten ]

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.

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

[Bearbeiten | Quelltext bearbeiten ]

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

publicclassGraphNode
{
publicconstInt32NodeRadius=10;// Draw node as point, use radius = 10.
publicList<GraphNode>Children=newList<GraphNode>();// Every node circa have 0..N child nodes.
publicInt32Level;// Define the level of equivalence.
publicInt32Weight;// Store the aggregated weight.
privateGraphNode()// Prevent default constructor calls.
{;}
publicGraphNode(Int32level)// Initializing constructor.
{Level=level;}
publicInt32CalculateWeight()// Calculate weight recursively.
{if(Children.Count==0)Weight=1;
elseWeight=0;
foreach(GraphNodechildinChildren)Weight+=child.CalculateWeight();
returnWeight;
}
privateInt32X(Graphicsg,doubleangle,doubleradius)// Calculate x-position on concentric circle.
{return(Int32)((g.VisibleClipBounds.Width)/2+Math.Cos(angle)*radius*Level);}
privateInt32Y(Graphicsg,doubleangle,doubleradius)// Calculate y-position on concentric circle.
{return(Int32)((g.VisibleClipBounds.Height)/2+Math.Sin(angle)*radius*Level);}
publicvoidDrawEqualAngle(Graphicsg,doubleradius,doublestart,doubleshare,Rectangleparent)
{Brushbrush;
Penpen;
Doubleangle;
Rectanglerect;
angle=start+Weight*share/2;// Calculate angle of this node.
rect=newRectangle(X(g,angle,radius)-NodeRadius,// Calculate position of this node.
Y(g,angle,radius)-NodeRadius,
NodeRadius*2,NodeRadius*2);
foreach(GraphNodechildinChildren)// Draw child nodes.
{child.DrawEqualAngle(g,radius,start,share,rect);
start+=share*child.Weight;
}
brush=newSolidBrush((Level==1?Color.DarkBlue:
(Level==2?Color.DarkGreen:Color.DarkRed)));
pen=newPen(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.

privatevoidPaintEqualAngle()
{Int32totalWeight=0;
DoublestartAngle=0;
Graphicsg;
Brushbrush;
Rectanglerect;
foreach(GraphNodenodeinGraph)// Calculate maximum weight.
totalWeight+=node.CalculateWeight();
g=this.CreateGraphics();
brush=newSolidBrush(BackColor);
g.FillRectangle(brush,g.VisibleClipBounds);// Clear background.
brush.Dispose();
rect=newRectangle((Int32)((g.VisibleClipBounds.Width)/2)-GraphNode.NodeRadius,
(Int32)((g.VisibleClipBounds.Height)/2)-GraphNode.NodeRadius,
GraphNode.NodeRadius*2,GraphNode.NodeRadius*2);
foreach(GraphNodenodeinGraph)// 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=newSolidBrush(Color.Black);
g.FillEllipse(brush,rect);// Draw root.
brush.Dispose();
g.Dispose();
}
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

[Bearbeiten | Quelltext bearbeiten ]

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

publicvoidDrawHorizontalTree(Graphicsg,doubledistance,doublestart,doubleshare,Rectangleparent)
{Brushbrush;
Penpen;
Doubleposition;
Rectanglerect;
position=start+Weight*share/2;// Calculate angle of this node.
rect=newRectangle((Int32)(position-NodeRadius),// Calculate position of this node.
(Int32)(distance*(Level+1)-NodeRadius),
NodeRadius*2,NodeRadius*2);
foreach(GraphNodechildinChildren)// Draw child nodes.
{child.DrawHorizontalTree(g,distance,start,share,rect);
start+=share*child.Weight;
}
brush=newSolidBrush((Level==1?Color.DarkBlue:
(Level==2?Color.DarkGreen:Color.DarkRed)));
pen=newPen(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.

privatevoidPaintHorizontalTree()
{Int32totalWeight=0;
DoublestartWidth=0;
Graphicsg;
Brushbrush;
Rectanglerect;
foreach(GraphNodenodeinGraph)// Calculate maximum weight.
totalWeight+=node.CalculateWeight();
g=this.CreateGraphics();
brush=newSolidBrush(BackColor);
g.FillRectangle(brush,g.VisibleClipBounds);// Clear background.
brush.Dispose();
rect=newRectangle((Int32)((g.VisibleClipBounds.Width)/2)-GraphNode.NodeRadius,
(Int32)((g.VisibleClipBounds.Height)/5)-GraphNode.NodeRadius,
GraphNode.NodeRadius*2,GraphNode.NodeRadius*2);
foreach(GraphNodenodeinGraph)// Draw child nodes.
{node.DrawHorizontalTree(g,g.VisibleClipBounds.Height/5,
startWidth,g.VisibleClipBounds.Width/totalWeight,rect);
startWidth+=g.VisibleClipBounds.Width/totalWeight*node.Weight;
}
brush=newSolidBrush(Color.Black);
g.FillEllipse(brush,rect);// Draw root.
brush.Dispose();
g.Dispose();
}

Anwendungen hierarchischer Layouts

[Bearbeiten | Quelltext bearbeiten ]

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

Abgerufen von „https://de.wikipedia.org/w/index.php?title=Hierarchisches_Layout&oldid=251000356"