Hierarchical layout
The development of algorithms for hierarchical layout is a subject area of computer science and deals with the definition of calculation rules for the layout and drawing of hierarchical graphs . The calculation of the layout and the drawing of the graphs can be carried out statically (the layout is calculated and drawn in one pass) or dynamically (a start layout is calculated and optimized and drawn in several passes).
Basics
In its pure form, the hierarchical graph is a directed graph and has a source (nodes without incoming edges) and several sinks (nodes without outgoing edges). The nodes between the source and the sink can be divided into equivalence classes depending on their distance from the source .
Layout approaches
To work out the characteristics of a hierarchical graph, there are two approaches to the layout, i.e. the arrangement of the nodes and edges of the graph to one another.
Ice crystal
A hierarchical layout as an ice crystal enables many different concrete forms with usually less space consumption compared to a layout as a tree, but cannot represent an order between nodes on the same level of equivalence.
With this layout approach, the source is the focus and all nodes of an equivalence class are equidistant from the node of the parent equivalence class. The concrete form of the layout differs on the one hand in whether
- all edges in the graph have the same length,
- all edges to nodes of a defined equivalence level have the same length, but all edges to nodes of the subordinate equivalence level have a different length that is the same as one another or
- all edges in the graph have a different length
and on the other hand by whether
- Nodes of a subordinate equivalence level can only be arranged away from the source or
- be arranged in any direction.
The simplest static algorithm for ice crystal layout calculates the arrangement of the nodes in concentric circles around the source. It determines the weight of each node based on the number of nodes of all subordinate equivalence levels connected to it. This weight is then a measure of the angle that the node claims on the concentric circle assigned to its equivalent planes. Both the calculation of the weight of the nodes and the drawing of nodes and edges are implemented using recursive method calls. In addition, a starting angle must be specified for drawing.
implementation
The following class gives an example of the implementation of a Node class in C #, which can be used to understand how it works.
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();
}
}
The following method gives an example of the implementation of full drawing in C #, calling the methods of the Node class for calculating the weight and drawing.
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();
}
tree
A hierarchical layout as a tree enables the representation of an order between nodes of the same equivalence level (e.g. by horizontal or vertical arrangement), but usually takes up more space than a layout than an ice crystal.
With this layout approach, a direction (e.g. from top to bottom) is given in which the graph spreads. All nodes of an equivalence class are on the same level. The specific form of the layout is characterized by the direction of development (horizontal or vertical) for each level of equivalence.
The simplest static algorithm for tree layout computes the arrangement of nodes on all equivalence levels in the same, e.g. B. horizontal, direction of development. It determines the weight of each node based on the number of nodes of all subordinate equivalence levels connected to it. This weight is then a measure of the proportion that the node demands on the direction of development assigned to its levels of equivalence. Both the calculation of the weight of the nodes and the drawing of nodes and edges are implemented using recursive method calls.
implementation
The following method gives an example of an implementation for extending the Node class in C #, which can be used to understand how it works.
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();
}
The following method gives an example of the implementation of full drawing in C #, calling the methods of the Node class for calculating the weight and drawing.
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();
}
Applications of hierarchical layouts
Hierarchical graphs are suitable for displaying structures without cycles (loops back and merging partial paths) such as: