KIELER Project


Get me back to the home page!

Page tree

Versions Compared

Old Version 7

changes.mady.by.user Unknown User (cds)

Saved on

compared with

New Version 8

changes.mady.by.user Michel Spils

Saved on

Key

  • This line was added.
  • This line was removed.
  • Formatting was changed.

...

Preconditions
  • Document
Postconditions
  • Document
SlotBefore phase 2.
Dependencies
  • Document
Remarks
  • Document

Comment Postprocessor

TODO: DocumentIf 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.

Document
Preconditions
  • Document
Postconditions
  • 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.

SlotAfter phase 5.
Dependencies
  • DocumentNone.
Remarks
  • Document

Comment Preprocessor

TODO: Document.

Preconditions
  • Document
Postconditions
  • Document
SlotBefore phase 1.
Dependencies
  • Document
Remarks
  • Document

Compound Cycle Processor

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.

Preconditions
  • 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
  • Cyclic dependencies of compound nodes are removed by edge reversion.
  • Dummy edges are added to improve the layering of compound nodes with hierarchy crossing edges.
SlotBefore phase 1.
DependenciesNone.
Remarks
  • 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.

Compound Dummy Edge Remover

Removes the dummy edges that were inserted during compound graph import or by the Compound Cycle Processor to implement constraints for the layering phase.

Preconditions
  • A Layered Graph that is layered.
Postconditions
  • The graph does not contain compound dummy

    Comments with only one connection to a port of degree 1 are removed and stored for later processing.

SlotBefore phase 1.
Dependencies
  • None.
Remarks
  • None.

Compound Cycle Processor

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.

Preconditions
  • A Layered Graph, nodes are not assigned to layers yet.
Postconditions
  • Cyclic dependencies of compound nodes are removed by edge reversion.
  • Dummy edges are added to improve the layering of compound nodes with hierarchy crossing edges.
SlotBefore phase 31.
DependenciesNone.
RemarksNone.

Compound Graph Restorer

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.

Preconditions
  • Layered graph with fixed node positioning and edge routing. Long edges are joined.
Postconditions
  • 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.
SlotAfter phase 5.
Dependencies
  • LongEdgeJoiner (Edges have to be joined before the Compound Graph Restorer processes the graph.)
RemarksNone.

Compound Side Processor

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.

Preconditions
  • Layered graph with fixed node ordering.
  • Side dummy segments are placed to form a straight line.
Postconditions
  • 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.
SlotAfter phase 3.
Dependencies

None.

RemarksNone.

Edge And Layer Constraint Edge Reverser

...

  • 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.

Compound Dummy Edge Remover

Removes the dummy edges that were inserted during compound graph import or by the Compound Cycle Processor to implement constraints for the layering phase.

Preconditions
  • A Layered Graph that is layered.
Postconditions
  • The graph does not contain compound dummy edges.
SlotBefore phase 3.
DependenciesNone.
RemarksNone.

Compound Graph Restorer

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.

Preconditions
  • Layered graph with fixed node positioning and edge routing. Long edges are joined.
Postconditions
  • 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.
SlotAfter phase 5.
Dependencies
  • LongEdgeJoiner (Edges have to be joined before the Compound Graph Restorer processes the graph.)
RemarksNone.

Compound Side Processor

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.

Preconditions
  • Layered graph with fixed node ordering.
  • Side dummy segments are placed to form a straight line.
Postconditions
  • 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.
SlotAfter phase 3.
Dependencies

None.

RemarksNone.

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.

...

  • The graph is not layered yet.

...

  • Nodes with edge or layer constraints have only incoming or only outgoing edges, as appropriate.

...

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.
SlotBefore phase 1.
DependenciesNone.
Remarks
  • Layerers should usually include a dependency on this processor.

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
  • Layerers should usually include a dependency on this processor.

Graph Transformer

TODO: Document.

Preconditions
  • Document
Postconditions
  • Document
Slot
  • Before phase 1.
  • After phase 5.
Dependencies
  • Document
Remarks
  • DocumentDirection 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

...

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.
SlotBefore phase 4.
Dependencies
  • InLayerConstraintProcessor
Remarks
  • This processor only makes sense if the LongEdgeSplitter was used before.

Hypernode Processor

TODO: Document.

Preconditions
  • Document
Postconditions
  • Document
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.
SlotAfter phase 5.
Dependencies
  • DocumentNone.
Remarks
  • DocumentThe resulting layout of hypernodes is not optimal, but a significant improvement over the standard layout.

In-Layer Constraint Processor

...