com.yworks.yfiles.layout.router

Class BusRouter

java.lang.Object

com.yworks.yfiles.layout.AbstractLayoutStage

com.yworks.yfiles.layout.router.BusRouter

All Implemented Interfaces:

ILayoutAlgorithm, ILayoutStage

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 representation, with many edge segments drawn on top of each other, leaves little room for a sensible interpretation of edge direction.

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 IDataProvider 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

Fields

Modifier and Type	Field and Description
static EdgeDpKey<Boolean>	DEFAULT_AFFECTED_EDGES_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 AffectedEdgesDpKey.
static EdgeDpKey<BusDescriptor>	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.

Constructor Summary

Constructors

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

Method Summary

Modifier and Type	Method and Description
void	applyLayout(LayoutGraph graph) Calculates bus-like routes for the edges in the given input graph.
Object	getAffectedEdgesDpKey() Gets the key to register a IDataProvider for marking edges as selected.
double	getCrossingCost() Gets the cost for each edge crossing.
int	getGridSpacing() Gets the equidistant spacing between the horizontal and vertical grid lines.
double	getMinimumBackboneSegmentLength() Gets the preferred minimum length of a backbone segment.
int	getMinimumBusConnectionsCount() Gets the minimum number of bus connections a backbone segment must have.
int	getMinimumDistanceToEdge() Gets the minimum distance between any two edge segments.
int	getMinimumDistanceToNode() Gets the minimum distance between edge segments and nodes.
int	getPreferredBackboneSegmentCount() Gets the maximum number of selected backbone segments with the same orientation.
Scope	getScope() Gets the scope for this routing algorithm that determines which edges are routed.
boolean	isCollinearBendsRemovalEnabled() Gets whether or not collinear bends are removed from the layout.
boolean	isGridRoutingEnabled() Gets whether or not to route edge segments on grid lines only.
boolean	isReroutingEnabled() Gets whether or not to perform an additional step to reroute the edges such that the number of edge crossings is reduced.
void	setAffectedEdgesDpKey(Object value) Sets the key to register a IDataProvider for marking edges as selected.
void	setCollinearBendsRemovalEnabled(boolean value) Sets whether or not collinear bends are removed from the layout.
void	setCrossingCost(double value) Sets the cost for each edge crossing.
void	setGridRoutingEnabled(boolean value) Sets whether or not to route edge segments on grid lines only.
void	setGridSpacing(int value) Sets the equidistant spacing between the horizontal and vertical grid lines.
void	setMinimumBackboneSegmentLength(double value) Sets the preferred minimum length of a backbone segment.
void	setMinimumBusConnectionsCount(int value) Sets the minimum number of bus connections a backbone segment must have.
void	setMinimumDistanceToEdge(int value) Sets the minimum distance between any two edge segments.
void	setMinimumDistanceToNode(int value) Sets the minimum distance between edge segments and nodes.
void	setPreferredBackboneSegmentCount(int value) Sets the maximum number of selected backbone segments with the same orientation.
void	setReroutingEnabled(boolean value) Sets whether or not to perform an additional step to reroute the edges such that the number of edge crossings is reduced.
void	setScope(Scope value) Sets the scope for this routing algorithm that determines which edges are routed.

Methods inherited from class com.yworks.yfiles.layout.AbstractLayoutStage

applyLayoutCore, getCoreLayout, setCoreLayout

Methods inherited from class java.lang.Object

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

Field Detail

DEFAULT_AFFECTED_EDGES_DPKEY

public static final EdgeDpKey<Boolean> DEFAULT_AFFECTED_EDGES_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 AffectedEdgesDpKey.

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

See Also:

setScope(Scope), setAffectedEdgesDpKey(Object)

EDGE_DESCRIPTOR_DPKEY

public static final EdgeDpKey<BusDescriptor> 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.

Constructor Detail

BusRouter

public BusRouter()

Creates a new instance of BusRouter with default settings.

Method Detail

applyLayout

public void applyLayout(LayoutGraph graph)

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

Specified by:

applyLayout in interface ILayoutAlgorithm

Specified by:

applyLayout in class AbstractLayoutStage

Throws:

IllegalArgumentException - if the graph is not supported by this algorithm

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

getAffectedEdgesDpKey

public Object getAffectedEdgesDpKey()

Gets the key to register a IDataProvider for marking edges as selected.

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

Throws:

IllegalArgumentException - if the specified key is null

Default Value:

The default value is DEFAULT_AFFECTED_EDGES_DPKEY

Returns:

the IDataProvider key for edge selection

See Also:

setAffectedEdgesDpKey(Object)

getCrossingCost

public double getCrossingCost()

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

Throws:

IllegalArgumentException - if the given cost value is negative

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.

Returns:

the non-negative cost value for each crossing

See Also:

setCrossingCost(double)

getGridSpacing

public int getGridSpacing()

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

Returns:

the grid spacing

See Also:

setGridRoutingEnabled(boolean), setGridSpacing(int)

getMinimumBackboneSegmentLength

