y.layout.router.polyline
Class EdgeRouter

java.lang.Object
  y.layout.AbstractLayoutStage
      y.layout.router.polyline.EdgeRouter

All Implemented Interfaces:

Layouter, LayoutStage

public class EdgeRouter
extends AbstractLayoutStage

This class represents a polyline edge router which calculates an edge layout containing only straight segments. The router does not change the location or the size of the nodes in a diagram in any way.

Features

Edges can be routed orthogonally, i.e. only horizontal and vertical segments, or with additional segments with other slopes.
Fig. 1: The same graph with orthogonal (left) and polylinear (right) edge routing. Polyline routing can be activated using setPolylineRoutingEnabled(boolean).

In both routing styles, edges can be grouped so they share common segments in the beginning or end of their routes.

Fig. 2: Same graph as in Fig. 1 with grouped edges. Edges are marked as grouped by using the data provider keys PortConstraintKeys.SOURCE_GROUPID_KEY (for source grouped edges) or PortConstraintKeys.TARGET_GROUPID_KEY (for target grouped edges).

Many settings of the edge layout can be controlled individually for every edge using EdgeLayoutDescriptor instances. So, if at the time of the invocation a DataProvider instance is bound to the graph using the EDGE_LAYOUT_DESCRIPTOR_DPKEY key, the EdgeLayoutDescriptors provided for the individual edges are used. Whenever no descriptor is provided for an edge, a default edge layout descriptor is used as fall-back value. This edge layout descriptor can be obtained with getDefaultEdgeLayoutDescriptor().

Concept

EdgeRouter coordinates all settings and steps that are needed to achieve a polylinear or orthogonal edge routing.
There are three steps that are executed in the following order:

1. Dividing the graph's area into several rectangular cells (see: Partition, GraphPartition, PartitionCell).
2. Finding the shortest/cheapest paths for all edges through the Partition (see: PathSearch, Path).
3. Assigning coordinates to the edges' segments based on the paths that were calculated before (see: ChannelBasedPathRouting).

It is possible to customize the first two steps by adding extensions for Partition or for PathSearch, respectively.
GraphPartitionExtensions add obstacles which the PathSearch will consider. They also can add some information to PartitionCells that, for example, specifies whether or not the PartitionCell belongs to a node.
PathSearchExtensions influence the PathSearch by adding costs for traversing specified PartitionCells or narrowing their intervals to allow a less expensive traversal of a PartitionCell. For example, the PathSearch adds costs to a PartitionCell that was marked as an obstacle that belongs to a node, so the edge will avoid the node.

Field Summary

static String	EDGE_LAYOUT_DESCRIPTOR_DPKEY DataProvider key used to store the EdgeLayoutDescriptor for each edge.
static byte	ROUTE_ALL_EDGES Sphere of action specifier.
static byte	ROUTE_EDGES_AT_SELECTED_NODES Sphere of action specifier.
static byte	ROUTE_SELECTED_EDGES Sphere of action specifier.

Fields inherited from interface y.layout.Layouter

EDGE_ID_DPKEY, NODE_ID_DPKEY, SELECTED_EDGES, SELECTED_NODES

Constructor Summary

EdgeRouter()
Creates a new EdgeRouter instance.

EdgeRouter(Layouter core)
Creates a new EdgeRouter instance with the given core Layouter.

Method Summary

