y.layout.router
Class BusRouter

java.lang.Object
  y.layout.AbstractLayoutStage
      y.layout.router.BusRouter

All Implemented Interfaces:

Layouter, LayoutStage

public class BusRouter
extends AbstractLayoutStage

An edge routing algorithm which routes edges of a graph in an orthogonal bus-style.

Carefully observe that the resulting bus representation, with many edge segments drawn on top of each other, leaves little room for a sensible interpretation of edge direction.

Note that class EdgeRouter offers a newer, improved bus-style support (also see BusDescriptor) and it is recommended to use this instead.

Layout Style

Edge segments are bundled to buses. A bus is a segment shared by multiple edges to which shorter segments that connect to actual nodes are attached. Buses and all other segments are routed orthogonally.

A bus can, for example, be created in parts of a diagram where each node is connected to each other node. There are no cycles induced by any two edge paths of the same bus, that is, the combination of all edge routes looks like an orthogonal tree.

The algorithm tries to produce routes where the edges share as much of their paths as possible. It yields long line segments (so-called backbone segments) where ideally all but the first and last segments of all edge paths are drawn on top of each other (forming a bus), with short connections branching off to the nodes (bus connections). These short connections bundle the respective first or last segments of a node's incident edges.

This algorithm will not modify positions or sizes of nodes in any way, but will route the edges of the graph.

Bus-style edge routing with default settings

Edge routing sample including four different buses

Concept

The algorithm uses a two-phase process:

1. Backbone Selection: a set of suitable initial backbone segments is determined.
2. Routing and Recombination: each initial backbone segment is connected to all other backbone segments and to each node by using orthogonal edge paths. Then, the resulting structure is reduced to the most optimal structure where backbone segments are long and connections to the nodes are short.

Features

To determine which edges belong to a common bus, a mapping that assigns a bus ID to each edge must be specified using BusDescriptors. A DataProvider holding BusDescriptor instances is expected to be registered with the graph using the descriptor key. In the absence of an individual bus ID for an edge, a bus consisting only of the single edge is created.

This algorithm supports PortConstraints as well as PortCandidates to control where edges should connect to nodes.

Note that if edges of the same bus connect to a common node but have inconsistent or contradicting port constraints/candidates, then any of these constraints/candidates can determine the actual location of the common port. The same applies for edges that, in addition, belong to the same edge group.

Also, the cardinality defined with a PortCandidateSet object is interpreted in terms of different bus IDs (group IDs) instead of number of edges.

This algorithm supports incremental edge routing, that is, extending or updating an already existing bus-style representation. This is useful to rearrange existing edges or to include additional edges in an existing bus.
Incremental routing is supported by denoting so-called fixed edges using the corresponding BusDescriptor property. The paths of edges which are not marked as fixed are calculated by the algorithm. The structure induced by the fixed edges must be orthogonal and cycle-free.

Field Summary

static java.lang.Object	EDGE_DESCRIPTOR_DPKEY A DataProvider key for specifying a bus descriptor object for each edge The BusDescriptor for an edge provides the edge's bus ID, its optional group IDs and whether or not the edge is fixed.
static java.lang.Object	EDGE_SUBSET_DPKEY A DataProvider key for specifying the edge subset to be routed This key is used if no custom key for specifying the subset is defined using setSelectedEdgesDpKey(Object).
static byte	SCOPE_ALL A scope specifier which defines that all edges of the input graph will be routed.
static byte	SCOPE_SUBSET A scope specifier which defines that only the selected edges of the input graph will be routed.

Fields inherited from interface y.layout.Layouter

EDGE_ID_DPKEY, NODE_ID_DPKEY, NODE_TYPE_DPKEY, SELECTED_EDGES, SELECTED_NODES

Constructor Summary

BusRouter()
Creates a new instance of BusRouter with default settings.

Method Summary

