This section describes the intermediate processors that are available. For a description of what intermediate processors actually are, see KLay Layered.

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.

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. Within each slot, processors are ordered by theirs dependencies on each other.

Slot	Processor	Tested
Before phase 1	Graph Transformer Comment Preprocessor Edge And Layer Constraint Edge Reverser
Before phase 2	Big Nodes Processor Label Dummy Inserter
Before phase 3	Layer Constraint Processor Hierarchical Port Constraint Processor Long Edge Splitter Port Side Processor Label Dummy Switcher Inverted Port Processor Self Loop Processor Port List Sorter North South Port Preprocessor
Before phase 4	In Layer Constraint Processor Hierarchical Port Dummy Size Processor Hyperedge Dummy Merger Label Side Selector Label And Node Size Processor Node Margin Calculator
Before phase 5	Layer Size and Graph Height Calculator Hierarchical Port Position Processor
After phase 5	Comment Postprocessor Hypernode Processor Hierarchical Port Orthogonal Edge Router Long Edge Joiner North South Port Postprocessor Label Dummy Remover Reversed Edge Restorer Graph Transformer End Label Processor

Contents

Big Nodes Processor

TODO: Document.

Preconditions	Document
Postconditions	Document
Slot	Before phase 2.
Dependencies	Document
Remarks	Document

Comment Postprocessor

If any comments are found that were removed by the Comment Preprocessor, they are reinserted and placed above or below their corresponding connected node. This requires the margin around the node to be large enough to hold all comments, which is ensured by the Node Margin Calculator.

Preconditions	Comments have been processed by the Comment Preprocessor. Nodes are organized in layers and have been placed with enough spacing to hold their connected comment boxes.
Postconditions	Comments that have been removed by pre-processing are reinserted properly in the graph.
Slot	After phase 5.
Dependencies	None.
Remarks	This processor only makes sense if the `CommentPreprocessor` was used before.

Comment Preprocessor

Looks for comments that have exactly one connection to a normal node and removes them from the graph. Such comments are put either into the Properties.TOP_COMMENTS or the Properties.BOTTOM_COMMENTS list of the connected node and processed later by the Comment Postprocessor. Other comments are processed normally, i.e. they are treated as regular nodes, but their incident edges may be reversed.

Preconditions	A Layered Graph, nodes are not assigned to layers yet.
Postconditions	Comments with only one connection to a port of degree 1 are removed and stored for later processing.
Slot	Before phase 1.
Dependencies	None.
Remarks	None.

Edge And Layer Constraint Edge Reverser

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.

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.

Preconditions	The graph is not layered yet.
Postconditions	Nodes with edge or layer constraints have only incoming or only outgoing edges, as appropriate.
Slot	Before phase 1.
Dependencies	None.
Remarks	Layerers should usually include a dependency on this processor.
Tests	Nodes with a LayerConstraint must not have any outgoing or incoming edges depending on the constraint.

End Label Processor

TODO: Document.

Preconditions	Document
Postconditions	Document
Slot	After phase 5.
Dependencies	Document
Remarks	Document

Graph Transformer

A layout processor that is able to perform transformations on the coordinates of a graph. The supported operations are mirror (invert the x coordinates), transpose (swap the x and y coordinates), or both. This is used to support all four layout directions, since the basic algorithm only performs left-to-right layout.

Preconditions	None.
Postconditions	The coordinates of all graph elements are transformed according to the selected operation.
Slots	Before phase 1. After phase 5.
Dependencies	None.
Remarks	Direction LEFT: Mirror the graph before and after layout. Direction DOWN: Transpose the graph before and after layout. Direction UP: Mirror and transpose the graph before and after layout.

Hierarchical Port Constraint Processor

This processor is concerned with hierarchical ports.

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.

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.

