y.layout.partial
Class FillAreaLayouter

java.lang.Object
  y.layout.partial.FillAreaLayouter

All Implemented Interfaces:

Layouter

public class FillAreaLayouter
extends java.lang.Object
implements Layouter

This layout algorithm tries to fill a specified area with graph elements by moving nearby elements towards it, with the goal to make the existing layout more compact and not changing it too much.

Layout Style

The algorithm can make an existing layout more compact in the region of the defined area. It moves nearby graph elements, while keeping the given layout style as much as possible. Ideally, only local changes around the marked area are made such that the mental map for the user is preserved. The best applications are those where it shall be avoided to calculate a completely new layout after local changes have been made to an already existing and good layout. Also not that the results for this application are much better when the edge paths are already good orthogonal, polyline or octilinear paths. For straight-line edge routes, the shape and overall mental map of the layout can not be preserved that well and the changes may be more global.

An example application is the use case that nodes were removed from the graph. The region where the nodes have been removed can then be defined as the area so that the algorithm can try to fill/use this free space and make the layout more compact. This way it can be avoided to compute a completely new layout for such cases. Another use case would be when a group node is collapsed and converted to a smaller folder node. In that case the folder node should be marked as fixed. Note that it isn't guaranteed that the area is filled with elements after calling the algorithm.

Sample input graph where the gray area should be filled with elements.

Result layout after applying this algorithm - the drawing was made much more compact and the free area is used.

Concept

The area (see setArea(YRectangle)) defines a region in the given graph which should be filled with elements, with the goal to make the overall layout more compact. To do so, graph elements must be moved. This includes nodes, edges and their labels. Whether node labels and edge labels should be considered can be controlled via settings isNodeLabelConsiderationEnabled() and isEdgeLabelConsiderationEnabled().

Keep in mind that the goal is to make the layout more compact. Therefore, if the area is located such that it brings no advantage to move elements towards it, the algorithm may also do nothing - based on a heuristic decision. This means that it does not fill the specified area in any case.

Features

The algorithm is able to consider a specified PartitionGrid as long as there are no group nodes that span multiple grid cells. For this feature to work properly it is required that the values of the properties ColumnDescriptor.getOriginalPosition(), RowDescriptor.getOriginalPosition() ColumnDescriptor.getOriginalWidth() and RowDescriptor.getOriginalHeight() are correctly specified. This is usually automatically the case when executing the FillAreaLayouter as a standalone algorithm via layout execution convenience methods (e.g. the values are taken from the table visualization of the grid). However, if the FillAreaLayouter is applied as part of a more complex layout pipeline it may be necessary to specify the values manually. For example, if another algorithm previously computed the grid position values and stored them in the respective 'computed' properties (e.g. ColumnDescriptor.getComputedPosition()), and afterwards FillAreaLayouter should be applied, then the 'computed' values of the first algorithm should be written to the 'original' values prior to the run of the FillAreaLayouter.

This algorithm is not meant to be a general layout compaction algorithm. It focuses on the defined area but may also do nothing if, for example, moving elements would heavily affect the mental map of the existing layout or not make the layout more compact.

The input graph should already have a rather good layout for this algorithm to produce sophisticated results. The reason is that it analyzes the existing layout to decide how to change it. Overlapping nodes, edges intersecting nodes and other suboptimal arrangements can cause that this algorithm generates unexpected results. Furthermore, it is not meant to repair things like that in the input layout.

Field Summary