boolean	canLayout(LayoutGraph graph) Returns true iff the given graph can be laid out by this algorithm.
protected void	cleanupGraphPartition(GraphPartition partition) Cleans up the given GraphPartition.
protected void	configureGraphPartition(GraphPartition partition) Configures the given GraphPartition.
protected void	configurePathSearch(PathSearch pathSearch) Configures the given PathSearch.
protected PathSearchConfiguration	createConfiguration(LayoutGraph graph, Grouping grouping) Creates the PathSearchConfiguration that is used during the path search.
protected GraphPartition	createGraphPartition(ObstaclePartition decomposition) Creates a GraphPartition that divides the area of the graph into several rectangles.
protected DynamicObstacleDecomposition	createObstacleDecomposition() Creates a DynamicObstacleDecomposition that is used by the GraphPartition to divide the graph area in rectangles.
protected ChannelBasedPathRouting	createPathRouting() Creates a ChannelBasedPathRouting that routes the edges using pre-calculated Path objects.
protected PathSearch	createPathSearch() Creates a PathSearch that finds the edges' paths through the GraphPartition.
protected PathSearchContext	createPathSearchContext(PathSearch pathSearch, PathSearchConfiguration configuration) Creates a PathSearchContext that provides context information for the path search algorithm.
void	doLayout(LayoutGraph graph) Main layout routine that assigns new layout information to the given graph.
EdgeLayoutDescriptor	getDefaultEdgeLayoutDescriptor() Returns the EdgeLayoutDescriptor instance used for all those edges, that do not have a specific layout descriptor assigned.
protected EdgeLayoutDescriptor	getEdgeLayoutDescriptor(Edge edge) Returns the EdgeLayoutDescriptor provided by the DataProvider with the key EDGE_LAYOUT_DESCRIPTOR_DPKEY for the given edge.
Grid	getGrid() Returns the Grid the edge router tries to place the orthogonal segments on.
long	getMaximumDuration() Returns the time limit (in milliseconds) set for the layout algorithm.
double	getMaximumPolylineSegmentRatio() Returns the maximum segment length ratio at each end of an orthogonal segment that may get converted into a (non-orthogonal) polyline segment.
double	getMinimalNodeToEdgeDistance() Determines the minimal distance between edges and node bounds.
GraphPartition	getPartition() Returns the GraphPartition used during the layout.
double	getPreferredPolylineSegmentLength() Returns the preferred length of (non-orthogonal) polyline segments.
List	getRegisteredPartitionExtensions() Returns a list containing all registered GraphPartitionExtensions.
List	getRegisteredPathSearchExtensions() Returns a list containing all registered PathSearchExtensions.
Object	getSelectedEdgesDpKey() Returns the data provider key used to look up the selected state of the edges of the graph to be laid out.
Object	getSelectedNodesDpKey() Returns the data provider key used to look up the selected state of the nodes of the graph to be laid out.
byte	getSphereOfAction() Returns the currently set sphere of action specifier.
boolean	isConsiderEdgeLabelsEnabled() Determines whether or not this edge router considers labels of edges that are not in the edge (sub-)set to be routed (see setSphereOfAction(byte).
boolean	isConsiderNodeLabelsEnabled() Determines whether or not this edge router considers node labels as obstacles for edge routes.
boolean	isPolylineRoutingEnabled() Determines whether or not this edge router creates (non-orthogonal) polyline segments.
boolean	isReroutingEnabled() Determines whether or not the edge router uses an additional step to reroute those edges that are considered to have the worst paths.
void	setConsiderEdgeLabelsEnabled(boolean considerEdgeLabelsEnabled) Specifies whether or not this edge router considers labels of edges that are not in the edge (sub-)set to be routed (see setSphereOfAction(byte).
void	setConsiderNodeLabelsEnabled(boolean considerNodeLabelsEnabled) Specifies whether or not this edge router considers node labels as obstacles for edge routes.
void	setGrid(Grid grid) Specifies the Grid on which orthogonal segments are placed.
void	setMaximumDuration(long maximumDuration) Sets a preferred time limit (>= 0 and in milliseconds) for the layout algorithm.
void	setMaximumPolylineSegmentRatio(double maximumPolylineSegmentRatio) Sets the maximum segment length ratio at each end of an orthogonal segment that may get converted into a (non-orthogonal) polyline segment.
void	setMinimalNodeToEdgeDistance(double minimalNodeToEdgeDistance) Specifies the minimal distance between edges and node bounds.
void	setPolylineRoutingEnabled(boolean polylineRoutingEnabled) Specifies whether or not this edge router creates (non-orthogonal) polyline segments.
void	setPreferredPolylineSegmentLength(double preferredPolylineSegmentLength) Sets the preferred length of (non-orthogonal) polyline segments.
void	setReroutingEnabled(boolean reroutingEnabled) Specifies whether or not the edge router uses an additional step to reroute those edges that are considered to have the worst paths.
void	setSelectedEdgesDpKey(Object selectedEdgesDpKey) Specifies the data provider key used to look up the selected state of the edges of the graph to be laid out.
void	setSelectedNodesDpKey(Object key) Specifies the data provider key used to look up the selected state of the nodes of the graph to be laid out.
void	setSphereOfAction(byte sphere) Sets the edge (sub-)set to be routed.

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

EDGE_LAYOUT_DESCRIPTOR_DPKEY

public static final String EDGE_LAYOUT_DESCRIPTOR_DPKEY

DataProvider key used to store the EdgeLayoutDescriptor for each edge. If there is no descriptor mapped for an edge, the default descriptor is used.

See Also:

getDefaultEdgeLayoutDescriptor(), Constant Field Values

ROUTE_ALL_EDGES

public static final byte ROUTE_ALL_EDGES

Sphere of action specifier. Route all edges of the input graph.

See Also:

setSphereOfAction(byte), Constant Field Values

ROUTE_SELECTED_EDGES

public static final byte ROUTE_SELECTED_EDGES

Sphere of action specifier. Route only selected edges of the input graph. The selection state of an edge is determined by a boolean value returned by the data provider associated with the data provider key getSelectedEdgesDpKey().

See Also:

Graph.addDataProvider(Object,DataProvider), setSphereOfAction(byte), Constant Field Values

ROUTE_EDGES_AT_SELECTED_NODES

public static final byte ROUTE_EDGES_AT_SELECTED_NODES

Sphere of action specifier. Route only edges connected to selected nodes. The selection state of a node is determined by a boolean value returned by the data provider associated with the data provider key getSelectedNodesDpKey().

See Also:

Graph.addDataProvider(Object,DataProvider), setSphereOfAction(byte), Constant Field Values

Constructor Detail

EdgeRouter

public EdgeRouter(Layouter core)

Creates a new EdgeRouter instance with the given core Layouter.

EdgeRouter

public EdgeRouter()

Creates a new EdgeRouter instance.

Method Detail

getMaximumDuration

public long getMaximumDuration()

Returns the time limit (in milliseconds) set for the layout algorithm.

Returns:

the time limit.

See Also:

setMaximumDuration(long)

setMaximumDuration

public void setMaximumDuration(long maximumDuration)

Sets a preferred time limit (>= 0 and in milliseconds) for the layout algorithm.

Note that restricting the maximum duration may result in a worse layout quality. Furthermore, the actual runtime may exceed the maximum duration since the layout algorithm still has to find a valid solution.

Parameters:

maximumDuration - the time limit.

See Also:

getMaximumDuration()

getDefaultEdgeLayoutDescriptor

public EdgeLayoutDescriptor getDefaultEdgeLayoutDescriptor()

Returns the EdgeLayoutDescriptor instance used for all those edges, that do not have a specific layout descriptor assigned.

Returns:

The default edge layout descriptor.

See Also:

EDGE_LAYOUT_DESCRIPTOR_DPKEY

getEdgeLayoutDescriptor

protected EdgeLayoutDescriptor getEdgeLayoutDescriptor(Edge edge)

Returns the EdgeLayoutDescriptor provided by the DataProvider with the key EDGE_LAYOUT_DESCRIPTOR_DPKEY for the given edge.

For all those edges, that do not have a specific layout descriptor assigned, the default descriptor is returned.

Parameters:

edge - The edge to return the layout descriptor for.

Returns:

The layout descriptor used for the given edge.

See Also:

EDGE_LAYOUT_DESCRIPTOR_DPKEY, getDefaultEdgeLayoutDescriptor()

isPolylineRoutingEnabled

public boolean isPolylineRoutingEnabled()

Determines whether or not this edge router creates (non-orthogonal) polyline segments.

Returns:

true if this edge router creates (non-orthogonal) polyline segments, false if only orthogonal segments shall be used.

See Also:

getPreferredPolylineSegmentLength(), getMaximumPolylineSegmentRatio()

setPolylineRoutingEnabled

public void setPolylineRoutingEnabled(boolean polylineRoutingEnabled)

Specifies whether or not this edge router creates (non-orthogonal) polyline segments.

Parameters:

polylineRoutingEnabled - true if this edge router creates (non-orthogonal) polyline segments, false if only orthogonal segments shall be used.

See Also:

setPreferredPolylineSegmentLength(double), setMaximumPolylineSegmentRatio(double)

getPreferredPolylineSegmentLength

public double getPreferredPolylineSegmentLength()

Returns the preferred length of (non-orthogonal) polyline segments.

Note that this restriction isn't used for orthogonal segments.

Returns:

The preferred length of (non-orthogonal) polyline segments.

See Also:

isPolylineRoutingEnabled(), getMaximumPolylineSegmentRatio()

setPreferredPolylineSegmentLength

public void setPreferredPolylineSegmentLength(double preferredPolylineSegmentLength)

Sets the preferred length of (non-orthogonal) polyline segments.

Note that this restriction isn't used for orthogonal segments.

Parameters:

preferredPolylineSegmentLength - The preferred length of (non-orthogonal) polyline segments.

See Also:

setPolylineRoutingEnabled(boolean), setMaximumPolylineSegmentRatio(double)

getMaximumPolylineSegmentRatio

public double getMaximumPolylineSegmentRatio()

Returns the maximum segment length ratio at each end of an orthogonal segment that may get converted into a (non-orthogonal) polyline segment.

Returns:

The maximum polyline segment ratio at each end of an orthogonal segment.

setMaximumPolylineSegmentRatio

public void setMaximumPolylineSegmentRatio(double maximumPolylineSegmentRatio)

Sets the maximum segment length ratio at each end of an orthogonal segment that may get converted into a (non-orthogonal) polyline segment.

Parameters:

maximumPolylineSegmentRatio - The maximum polyline segment ratio at each end of an orthogonal segment. The ratio must be between 0 and 0.5.

isReroutingEnabled

public boolean isReroutingEnabled()

Determines whether or not the edge router uses an additional step to reroute those edges that are considered to have the worst paths.

Rerouting is only used, if the getMaximumDuration() isn't exceeded, yet.

Returns:

true if a rerouting step will be done afterwards, false otherwise.

setReroutingEnabled

public void setReroutingEnabled(boolean reroutingEnabled)

Specifies whether or not the edge router uses an additional step to reroute those edges that are considered to have the worst paths.

Rerouting is only used, if the getMaximumDuration() isn't exceeded, yet.

Parameters:

reroutingEnabled - Whether or not a rerouting step shall be done afterwards.

setSphereOfAction

public void setSphereOfAction(byte sphere)

Sets the edge (sub-)set to be routed. Default setting is ROUTE_ALL_EDGES.

Throws:

IllegalArgumentException - if the given argument is not one of the above constants.

Parameters:

sphere - One of ROUTE_SELECTED_EDGES, ROUTE_EDGES_AT_SELECTED_NODES, and ROUTE_ALL_EDGES.

See Also:

getSelectedEdgesDpKey()

getSphereOfAction

public byte getSphereOfAction()

Returns the currently set sphere of action specifier.

See Also:

setSphereOfAction(byte), ROUTE_ALL_EDGES, ROUTE_SELECTED_EDGES, ROUTE_EDGES_AT_SELECTED_NODES

getSelectedNodesDpKey

public Object getSelectedNodesDpKey()

Returns the data provider key used to look up the selected state of the nodes of the graph to be laid out. By default, Layouter.SELECTED_NODES is used.

If the sphere of action is set to ROUTE_EDGES_AT_SELECTED_NODES, only edges of selected nodes are routed while all other edges are considered to have fixed routes.

Returns:

The data provider key for the node selection.

See Also:

setSphereOfAction(byte)

setSelectedNodesDpKey

public void setSelectedNodesDpKey(Object key)

Specifies the data provider key used to look up the selected state of the nodes of the graph to be laid out. By default, Layouter.SELECTED_NODES is used.

If the sphere of action is set to ROUTE_EDGES_AT_SELECTED_NODES, only edges of selected nodes are routed while all other edges are considered to have fixed routes.

Throws:

IllegalArgumentException - if the specified key is null.

Parameters:

key - The data provider key for the node selection.

See Also:

getSphereOfAction()

getSelectedEdgesDpKey

public Object getSelectedEdgesDpKey()

Returns the data provider key used to look up the selected state of the edges of the graph to be laid out. By default, Layouter.SELECTED_EDGES is used.

If the sphere of action is set to ROUTE_SELECTED_EDGES, only the selected keys are routed while all other edges are considered to have fixed routes.

Returns:

The data provider key for the edge selection.

See Also:

getSphereOfAction()

setSelectedEdgesDpKey

public void setSelectedEdgesDpKey(Object selectedEdgesDpKey)

Specifies the data provider key used to look up the selected state of the edges of the graph to be laid out. By default, Layouter.SELECTED_EDGES is used.

If the sphere of action is set to ROUTE_SELECTED_EDGES, only the selected keys are routed while all other edges are considered to have fixed routes.

Throws:

IllegalArgumentException - if the specified key is null.

Parameters:

selectedEdgesDpKey - The data provider key for the edge selection.

See Also:

getSphereOfAction()

canLayout

public boolean canLayout(LayoutGraph graph)

Description copied from interface: Layouter

Returns true iff the given graph can be laid out by this algorithm. Calling doLayout with the given graph as its argument will only success if this method returns true.

setConsiderNodeLabelsEnabled

public void setConsiderNodeLabelsEnabled(boolean considerNodeLabelsEnabled)

Specifies whether or not this edge router considers node labels as obstacles for edge routes.

Parameters:

considerNodeLabelsEnabled - true, in case the edge router considers node labels as obstacles for edge routes, false otherwise.

See Also:

PenaltySettings.getNodeLabelCrossingPenalty()

isConsiderNodeLabelsEnabled

public boolean isConsiderNodeLabelsEnabled()

Determines whether or not this edge router considers node labels as obstacles for edge routes.

Returns:

true if this edge router considers node labels as obstacles for edge routes, false otherwise.

See Also:

PenaltySettings.getNodeLabelCrossingPenalty()

setConsiderEdgeLabelsEnabled

public void setConsiderEdgeLabelsEnabled(boolean considerEdgeLabelsEnabled)

Specifies whether or not this edge router considers labels of edges that are not in the edge (sub-)set to be routed (see setSphereOfAction(byte).

Parameters:

considerEdgeLabelsEnabled - true, in case the edge router considers labels of edges that are not routed; false otherwise

See Also:

PenaltySettings.getNodeLabelCrossingPenalty(), setSphereOfAction(byte), setSelectedEdgesDpKey(Object)

isConsiderEdgeLabelsEnabled

public boolean isConsiderEdgeLabelsEnabled()

Determines whether or not this edge router considers labels of edges that are not in the edge (sub-)set to be routed (see setSphereOfAction(byte).

Returns:

true if this edge router considers labels of edges that are not routed; false otherwise

See Also:

PenaltySettings.getNodeLabelCrossingPenalty(), setSphereOfAction(byte), setSelectedEdgesDpKey(Object)

getGrid

public Grid getGrid()

Returns the Grid the edge router tries to place the orthogonal segments on.

Returns:

The grid to place the segments on.

setGrid

public void setGrid(Grid grid)

Specifies the Grid on which orthogonal segments are placed.

Parameters:

grid - The grid to place the segments on.

setMinimalNodeToEdgeDistance

public void setMinimalNodeToEdgeDistance(double minimalNodeToEdgeDistance)

Specifies the minimal distance between edges and node bounds.

Parameters:

minimalNodeToEdgeDistance - The minimal distance between edges and node bounds.

See Also:

PenaltySettings.getMinimalNodeToEdgeDistancePenalty()

getMinimalNodeToEdgeDistance

public double getMinimalNodeToEdgeDistance()

Determines the minimal distance between edges and node bounds.

Returns:

The minimal distance between edges and node bounds.

See Also:

PenaltySettings.getMinimalNodeToEdgeDistancePenalty()

createGraphPartition

protected GraphPartition createGraphPartition(ObstaclePartition decomposition)

Creates a GraphPartition that divides the area of the graph into several rectangles.

This implementation creates a GraphPartition using the current ObstaclePartition. It may be overridden to customize the partition used in EdgeRouter.

Returns:

a new GraphPartition

See Also:

configureGraphPartition(GraphPartition), getRegisteredPartitionExtensions()

configureGraphPartition

protected void configureGraphPartition(GraphPartition partition)

Configures the given GraphPartition.

This implementation gets all registered GraphPartitionExtensions and adds them to the given GraphPartition. It may be overridden to adjust the configuration of the GraphPartition.

Parameters:

partition - the partition that shall be configured

See Also:

configureGraphPartition(GraphPartition), getRegisteredPartitionExtensions()

cleanupGraphPartition

protected void cleanupGraphPartition(GraphPartition partition)

Cleans up the given GraphPartition.

This implementation gets all registered GraphPartitionExtensions and removes them from the given GraphPartition. It may be overridden to adjust the configuration of the GraphPartition.

Parameters:

partition - the partition that shall be configured

See Also:

configureGraphPartition(GraphPartition), getRegisteredPartitionExtensions()

getRegisteredPartitionExtensions

public List getRegisteredPartitionExtensions()

Returns a list containing all registered GraphPartitionExtensions.

GraphPartitionExtensions can be added and removed to change the composition of extensions used by the GraphPartition.

Returns:

a list containing all registered GraphPartitionExtensions

See Also:

createGraphPartition(ObstaclePartition), configureGraphPartition(GraphPartition)

createPathSearch

protected PathSearch createPathSearch()

Creates a PathSearch that finds the edges' paths through the GraphPartition.

This implementation creates a new PathSearch. May be overridden to customize the path search.

Returns:

a new PathSearch

See Also:

configurePathSearch(PathSearch), getRegisteredPathSearchExtensions()

configurePathSearch

protected void configurePathSearch(PathSearch pathSearch)

Configures the given PathSearch.

This implementation gets all registered PathSearchExtensions and adds them to the given PathSearch. It may be overridden to adjust the configuration of the PathSearch.

Parameters:

pathSearch - the path search that shall be configured

See Also:

createPathSearch(), getRegisteredPathSearchExtensions()

getRegisteredPathSearchExtensions

public List getRegisteredPathSearchExtensions()

Returns a list containing all registered PathSearchExtensions.

PathSearchExtension can be added and removed to change the composition of extensions used by the PathSearch.

Returns:

a list containing all registered PathSearchExtensions

See Also:

createPathSearch(), configurePathSearch(PathSearch)

createPathRouting

protected ChannelBasedPathRouting createPathRouting()

Creates a ChannelBasedPathRouting that routes the edges using pre-calculated Path objects.

This implementation creates a new ChannelBasedPathRouting. May be overridden to customize the path routing.

Returns:

A new ChannelBasedPathRouting

createObstacleDecomposition

protected DynamicObstacleDecomposition createObstacleDecomposition()

Creates a DynamicObstacleDecomposition that is used by the GraphPartition to divide the graph area in rectangles.

This implementation creates a new DynamicObstacleDecomposition. May be overridden to customize the area decomposition.

Returns:

A new DynamicObstacleDecomposition

See Also:

createGraphPartition(ObstaclePartition)

createPathSearchContext

protected PathSearchContext createPathSearchContext(PathSearch pathSearch,
                                                    PathSearchConfiguration configuration)

Creates a PathSearchContext that provides context information for the path search algorithm.

This implementation creates a new PathSearchContext. May be overridden to customize the context information providing.

Parameters:

pathSearch - The path search that uses the context to be created.

configuration - The configuration used for the path search.

Returns:

A new PathSearchContext

createConfiguration

protected PathSearchConfiguration createConfiguration(LayoutGraph graph,
                                                      Grouping grouping)

Creates the PathSearchConfiguration that is used during the path search.

This implementation creates a new PathSearchConfiguration. May be overridden to use a subclassed configuration.

Returns:

A new PathSearchConfiguration.

doLayout

public void doLayout(LayoutGraph graph)

Description copied from interface: Layouter

Main layout routine that assigns new layout information to the given graph.

getPartition

public GraphPartition getPartition()

Returns the GraphPartition used during the layout.

Returns:

The GraphPartition used during the layout or null if no layout is running right now.