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 orthogonal bus-style edge routing algorithm which combines the large number of edges of complete subgraphs in a concise, tree-like structure that consists of vertical and horizontal line segments. A complete (sub)graph is a set of nodes, in which each node is connected to every other node. The positions of the nodes in a graph are not altered by this algorithm.

In a drawing of this algorithm, each edge path is orthogonal and 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. Besides these strict requirements, the algorithm aims to find routes where shared paths of edges with different end-nodes are drawn on top of each other and form long straight lines, so-called backbone segments. From these backbone segments, short connections of grouped edges branch off to each node (bus connections).

This routing algorithm uses a two-phase process. First, in backbone selection, a set of good initial backbone segments is determined. In routing and recombination, each initial backbone segment is connected to all others and also to each node by using orthogonal edge paths. Then, the set of resulting structures is reduced to the most optimal structure where backbone segments are long and connections to the nodes are short. Note that the calculated paths can join before reaching an initial backbone segment and, thus, establish additional backbone segments. Contrariwise, initial backbone segments of low overall profit are discarded and connections to them are rerouted to other backbone segments.

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 data provider holding bus descriptor objects is expected to be registered with the graph using the EDGE_DESCRIPTOR_DPKEY look-up key. In the absence of an individual bus ID for an edge, a bus consisting only of the single edge is created. Additionally, a bus descriptors allows to mark its associated edge as fixed or movable, which is required for incremental routing, and to specify an optional group ID for an edge's source end and target end, respectively.

Incremental routing means extending or updating an already existing bus-style representation. This can be used to rearrange existing edges or to include additional edges in an existing bus. The paths of edges not marked as fixed by their associated BusDescriptor are calculated anew. The structure induced by the fixed edges must be orthogonal and cycle-free.

Field Summary

static Object	EDGE_DESCRIPTOR_DPKEY DataProvider key used to store the BusDescriptor of every edge.
static Object	EDGE_SUBSET_DPKEY DataProvider key used for specifying the edge subset to be laid out.
static byte	SCOPE_ALL Scope constant - used for routing all edges in the graph.
static byte	SCOPE_SUBSET Scope constant - used for routing only a subset of edges.

Fields inherited from interface y.layout.Layouter

EDGE_ID_DPKEY, NODE_ID_DPKEY, SELECTED_EDGES, SELECTED_NODES

Constructor Summary

BusRouter()
Creates a new instance of BusRouter.

Method Summary

boolean	canLayout(LayoutGraph graph) Returns true if the specified graph can be routed by this algorithm.
protected OrthogonalEdgeRouter	createOrthogonalEdgeRouter() Factory method that creates an appropriate OrthogonalEdgeRouter implementation.
void	doLayout(LayoutGraph graph) Calculates a new bus layout for the specified graph.
double	getCrossingCost() Returns the cost for each edge crossing of a routed path.
int	getGridSpacing() Returns the grid spacing that is used when grid routing is enabled.
double	getMinimumBackboneSegmentLength() Returns the preferred minimum length of a backbone segment.
int	getMinimumBusConnectionsCount() Returns the minimum number of bus connections each backbone segment must have.
int	getMinimumDistanceToEdge() Returns the minimum distance between edge segments.
int	getMinimumDistanceToNode() Returns the minimum distance between edge segments and nodes.
int	getPreferredBackboneSegmentCount() Returns the preferred number of backbone segments with the same orientation.
byte	getScope() Returns the scope set for this router.
Object	getSelectedEdgesDpKey() Returns the DataProvider key to mark edges as selected.
boolean	isGridRoutingEnabled() Returns whether or not to route edge segments on grid lines.
boolean	isRemovingCollinearBends() Returns whether or not collinear bends are removed from the layout.
boolean	isReroutingEnabled() Returns whether rerouting of edges with many crossings is enabled.
void	setCrossingCost(double cost) Sets the cost for each edge crossing of a routed path.
void	setGridRoutingEnabled(boolean enabled) Specifies whether or not to route edge segments on grid lines only.
void	setGridSpacing(int spacing) Sets the grid spacing that is used when grid routing is enabled.
void	setMinimumBackboneSegmentLength(double minimumLength) Sets the preferred minimum length of a backbone segment.
void	setMinimumBusConnectionsCount(int minimumCount) Sets the minimum number of bus connections a backbone segment must have.
void	setMinimumDistanceToEdge(int dist) Sets the minimum distance between edge segments.
void	setMinimumDistanceToNode(int dist) Sets the minimum distance between edge segments and nodes.
void	setPreferredBackboneSegmentCount(int preferredCount) Sets the maximal number of selected backbone segments with the same orientation.
boolean	setProperty(String key, Object value) Provides access to implementation specific properties of the algorithms used internally.
void	setRemovingCollinearBends(boolean removingCollinearBends) Specifies whether or not collinear bends are removed from the layout.
void	setReroutingEnabled(boolean enabled) Specifies whether or not to enable a further crossing minimization optimization based on rerouting edges that cross many edges.
void	setScope(byte scope) Sets the scope for this router.
void	setSelectedEdgesDpKey(Object key) Specifies the DataProvider key to mark 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