Preconditions	A layered graph. Long edge dummies have not yet been inserted. Layer constraints are satisfied.
Postconditions	For graphs with port constraints at least at `FIXED_ORDER`, northern and southern hierarchical port dummies are handled.
Slot	Before phase 3.
Dependencies	`LayerConstraintProcessor`
Remarks	This processor is necessary to ensure proper functioning of the `HierarchicalPortOrthogonalEdgeRouter`.

Hierarchical Port Dummy Size Processor

Sets the width of hierarchical port dummy nodes.

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.

Preconditions	A layered graph. Nodes are not assigned x coordinates yet. Bend points for edges have not yet been set. Nodes are ordered such that in-layer constraints are respected.
Postconditions	Hierarchical port dummies are assigned appropriate widths.
Slot	Before phase 4.
Dependencies	None.
Remarks	This processor is required for `HierarchicalPortOrthogonalEdgeRouter` to function properly.

Hierarchical Port Orthogonal Edge Router

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.

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.

Preconditions	A layered graph. Nodes are assigned y coordinates. The bend points of all internal edges are set.
Postconditions	All hierarchical port dummy nodes left map onto an actual hierarchical port. The coordinates of hierarchical port dummy nodes specify the coordinates of their respective hierarchical port. All hierarchical port dummy nodes have a size of (0, 0). Edges connected to hierarchical ports have their bend points set.
Slot	After phase 5.
Dependencies	None.
Remarks	For anything other than free port constraints, this processor requires that `ConstrainedHierarchicalPortProcessor` has executed. This processor requires that `HierarchicalPortDummySizeProcessor` has executed.

Hierarchical Port Position Processor

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.