static byte	COMPONENT_ASSIGNMENT_STRATEGY_CLUSTERING A component assignment strategy where the subgraph components correspond to the clusters computed by a clustering algorithm based on edge betweenness centrality.
static byte	COMPONENT_ASSIGNMENT_STRATEGY_CONNECTED A component assignment strategy where the subgraph components correspond to the connected components of the graph.
static byte	COMPONENT_ASSIGNMENT_STRATEGY_CUSTOMIZED A component assignment strategy where the subgraph components are defined by the user.
static byte	COMPONENT_ASSIGNMENT_STRATEGY_SINGLE A component assignment strategy that assigns each node to a separate subgraph component.
static java.lang.Object	COMPONENT_ID_DPKEY A DataProvider key for defining custom components whose elements should preferably not be separated While the algorithm may move a whole component, it should preferably not move only a subset of its elements.
static java.lang.Object	FIXED_NODE_DPKEY A DataProvider key for marking nodes as fixed A node marked as fixed will not be moved by this algorithm but stay at its current position.
static byte	ORIENTATION_AUTO_DETECTION Layout orientation specifier where the orientation is automatically detected.
static byte	ORIENTATION_BOTTOM_TO_TOP Layout orientation specifier which defines that the main layout orientation is from bottom to top.
static byte	ORIENTATION_LEFT_TO_RIGHT Layout orientation specifier which defines that the main layout orientation is from left to right.
static byte	ORIENTATION_NONE Layout orientation specifier where the layout orientation is completely ignored.
static byte	ORIENTATION_RIGHT_TO_LEFT Layout orientation specifier which defines that the main layout orientation is from right to left.
static byte	ORIENTATION_TOP_TO_BOTTOM Layout orientation specifier which defines that the main layout orientation is from top to bottom.

Fields inherited from interface y.layout.Layouter

EDGE_ID_DPKEY, NODE_ID_DPKEY, NODE_TYPE_DPKEY, SELECTED_EDGES, SELECTED_NODES

Constructor Summary

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

Method Summary

boolean	canLayout(LayoutGraph graph) Accepts all general graphs.
void	doLayout(LayoutGraph graph) Tries to fill the specified area in the given graph with elements, such that the resulting layout is more compact.
YRectangle	getArea() Returns the rectangular area that should be filled.
byte	getComponentAssignmentStrategy() Returns the strategy that assigns nodes to components whose elements should preferably not be separated.
double	getGridSpacing() Returns the current grid spacing.
byte	getLayoutOrientation() Returns the layout orientation that is considered during the compaction process.
long	getMaximumDuration() Returns the time limit in milliseconds for the layout algorithm.
double	getSpacing() Returns the spacing that is considered between elements when they are moved.
boolean	isEdgeLabelConsiderationEnabled() Returns whether or not the layout algorithm considers edge labels.
boolean	isNodeLabelConsiderationEnabled() Returns whether or not the layout algorithm considers node labels.
void	setArea(YRectangle area) Specifies the rectangular area that should be filled.
void	setComponentAssignmentStrategy(byte componentAssignmentStrategy) Specifies the strategy that assigns nodes to components whose elements should preferably not be separated.
void	setEdgeLabelConsiderationEnabled(boolean edgeLabelConsiderationEnabled) Specifies whether or not the layout algorithm considers edge labels.
void	setGridSpacing(double gridSpacing) Specifies the current grid spacing.
void	setLayoutOrientation(byte layoutOrientation) Specifies the layout orientation that is considered during the compaction process.
void	setMaximumDuration(long maximumDuration) Specifies the time limit in milliseconds for the layout algorithm.
void	setNodeLabelConsiderationEnabled(boolean nodeLabelConsiderationEnabled) Specifies whether or not the layout algorithm considers node labels.
void	setSpacing(double spacing) Specifies the spacing that is considered between elements when they are moved.

Methods inherited from class java.lang.Object

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

Field Detail

COMPONENT_ID_DPKEY

public static final java.lang.Object COMPONENT_ID_DPKEY

A DataProvider key for defining custom components whose elements should preferably not be separated

While the algorithm may move a whole component, it should preferably not move only a subset of its elements. This means that the algorithm tries to move all elements of a component by the same offset (if at all). In order to achieve good results with this feature, the different components should not overlap in the initial drawing.

The specified custom components are only considered when property getComponentAssignmentStrategy() is set to COMPONENT_ASSIGNMENT_STRATEGY_CUSTOMIZED.

See Also:

setComponentAssignmentStrategy(byte)

FIXED_NODE_DPKEY

public static final java.lang.Object FIXED_NODE_DPKEY