Scope constant - used for routing all edges in the graph.

See Also:

setScope(byte), Constant Field Values

SCOPE_SUBSET

public static final byte SCOPE_SUBSET

Scope constant - used for routing only a subset of edges. This subset has to be specified by registering an appropriate DataProvider.

See Also:

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

EDGE_DESCRIPTOR_DPKEY

public static final Object EDGE_DESCRIPTOR_DPKEY

DataProvider key used to store the BusDescriptor of every edge. A bus descriptor provides the edge's bus ID, its optional group IDs and whether or not the edge is fixed.

EDGE_SUBSET_DPKEY

public static final Object EDGE_SUBSET_DPKEY

DataProvider key used for specifying the edge subset to be laid out. This key is used if no custom key is set. The algorithm expects for each edge in the graph to find a boolean that indicates whether the node belongs to the scope.

See Also:

setScope(byte), setSelectedEdgesDpKey(Object)

Constructor Detail

BusRouter

public BusRouter()

Creates a new instance of BusRouter.

Method Detail

createOrthogonalEdgeRouter

protected OrthogonalEdgeRouter createOrthogonalEdgeRouter()

Factory method that creates an appropriate OrthogonalEdgeRouter implementation.

Returns:

an appropriate OrthogonalEdgeRouter

canLayout

public boolean canLayout(LayoutGraph graph)

Returns true if the specified graph can be routed by this algorithm. Calling doLayout(y.layout.LayoutGraph) with the specified graph as its argument will only succeed if this method returns true.

If there is no fixed edge in the graph, routing is always possible. Otherwise, the route of each fixed edge must be orthogonal.

doLayout

public void doLayout(LayoutGraph graph)

Calculates a new bus layout for the specified graph.

Parameters:

graph - the graph to lay out

setGridSpacing

public void setGridSpacing(int spacing)

Sets the grid spacing that is used when grid routing is enabled. By default, a spacing of 10 is set.

Parameters:

spacing - determines the desired grid spacing. Positive values less than 2 are ignored, negative values are mapped to their absolute.

See Also:

getGridSpacing(), setGridRoutingEnabled(boolean), OrthogonalEdgeRouter.setGridSpacing(int)

getGridSpacing

public int getGridSpacing()

Returns the grid spacing that is used when grid routing is enabled.

Returns:

the grid spacing

See Also:

setGridSpacing(int), OrthogonalEdgeRouter.getGridSpacing()

setGridRoutingEnabled

public void setGridRoutingEnabled(boolean enabled)

Specifies whether or not to route edge segments on grid lines only. By default, this feature is disabled.

Parameters:

enabled - specifies whether this feature is enabled or not

See Also:

isGridRoutingEnabled(), OrthogonalEdgeRouter.setGridRoutingEnabled(boolean)

isGridRoutingEnabled

public boolean isGridRoutingEnabled()

Returns whether or not to route edge segments on grid lines.

Returns:

whether or not to route edge segments on grid lines

See Also:

setGridRoutingEnabled(boolean), OrthogonalEdgeRouter.isGridRoutingEnabled()

setMinimumDistanceToNode

public void setMinimumDistanceToNode(int dist)

Sets the minimum distance between edge segments and nodes. By default, a distance of 10 is set.

Parameters:

dist - determines the desired distance. Positive values less than 2 are ignored, negative values are mapped to their absolute.

See Also:

getMinimumDistanceToNode(), OrthogonalEdgeRouter.setMinimumDistanceToNode(int)

getMinimumDistanceToNode

public int getMinimumDistanceToNode()

Returns the minimum distance between edge segments and nodes.

Returns:

the minimum distance between edge segments and nodes

See Also:

setMinimumDistanceToNode(int), OrthogonalEdgeRouter.getMinimumDistanceToNode()

setMinimumDistanceToEdge

public void setMinimumDistanceToEdge(int dist)

Sets the minimum distance between edge segments. By default, a distance of 5 is set.

Parameters:

dist - determines the desired distance. Positive values less than 4 are ignored, negative values are mapped to their absolute.

See Also:

getMinimumDistanceToEdge(), OrthogonalEdgeRouter.setMinimumDistance(int)

getMinimumDistanceToEdge

public int getMinimumDistanceToEdge()

Returns the minimum distance between edge segments.

Returns:

