y.layout.grouping
Class CactusGroupLayouter

java.lang.Object
  y.layout.CanonicMultiStageLayouter
      y.layout.grouping.CactusGroupLayouter

All Implemented Interfaces:

Layouter

public class CactusGroupLayouter
extends CanonicMultiStageLayouter

This layout algorithm arranges grouped graphs in a recursive structure.

Layout Style

CactusGroupLayouter is designed to arrange directed and undirected, hierarchically grouped graphs. All members of a group are placed adjacent to the group node along its circular border, resembling the structure of a cactus. The group hierarchy of the graph is represented implicitly by the position of the nodes. Non-hierarchical edges are routed through the centers of all nodes on a path through the hierarchy tree, connecting the edge's endpoints.

Sample cactus drawing of a large graph with default settings

Cactus group layout algorithms are commonly used for visualizing relational data and for producing diagrams of high quality that are able to showcase hierarchic properties of the graph. They especially address the concern of recognizability between identical subtrees.

Concept

The algorithm executes the following steps

1. If no single group acts as a unique root of the hierarchy, create a virtual root containing all nodes to base the layout on.
2. Recursively determine the size of each node to accommodate the subtrees rooted in its children and place the subtrees relative to it. Prioritize placing large subtrees in centered positions to promote vertical growth.
3. Adjust the placement of individual subtrees to optimize the usage of space around the subtree roots and improve the compactness of the drawing.
4. Route the non-hierarchical edges of the graph according to the specified routing policies.
5. Remove the virtual root of the group, if it was added during the first step of the algorithm.

Features

The algorithm features the possibility to collapse the hierarchy at one or more of its groups, to gather all direct and indirect members of the specified group or groups along their boundary. Collapsed groups can be specified using the DataProvider registered with COLLAPSED_SUBTREE_ROOTS_DPKEY.

The CactusGroupLayouter allows for integrated node labeling. Node labels are placed automatically without generating overlaps with other labels or graph elements. Note that for nodes with multiple labels such overlaps may occur. There are different ways to place node labels.

The algorithm supports edge bundling and all its included features for non-hierarchical edges of the graph.

Defining a preferred wedge angle has a great influence on the layout style. Subtrees at the hierarchy's root get a certain amount of radial space to be placed around the root node, such that a large preferred angle will generally lead to more compact drawings while a smaller angle will focus the drawing towards a singular direction.

The CactusGroupLayouter supports customizing the overlap between nodes and their parent nodes. The overlap can be set individually for each node by registering a DataProvider with PARENT_OVERLAP_RATIO_DPKEY.

Since it is computationally not very complex, CactusGroupLayouter is well suited for large graphs. It performs well even for huge graphs.

Even though the integrated node labeling is enabled, there may sometimes be overlapping labels if there are nodes with multiple labels.

The layout algorithm considers the nodes as circles and, thus, using a circular node style is strongly recommended to obtain suitable visualizations.

Field Summary

static java.lang.Object	COLLAPSED_SUBTREE_ROOTS_DPKEY A DataProvider key for specifying the roots of collapsed subtrees in the hierarchy.
static byte	GROUP_SIZING_POLICY_ADAPTIVE Policy for sizing group nodes individually that optimizes for compact drawings.
static byte	GROUP_SIZING_POLICY_COMPACT Policy for sizing group nodes individually that optimizes for compact drawings.
static byte	GROUP_SIZING_POLICY_STABLE Policy for sizing group nodes individually that optimizes for compact drawings which can be collapsed at any group without producing overlaps.
static java.lang.Object	PARENT_OVERLAP_RATIO_DPKEY A DataProvider key for specifying the overlap of nodes with their parent in the hierarchy.

Fields inherited from interface y.layout.Layouter

EDGE_ID_DPKEY, NODE_ID_DPKEY, NODE_TYPE_DPKEY, SELECTED_EDGES, SELECTED_NODES

Constructor Summary

CactusGroupLayouter()
Creates a new CactusGroupLayouter instance with default settings.

Method Summary

