Page History
...
The reversed edges have to be restored at some point. There's a processor for that, called ReversedEdgeRestorer. All implementations of phase one must include a dependency on that processor, to be included after phase 5.
...
| Preconditions |
|
|---|
...
| Postconditions |
|
Remarks |
|
...
|
...
|
...
| Implementations |
|
Phase 2: Layering
The second phase assigns nodes to layers. (also called ranks in some papers) Nodes in the same layer are assigned the same x coordinate. (give or take) The problem to solve here is to assign each node x a layer i such that each successor of x is in a layer j>i. The only exception are self-loops, that may or may not be supported by later phases.
...
Note that nodes can have a property associated with them that constraints the layers they can be placed in.
...
| Preconditions |
|
|---|
...
| Postconditions |
|
| Remarks |
|
...
|
...
| Implementations |
|
...
|
Phase 3: Crossing Reduction
The objective of phase 3 is to determine how the nodes in each layer should be ordered. The order determines the number of edge crossings, and thus is a critical step towards readable diagrams. Unfortunately, the problem is NP-hard even for only two layers. Did I just hear you saying say "heuristic"? The usual approach is to sweep through the pairs of layers from left to right and back, along the way applying some heuristic to minimize crossings between each pair of layers. The two most prominent and well-studied kinds of heuristics used here are the barycenter method and the median method. We have currently implemented the former.
Our crossing reduction implementations may or may not support the concepts of node successor constraints and layout groups. The former allows a node x to specify a node y!=x that may only appear after x. Layout groups are groups of nodes. Nodes belonging to different layout groups are not to be interleaved.
...
| Preconditions |
|
|---|
...
|
|---|
...
|
|---|
...
| Postconditions |
|
| Remarks |
|
...
|
...
| Implementations |
...
|
Phase 4: Node Placement
So far, the coordinates of the nodes have not been touched. That's about to change in phase 4, which determines the y coordinate. While phase 3 has an impact on the number of edge crossings, phase 4 has an influence on the number of edge bends. Usually, some kind of heuristic is employed to yield a good y coordinate.
Our node placers may or may not support node margins. Node margins define the space occupied by ports, labels and such. The idea is to keep that space free from edges and other nodes.
...
| Preconditions |
|
|---|
...
| Postconditions |
|
| Remarks |
|
...
|
...
|
...
| Implementations | LinearSegmentsNodePlacer. Builds linear segments of nodes that should have the same y coordinate and tries to respect those linear segments. Linear segments are placed according to a barycenter heuristic. |
Phase 5: Edge Routing
In the last phase, it's time to determine x coordinates for all nodes and route the edges. The routing may support very different kinds of features, such as support for odd port sides, (input ports that are on the node's right side) orthogonal edges, spline edges etc. Often times, the set of features supported by an edge router largely determines the intermediate processors used during the layout process.
...
| Preconditions |
|
|---|
...
| Postconditions |
|
| Remarks | None. |
...
| Implementations |
|
...
|
...
|
Overview
Content Tools