Download
as PDF

Orthogonal Bus-style Edge Router

This layout algorithm routes the edges of a diagram using only vertical and horizontal line segments. Additionally, it creates a bus-style tree-like impression by routing the middle segments of edges as long as possible on a shared way. It yields long line segments where ideally all but the first and last segments of all edge paths are drawn on top of each other (so-called backbones), with short connections branching off to the nodes. The short connections bundle the respective first or last segments of a node's incident edges. These abilities make it a perfect layouter for combining the likely confusing mass of edges in parts of a diagram where each node is connected to each other node in a concise, tree-like structure.

Like the other edge routing algorithms, this method does not alter the positions of the nodes in a diagram. The routed edges will usually not cross through any nodes.

This routing algorithm consists of two phases. Accordingly, some of its settings described below are only applicable for one phase and not for the overall layout.

Phase 1: Backbone Selection
Find a set of good initial backbone segments.
Phase 2: Routing and Recombination
Connect initial backbone segments with each other and also each node to each of the initial backbone segments by using orthogonal edge paths. Reduce the set of resulting structures to the most optimal structure where backbone segments are long and bus connections from the nodes are short.

Layout Settings

Scope

Determines the set of edges that the router should process.

All Edges
Routes all edges in the graph.
Selected Edges
Routes only the selected edges in the graph.
Buses of Selected Edges
Routes all buses with at least one selected edge.
Reroute to Selected Nodes
Routes all buses which are adjacent to a selected node. Edges of these buses which are not adjacent to a selected node are fixed and edges adjacent to selected nodes are added nicely to the fixed part. Please note that the fixed part must form an orthogonal tree-like bus.

Bus Membership

Determines how the bus membership of each edge is defined.

Single Bus
All edges belong to one single bus.
Defined by Color
Edges of the same color belong to the same bus.
Defined by Connected Component
Edges of the same connected component belong to the same bus.

Route on Grid

If enabled, all edge paths will be routed on grid lines. The origin of the grid is (0, 0) and the spacing between grid lines is defined by the following setting.

Grid Spacing

The spacing of the grid lines where all edge paths will be routed upon. Grid spacing plays the same role for routing on grid lines as minimum distance between any two edge segments does for "free" routing. The edge router adheres to the set value as possible, but reduces the spacing value selectively, i.e. only for a currently processed edge, when there is too little space to find a path with the proper value.

Minimum Node Distance

The distance between any edge segment and any node.

Minimum Edge Distance

The distance between any two edge segments. The edge router adheres to the set value as possible, but reduces the distance value selectively, i.e. only for a currently processed edge, when there is too little space to find a path with the proper value.

Settings for Backbone Selection

The settings in this section are taken into account only in the backbone selection phase.

Preferred Segment Count

The number of backbone segments of the same orientation which are computed by the backbone selection phase. The final number of backbone segments may be different due to changes in the routing and recombination phase.

Minimum Segment Length

The minimum length of backbone segments which are computed by the backbone selection phase. Some of the final backbone segments may be shorter due to changes in the routing and recombination phase.

Settings for Routing and Recombination

The settings in this section are taken into account only in the routing phase and do not affect the selection of the initial backbone segments.

Crossing Cost

The cost for each edge crossing of a routed path. A cost of n means that a path rather changes direction n times than crossing the path of an edge. If the cost is set to 0.0, no crossing optimization is performed. Setting a higher value will activate global crossing minimization. A good trade-off between the number of direction changes and few crossings of a path is achieved by values between 1.0 and 3.0.

Reroute Crossing Edges

Specifies whether or not to enable a further crossing minimization optimization based on rerouting edges that cross many edges. By default, this feature is disabled. Activating this feature only makes sense if the global crossing cost is set to a value greater than 0.0.

Minimum Bus Connections Count

The minimum number of bus connections a backbone segment must have. If a backbone segment has less connections, it is removed and the affected nodes are reconnected to another backbone segment.