A DataProvider key for marking nodes as fixed

A node marked as fixed will not be moved by this algorithm but stay at its current position.

The algorithm tries to preserve the mental map and, thus, non-fixed nodes cannot simply pass/jump over the fixed nodes (i.e., fixed nodes restrict the possible movement of non-fixed nodes).

COMPONENT_ASSIGNMENT_STRATEGY_SINGLE

public static final byte COMPONENT_ASSIGNMENT_STRATEGY_SINGLE

A component assignment strategy that assigns each node to a separate subgraph component.

See Also:

PartialLayouter.setComponentAssignmentStrategy(byte), ClearAreaLayouter.setComponentAssignmentStrategy(byte), setComponentAssignmentStrategy(byte), Constant Field Values

COMPONENT_ASSIGNMENT_STRATEGY_CONNECTED

public static final byte COMPONENT_ASSIGNMENT_STRATEGY_CONNECTED

A component assignment strategy where the subgraph components correspond to the connected components of the graph.

See Also:

PartialLayouter.setComponentAssignmentStrategy(byte), ClearAreaLayouter.setComponentAssignmentStrategy(byte), setComponentAssignmentStrategy(byte), Constant Field Values

COMPONENT_ASSIGNMENT_STRATEGY_CLUSTERING

public static final byte COMPONENT_ASSIGNMENT_STRATEGY_CLUSTERING

A component assignment strategy where the subgraph components correspond to the clusters computed by a clustering algorithm based on edge betweenness centrality.

See Also:

PartialLayouter.setComponentAssignmentStrategy(byte), ClearAreaLayouter.setComponentAssignmentStrategy(byte), setComponentAssignmentStrategy(byte), Constant Field Values

COMPONENT_ASSIGNMENT_STRATEGY_CUSTOMIZED

public static final byte COMPONENT_ASSIGNMENT_STRATEGY_CUSTOMIZED

A component assignment strategy where the subgraph components are defined by the user.

See Also:

PartialLayouter.setComponentAssignmentStrategy(byte), ClearAreaLayouter.setComponentAssignmentStrategy(byte), setComponentAssignmentStrategy(byte), Constant Field Values

ORIENTATION_TOP_TO_BOTTOM

public static final byte ORIENTATION_TOP_TO_BOTTOM

Layout orientation specifier which defines that the main layout orientation is from top to bottom.

See Also:

PartialLayouter.setLayoutOrientation(byte), ClearAreaLayouter.setLayoutOrientation(byte), setLayoutOrientation(byte), Constant Field Values

ORIENTATION_BOTTOM_TO_TOP

public static final byte ORIENTATION_BOTTOM_TO_TOP

Layout orientation specifier which defines that the main layout orientation is from bottom to top.

See Also:

PartialLayouter.setLayoutOrientation(byte), ClearAreaLayouter.setLayoutOrientation(byte), setLayoutOrientation(byte), Constant Field Values

ORIENTATION_LEFT_TO_RIGHT

public static final byte ORIENTATION_LEFT_TO_RIGHT

Layout orientation specifier which defines that the main layout orientation is from left to right.

See Also:

PartialLayouter.setLayoutOrientation(byte), ClearAreaLayouter.setLayoutOrientation(byte), setLayoutOrientation(byte), Constant Field Values

ORIENTATION_RIGHT_TO_LEFT

public static final byte ORIENTATION_RIGHT_TO_LEFT

Layout orientation specifier which defines that the main layout orientation is from right to left.

See Also:

PartialLayouter.setLayoutOrientation(byte), ClearAreaLayouter.setLayoutOrientation(byte), setLayoutOrientation(byte), Constant Field Values

ORIENTATION_AUTO_DETECTION

public static final byte ORIENTATION_AUTO_DETECTION

Layout orientation specifier where the orientation is automatically detected.

See Also:

PartialLayouter.setLayoutOrientation(byte), ClearAreaLayouter.setLayoutOrientation(byte), setLayoutOrientation(byte), Constant Field Values

ORIENTATION_NONE