boolean	canLayout(LayoutGraph graph) Accepts all graphs that can be handled by the core layout algorithm.
protected OrthogonalEdgeRouter	createOrthogonalEdgeRouter() Creates a configured instance of OrthogonalEdgeRouter that is used for orthogonal routing of edges.
void	doLayout(LayoutGraph graph) Calculates bus-like routes for the edges in the given input graph.
double	getCrossingCost() Returns the cost for each edge crossing.
int	getGridSpacing() Returns the equidistant spacing between the horizontal and vertical grid lines.
double	getMinimumBackboneSegmentLength() Returns the preferred minimum length of a backbone segment.
int	getMinimumBusConnectionsCount() Returns the minimum number of bus connections a backbone segment must have.
int	getMinimumDistanceToEdge() Returns the minimum distance between any two edge segments.
int	getMinimumDistanceToNode() Returns the minimum distance between edge segments and nodes.
int	getPreferredBackboneSegmentCount() Returns the maximum number of selected backbone segments with the same orientation.
byte	getScope() Returns the scope for this routing algorithm that determines which edges are routed.
java.lang.Object	getSelectedEdgesDpKey() Returns the key to register a DataProvider for marking edges as selected.
boolean	isGridRoutingEnabled() Specifies whether or not to route edge segments on grid lines only.
boolean	isRemovingCollinearBends() Specifies whether or not collinear bends are removed from the layout.
boolean	isReroutingEnabled() Specifies whether or not to perform an additional step to reroute the edges such that the number of edge crossings is reduced.
void	setCrossingCost(double cost) Specifies the cost for each edge crossing.
void	setGridRoutingEnabled(boolean enabled) Specifies whether or not to route edge segments on grid lines only.
void	setGridSpacing(int spacing) Specifies the equidistant spacing between the horizontal and vertical grid lines.
void	setMinimumBackboneSegmentLength(double minimumLength) Specifies the preferred minimum length of a backbone segment.
void	setMinimumBusConnectionsCount(int minimumCount) Specifies the minimum number of bus connections a backbone segment must have.
void	setMinimumDistanceToEdge(int dist) Sets the minimum distance between any two edge segments.
void	setMinimumDistanceToNode(int dist) Sets the minimum distance between edge segments and nodes.
void	setPreferredBackboneSegmentCount(int preferredCount) Specifies the maximum number of selected backbone segments with the same orientation.
boolean	setProperty(java.lang.String key, java.lang.Object value) Provides access to implementation-specific properties used for internal purposes only.
void	setRemovingCollinearBends(boolean removingCollinearBends) Specifies whether or not collinear bends are removed from the layout.
void	setReroutingEnabled(boolean enabled) Specifies whether or not to perform an additional step to reroute the edges such that the number of edge crossings is reduced.
void	setScope(byte scope) Sets the scope for this routing algorithm that determines which edges are routed.
void	setSelectedEdgesDpKey(java.lang.Object key) Specifies the key to register a DataProvider for marking edges as selected.

Methods inherited from class y.layout.AbstractLayoutStage

canLayoutCore, doLayoutCore, getCoreLayouter, setCoreLayouter

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

SCOPE_ALL

public static final byte SCOPE_ALL

A scope specifier which defines that all edges of the input graph will be routed.

See Also:

setScope(byte), Constant Field Values

Sample Graphs:

Initial graph

All the edges were routed

SCOPE_SUBSET

public static final byte SCOPE_SUBSET

A scope specifier which defines that only the selected edges of the input graph will be routed.

The selection state of an edge is determined by a boolean value returned by a DataProvider registered with key getSelectedEdgesDpKey().

All other non-selected edges will be considered to have fixed routes.

See Also:

setScope(byte), setSelectedEdgesDpKey(Object), EDGE_SUBSET_DPKEY, Constant Field Values

Sample Graphs:

Initial graph, three edges are marked

Only the marked edges were selected as subset and, thus, routed

EDGE_DESCRIPTOR_DPKEY

public static final java.lang.Object EDGE_DESCRIPTOR_DPKEY

A DataProvider key for specifying a bus descriptor object for each edge

The BusDescriptor for an edge provides the edge's bus ID, its optional group IDs and whether or not the edge is fixed.

The bus ID of an edge is needed to determine which edges belong to a common bus. In the absence of an individual bus ID for an edge, a bus consisting only of the single edge is created.

EDGE_SUBSET_DPKEY

public static final java.lang.Object EDGE_SUBSET_DPKEY

A DataProvider key for specifying the edge subset to be routed

This key is used if no custom key for specifying the subset is defined using setSelectedEdgesDpKey(Object).

The specified subset is only considered if the scope is set to SCOPE_SUBSET.

See Also:

setScope(byte), setSelectedEdgesDpKey(Object)

Constructor Detail

BusRouter

public BusRouter()

Creates a new instance of BusRouter with default settings.

Method Detail

createOrthogonalEdgeRouter

protected OrthogonalEdgeRouter createOrthogonalEdgeRouter()