the minimum distance between edge segments

See Also:

setMinimumDistanceToEdge(int), OrthogonalEdgeRouter.getMinimumDistance()

setCrossingCost

public void setCrossingCost(double cost)

Sets 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 global 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. By default, a cost of 1.0 is set.

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

Parameters:

cost - the cost for each edge crossing

See Also:

getCrossingCost()

getCrossingCost

public double getCrossingCost()

Returns the cost for each edge crossing of a routed path.

Returns:

the cost for each edge crossing

See Also:

setCrossingCost(double)

setReroutingEnabled

public void setReroutingEnabled(boolean enabled)

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.

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

Parameters:

enabled - specifies whether this feature is enabled or not

See Also:

setCrossingCost(double), isReroutingEnabled(), OrthogonalEdgeRouter.setReroutingEnabled(boolean)

isReroutingEnabled

public boolean isReroutingEnabled()

Returns whether rerouting of edges with many crossings is enabled.

Returns:

true if rerouting of specific edges is enabled.

See Also:

setCrossingCost(double), setReroutingEnabled(boolean), OrthogonalEdgeRouter.isReroutingEnabled()

getPreferredBackboneSegmentCount

public int getPreferredBackboneSegmentCount()

Returns the preferred number of backbone segments with the same orientation.

Returns:

the preferred number of backbone candidates with the same orientation.

See Also:

setPreferredBackboneSegmentCount(int)

setPreferredBackboneSegmentCount

public void setPreferredBackboneSegmentCount(int preferredCount)

Sets the maximal number of selected backbone segments with the same orientation. The more initial backbone segments, the longer the running time. By default, a count of 2 is set.

This count 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.

Parameters:

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

See Also:

getPreferredBackboneSegmentCount()

getMinimumBackboneSegmentLength

public double getMinimumBackboneSegmentLength()

Returns the preferred minimum length of a backbone segment.

Returns:

the preferred minimum length of a backbone segment

See Also:

setMinimumBackboneSegmentLength(double)

setMinimumBackboneSegmentLength

public void setMinimumBackboneSegmentLength(double minimumLength)

Sets the preferred minimum length of a backbone segment. This 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. By default, a minimum length of 100.0 is set.

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.

Parameters:

minimumLength - the preferred minimum length of a backbone segment

See Also:

getMinimumBackboneSegmentLength()

getMinimumBusConnectionsCount

public int getMinimumBusConnectionsCount()

Returns the minimum number of bus connections each backbone segment must have.

Returns:

the minimum number of bus connections each backbone segment must have

See Also:

setMinimumBusConnectionsCount(int)

setMinimumBusConnectionsCount

public void setMinimumBusConnectionsCount(int minimumCount)

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. Three or four is a good choice for small graphs, for larger graphs a much larger count can be reasonable. By default, a minimum count of 3 is set.

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

Parameters:

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

See Also:

getMinimumBusConnectionsCount()

isRemovingCollinearBends

public boolean isRemovingCollinearBends()

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

Returns:

whether or not collinear bends are removed from the layout

See Also:

setRemovingCollinearBends(boolean)

setRemovingCollinearBends

public void setRemovingCollinearBends(boolean removingCollinearBends)

Specifies whether or not collinear bends are removed from the layout. 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 is advantageous for some applications to keep such bends. By default, this feature is enabled.

Parameters:

removingCollinearBends - whether this feature is activated

See Also:

isRemovingCollinearBends()

getSelectedEdgesDpKey

public Object getSelectedEdgesDpKey()

Returns the DataProvider key to mark edges as selected.

By default, EDGE_SUBSET_DPKEY is used.

Returns:

the DataProvider key to mark edges as selected.

See Also:

setSelectedEdgesDpKey(Object)

setSelectedEdgesDpKey

public void setSelectedEdgesDpKey(Object key)

Specifies the DataProvider key to mark edges as selected.

By default, EDGE_SUBSET_DPKEY is used.

Throws:

IllegalArgumentException - if the specified key is null.

Parameters:

key - the DataProvider key.

See Also:

getSelectedEdgesDpKey()

getScope

public byte getScope()

Returns the scope set for this router.

Returns:

the scope, one of SCOPE_ALL or SCOPE_SUBSET

See Also:

setScope(byte)

setScope

public void setScope(byte scope)

Sets the scope for this router. The scope determines which edges are routed. Defaults to SCOPE_ALL.

Parameters:

scope - the new scope, should be one of SCOPE_ALL or SCOPE_SUBSET

See Also:

getScope()

setProperty

public boolean setProperty(String key,
                           Object value)

Provides access to implementation specific properties of the algorithms used internally.
Used for internal purposes.

Parameters:

key - the key to a property

value - the value to associate with the key