public static final byte ORIENTATION_NONE

Layout orientation specifier where the layout orientation is completely ignored.

See Also:

PartialLayouter.setLayoutOrientation(byte), ClearAreaLayouter.setLayoutOrientation(byte), setLayoutOrientation(byte), Constant Field Values

Constructor Detail

FillAreaLayouter

public FillAreaLayouter()

Creates a new instance of FillAreaLayouter with default settings.

Method Detail

getGridSpacing

public double getGridSpacing()

Returns the current grid spacing.

Elements are moved by multiples of this value, thus, keeping their offset to the grid. That way, components or parts of them that were placed on a grid before, will stay on their original grid.

The grid spacing needs to be a non-negative value. If it is set to 0, no grid is considered.

For edges that need to be rerouted, it is not guaranteed that the bends are placed on grid points.

Returns:

the grid spacing

See Also:

setGridSpacing(double)

setGridSpacing

public void setGridSpacing(double gridSpacing)

Specifies the current grid spacing.

Elements are moved by multiples of this value, thus, keeping their offset to the grid. That way, components or parts of them that were placed on a grid before, will stay on their original grid.

The grid spacing needs to be a non-negative value. If it is set to 0, no grid is considered.

For edges that need to be rerouted, it is not guaranteed that the bends are placed on grid points.

Default Value:

The default value is 0. No grid is considered.

Parameters:

gridSpacing - the grid spacing

Throws:

java.lang.IllegalArgumentException - if the given spacing is negative

getComponentAssignmentStrategy

public byte getComponentAssignmentStrategy()

Returns the strategy that assigns nodes to components whose elements should preferably not be separated.

While the algorithm may move a whole component, it tries to not move only a subset of its elements, thus, all elements of a component are not moved at all or moved by the same offset.

• COMPONENT_ASSIGNMENT_STRATEGY_CUSTOMIZED: the components can be user-defined. If the user does not specify any, there are no components that should explicitly be kept together, which is equal to the behavior of COMPONENT_ASSIGNMENT_STRATEGY_SINGLE.
• COMPONENT_ASSIGNMENT_STRATEGY_CONNECTED components are defined by the connected components of the graph.
• COMPONENT_ASSIGNMENT_STRATEGY_CLUSTERING: components are defined by edge betweenness clustering.
• COMPONENT_ASSIGNMENT_STRATEGY_SINGLE: each node is a separate component which basically means that there are no components that should explicitly be kept together.

Borders of groups and partition cells always split up the components, i.e., two nodes assigned to different groups or partition cells are always assigned to different subgraph components.

Returns:

one of the predefined assignment strategies

See Also:

setComponentAssignmentStrategy(byte), COMPONENT_ID_DPKEY

setComponentAssignmentStrategy

public void setComponentAssignmentStrategy(byte componentAssignmentStrategy)

Specifies the strategy that assigns nodes to components whose elements should preferably not be separated.

While the algorithm may move a whole component, it tries to not move only a subset of its elements, thus, all elements of a component are not moved at all or moved by the same offset.

• COMPONENT_ASSIGNMENT_STRATEGY_CUSTOMIZED: the components can be user-defined. If the user does not specify any, there are no components that should explicitly be kept together, which is equal to the behavior of COMPONENT_ASSIGNMENT_STRATEGY_SINGLE.
• COMPONENT_ASSIGNMENT_STRATEGY_CONNECTED components are defined by the connected components of the graph.
• COMPONENT_ASSIGNMENT_STRATEGY_CLUSTERING: components are defined by edge betweenness clustering.
• COMPONENT_ASSIGNMENT_STRATEGY_SINGLE: each node is a separate component which basically means that there are no components that should explicitly be kept together.

Borders of groups and partition cells always split up the components, i.e., two nodes assigned to different groups or partition cells are always assigned to different subgraph components.

Default Value:

The default value is COMPONENT_ASSIGNMENT_STRATEGY_CUSTOMIZED. Components can be user-defined and if none are defined, each node is a separate component.

Parameters:

componentAssignmentStrategy - one of the predefined assignment strategies

