This page documents how KLay Layered implements label placement, port placement, and node sizing.
Work in Progress
Everything on this page is still subject to change – this is the bleeding edge of science! We're still working on this stuff, trying out different concepts, and moving things around, all for the benefit of mankind. You're welcome.
Contents
Introducing Important Stuff
When talking about label placement and node sizing, it helps to know what the two actually are. Let's start with node sizing:
Node Sizing
Node sizing is the act of determining the size of a node. In KIML, a layout algorithm can be granted different kinds of freedom in calculating the size of a node. The different kinds are expressed through a subset of the following options, as defined (and documented) in the SizeConstraint enumeration:
PORTSPORT_LABELSNODE_LABELSMINIMUM_SIZEDEFAULT_MINIMUM_SIZE
On the one extreme, the subset can be empty, thereby fixing the node size. On the other extreme, the set can contain all options, thereby giving the layout algorithm the maximum amount of flexibility.
On to port placement:
Port Placement
Port placement is the act of determining the position of ports. This includes determining the side of their node where the port gets attached, determining an order between ports on the same side, and determining the final position of each port. There are different levels of constraints on placing ports, as defined (and documents) in the PortConstraints enumeration:
FREEFIXED_SIDEFIXED_ORDERFIXED_RATIOFIXED_POS
And finally label placement:
Label Placement
Label placement is the act of determining the position of labels, with the aim of keeping readability high. The two most critical objectives in label placement are the following:
- Avoiding overlaps between labels and other graphical objects, including other labels.
- Making sure that each label is closer to its associated graphical feature than to other, unrelated graphical features.
KLay Layered distinguishes three kinds of labels:
- Node labels
- Port labels
- Edge labels
- Tail labels
- Mid labels
- Head labels
Node labels and port labels can be placed inside or outside of their particular node.
Relationship Between Label Placement, Port Placement, and Node Sizing
At first glance, label placement and node sizing are two separate problems. However, out of the three types of labels we currently support, two have considerable influence on the size of nodes (node labels and port labels, but you already figured this out yourself). Well, in fact, that's not completely true. It's not the labels that influence the size of nodes, it's the placement of labels. And if we didn't care for readability, the placement wouldn't influence node size at all. But we do. Take this simple example:
ToDo
Insert an image here. Two nodes, each with one port on the western side and one port on the eastern side. Port labels are placed inside the nodes and are the same for both nodes. The left node is too narrow to avoid overlaps between the port labels, the right node is wide enough.
The two nodes have to labeled ports each. Let's assume port positions to be fixed, and labels to be placed inside the nodes. Clearly, the left node is too narrow for the port labels to be placed without overlaps. If the labels are to be placed without overlaps, we need to increase the width of the node. Label placement influences node sizing.
Matters get more complicated if we allow port positions to be changed. If the western port is moved upwards and the eastern port downwards, the labels don't overlap anymore. Thus, label placement also influences port placement.
Just how much and in what ways the three influence each other is one source of complexity. One important task in implementing label placement, port placement, and node sizing is to determine the cases where we simply give up. If the user gives us fixed node sizes and fixed port positions, he cannot expect us to find an overlap-free label placement if port labels are to be placed inside the node.
Overview
Content Tools