Creates a configured instance of OrthogonalEdgeRouter that is used for orthogonal routing of edges.

This method is called when initializing the BusRouter itself. It may be overridden to create a custom implementation or different settings for the internal routing algorithm.

Some properties of this routing algorithm are immediately mapped to properties of the internal OrthogonalEdgeRouter, for example, setCrossingCost(double) or setGridRoutingEnabled(boolean). Therefore, the defaults of properties of the BusRouter will change when overriding this method and creating an OrthogonalEdgeRouter with different initial settings.

Returns:

a configured OrthogonalEdgeRouter instance

canLayout

public boolean canLayout(LayoutGraph graph)

Accepts all graphs that can be handled by the core layout algorithm.

If there is no core layout algorithm, all graphs are accepted.

Parameters:

graph - the input graph

Returns:

true if there is no core layout algorithm or the core layout algorithm accepts the graph, false otherwise

See Also:

Layouter.doLayout(LayoutGraph)

doLayout

public void doLayout(LayoutGraph graph)

Calculates bus-like routes for the edges in the given input graph.

The given graph will not be copied during the edge routing process and the result will be immediately applied to the input graph.

Parameters:

graph - the input graph

See Also:

Layouter.canLayout(LayoutGraph)

setGridSpacing

public void setGridSpacing(int spacing)

Specifies the equidistant spacing between the horizontal and vertical grid lines.

Positive values greater than 2 are allowed. Positive values less than 2 are ignored, while negative values are mapped to their absolute value.

This option will take effect only if grid routing is enabled.

Default Value:

The default value is 10.

Parameters:

spacing - the grid spacing

See Also:

setGridRoutingEnabled(boolean)

Sample Graphs:

20

60

getGridSpacing

public int getGridSpacing()

Returns the equidistant spacing between the horizontal and vertical grid lines.

Positive values greater than 2 are allowed. Positive values less than 2 are ignored, while negative values are mapped to their absolute value.

This option will take effect only if grid routing is enabled.

Returns:

the grid spacing

See Also:

setGridSpacing(int), setGridRoutingEnabled(boolean)

setGridRoutingEnabled

public void setGridRoutingEnabled(boolean enabled)

Specifies whether or not to route edge segments on grid lines only.

The spacing of the grid can be controlled via setGridSpacing(int).

Default Value:

The default value is false. Edges are freely routed.

Parameters:

enabled - true if edge segments should be routed on a grid, false otherwise

Sample Graphs:

true - edge segments lie on the grid

false - edge segments are not aligned with the grid

isGridRoutingEnabled

public boolean isGridRoutingEnabled()

Specifies whether or not to route edge segments on grid lines only.

The spacing of the grid can be controlled via setGridSpacing(int).

Returns:

true if edge segments are routed on a grid, false otherwise

See Also:

setGridRoutingEnabled(boolean)

setMinimumDistanceToNode

public void setMinimumDistanceToNode(int dist)

Sets the minimum distance between edge segments and nodes.

Positive values greater than 2 are allowed. Positive values less than 2 are ignored, while negative values are mapped to their absolutes.

Default Value:

The default value is 10.

Parameters:

dist - the minimum distance between edges and nodes

Sample Graphs:

10 - edges are placed in between the highlighted nodes, the minimum distance is not violated

30 - edges do not fit in between the highlighted nodes, as this would violate the minimum distance

getMinimumDistanceToNode

public int getMinimumDistanceToNode()

Returns the minimum distance between edge segments and nodes.

Positive values greater than 2 are allowed. Positive values less than 2 are ignored, while negative values are mapped to their absolutes.

Returns:

the minimum distance between edges and nodes

See Also:

setMinimumDistanceToNode(int)

setMinimumDistanceToEdge

public void setMinimumDistanceToEdge(int dist)

Sets the minimum distance between any two edge segments.

The edge routing algorithm adheres to this value if possible, but reduces the distance value selectively, i.e., only for a currently processed edge, when there is not enough space to find a path with the proper value.

Positive values greater than 4 are allowed. Positive values less than 4 are ignored, while negative values are mapped to their absolute values.

Default Value:

The default value is 5.

Parameters:

dist - the minimum distance between edges

Sample Graphs:

Minimum edge-to-edge distance 5

Minimum edge-to-edge distance 20

getMinimumDistanceToEdge

public int getMinimumDistanceToEdge()