Throws:

java.lang.IllegalArgumentException - if the specified strategy does not match one of the predefined strategies

See Also:

COMPONENT_ID_DPKEY

getMaximumDuration

public long getMaximumDuration()

Returns the time limit in milliseconds for the layout algorithm.

Values have to be greater than or equal to 0.

Restricting the maximum duration may result in a lower layout quality. Furthermore, the real runtime may exceed the maximum duration since the layout algorithm still has to find a valid solution.

Returns:

the non-negative value that specifies the time limit in milliseconds

See Also:

setMaximumDuration(long)

setMaximumDuration

public void setMaximumDuration(long maximumDuration)

Specifies the time limit in milliseconds for the layout algorithm.

Values have to be greater than or equal to 0.

Restricting the maximum duration may result in a lower layout quality. Furthermore, the real runtime may exceed the maximum duration since the layout algorithm still has to find a valid solution.

Default Value:

The default value is Long.MAX_VALUE.

Parameters:

maximumDuration - the non-negative value that specifies the time limit in milliseconds

Throws:

java.lang.IllegalArgumentException - if the maximum duration is negative

getArea

public YRectangle getArea()

Returns the rectangular area that should be filled.

The specified area may already contain some elements. In order to fill the area, the algorithm may move elements while it still tries to preserve the mental map of the initial layout. Note that after applying this algorithm it is not guaranteed that there are any elements in the specified area.

If the area is set to null (default) or if it is specified and contains all elements of the graph, the algorithm terminates without changing anything.

Returns:

the rectangular area that should be filled

See Also:

setArea(YRectangle)

setArea

public void setArea(YRectangle area)

Specifies the rectangular area that should be filled.

The specified area may already contain some elements. In order to fill the area, the algorithm may move elements while it still tries to preserve the mental map of the initial layout. Note that after applying this algorithm it is not guaranteed that there are any elements in the specified area.

If the area is set to null (default) or if it is specified and contains all elements of the graph, the algorithm terminates without changing anything.

Default Value:

The default value is null. There is no area to be filled.

Parameters:

area - the rectangular area that should be filled

getSpacing

public double getSpacing()

Returns the spacing that is considered between elements when they are moved.

This spacing only affects the moving of elements towards the desired area. Elements keep the specified distance to other elements and among each other. Carefully observe that if the distance between two elements is already smaller, then they may not be moved apart.

The spacing is considered for all graph elements, including nodes, edges, node labels and edge labels when they are encountered during the movement process.

Returns:

the non-negative spacing between elements

See Also:

setSpacing(double)

setSpacing

public void setSpacing(double spacing)

Specifies the spacing that is considered between elements when they are moved.

This spacing only affects the moving of elements towards the desired area. Elements keep the specified distance to other elements and among each other. Carefully observe that if the distance between two elements is already smaller, then they may not be moved apart.

The spacing is considered for all graph elements, including nodes, edges, node labels and edge labels when they are encountered during the movement process.

Default Value:

The default value is 10.

Parameters:

spacing - the non-negative spacing between elements

Throws:

java.lang.IllegalArgumentException - if the given spacing is negative

Sample Graphs:

Spacing set to 10 (the gray region was compacted).

Spacing set to 30 (the gray region was compacted).

isNodeLabelConsiderationEnabled

public boolean isNodeLabelConsiderationEnabled()

Returns whether or not the layout algorithm considers node labels.

If enabled, node labels are considered when moving elements such that overlaps with them are not allowed.

If disabled, elements that are moved may overlap with node labels, even if they did not overlap in the input.

Returns:

true if node labels are considered, false otherwise

See Also:

setNodeLabelConsiderationEnabled(boolean)

setNodeLabelConsiderationEnabled

public void setNodeLabelConsiderationEnabled(boolean nodeLabelConsiderationEnabled)

Specifies whether or not the layout algorithm considers node labels.

If enabled, node labels are considered when moving elements such that overlaps with them are not allowed.

If disabled, elements that are moved may overlap with node labels, even if they did not overlap in the input.