protected boolean	canLayoutCore(LayoutGraph graph) Accepts all graphs.
protected void	doLayoutCore(LayoutGraph graph) Arranges the given grouped graph in the style of a cactus group layout.
java.util.Comparator	getDefaultNodeComparator() Returns the default policy for ordering subtree roots around their common parent.
EdgeBundling	getEdgeBundling() Returns the EdgeBundling instance that defines the settings of the edge bundling feature.
byte	getGroupSizingPolicy() Returns the policy defining how group node sizes are determined.
java.util.Comparator	getNodeComparator() Returns a Comparator for children of the same parent node, by which the order of the subtrees around their parent is determined.
byte	getNodeLabelingPolicy() Returns the policy defining how node labels are placed by the integrated node labeling mechanism (for example, the desired label orientation).
double	getNodeLabelSpacing() Returns the spacing used for node labels when integrated node labeling is enabled.
double	getPreferredRootWedge() Returns the maximum angle on which the root's children can be distributed around its center.
boolean	isFromSketchModeEnabled() Returns whether or not the order of subtrees around a root may be changed by the algorithm.
boolean	isIntegratedNodeLabelingEnabled() Returns whether or not the layout algorithm automatically places node labels.
boolean	isNodeLabelConsiderationEnabled() Returns whether the algorithm actively prevents node label overlaps when computing the layout.
void	setFromSketchModeEnabled(boolean fromSketchModeEnabled) Specifies whether or not the order of subtrees around a root may be changed by the algorithm.
void	setGroupSizingPolicy(byte groupSizingPolicy) Specifies the policy defining how group node sizes are determined.
void	setIntegratedNodeLabelingEnabled(boolean integratedNodeLabelingEnabled) Specifies whether or not the layout algorithm automatically places node labels.
void	setNodeComparator(java.util.Comparator comp) Specifies a Comparator for children of the same parent node, by which the order of the subtrees around their parent is determined.
void	setNodeLabelConsiderationEnabled(boolean nodeLabelConsiderationEnabled) Specifies whether the algorithm actively prevents node label overlaps when computing the layout.
void	setNodeLabelingPolicy(byte nodeLabelingPolicy) Specifies the policy defining how node labels are placed by the integrated node labeling mechanism (for example, the desired label orientation).
void	setNodeLabelSpacing(double nodeLabelSpacing) Specifies the spacing used for node labels when integrated node labeling is enabled.
void	setPreferredRootWedge(double preferredRootWedge) Specifies the maximum angle on which the root's children can be distributed around its center.

Methods inherited from class y.layout.CanonicMultiStageLayouter

appendStage, calcLayout, calcLayout, canLayout, checkGroupNodeSize, checkNodeSize, doLayout, doLayout, enableOnlyCore, getComponentLayouter, getGroupNodeHider, getLabelLayouter, getLayoutOrientation, getOrientationLayouter, getParallelEdgeLayouter, getSelfLoopLayouter, getSubgraphLayouter, isComponentLayouterEnabled, isGroupNodeHidingEnabled, isLabelLayouterEnabled, isOrientationLayouterEnabled, isParallelEdgeLayouterEnabled, isSelfLoopLayouterEnabled, isSubgraphLayouterEnabled, prependStage, removeStage, setComponentLayouter, setComponentLayouterEnabled, setGroupNodeHider, setGroupNodeHidingEnabled, setLabelLayouter, setLabelLayouterEnabled, setLayoutOrientation, setOrientationLayouter, setOrientationLayouterEnabled, setParallelEdgeLayouter, setParallelEdgeLayouterEnabled, setSelfLoopLayouter, setSelfLoopLayouterEnabled, setSubgraphLayouter, setSubgraphLayouterEnabled

Methods inherited from class java.lang.Object

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

Field Detail

COLLAPSED_SUBTREE_ROOTS_DPKEY

public static final java.lang.Object COLLAPSED_SUBTREE_ROOTS_DPKEY

A DataProvider key for specifying the roots of collapsed subtrees in the hierarchy.

If the data provider entry for a group node is set to false all children of the node are placed on its border and their respective descendants are arranged recursively. If the entry is however set to true, all descendants of the node are placed depending on whether they are inner nodes or leaves. Inner nodes are positioned at the center of the node whereas leaves are placed on its border in place of child nodes. The entries of leaf nodes in the hierarchy have no effect.

If no DataProvider is registered with this key, the algorithm assumes that all nodes have the value false.

