Search this API

y.layout.partial
Class FillAreaLayouter

java.lang.Object
  extended by 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.

 
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.

 
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)

© Copyright 2000-2022,
yWorks GmbH.
All rights reserved.