public double getMinimumBackboneSegmentLength()

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

Throws:

IllegalArgumentException - if the given minimum length is smaller than 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.

Returns:

the preferred minimum length of a backbone segment

See Also:

setMinimumBackboneSegmentLength(double)

getMinimumBusConnectionsCount

public int getMinimumBusConnectionsCount()

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

Throws:

IllegalArgumentException - if the given minimum count is smaller than 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.

Returns:

the minimum number of bus connections each backbone segment must have

See Also:

setMinimumBusConnectionsCount(int)

getMinimumDistanceToEdge

public int getMinimumDistanceToEdge()

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

Returns:

the minimum distance between edges

See Also:

setMinimumDistanceToEdge(int)

getMinimumDistanceToNode

public int getMinimumDistanceToNode()

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

Returns:

the minimum distance between edges and nodes

See Also:

setMinimumDistanceToNode(int)

getPreferredBackboneSegmentCount

public int getPreferredBackboneSegmentCount()

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

Throws:

IllegalArgumentException - if the given preferred number is smaller than 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.

Returns:

the maximum number of backbone candidates with the same orientation

See Also:

setPreferredBackboneSegmentCount(int)

getScope

public Scope getScope()

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

Throws:

IllegalArgumentException - if an unknown scope is given

Default Value:

The default value is Scope.ROUTE_ALL_EDGES

Returns:

one of the predefined scope values

See Also:

setScope(Scope)

isCollinearBendsRemovalEnabled

public boolean isCollinearBendsRemovalEnabled()

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

Returns:

true if collinear bends are removed, false otherwise

See Also:

setCollinearBendsRemovalEnabled(boolean)

isGridRoutingEnabled

public boolean isGridRoutingEnabled()

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

The spacing of the grid can be controlled via GridSpacing.

Default Value:

The default value is false. Edges are freely routed.

Returns:

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

See Also:

setGridRoutingEnabled(boolean)

isReroutingEnabled

public boolean isReroutingEnabled()

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

Default Value:

The default value is false.

Returns:

true if the rerouting feature is enabled, false otherwise

See Also:

setCrossingCost(double), setReroutingEnabled(boolean)

setAffectedEdgesDpKey

public void setAffectedEdgesDpKey(Object value)

Sets the key to register a IDataProvider for marking edges as selected.

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

Throws:

IllegalArgumentException - if the specified key is null

Default Value:

The default value is DEFAULT_AFFECTED_EDGES_DPKEY

Parameters:

value - the IDataProvider key for edge selection

See Also:

getAffectedEdgesDpKey()

setCollinearBendsRemovalEnabled

public void setCollinearBendsRemovalEnabled(boolean value)

Sets 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:

value - true if collinear bends are removed, false otherwise

See Also:

isCollinearBendsRemovalEnabled()

setCrossingCost

public void setCrossingCost(double value)

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

Throws:

IllegalArgumentException - if the given cost value is negative

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:

value - the non-negative cost value for each crossing

See Also:

getCrossingCost()

setGridRoutingEnabled

public void setGridRoutingEnabled(boolean value)

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

The spacing of the grid can be controlled via GridSpacing.

Default Value:

The default value is false. Edges are freely routed.

Parameters:

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

See Also:

isGridRoutingEnabled()

setGridSpacing

public void setGridSpacing(int value)

Sets 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:

value - the grid spacing

See Also:

setGridRoutingEnabled(boolean), getGridSpacing()

setMinimumBackboneSegmentLength

public void setMinimumBackboneSegmentLength(double value)

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

Throws:

IllegalArgumentException - if the given minimum length is smaller than 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:

value - the preferred minimum length of a backbone segment

See Also:

getMinimumBackboneSegmentLength()

setMinimumBusConnectionsCount

public void setMinimumBusConnectionsCount(int value)

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

Throws:

IllegalArgumentException - if the given minimum count is smaller than 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:

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

See Also:

getMinimumBusConnectionsCount()

setMinimumDistanceToEdge

public void setMinimumDistanceToEdge(int value)

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:

value - the minimum distance between edges

See Also:

getMinimumDistanceToEdge()

setMinimumDistanceToNode

public void setMinimumDistanceToNode(int value)

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:

value - the minimum distance between edges and nodes

See Also:

getMinimumDistanceToNode()

setPreferredBackboneSegmentCount

public void setPreferredBackboneSegmentCount(int value)

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

Throws:

IllegalArgumentException - if the given preferred number is smaller than 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:

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

See Also:

getPreferredBackboneSegmentCount()

setReroutingEnabled

public void setReroutingEnabled(boolean value)

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

Default Value:

The default value is false.

Parameters:

value - true if the rerouting feature is enabled, false otherwise

See Also:

setCrossingCost(double), isReroutingEnabled()

setScope

public void setScope(Scope value)

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

Throws:

IllegalArgumentException - if an unknown scope is given

Default Value:

The default value is Scope.ROUTE_ALL_EDGES

Parameters:

value - one of the predefined scope values

See Also:

getScope()