Last modified by Richard Kreissig on 2023/09/14 10:22
Show last authors
1 This page documents how KLay Layered implements label placement, port placement, and node sizing.
2
3 **Contents**
4
5
6
7 {{toc/}}
8
9 = Introducing Important Stuff =
10
11 When talking about label placement and node sizing, it helps to know what the two actually are. Let's start with node sizing:
12
13 Node Sizing
14
15 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 [[{{code language="none"}}SizeConstraint{{/code}}>>url:http://rtsys.informatik.uni-kiel.de/fisheye/browse/~~br=master/kieler/plugins/de.cau.cs.kieler.kiml/src/de/cau/cs/kieler/kiml/options/SizeConstraint.java?r=HEAD||shape="rect"]] enumeration:
16
17 * {{code language="none"}}PORTS{{/code}}
18 * {{code language="none"}}PORT_LABELS{{/code}}
19 * {{code language="none"}}NODE_LABELS{{/code}}
20 * {{code language="none"}}MINIMUM_SIZE{{/code}}
21
22 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.
23
24 The way the node size is determined can also be influenced by specifying a subset of the following options, as defined (and documented) in the [[{{code language="none"}}SizeOptions{{/code}}>>url:http://rtsys.informatik.uni-kiel.de/fisheye/browse/~~br=master/kieler/plugins/de.cau.cs.kieler.kiml/src/de/cau/cs/kieler/kiml/options/SizeOptions.java?r=HEAD||shape="rect"]] enumeration:
25
26 * {{code language="none"}}DEFAULT_MINIMUM_SIZE{{/code}}
27 * {{code language="none"}}MINIMUM_SIZE_ACCOUNTS_FOR_INSETS{{/code}}
28 * {{code language="none"}}COMPUTE_INSETS{{/code}}
29
30 Label placement can be divided into port label placement and node label placement:
31
32 Port Placement
33
34 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 [[{{code language="none"}}PortConstraints{{/code}}>>url:http://rtsys.informatik.uni-kiel.de/fisheye/browse/~~br=master/kieler/plugins/de.cau.cs.kieler.kiml/src/de/cau/cs/kieler/kiml/options/PortConstraints.java?r=HEAD||shape="rect"]] enumeration:
35
36 * {{code language="none"}}FREE{{/code}}
37 * {{code language="none"}}FIXED_SIDE{{/code}}
38 * {{code language="none"}}FIXED_ORDER{{/code}}
39 * {{code language="none"}}FIXED_RATIO{{/code}}
40 * {{code language="none"}}FIXED_POS{{/code}}
41
42 Port placement can take place after crossing minimization, since the order of ports must be known and port placements needs to be fixed before node placement.
43
44 Label Placement
45
46 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:
47
48 1. Avoiding overlaps between labels and other graphical objects, including other labels.
49 1. Making sure that each label is closer to its associated graphical feature than to other, unrelated graphical features.
50
51 KLay Layered distinguishes three kinds of labels:
52
53 1. Node labels
54 1. Port labels
55 1. Edge labels\\
56 11. Tail labels
57 11. Mid labels
58 11. Head labels
59
60 Node labels and port labels can be placed inside or outside of their particular node.
61
62 == Relationship Between Label Placement, Port Placement, and Node Sizing ==
63
64 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:
65
66 [[image:attach:portlabels.png]]
67
68 The two nodes have two labelled ports each. Let's assume port positions to be fixed, and labels to be placed inside the nodes. While the port labels fit perfectly fine into Node 1, Node 2 is clearly too narrow for them to be placed without overlaps: we would have to increase the width of the node. Label placement influences node sizing.
69
70 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 any more. Thus, label placement also influences port placement.
71
72 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.
73
74 == Anatomy of a Node ==
75
76 When it comes to label placement and node size calculations, we can think of a node as having the following anatomy:
77
78 [[image:attach:node_anatomy.png]]
79
80 The insets area is the part of the node where port and node labels are placed (if they are placed inside the node as opposed to outside the node). The child area is what is left of the node with the insets subtracted. With the {{code language="none"}}SizeOptions.COMPUTE_INSETS{{/code}}, KLay Layered can compute the child area and return it. This makes it easy to use in cases where the child area of the node is going to be used for displaying graphics or further text. If a minimum size is set on the node and the options {{code language="none"}}SizeConstraint.MINIMUM_SIZE{{/code}} and {{code language="none"}}SizeOptions.MINIMUM_SIZE_ACCOUNTS_FOR_INSETS{{/code}} are set, the minimum size will effectively only apply to the child area. Thus, KLay Layered can be told to ensure that the child area of a node has at least a given size, whatever space the port labels and node labels require.
81
82 == Limitations of Our Algorithms ==
83
84 We cannot support everything – actually, many combinations of label placement, port placement, and node sizing constraints don't even make much sense. So here's a (possibly still growing – science can only do so much...) list of things we don't support:
85
86 * More than one port label.
87 * Different placements for each node label. As of now, node labels are placed by arranging them in a vertical stack at the desired node label position.
88
89 = General Approach =
90
91 The general approach to solving label placement, port placement, and node sizing follows the following general pattern:
92
93 1. Place port labels
94 1. Calculate required insets
95 1. Resize node
96 1. Place ports
97 1. Place node labels
98 1. Calculate insets
99
100 Each task will be described in more detail in the following.
101
102 == Place Port Labels ==
103
104 Each port's labels are placed. The exact placement strategy may differ depending on node sizing and port placement constraints. The easiest way of placing port labels, however, is not to care about other constraints just yet.
105
106 == Calculate Required Insets ==
107
108 Before resizing the node, we will need to find out how large it will have to be at the minimum. This requires iterating over ports and labels to find out how much space they will need, which is what this step is all about.
109
110 == Resize Node ==
111
112 With the insets calculated, this step resizes the node, ensuring that the node size constraints are met. If the node is to have a minimum size, it may be resized accordingly, for instance. If ports are to be taken into account for the size calculation, the node size is adjusted to accommodate for its ports.
113
114 == Place Ports ==
115
116 All ports are placed. If node sizing constraints allow for it, ports are placed in a way that ensures that port labels don't overlap each other. This is only possible, though, if {{code language="none"}}SizeConstraint.PORT_LABELS{{/code}}is set. In all other cases, we can only hope that the result is free of overlaps.
117
118 The only cases where we even have to talk about the placement of ports are those where their position is not fixed. That more or less leaves us with the three port constraints {{code language="none"}}FREE{{/code}}, {{code language="none"}}FIXED_SIDES{{/code}}, and {{code language="none"}}FIXED_ORDER{{/code}}. The first is reduced to the second by assigning ports to the eastern or western side depending on the number of incoming and outgoing edges (if a port has more outgoing edges than incoming ones, it can be regarded as an output port). The second is reduced to the third during crossing minimization, in an attempt to find an order that will yield the fewest amount of edge crossings. Thus, the only case of real interest to us is {{code language="none"}}FIXED_ORDER{{/code}}.
119
120 Port placement is influenced in the following ways by label placement and node sizing:
121
122 * Label Placement: Ports should be placed in a way that avoids label overlaps.
123 * Node Sizing: If node sizing doesn't pay any attention to ports, port placement options may be severely restricted.
124
125 == Place Node Labels ==
126
127 With the node size set and ports placed, the node labels are now placed.
128
129 = Layout Options Influencing This Stuff =
130
131 The following layout options influence how the algorithm places ports and labels and calculates the node size:
132
133 |=(((
134 Option
135 )))|=(((
136 Target
137 )))|=(((
138 Description
139 )))
140 |(% colspan="1" %)(% colspan="1" %)
141 (((
142 {{code language="none"}}
143 LayoutOptions.NODE_LABEL_PLACEMENT
144 {{/code}}
145 )))|(% colspan="1" %)(% colspan="1" %)
146 (((
147 Node
148 )))|(% colspan="1" %)(% colspan="1" %)
149 (((
150 Determines where node labels are placed. A valid set of values contains exactly one constant from each of the following sets of constants:
151
152 * {{code language="none"}}NodeLabelPlacement.INSIDE{{/code}} and {{code language="none"}}NodeLabelPlacement.OUTSIDE{{/code}}
153 * {{code language="none"}}NodeLabelPlacement.H_LEFT{{/code}}, {{code language="none"}}NodeLabelPlacement.H_CENTER{{/code}}, and {{code language="none"}}NodeLabelPlacement.H_RIGHT{{/code}}
154 * {{code language="none"}}NodeLabelPlacement.V_TOP{{/code}}, {{code language="none"}}NodeLabelPlacement.V_CENTER{{/code}}, and {{code language="none"}}NodeLabelPlacement.V_BOTTOM{{/code}}
155 )))
156 |(% colspan="1" %)(% colspan="1" %)
157 (((
158 {{code language="none"}}
159 LayoutOptions.PORT_LABEL_PLACEMENT
160 {{/code}}
161 )))|(% colspan="1" %)(% colspan="1" %)
162 (((
163 Node
164 )))|(% colspan="1" %)(% colspan="1" %)
165 (((
166 Determines where port labels are placed: inside or outside their node.
167 )))
168 |(((
169 {{code language="none"}}
170 LayoutOptions.LABEL_SPACING
171 {{/code}}
172 )))|(((
173 Graph
174 )))|(((
175 Determines the amount of space left between labels and the objects they label.
176 )))
177 |(((
178 {{code language="none"}}
179 LayoutOptions.SIZE_CONSTRAINT
180 {{/code}}
181 )))|(((
182 Node
183 )))|(((
184 The amount of freedom in determining the size of a node.
185 )))
186 |(((
187 {{code language="none"}}
188 LayoutOptions.SIZE_OPTIONS
189 {{/code}}
190 )))|(((
191 Node
192 )))|(((
193 Options for node size calculation.
194 )))
195 |(% colspan="1" %)(% colspan="1" %)
196 (((
197 {{code language="none"}}
198 LayoutOptions.MIN_WIDTH
199 {{/code}}
200 )))|(% colspan="1" %)(% colspan="1" %)
201 (((
202 Node
203 )))|(% colspan="1" %)(% colspan="1" %)
204 (((
205 The minimal width of a node. If set, overrides the default minimal width.
206 )))
207 |(% colspan="1" %)(% colspan="1" %)
208 (((
209 {{code language="none"}}
210 LayoutOptions.MIN_HEIGHT
211 {{/code}}
212 )))|(% colspan="1" %)(% colspan="1" %)
213 (((
214 Node
215 )))|(% colspan="1" %)(% colspan="1" %)
216 (((
217 The minimal height of a node. If set, overrides the default minimal height.
218 )))
219 |(% colspan="1" %)(% colspan="1" %)
220 (((
221 {{code language="none"}}
222 LayoutOptions.PORT_CONSTRAINTS
223 {{/code}}
224 )))|(% colspan="1" %)(% colspan="1" %)
225 (((
226 Node
227 )))|(% colspan="1" %)(% colspan="1" %)
228 (((
229 Freedom in placing ports.
230 )))
231 |(% colspan="1" %)(% colspan="1" %)
232 (((
233 {{code language="none"}}
234 Properties.PORT_SPACING
235 {{/code}}
236 )))|(% colspan="1" %)(% colspan="1" %)
237 (((
238 Node
239 )))|(% colspan="1" %)(% colspan="1" %)
240 (((
241 How much space should be left between ports.
242 )))