Sample Graphs:

false

true

PARENT_OVERLAP_RATIO_DPKEY

public static final java.lang.Object PARENT_OVERLAP_RATIO_DPKEY

A DataProvider key for specifying the overlap of nodes with their parent in the hierarchy.

Generally, the cactus group layout algorithm places all child nodes in the hierarchy such that they are touching their respective parent node. However, an overlap can be specified as a fraction of the child's radius, by which the node will be moved towards the parent node's center.

If no DataProvider is registered with this key, the algorithm assumes that all nodes have the value 0.2.

Sample Graphs:

0.0

0.5

GROUP_SIZING_POLICY_COMPACT

public static final byte GROUP_SIZING_POLICY_COMPACT

Policy for sizing group nodes individually that optimizes for compact drawings.

The size of group nodes is determined individually for each group so as to maximize the compactness of the drawing without producing overlaps. With this policy, some emphasis is placed on maintaining the group sizes in the remaining graph when collapsing subtrees.

See Also:

setGroupSizingPolicy(byte), Constant Field Values

Sample Graphs:

Compact cactus drawing without collapsed subtrees

Compact cactus drawing with a collapsed subtree

GROUP_SIZING_POLICY_ADAPTIVE

public static final byte GROUP_SIZING_POLICY_ADAPTIVE

Policy for sizing group nodes individually that optimizes for compact drawings.

The size of group nodes is determined individually for each group so as to maximize the compactness of the drawing without producing overlaps. This policy places less emphasis on maintaining the group sizes in the remaining graph when collapsing subtrees than other policies.

See Also:

setGroupSizingPolicy(byte), Constant Field Values

Sample Graphs:

Adaptive cactus drawing without collapsed subtrees

Adaptive cactus drawing with a collapsed subtree

GROUP_SIZING_POLICY_STABLE

public static final byte GROUP_SIZING_POLICY_STABLE

Policy for sizing group nodes individually that optimizes for compact drawings which can be collapsed at any group without producing overlaps.

The size of group nodes is determined individually for each group so as to produce the most compact drawing while reserving enough space to collapse any subtree without producing overlaps or necessitating a change in the layout of the remaining graph.

See Also:

setGroupSizingPolicy(byte), Constant Field Values

Sample Graphs:

Stable cactus drawing without collapsed subtrees

Stable cactus drawing with a collapsed subtree

Constructor Detail

CactusGroupLayouter

public CactusGroupLayouter()

Creates a new CactusGroupLayouter instance with default settings.

Method Detail

isFromSketchModeEnabled

public boolean isFromSketchModeEnabled()

Returns whether or not the order of subtrees around a root may be changed by the algorithm.

Returns:

true if subtree order is fixed, false otherwise.

See Also:

setFromSketchModeEnabled(boolean)

setFromSketchModeEnabled

public void setFromSketchModeEnabled(boolean fromSketchModeEnabled)

Specifies whether or not the order of subtrees around a root may be changed by the algorithm.

Default Value:

The default value is false. The order given by the sketch is ignored.

Parameters:

fromSketchModeEnabled - true if subtree order is fixed, false otherwise.

See Also:

isFromSketchModeEnabled()

setNodeLabelSpacing

public void setNodeLabelSpacing(double nodeLabelSpacing)

Specifies the spacing used for node labels when integrated node labeling is enabled.

For ray-like label placement of leaf nodes, the spacing defines the distance between labels and the node they belong to (e.g. for ray-like label placement). For labels of inner nodes, the spacing specifies the distance between the labels (if there are multiple labels).

The spacing must have a non-negative value.

The spacing value has an effect only if integrated node labeling is enabled.

Default Value:

The default value is 4.0.

Parameters:

nodeLabelSpacing - the non-negative node label spacing

Throws:

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

See Also:

setIntegratedNodeLabelingEnabled(boolean)

Sample Graphs:

Node label spacing set to 2.0

Node label spacing set to 10.0

getNodeLabelSpacing

public double getNodeLabelSpacing()

Returns the spacing used for node labels when integrated node labeling is enabled.

For ray-like label placement of leaf nodes, the spacing defines the distance between labels and the node they belong to (e.g. for ray-like label placement). For labels of inner nodes, the spacing specifies the distance between the labels (if there are multiple labels).

