Intermediate Processors

Version 31.1 by msp on 2013/10/24 19:16

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
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 Dummy Size Processor
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 assigned y coordinates.
  • 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 5.

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.

Tags:
Created by cds on 2012/03/23 15:36
    

Navigation

Quick Links

KIELER on GitHub
RTSYS Homepage