Returns the minimum distance between any two edge segments.

The edge routing algorithm to this value if possible, but reduces the distance value selectively, i.e., only for a currently processed edge, when there is not enough space to find a path with the proper value.

Positive values greater than 4 are allowed. Positive values less than 4 are ignored, while negative values are mapped to their absolute values.

Returns:

the minimum distance between edges

See Also:

setMinimumDistanceToEdge(int)

setCrossingCost

public void setCrossingCost(double cost)

Specifies the cost for each edge crossing.

A cost value of n means that it is more profitable for a path to change its direction n times rather than crossing the path of an edge. If the cost value is set to 0.0, no global crossing optimization is performed.

The cost is defined to be a non-negative value.

A good trade-off between the number of direction changes and the number of crossings of an edge path is achieved by selecting values between 1.0 and 3.0.

This setting is taken into account only in the routing and recombination phase and does not affect the selection of the initial backbone segments.

Default Value:

The default value is 1.0. One direction change is preferred over the crossing of an edge.

Parameters:

cost - the non-negative cost value for each crossing

Throws:

java.lang.IllegalArgumentException - if the given cost value is negative

Sample Graphs:

3.0 - results in 1 crossing

0.0 - results in 5 crossings

getCrossingCost

public double getCrossingCost()

Returns the cost for each edge crossing.

A cost value of n means that it is more profitable for a path to change its direction n times rather than crossing the path of an edge. If the cost value is set to 0.0, no global crossing optimization is performed.

The cost is defined to be a non-negative value.

A good trade-off between the number of direction changes and the number of crossings of an edge path is achieved by selecting values between 1.0 and 3.0.

This setting is taken into account only in the routing and recombination phase and does not affect the selection of the initial backbone segments.

Returns:

the non-negative cost value for each crossing

See Also:

setCrossingCost(double)

setReroutingEnabled

public void setReroutingEnabled(boolean enabled)

Specifies whether or not to perform an additional step to reroute the edges such that the number of edge crossings is reduced.

This features does not guarantee that the number of crossings will be the minimal.

The rerouting step will only take effect if a value greater than 0.0 is assigned to the crossing cost.

Default Value:

The default value is false.

Parameters:

enabled - true if the rerouting feature should be enabled, false otherwise

See Also:

setCrossingCost(double)

isReroutingEnabled

public boolean isReroutingEnabled()

Specifies whether or not to perform an additional step to reroute the edges such that the number of edge crossings is reduced.

This features does not guarantee that the number of crossings will be the minimal.

The rerouting is taken into account only in the routing and recombination phase and does not affect the selection of the initial backbone segments.

The rerouting step will only take effect if a value greater than 0.0 is assigned to the crossing cost.

Returns:

true if the rerouting feature is enabled, false otherwise

See Also:

setReroutingEnabled(boolean)

getPreferredBackboneSegmentCount

public int getPreferredBackboneSegmentCount()

Returns the maximum number of selected backbone segments with the same orientation.

This setting defines 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.

The number must be a value greater than or equal to 1.

The more initial backbone segments, the longer the running time. It is not recommended to specify large values for this setting.

Returns:

the maximum number of backbone candidates with the same orientation

See Also:

setPreferredBackboneSegmentCount(int)

setPreferredBackboneSegmentCount

public void setPreferredBackboneSegmentCount(int preferredCount)

Specifies the maximum number of selected backbone segments with the same orientation.

This setting defines 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.

The number must be a value greater than or equal to 1.

The more initial backbone segments, the longer the running time. It is not recommended to specify large values for this setting.

Default Value:

The default value is 2.

Parameters:

preferredCount - the maximum number of backbone candidates with the same orientation

Throws:

java.lang.IllegalArgumentException - if the given preferred number is smaller than 1

Sample Graphs:

1 - resulting backbones are highlighted

2 - resulting backbones are highlighted

getMinimumBackboneSegmentLength

public double getMinimumBackboneSegmentLength()

Returns the preferred minimum length of a backbone segment.

This number defines 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.

The minimum length is defined to be a value greater than or equal to 1.0.

The minimum length should be at least as large as the typical distance between nodes to avoid small backbone segments. It is reasonable to set this according to the dimension of the graph's bounding box.

Returns:

the preferred minimum length of a backbone segment

See Also:

setMinimumBackboneSegmentLength(double)

setMinimumBackboneSegmentLength

public void setMinimumBackboneSegmentLength(double minimumLength)

