Wiki source code of Intermediate Processors

Version 1.1 by cds on 2012/03/23 15:36
Show last authors
1 This section describes the intermediate processors that are available. For a description of what intermediate processors actually are, see [[doc:KLay Layered]].
2
3 Each intermediate processor is described by its required preconditions, its postconditions, the slot where it should be placed in and dependencies to intermediate processors in the same slot. The descriptions are kept very brief, since layout processors are usually well documented. Programmers using layout processors need not worry about dependencies. However, when adding a new processor, dependencies matter. For more information, see the documentation of IntermediateLayoutProcessor.
4
5 The following table provides an overview of all available layout processors and the slots they can be placed in. Note that a processor may appear in more than one slot.
6
7 |=(((
8 Slot
9 )))|=(((
10 Processor
11 )))
12 |(((
13 Before phase 1
14 )))|(((
15 Edge And Layer Constraint Edge Reverser
16 )))
17 |(((
18 Before phase 2
19 )))|(((
20 None
21 )))
22 |(((
23 Before phase 3
24 )))|(((
25 Hierarchical Port Constraint Processor
26 Inverted Port Processor
27 Layer Constraint Processor
28 Long Edge Splitter
29 North South Port Preprocessor
30 Port List Sorter
31 Port Side Processor
32 Self Loop Processor
33 )))
34 |(((
35 Before phase 4
36 )))|(((
37 Hyperedge Dummy Merger
38 In-Layer Constraint Processor
39 Node Margin Calculator
40 Port Position Processor
41 Port Side And Order Processor
42 )))
43 |(((
44 Before phase 5
45 )))|(((
46 Hierarchical Port Dummy Size Processor
47 Hierarchical Port Position Processor
48 )))
49 |(((
50 After phase 5
51 )))|(((
52 Hierarchical Port Orthogonal Edge Router
53 Long Edge Joiner
54 North South Port Postprocessor
55 Reversed Edge Restorer
56 )))
57
58 **Contents**
59
60
61
62 {{toc maxLevel="2"/}}
63
64 = Processor Documentation =
65
66 === Edge And Layer Constraint Edge Reverser ===
67
68 Edge constraints affect if a node may have only incoming or only outgoing edges. This processor reverses edges if necessary to respect the edge constraints.
69
70 Layer constraints can be seen as implicit edge constraints. If a node should be placed in the first layer, it may have only outgoing edges. Similar for the last layer.
71
72 ==== Preconditions ====
73
74 * The graph is not layered yet.
75
76 ==== Postconditions ====
77
78 * Nodes with edge or layer constraints have only incoming or only outgoing edges, as appropriate.
79
80 ==== Slot ====
81
82 Before phase 1.
83
84 ==== Dependencies ====
85
86 None.
87
88 ==== Remarks ====
89
90 * Layerers should usually include a dependency on this processor.
91
92 === Hierarchical Port Constraint Processor ===
93
94 This processor is concerned with hierarchical ports.
95
96 For eastern and western ports, the order of the nodes is fixed if the port constraints are at least at FIXED_ORDER. This processor inserts the necessary in-layer successor constraints to ensure that this order is respected during crossing reduction.
97
98 For northern and southern hierarchical ports, we just need one hierarchical port dummy per hierarchical port in the simple cases. With port constraints at least at FIXED_ORDER, however, we need to modify that approach a little. For each node connected to a hierarchical port on the northern or southern side, we insert a hierarchical port dummy in the following layer. We then remove the original hierarchical port dummy representing the port, setting the new dummy's ORIGIN property to that original dummy node. The old dummy nodes are inserted again by the HierarchicalPortOrthogonalEdgeRouter. For all other port constraints, the original port dummy nodes are replaced by a single new dummy node, in a similar way as described above. This greatly simplifies hierarchical port dummy handling later on during edge routing.
99
100 ==== Preconditions ====
101
102 * A layered graph.
103 * Long edge dummies have not yet been inserted.
104 * Layer constraints are satisfied.
105
106 ==== Postconditions ====
107
108 * For graphs with port constraints at least at FIXED_ORDER, northern and southern hierarchical port dummies are handled.
109
110 ==== Slot ====
111
112 Before phase 3.
113
114 ==== Dependencies ====
115
116 * LayerConstraintProcessor?
117
118 ==== Remarks ====
119
120 * This processor is necessary to ensure proper functioning of the HierarchicalPortOrthogonalEdgeRouter.
121
122 === Hierarchical Port Dummy Size Processor ===
123
124 Sets the width of hierarchical port dummy nodes.
125
126 To see why this is necessary, let's step back for a minute and imagine three hierarchical northern port dummy nodes in the same layer. With the default hierarchical port edge router, what will happen is the following. Each each going into one of the nodes is routed upwards, the bend point being placed at the dummy node's input port. If all dummy nodes have the same width, these ports will have the same x coordinate - the edges incident to all three nodes will be routed on top of each other. To make the task of avoiding this easier, this processor sets the width in a way ensuring that the x coordinates of the three ports are as far apart as the edge spacing dictates.
127
128 ==== Preconditions ====
129
130 * A layered graph.
131 * Nodes are assigned y coordinates.
132 * Nodes are not assigned x coordinates yet.
133 * Bend points for edges have not yet been set.
134 * Nodes are ordered such that in-layer constraints are respected.
135
136 ==== Postconditions ====
137
138 * Hierarchical port dummies are assigned appropriate widths.
139
140 ==== Slot ====
141
142 Before phase 5.
143
144 ==== Dependencies ====
145
146 None.
147
148 ==== Remarks ====
149
150 * This processor is required for HierarchicalPortOrthogonalEdgeRouter to function properly.
151
152 === Hierarchical Port Orthogonal Edge Router ===
153
154 After edge routing, edges have only been routed inside the graph. What remains to be done is to route the edges to the hierarchical ports. This processor does just that, using an orthogonal edge routing approach. During that process, hierarchical port dummy nodes that map onto hierarchical port are assigned the coordinates of the hierarchical port, relative to the graph's content area and already corrected for the offset. The necessary bend points are added to the edges connected to hierarchical ports. Hierarchical port dummy nodes that don't map onto a hierarchical port are removed, their incident edges connected to the appropriate hierarchical port dummy node representing a hierarchical port.
155
156 This is the default edge router for edges incident to hierarchical ports. Other edge routers are free to come with an own implementation for routing hierarchical edges.
157
158 ==== Preconditions ====
159
160 * A layered graph.
161 * Nodes are assigned y coordinates.
162 * The bend points of all internal edges are set.
163
164 ==== Postconditions ====
165
166 * All hierarchical port dummy nodes left map onto an actual hierarchical port.
167 * The coordinates of hierarchical port dummy nodes specify the coordinates of their respective hierarchical port.
168 * All hierarchical port dummy nodes have a size of (0, 0).
169 * Edges connected to hierarchical ports have their bend points set.
170
171 ==== Slot ====
172
173 After phase 5.
174
175 ==== Dependencies ====
176
177 None.
178
179 ==== Remarks ====
180
181 * For anything other than free port constraints, this processor requires that ConstrainedHierarchicalPortProcessor has executed.
182 * This processor requires that HierarchicalPortDummySizeProcessor has executed.
183
184 === Hierarchical Port Position Processor ===
185
186 If port constraints are set to at least FIXED_RATIO, the node placement phase is not free to position external port dummies at will. If the node placement algorithm doesn't support fixed positions, including a dependency on this processor fixes the y positions of external port dummies representing western or eastern ports.
187
188 ==== Preconditions ====
189
190 * A layered graph.
191 * Nodes are assigned y coordinates.
192 * External port dummies for western and eastern ports are placed in the first and last layer, respectively.
193
194 ==== Postconditions ====
195
196 * The y coordinates of external port dummies are set as needed in the FIXED_RATIO and FIXED_POS port constraint cases.
197
198 ==== Slot ====
199
200 Before phase 5.
201
202 ==== Dependencies ====
203
204 None.
205
206 ==== Remarks ====
207
208 * If northern or southern external edge routing modifies the height of the diagram, the dummy node positions become invalid in the FIXED_RATIO case. They are then recomputed by the HierarchicalPortOrthogonalEdgeRouter.
209
210 === Hyperedge Dummy Merger ===
211
212 Merges long edge dummy nodes with edges originally coming from the same port or going into the same port. The idea is to reduce the amount of edges in the diagram as much as possible.
213
214 ==== Preconditions ====
215
216 * The graph is layered.
217 * Node orders are fixed.
218 * For long edge dummies to be joined, their LONG_EDGE_SOURCE and LONG_EDGE_TARGET properties must be set.
219
220 ==== Postconditions ====
221
222 * Some long edge dummy nodes may have been merged.
223
224 ==== Slot ====
225
226 Before phase 4.
227
228 ==== Dependencies ====
229
230 * InLayerConstraintProcessor
231
232 ==== Remarks ====
233
234 * This processor only makes sense if the LongEdgeSplitter was used before.
235
236 === In-Layer Constraint Processor ===
237
238 Makes sure that in-layer constraints are respected. This processor is only necessary for crossing minimizers that don't respect in-layer constraints.
239
240 ==== Preconditions ====
241
242 * The graph is layered.
243 * Crossing minimization is finished.
244
245 ==== Postconditions ====
246
247 * Nodes may have been reordered to match in-layer constraints.
248
249 ==== Slot ====
250
251 Before phase 4.
252
253 ==== Dependencies ====
254
255 None.
256
257 ==== Remarks ====
258
259 * Crossing minimizers that don't support in-layer constraints must include a dependency on this processor. Other crossing minimizers should not depend on it.
260
261 === Inverted Port Processor ===
262
263 Inserts odd port side dummy nodes to cope with odd port sides. Odd port sides are the eastern side for input ports and the western side for output ports. In both cases, the incoming or outgoing edges have to be routed around the node.
264
265 ==== Preconditions ====
266
267 * The graph is layered.
268
269 ==== Postconditions ====
270
271 * Odd port side dummy nodes are inserted for odd ports.
272 * The graph may contain new in-layer connections.
273
274 ==== Slot ====
275
276 Before phase 3.
277
278 ==== Dependencies ====
279
280 * PortSideProcessor
281
282 ==== Remarks ====
283
284 * The following phases must support in-layer connections for this to work.
285
286 === Layer Constraint Processor ===
287
288 Nodes can have a property associated with them that restricts the layers they can be placed in. They can be forced in the first or the last existing layer. They can also be forced into a newly created first or last layer, along with all other nodes with the appropriate property set. While they may not be treated differently by the layerer, this processor moves them into the layer they should be placed in. A node placed in the first layer must have only outgoing edges; similarly, nodes placed in the last layer must have only incoming edges. This processor assumes that as a precondition.
289
290 ==== Preconditions ====
291
292 * The graph is layered.
293 * Nodes to be placed in the first layer only have outgoing edges.
294 * Nodes to be placed in the last layer only have incoming edges.
295
296 ==== Postconditions ====
297
298 * Nodes with layer constraints have been placed in the appropriate layers.
299
300 ==== Slot ====
301
302 Before phase 3.
303
304 ==== Dependencies ====
305
306 * ConstrainedHierarchicalPortProcessor
307
308 ==== Remarks ====
309
310 * Layerers should usually include a dependency on this processor, unless they already adhere to layer constraints themselves.
311 * The LayerConstraintEdgeReverser ensures that this processor's preconditions are met. Thus, layerers should also include a dependency on that processor.
312
313 === Long Edge Joiner ===
314
315 Removes all long edge dummy nodes, joining their edges together.
316
317 ==== Preconditions ====
318
319 * The graph is layered.
320 * Nodes are assigned x and y coordinates.
321 * The bend points of all edges are set.
322
323 ==== Postconditions ====
324
325 * There are no long edge dummy nodes anymore.
326 * The graph may not be properly layered anymore.
327
328 ==== Slot ====
329
330 After phase 5.
331
332 ==== Dependencies ====
333
334 * HierarchicalPortOrthogonalEdgeRouter
335
336 ==== Remarks ====
337
338 * Since there are multiple processors that generate long edge dummies, this processor doesn't only make sense if the LongEdgeSplitter was used before.
339
340 === Long Edge Splitter ===
341
342 Turns a layered graph into a properly layered graph by inserting long edge dummies where appropriate..
343
344 ==== Preconditions ====
345
346 * The graph is layered.
347
348 ==== Postconditions ====
349
350 * The graph is properly layered.
351
352 ==== Slot ====
353
354 Before phase 3.
355
356 ==== Dependencies ====
357
358 * LayerConstraintProcessor
359
360 ==== Remarks ====
361
362 None.
363
364 === Node Margin Calculator ===
365
366 Calculates node margins based on port positions and sizes and label positions and sizes.
367
368 ==== Preconditions ====
369
370 * The graph is layered.
371 * Port positions are fixed.
372
373 ==== Postconditions ====
374
375 * Node margins are properly set to form a bounding box around the node and its ports and labels.
376
377 ==== Slot ====
378
379 Before phase 4.
380
381 ==== Dependencies ====
382
383 * PortPositionProcessor
384
385 ==== Remarks ====
386
387 None.
388
389 === North South Port Postprocessor ===
390
391 Removes north / south port dummy nodes and routes the edges properly.
392
393 ==== Preconditions ====
394
395 * The graph is layered.
396 * Nodes are assigned y coordinates.
397 * The bend points of all edges are set.
398 * Port positions are fixed.
399
400 ==== Postconditions ====
401
402 * North / south port dummy nodes are removed, their edges being properly routed and connected.
403
404 ==== Slot ====
405
406 After phase 5.
407
408 ==== Dependencies ====
409
410 None.
411
412 ==== Remarks ====
413
414 * This processor only makes sense if the NorthSouthPortPreprocessor was used before.
415
416 === North South Port Preprocessor ===
417
418 Inserts dummy nodes to cope with northern and southern ports. Dummy nodes are assigned to layout groups identified by the node whose ports they were created from. Also, node successor constraints are set to keep north / south port dummy nodes in a certain order. This processor is capable of processing self-loops connecting two northern or two southern ports. For other kinds of self-loops, the SelfLoopProcessor may be required.
419
420 ==== Preconditions ====
421
422 * The graph is layered.
423 * Port sides are fixed.
424
425 ==== Postconditions ====
426
427 * North / south port dummy nodes have been inserted.
428 * No edge is connected to a northern or southern port any more.
429
430 ==== Slot ====
431
432 Before phase 3.
433
434 ==== Dependencies ====
435
436 * PortListSorter
437 * SelfLoopProcessor
438
439 ==== Remarks ====
440
441 * The dummy nodes must later be postprocessed by NorthSouthPortPostprocessor.
442 * A crossing minimizer must support layout groups and node successor constraints.
443
444 === Port List Sorter ===
445
446 If a node already has a fixed port order, its port lists are sorted accordingly.
447
448 ==== Preconditions ====
449
450 * The graph is layered.
451
452 ==== Postconditions ====
453
454 * Nodes with fixed port orders have their port lists sorted accordingly.
455
456 ==== Slot ====
457
458 Before phase 3, before phase 4.
459
460 ==== Dependencies ====
461
462 None.
463
464 ==== Remarks ====
465
466 * It may make sense to use this processor in multiple slots. Once to ensure fixed port sides, once more to sort the port lists again for nodes that have just had their port orders fixed.
467
468 === Port Position Processor ===
469
470 Calculates the exact coordinates a ports.
471
472 ==== Preconditions ====
473
474 * The graph is layered.
475 * All nodes have a fixed port order.
476
477 ==== Postconditions ====
478
479 * All nodes have fixed port positions.
480
481 ==== Slot ====
482
483 Before phase 4.
484
485 ==== Dependencies ====
486
487 None.
488
489 ==== Remarks ====
490
491 None.
492
493 === Port Side Processor ===
494
495 Ensures that nodes have at least fixed port sides.
496
497 ==== Preconditions ====
498
499 * The graph is layered.
500
501 ==== Postconditions ====
502
503 * All nodes have at least fixed port sides.
504
505 ==== Slot ====
506
507 Before phase 3.
508
509 ==== Dependencies ====
510
511 None.
512
513 ==== Remarks ====
514
515 None.
516
517 === Reversed Edge Restorer ===
518
519 Restores the direction of reversed edges.
520
521 ==== Preconditions ====
522
523 * The graph is layered.
524
525 ==== Postconditions ====
526
527 * Reversed edges are restored to their original direction.
528
529 ==== Slot ====
530
531 After phase 5.
532
533 ==== Dependencies ====
534
535 None.
536
537 ==== Remarks ====
538
539 * Note that this processor doesn't have any dependencies. Let's take a long edge that was reversed during phase 1 and then split into multiple segments by the LongEdgeSplitter. All the edges generated by that processor inherit the REVERSED property of the original long edge. Thus, it doesn't make any difference if we reverse all those edges before joining them to the original long edge, or if we join them first and reverse the original long edge afterwards.
540
541 === Self Loop Processor ===
542
543 Does some work that enables the other processors and phases to handle self-loops. To handle them well, the NorthSouthPortPreprocessor may be required.
544
545 ==== Preconditions ====
546
547 * The graph is layered.
548
549 ==== Postconditions ====
550
551 * Self-loop edges going into a western port have been reversed.
552 * For west-east self-loops, a dummy node has been inserted.
553
554 ==== Slot ====
555
556 After phase 3.
557
558 ==== Dependencies ====
559
560 * InvertedPortProcessor
561
562 === Compound Cycle Processor ===
563
564 Removes cyclic dependencies between compound nodes from the graph. Adds dummy edges that enhance the layering with respect to hierarchy crossing edges: the Compound Cycle Processor determines an ancestor for each source and target of the edge such that both ancestors share a common parent. The source ancestor is to be put in layers left of the layers spanned by the target ancestor.
565
566 ==== Preconditions ====
567
568 * A Layered Graph, nodes are not assigned to layers yet.
569
570 ==== Postconditions ====
571
572 * cyclic dependencies of compound nodes are removed by edge reversion.
573 * dummy edges are added to improve the layering of compound nodes with hierarchy crossing edges
574
575 ==== Slot ====
576
577 Before phase 1.
578
579 ==== Dependencies ====
580
581 None.
582
583 ==== Remarks ====
584
585 The addition of dummy edges for the layering phase could be done after the cycle removal phase. However, the Compound Cycle Processor already performs some calculations needed for this task, which are directly reused.
586
587 === Compound Dummy Edge Remover ===
588
589 Removes the dummy edges that were inserted during compound graph import or by the Compound Cycle Processor to implement constraints for the layering phase.
590
591 ==== Preconditions ====
592
593 * A Layered Graph that is layered.
594
595 ==== Postconditions ====
596
597 * The graph does not contain compound dummy edges.
598
599 ==== Slot ====
600
601 Before phase 3.
602
603 ==== Dependencies ====
604
605 None.
606
607 === Compound Side Processor ===
608
609 Sets up dummy nodes at the sides of a compound node, connects these nodes with dummy edges. Those dummy nodes and edges are used to determine and reserve drawing space for the upper and lower segments of the bounding rectangles for compound nodes. The Linear Segments Node Placer arranges the dummy nodes in straight lines.
610
611 ==== Preconditions ====
612
613 * Layered graph with fixed node ordering.
614
615 ==== Postcondition ====
616
617 * For each compound node two compound side dummy nodes are inserted into each layer the compound node spans. One dummy node is placed above all nodes belonging to the compound node, while the other is placed below them.
618
619 ==== Slot ====
620
621 After phase 3.
622
623 ==== Dependencies ====
624
625 None to other intermediate processors. The node placement is expected to put side dummy segments in line, though.
626
627 === Subgraph Ordering Processor ===
628
629 Postprocesses the node ordering phase to ensure that subgraphs are not intertwined across the layers.
630
631 ==== Preconditions ====
632
633 * A layered graph with fixed node ordering.
634 * Nodes on a layer that belong to the same compound node are placed in an unbroken sequence in the layer.
635
636 ==== Postcondition ====
637
638 * Nodes of different subgraphs (compound nodes) have the same relative position on all layers. The second precondition still holds.
639
640 ==== Slot ====
641
642 After phase 3.
643
644 ==== Dependencies ====
645
646 None.
647
648 === Compound Graph Restorer ===
649
650 Determines positioning and size of the compound nodes according to the positioning of their dummy nodes and stores the information with the Left Compound Border dummy nodes. Transfers adjacency edges from Left Compound Port, Right Compound Port, and Right Compound Border dummy nodes to the Left Compound Border dummy nodes. Removes all dummy edges and dummy nodes apart from upper compound border dummy nodes from the graph.
651
652 ==== Preconditions ====
653
654 * Layered graph with fixed node positioning and edge routing. Long edges are joined.
655
656 ==== Postconditions ====
657
658 * The layered graph contains no more dummy edges and nodes except for Left Compound Border dummy nodes. The position and size for each node is set. Edges from/to compound nodes are connected to the according Left Compound Border dummy nodes.
659
660 ==== Slot ====
661
662 After phase 5.
663
664 ==== Depencencies ====
665
666 * LongEdgeJoiner? (Edges have to be joined before the Compound Graph Restorer processes the graph.)

Navigation

Quick Links

KIELER on GitHub
RTSYS Homepage