Preconditions	A layered graph. Nodes are assigned y coordinates. External port dummies for western and eastern ports are placed in the first and last layer, respectively.
Postconditions	The y coordinates of external port dummies are set as needed in the `FIXED_RATIO` and `FIXED_POS` port constraint cases.
Slot	Before phase 5.
Dependencies	None.
Remarks	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`.

Hyperedge Dummy Merger

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.

Preconditions	The graph is layered. Node orders are fixed. For long edge dummies to be joined, their `LONG_EDGE_SOURCE` and `LONG_EDGE_TARGET` properties must be set.
Postconditions	Some long edge dummy nodes may have been merged.
Slot	Before phase 4.
Dependencies	`InLayerConstraintProcessor`
Remarks	This processor only makes sense if the `LongEdgeSplitter` was used before.

Hypernode Processor

Improves the placement of hypernodes by moving them such that they replace the join points of connected edges. This is done as a post-processing, since hypernodes are treated as regular nodes for the rest of the algorithm.

Preconditions	The edges have been routed orthogonally.
Postconditions	None.
Slot	After phase 5.
Dependencies	None.
Remarks	The resulting layout of hypernodes is not optimal, but a significant improvement over the standard layout.

In-Layer Constraint Processor

Makes sure that in-layer constraints are respected. This processor is only necessary for crossing minimizers that don't respect in-layer constraints.

Preconditions	The graph is layered. Crossing minimization is finished.
Postconditions	Nodes may have been reordered to match in-layer constraints.
Slot	Before phase 4.
Dependencies	None.
Remarks	Crossing minimizers that don't support in-layer constraints must include a dependency on this processor. Other crossing minimizers should not depend on it.
Tests	Nodes that hold a `InLayerConstraint` are ordered according to that property (i.e. first `TOP`, then `NONE`, then `BOTTOM`).

Inverted Port Processor

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.

Preconditions	The graph is layered.
Postconditions	Odd port side dummy nodes are inserted for odd ports. The graph may contain new in-layer connections.
Slot	Before phase 3.
Dependencies	`PortSideProcessor`
Remarks	The following phases must support in-layer connections for this to work.
Tests	Westwards outgoing edges have to target a dummy node in the same layer. Analog: Eastwards incoming edges.

Label And Node Size Processor

Calculates node sizes, places ports, and places node and port labels.

Preconditions	The graph is layered. Crossing minimization is finished. Port constraints are at least at `FIXED_ORDER`. Port lists are properly sorted going clockwise, starting at the leftmost northern port.
Postconditions	Port positions are fixed. Port labels are placed. Node labels are placed. Node sizes are set.
Slot	Before phase 4.
Dependencies	`LabelSideSelector`
Remarks	Replaces the old `PortPositionProcessor`.

Label Dummy Inserter

TODO: Document.

Preconditions	Document
Postconditions	Document
Slot	Before phase 2.
Dependencies	Document
Remarks	Document

Label Dummy Remover

TODO: Document.

Preconditions	Document
Postconditions	Document
Slot	After phase 5.
Dependencies	Document
Remarks	Document
Tests	No node exists with type `LABEL`. Only nodes of the type `LABEL` are deleted from the graph.

Label Dummy Switcher

TODO: Document.

Preconditions	Document
Postconditions	Document
Slot	Before phase 3.
Dependencies	Document
Remarks	Document

Label Side Selector

TODO: Document.

Preconditions	Document
Postconditions	Document
Slot	Before phase 4.
Dependencies	`HyperedgeDummyMerger` `InLayerConstraintProcessor` `SubgraphOrderingProcessor`
Remarks	Document
Tests	All labels on ports and edges have an assigned `LabelSide` unequal to `UNKNOWN`.

Layer Constraint Processor

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.

Preconditions	The graph is layered. Nodes to be placed in the first layer only have outgoing edges. Nodes to be placed in the last layer only have incoming edges.
Postconditions	Nodes with layer constraints have been placed in the appropriate layers.
Slot	Before phase 3.
Dependencies	`ConstrainedHierarchicalPortProcessor`
Remarks	Layerers should usually include a dependency on this processor, unless they already adhere to layer constraints themselves. The `LayerConstraintEdgeReverser` ensures that this processor's preconditions are met. Thus, layerers should also include a dependency on that processor.
Tests	If `FIRST_SEPARATE` nodes exist, they must all be present in the first layer. In that case all `FIRST` nodes must be located in the next layer, otherwise in the first layer. Analog for `LAST_SEPARATE` and `LAST`.

Layer Size and Graph Height Calculator

This processor, which is always part of the processing pipeline, calculates the height and width of each layer, sets the graph's height accordingly, and calculates the graph's vertical offset based on vertical node positions. The offset is calculated such that the topmost node will have a y coordinate equal to 0. The graph's width cannot be set in this processor since that is only determined during edge routing.

The reason for this processor's existence is to factor this code out of the node placement implementations.

Preconditions	The graph is layered. Node margins are set. Nodes are assigned y coordinates.
Postconditions	Layer sizes are set. The graph's height is set. The graph's vertical offset is set.
Slot	Before phase 5.
Dependencies	`HierarchicalPortDummySizeProcessor` `HierarhicalPortPositionProcessor`
Remarks	This processor is always part of the processing pipeline. Thus, no phase needs to add a dependency to it.
Tests	All nodes are within the range of the maximal vertical graph extend.

Long Edge Joiner

Removes all long edge dummy nodes, joining their edges together.

Preconditions	The graph is layered. Nodes are assigned x and y coordinates. The bend points of all edges are set.
Postconditions	There are no long edge dummy nodes anymore. The graph may not be properly layered anymore.
Slot	After phase 5.
Dependencies	`HierarchicalPortOrthogonalEdgeRouter`
Remarks	Since there are multiple processors that generate long edge dummies, this processor doesn't only make sense if the `LongEdgeSplitter` was used before.
Tests	No node exists with type `LONG_EDGE`. Only nodes of the type `LONG_EDGE` are deleted from the graph.

Long Edge Splitter

Turns a layered graph into a properly layered graph by inserting long edge dummies where appropriate..

Preconditions	The graph is layered.
Postconditions	The graph is properly layered.
Slot	Before phase 3.
Dependencies	`LayerConstraintProcessor`
Remarks	None.
Tests	All edges connect directly adjacent layers with an increasing index.

Node Margin Calculator

Calculates node margins based on port positions and sizes and label positions and sizes.

Preconditions	The graph is layered. Port positions are fixed.
Postconditions	Node margins are properly set to form a bounding box around the node and its ports and labels.
Slot	Before phase 4.
Dependencies	`LabelAndNodeSizeProcessor`
Remarks	None.
Tests	The margins property of a node is not `null` and every value is greater or equal to 0. Ports located outside the node's bounding box are fully contained by the bounding box plus margin.

North South Port Postprocessor

Removes north / south port dummy nodes and routes the edges properly.

Preconditions	The graph is layered. Nodes are assigned y coordinates. The bend points of all edges are set. Port positions are fixed.
Postconditions	North / south port dummy nodes are removed, their edges being properly routed and connected.
Slot	After phase 5.
Dependencies	None.
Remarks	This processor only makes sense if the `NorthSouthPortPreprocessor` was used before.
Tests	No node exists with type `NORTH_SOUTH_PORT`. Only nodes of the type `NORTH_SOUTH_PORT` are deleted from the graph.

North South Port Preprocessor

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.

Preconditions	The graph is layered. Port sides are fixed.
Postconditions	North / south port dummy nodes have been inserted. No edge is connected to a northern or southern port any more.
Slot	Before phase 3.
Dependencies	`PortListSorter` `SelfLoopProcessor`
Remarks	The dummy nodes must later be postprocessed by `NorthSouthPortPostprocessor`. A crossing minimizer must support layout groups and node successor constraints.

Port List Sorter

If a node already has a fixed port order, its port lists are sorted accordingly.

Preconditions	The graph is layered.
Postconditions	Nodes with fixed port orders have their port lists sorted accordingly.
Slot	Before phase 3, before phase 4.
Dependencies	None.
Remarks	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.
Tests	Each node's port list has to be sorted depending on the port sides (NORTH, EAST, SOUTH, WEST). The x/y-coordinates of ports at the same side have to be strictly monotonically increasing.

Port Side Processor

Ensures that nodes have at least fixed port sides.

Preconditions	The graph is layered.
Postconditions	All nodes have at least fixed port sides.
Slot	Before phase 3.
Dependencies	None.
Remarks	None.
Tests	No node has its PortConstraints set to `FREE` or `UNDEFINED`. Every port has a specified PortSide.

Reversed Edge Restorer

Restores the direction of reversed edges.

Preconditions	The graph is layered.
Postconditions	Reversed edges are restored to their original direction.
Slot	After phase 5.
Dependencies	None.
Remarks	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.
Tests	No edge exists with the `REVERSED` property set to `true`.

Self Loop Processor

Does some work that enables the other processors and phases to handle self-loops. To handle them well, the NorthSouthPortPreprocessor may be required.

Preconditions	The graph is layered.
Postconditions	Self-loop edges going into a western port have been reversed. For west-east self-loops, a dummy node has been inserted.
Slot	After phase 3.
Dependencies	`InvertedPortProcessor`
Remarks	None.

Page tree

Intermediate Processors

Big Nodes Processor

Comment Postprocessor

Comment Preprocessor

Edge And Layer Constraint Edge Reverser

End Label Processor

Graph Transformer

Hierarchical Port Constraint Processor

Hierarchical Port Dummy Size Processor

Hierarchical Port Orthogonal Edge Router

Hierarchical Port Position Processor

Hyperedge Dummy Merger

Hypernode Processor

In-Layer Constraint Processor

Inverted Port Processor

Label And Node Size Processor

Label Dummy Inserter

Label Dummy Remover

Label Dummy Switcher

Label Side Selector

Layer Constraint Processor

Layer Size and Graph Height Calculator

Long Edge Joiner

Long Edge Splitter

Node Margin Calculator

North South Port Postprocessor

North South Port Preprocessor

Port List Sorter

Port Side Processor

Reversed Edge Restorer

Self Loop Processor