Specifies the preferred minimum length of a backbone segment.

This number defines 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.

The minimum length is defined to be a value greater than or equal to 1.0.

The minimum length should be at least as large as the typical distance between nodes to avoid small backbone segments. It is reasonable to set this according to the dimension of the graph's bounding box.

Default Value:

The default value is 100.0.

Parameters:

minimumLength - the preferred minimum length of a backbone segment

Throws:

java.lang.IllegalArgumentException - if the given minimum length is smaller than 1.0

Sample Graphs:

100.0

300.0

getMinimumBusConnectionsCount

public int getMinimumBusConnectionsCount()

Returns 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 connect to another backbone segment.

The minimum connection count must be a value greater than or equal to 1.

A minimum count of 3 or 4 is a good choice for small graphs. For larger graphs a much larger count can be reasonable.

This setting is taken into account only in the routing and recombination phase and does not affect the selection of the initial backbone segments.

Returns:

the minimum number of bus connections each backbone segment must have

See Also:

setMinimumBusConnectionsCount(int)

setMinimumBusConnectionsCount

public void setMinimumBusConnectionsCount(int minimumCount)

Specifies 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 connect to another backbone segment.

The minimum connection count must be a value greater than or equal to 1.

A minimum count of 3 or 4 is a good choice for small graphs. For larger graphs a much larger count can be reasonable.

This setting is taken into account only in the routing and recombination phase and does not affect the selection of the initial backbone segments.

Default Value:

The default value is 3.

Parameters:

minimumCount - the minimum number of bus connections each backbone segment must have

Throws:

java.lang.IllegalArgumentException - if the given minimum count is smaller than 1

Sample Graphs:

2 - results in two backbones (in this example)

6 - results in a single backbone all nodes are connected to (in this example)

isRemovingCollinearBends

public boolean isRemovingCollinearBends()

Specifies whether or not collinear bends are removed from the layout.

A collinear bend is a bend that lies on a common line with its predecessor bend and successor bend.

If an edge has a collinear bend, there is another edge which has a real bend at this point, i.e., the bend location is an intersection of the bus. Therefore, it may be advantageous for some applications to keep such bends.

Returns:

true if collinear bends are removed, false otherwise

See Also:

setRemovingCollinearBends(boolean)

setRemovingCollinearBends

public void setRemovingCollinearBends(boolean removingCollinearBends)

Specifies whether or not collinear bends are removed from the layout.

A collinear bend is a bend that lies on a common line with its predecessor bend and successor bend.

If an edge has a collinear bend, there is another edge which has a real bend at this point, i.e., the bend location is an intersection of the bus. Therefore, it may be advantageous for some applications to keep such bends.

Default Value:

The default value is true.

Parameters:

removingCollinearBends - true if collinear bends should be removed, false otherwise

getSelectedEdgesDpKey

public java.lang.Object getSelectedEdgesDpKey()

Returns the key to register a DataProvider for marking edges as selected.

If the scope is set to SCOPE_SUBSET, only the edges for which the registered DataProvider returns true will be routed. All other edges will be considered to have fixed routes.

Returns:

the DataProvider key for edge selection

See Also:

setSelectedEdgesDpKey(Object)

setSelectedEdgesDpKey

public void setSelectedEdgesDpKey(java.lang.Object key)

Specifies the key to register a DataProvider for marking edges as selected.

If the scope is set to SCOPE_SUBSET, only the edges for which the registered DataProvider returns true will be routed. All other edges will be considered to have fixed routes.

Default Value:

The default value is EDGE_SUBSET_DPKEY

Parameters:

key - the DataProvider key for edge selection

Throws:

java.lang.IllegalArgumentException - if the specified key is null

See Also:

getSelectedEdgesDpKey()

getScope

public byte getScope()

Returns the scope for this routing algorithm that determines which edges are routed.

Returns:

one of the predefined scope values

See Also:

setScope(byte)

setScope

public void setScope(byte scope)

Sets the scope for this routing algorithm that determines which edges are routed.

Default Value:

The default value is SCOPE_ALL

Parameters:

scope - one of the predefined scope values

Throws:

java.lang.IllegalArgumentException - if an unknown scope is given

setProperty

public boolean setProperty(java.lang.String key,
                           java.lang.Object value)

Provides access to implementation-specific properties used for internal purposes only.

Parameters:

key - the key to a property

value - the value to associate with the key