The spacing must have a non-negative value.

The spacing value has an effect only if integrated node labeling is enabled.

Returns:

the non-negative node label spacing

See Also:

setIntegratedNodeLabelingEnabled(boolean), setNodeLabelSpacing(double)

setNodeComparator

public void setNodeComparator(java.util.Comparator comp)

Specifies a Comparator for children of the same parent node, by which the order of the subtrees around their parent is determined.

The algorithm uses the default Comparator in combination with a custom sorting procedure that symmetrically arranges the elements in ascending and then descending order around the largest element. If a custom Comparator is specified, the algorithm does however strictly adhere to the ascending order specified by it.

The specified Comparator is ignored if the from-sketch mode is enabled.

Default Value:

The default value is Comparator. Subtrees are ordered symmetrically by the number of leaves they contain.

Parameters:

comp - the Comparator to sort the children around their parent node

See Also:

getNodeComparator()

getNodeComparator

public java.util.Comparator getNodeComparator()

Returns a Comparator for children of the same parent node, by which the order of the subtrees around their parent is determined.

The algorithm uses the default Comparator in combination with a custom sorting procedure that symmetrically arranges the elements in ascending and then descending order around the largest element. If a custom Comparator is specified, the algorithm does however strictly adhere to the ascending order specified by it.

The specified Comparator is ignored if the from-sketch mode is enabled.

Default Value:

The default value is Comparator. Subtrees are ordered symmetrically by the number of leaves they contain.

Returns:

the Comparator to sort the children around their parent node

See Also:

setNodeComparator(Comparator)

isNodeLabelConsiderationEnabled

public boolean isNodeLabelConsiderationEnabled()

Returns whether the algorithm actively prevents node label overlaps when computing the layout.

Returns:

true if node label overlaps are prevented, false otherwise.

See Also:

setNodeLabelConsiderationEnabled(boolean)

setNodeLabelConsiderationEnabled

public void setNodeLabelConsiderationEnabled(boolean nodeLabelConsiderationEnabled)

Specifies whether the algorithm actively prevents node label overlaps when computing the layout.

Default Value:

The default value is true. Node labels are considered for automatic scaling.

Parameters:

nodeLabelConsiderationEnabled - true if node label overlaps should be prevented, false otherwise.

See Also:

isNodeLabelConsiderationEnabled()

Sample Graphs:

true

false

getNodeLabelingPolicy

public byte getNodeLabelingPolicy()

Returns the policy defining how node labels are placed by the integrated node labeling mechanism (for example, the desired label orientation).

Even though the integrated node labeling is enabled, there may sometimes be overlapping labels if there are nodes with multiple labels.

The policy only has an effect if integrated node labeling is enabled.

Returns:

one of the predefined node labeling policies

See Also:

setNodeLabelingPolicy(byte), setIntegratedNodeLabelingEnabled(boolean)

setNodeLabelingPolicy

public void setNodeLabelingPolicy(byte nodeLabelingPolicy)

Specifies the policy defining how node labels are placed by the integrated node labeling mechanism (for example, the desired label orientation).

Even though the integrated node labeling is enabled, there may sometimes be overlapping labels if there are nodes with multiple labels.

The policy only has an effect if integrated node labeling is enabled.

Default Value:

The default value is NodeLabelingPolicy.NODE_LABELING_MIXED

Parameters:

nodeLabelingPolicy - one of the predefined node labeling policies

Throws:

java.lang.IllegalArgumentException - if an unknown labeling policy is given

See Also:

getNodeLabelingPolicy(), setIntegratedNodeLabelingEnabled(boolean)

getGroupSizingPolicy

public byte getGroupSizingPolicy()

Returns the policy defining how group node sizes are determined.

Returns:

One of the predefined group sizing policies

See Also:

setGroupSizingPolicy(byte)

setGroupSizingPolicy

public void setGroupSizingPolicy(byte groupSizingPolicy)

Specifies the policy defining how group node sizes are determined.

Default Value:

The default value is GROUP_SIZING_POLICY_ADAPTIVE

Parameters:

groupSizingPolicy - One of the predefined group sizing policies

Throws:

java.lang.IllegalArgumentException - if an unknown group sizing policy is given