Default Value:

The default value is true. Node labels are considered.

Parameters:

nodeLabelConsiderationEnabled - true if node labels should be considered, false otherwise

isEdgeLabelConsiderationEnabled

public boolean isEdgeLabelConsiderationEnabled()

Returns whether or not the layout algorithm considers edge labels.

If enabled, edge labels are considered when moving elements such that overlaps with them are not allowed. Furthermore, they are correctly moved along with an edge if an edge is moved.

If disabled, elements that are moved may overlap with edge labels, even if they did not overlap in the input.

Returns:

true if edge labels are considered, false otherwise

See Also:

setEdgeLabelConsiderationEnabled(boolean)

setEdgeLabelConsiderationEnabled

public void setEdgeLabelConsiderationEnabled(boolean edgeLabelConsiderationEnabled)

Specifies whether or not the layout algorithm considers edge labels.

If enabled, edge labels are considered when moving elements such that overlaps with them are not allowed. Furthermore, they are correctly moved along with an edge if an edge is moved.

If disabled, elements that are moved may overlap with edge labels, even if they did not overlap in the input.

Default Value:

The default value is true. Edge labels are considered.

Parameters:

edgeLabelConsiderationEnabled - true if edge labels should be considered, false otherwise

getLayoutOrientation

public byte getLayoutOrientation()

Returns the layout orientation that is considered during the compaction process.

The orientation affects the direction that the algorithm prefers when moving elements. For the vertical orientations ORIENTATION_TOP_TO_BOTTOM and ORIENTATION_BOTTOM_TO_TOP, moving elements horizontally (i.e. to the left and to the right) is preferred. For the horizontal orientations ORIENTATION_LEFT_TO_RIGHT and ORIENTATION_RIGHT_TO_LEFT, the vertical moving direction is preferred. This is mainly useful for layouts that have a clear direction and nodes are divided into layers with respect to this directions, like e.g., hierarchical layouts.

If this behavior is undesired, the orientation can be ignored by specifying ORIENTATION_NONE. No specific moving direction will be preferred in that case. The orientation can also be automatically detected based on the flow direction of the edges when choosing ORIENTATION_AUTO_DETECTION.

Returns:

one of the predefined layout orientations

See Also:

setLayoutOrientation(byte)

setLayoutOrientation

public void setLayoutOrientation(byte layoutOrientation)

Specifies the layout orientation that is considered during the compaction process.

The orientation affects the direction that the algorithm prefers when moving elements. For the vertical orientations ORIENTATION_TOP_TO_BOTTOM and ORIENTATION_BOTTOM_TO_TOP, moving elements horizontally (i.e. to the left and to the right) is preferred. For the horizontal orientations ORIENTATION_LEFT_TO_RIGHT and ORIENTATION_RIGHT_TO_LEFT, the vertical moving direction is preferred. This is mainly useful for layouts that have a clear direction and nodes are divided into layers with respect to this directions, like e.g., hierarchical layouts.

If this behavior is undesired, the orientation can be ignored by specifying ORIENTATION_NONE. No specific moving direction will be preferred in that case. The orientation can also be automatically detected based on the flow direction of the edges when choosing ORIENTATION_AUTO_DETECTION.

Default Value:

The default value is ORIENTATION_NONE. The layout is considered to have no specific orientation.

Parameters:

layoutOrientation - one of the predefined layout orientations

Throws:

java.lang.IllegalArgumentException - if the specified orientation does not match one of the predefined orientations

canLayout

public boolean canLayout(LayoutGraph graph)

Accepts all general graphs.

Specified by:

canLayout in interface Layouter

Parameters:

graph - the input graph

Returns:

true for all kinds of graphs

See Also:

Layouter.doLayout(LayoutGraph)

doLayout

public void doLayout(LayoutGraph graph)

Tries to fill the specified area in the given graph with elements, such that the resulting layout is more compact.

Specified by:

doLayout in interface Layouter

Parameters:

graph - the input graph

See Also:

Layouter.canLayout(LayoutGraph)