See Also:

getGroupSizingPolicy()

isIntegratedNodeLabelingEnabled

public boolean isIntegratedNodeLabelingEnabled()

Returns whether or not the layout algorithm automatically places node labels.

If enabled, this layout algorithm will calculate the positions for the node labels assuring that no overlaps occur.

Different labeling strategies may be selected using setNodeLabelingPolicy(byte).

Optimal label placement with integrated labeling can be achieved using FreeNodeLabelModel as the NodeLabelModel for the nodes.

Even though the integrated node labeling is enabled, there may sometimes be overlapping labels if there are nodes with multiple labels.

Returns:

true if integrated node labeling is enabled, false otherwise.

See Also:

setIntegratedNodeLabelingEnabled(boolean)

setIntegratedNodeLabelingEnabled

public void setIntegratedNodeLabelingEnabled(boolean integratedNodeLabelingEnabled)

Specifies whether or not the layout algorithm automatically places node labels.

If enabled, this layout algorithm will calculate the positions for the node labels assuring that no overlaps occur.

Different labeling strategies may be selected using setNodeLabelingPolicy(byte).

Optimal label placement with integrated labeling can be achieved using FreeNodeLabelModel as the NodeLabelModel for the nodes.

Even though the integrated node labeling is enabled, there may sometimes be overlapping labels if there are nodes with multiple labels.

Default Value:

The default value is true. Node labels are placed by this algorithm.

Parameters:

integratedNodeLabelingEnabled - true if integrated node labeling should be enabled, false otherwise.

See Also:

setNodeLabelingPolicy(byte), isIntegratedNodeLabelingEnabled()

getPreferredRootWedge

public double getPreferredRootWedge()

Returns the maximum angle on which the root's children can be distributed around its center. The angle is given in degrees.

Returns:

the angle on which the root's children are distributed.

See Also:

setPreferredRootWedge(double)

setPreferredRootWedge

public void setPreferredRootWedge(double preferredRootWedge)

Specifies the maximum angle on which the root's children can be distributed around its center. The angle is given in degrees.

Default Value:

The default value is 180.

Parameters:

preferredRootWedge - the angle on which the root's children are distributed.

Throws:

java.lang.IllegalArgumentException - if a negative angle, or an angle of more than 360 degrees is specified.

See Also:

getPreferredRootWedge()

Sample Graphs:

180 degrees

360 degrees

getEdgeBundling

public EdgeBundling getEdgeBundling()

Returns the EdgeBundling instance that defines the settings of the edge bundling feature.

The specified EdgeBundling defines global bundling properties. Settings for individual edges can be defined by assigning an EdgeBundleDescriptor to an edge using a DataProvider registered with key EdgeBundling.EDGE_BUNDLE_DESCRIPTOR_DPKEY.

To enable bundling for all edges, set a default bundle descriptor which has bundling enabled.

Returns:

the EdgeBundling instance defining the edge bundling setup

getDefaultNodeComparator

public java.util.Comparator getDefaultNodeComparator()

Returns the default policy for ordering subtree roots around their common parent. By default, subtrees are ordered by their size.

CactusGroupLayouter arranges nodes in a radial fashion around their parent node. The order is determined by a comparator specified with setNodeComparator(Comparator). By default all subtrees are arranged according to the number of leaves they contain, placing the largest subtrees in the center and smaller subtrees towards beginning and end of the order.

the default comparator has no effect if From Sketch mode is enabled.

Returns:

the default policy for ordering subtree roots. By default, subtrees are ordered by their area

See Also:

setNodeComparator(Comparator)

canLayoutCore

protected boolean canLayoutCore(LayoutGraph graph)

Accepts all graphs.

Specified by:

canLayoutCore in class CanonicMultiStageLayouter

Parameters:

graph - the input graph

Returns:

true for all graphs

doLayoutCore

protected void doLayoutCore(LayoutGraph graph)

Arranges the given grouped graph in the style of a cactus group layout.

Specified by:

doLayoutCore in class CanonicMultiStageLayouter

The given graph will not be copied during the layout process and the layout will be immediately applied to the given graph. This method is not side effect free in the sense that the order of edges or nodes in the input graph may change during the layout process.

Parameters:

graph - the grouped input graph