y.layout.tree
Class TreeMapLayouter

java.lang.Object
  y.layout.tree.TreeMapLayouter

All Implemented Interfaces:

Layouter

public class TreeMapLayouter
extends java.lang.Object
implements Layouter

This layout algorithm produces tree map layouts.

Layout Style

Tree maps are suitable to visualize hierarchical data structures. They use nested rectangles to do so, where the size of the rectangles encodes its weight. More generally, the area of a rectangle is proportional to a specific dimension of data associated to it.

Tree maps can, for example, be used to show a file structure on a hard disk, where the dimension of data is the size of the files/folders. There are many other use cases where the tree map can show the distribution of the dimension of data among the entities in a hierarchy.

A tree map with four different sub-groups - node labels define the weight; note that there are no edges in a tree map

Concept

TreeMapLayouter offers implementations of the well-known treemapping-algorithms Slice-and-Dice and Squarified. These tiling policies divide a rectangle with a given size into multiple sub-rectangles. Speaking in terms of graphs this means that nodes are placed in a nested fashion such that child nodes are placed inside the parent node.

Importantly, node sizes are changed by this layout algorithm to show the proportional weight of a node in the map. The weight is specified by registering a DataProvider with key NODE_WEIGHT_DPKEY with the input graph.

Features

The input can be specified in two ways:

1. As a hierarchic grouping structure that defines the nesting. Note that for group nodes, the specified insets are considered (see GroupingKeys.GROUP_NODE_INSETS_DPKEY). If the graph is a tree graph, then the grouping structure is ignored - see second input variant. To continue using the hierarchy information of the grouping structure on a tree graph, one can temporarily hide the tree edges before running the layout.
2. As a directed tree graph. The parent-child relation is directly taken from the graph's tree structure. If the graph also contains group nodes, the hierarchy relation induced by them is ignored. If necessary, an undirected tree can be (temporarily) directed prior to the layout run by using Trees.directTree(Graph, Node). The tree needs to be directed from the root (top-level hierarchy) to the children (lower-level hierarchies). Note that a forest graph is no valid input.

The offered tiling policies produce drawings with a quite different style. TILING_POLICY_SLICE_AND_DICE offers results that have a stable, clear ordering but the rectangles have a high aspect ratio. On the other hand, TILING_POLICY_SQUARIFIED tries to create rectangles close to a given aspect ratio - in consequence, the ordering of neighbor nodes might not be clearly predictable.

If the range of the provided weights is large, i.e., a large difference between the minimum and maximum weight value, then the resulting tree map might become really large, making readability bad. The reason is that the relative weight differences need to be considered while still satisfying the minimum node size for the nodes with low weight. A solution would be to scale/interpolate the weight values before running the layout.

Due to insets specified at parent nodes of different hierarchies and the inter-node padding defined by the spacing, nodes that have the same actual weight can get slightly different sizes - especially if they are on different hierarchy levels. This is necessary to satisfy the specified distances and insets. If exact same sizes throughout hierarchies is a requirement, set the spacing to 0 and do not specify insets for the group nodes that have children (if input is specified as grouping structure).

This layout algorithm does not consider NodeHalos assigned to nodes.

Nested Class Summary

static class

TreeMapLayouter.NodeWeightComparator A Comparator that compares two nodes with respect to their weight value defined via the DataProvider registered with NODE_WEIGHT_DPKEY.

Field Summary

static java.lang.Object	NODE_WEIGHT_DPKEY A DataProvider key for specifying the weight of the nodes.
static byte	TILING_POLICY_SLICE_AND_DICE A tiling policy that places the child nodes one after another inside the parent node.
static byte	TILING_POLICY_SQUARIFIED A tiling policy that uses the so-called 'squarify' algorithm.

Fields inherited from interface y.layout.Layouter

EDGE_ID_DPKEY, NODE_ID_DPKEY, NODE_TYPE_DPKEY, SELECTED_EDGES, SELECTED_NODES

Constructor Summary

TreeMapLayouter()

Method Summary

boolean	canLayout(LayoutGraph graph) Accepts all graphs.
void	doLayout(LayoutGraph graph) Arranges the given input graph as a tree map.
double	getAspectRatio() Returns the target aspect ratio of the squarified tiling policy.
YDimension	getMinimumNodeSize() Returns the minimum size (height and width) a node in the tree map must have.
java.util.Comparator	getNodeComparator() Returns the TreeMapLayouter.NodeWeightComparator that defines the order in which child nodes are placed inside their parent node.
YDimension	getPreferredSize() Returns the desired dimension of the root rectangle into which all nodes are placed.
double	getSpacing() Returns the spacing between nodes of the same hierarchy.
byte	getTilingPolicy() Returns the tiling policy that defines how the input is divided into sub-rectangles.
void	setAspectRatio(double aspectRatio) Specifies the target aspect ratio of the squarified tiling policy.
void	setMinimumNodeSize(YDimension minimumNodeSize) Specifies the minimum size (height and width) a node in the tree map must have.
void	setNodeComparator(java.util.Comparator comp) Specifies the TreeMapLayouter.NodeWeightComparator that defines the order in which child nodes are placed inside their parent node.
void	setPreferredSize(YDimension preferredSize) Specifies the desired dimension of the root rectangle into which all nodes are placed.
void	setSpacing(double spacing) Specifies the spacing between nodes of the same hierarchy.
void	setTilingPolicy(byte tilingPolicy) Specifies the tiling policy that defines how the input is divided into sub-rectangles.

Methods inherited from class java.lang.Object

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

Field Detail

NODE_WEIGHT_DPKEY

public static final java.lang.Object NODE_WEIGHT_DPKEY

A DataProvider key for specifying the weight of the nodes.

The weight of a node defines the area assigned to the node inside the available parent area with respect to the other child nodes. Child nodes with the same weight get the same area, they do not necessarily get equal width and height values.

All leaf nodes (nodes without further children, including empty group nodes) must have a weight greater than 0. Non-leaf nodes do not need to have a weight. They will basically get the sum of the weight of their children. If they have a weight on their own, some free space is generated inside the representative rectangle (i.e. the parent node is larger than the combined children).

Due to insets specified at parent nodes of different hierarchies and the inter-node padding defined by getSpacing(), nodes that have the same actual weight can get slightly different sizes.

TILING_POLICY_SQUARIFIED

public static final byte TILING_POLICY_SQUARIFIED

A tiling policy that uses the so-called 'squarify' algorithm.

It tries to generate nodes with a size close to a specified aspect ratio. This increases the readability of the tree maps.

The child ordering given by getNodeComparator() is considered but it is not as predictable as for TILING_POLICY_SLICE_AND_DICE. The order is not strictly from top to bottom or from left to right, but it might differ for different subsets of children. This is an inherent part of the squarified procedure.

The implementation follows the approach of Bruls et al. [Bruls, Mark; Huizing, Kees; van Wijk, Jarke J. (2000). 'Squarified treemaps'].

See Also:

setTilingPolicy(byte), setAspectRatio(double), Constant Field Values

Sample Graph:

Squarified tree map with single hierarchy level - labels define the weights

TILING_POLICY_SLICE_AND_DICE

public static final byte TILING_POLICY_SLICE_AND_DICE

A tiling policy that places the child nodes one after another inside the parent node.

Child nodes are either tiled vertically (slice), one on top of the other with the width equal to the parent's width. Or they are tiled horizontally (dice), one next to the other with the height equal to the parent's height. The tiling strategy alternates with the hierarchy levels, e.g., level 1 uses slice, level 2 uses dice, level 3 uses slice and so on.

This policy keeps the ordering of the children defined by getNodeComparator() stable. Either children are strictly ordered from left to right (dice) or from top to bottom (slice).

See Also:

setTilingPolicy(byte), Constant Field Values

Sample Graph:

Slice-and-Dice tree map with single hierarchy level - labels define the weights

Constructor Detail

TreeMapLayouter

public TreeMapLayouter()

Method Detail

getTilingPolicy

public byte getTilingPolicy()

Returns the tiling policy that defines how the input is divided into sub-rectangles.

Returns:

the tiling policy that is used

See Also:

setTilingPolicy(byte)

setTilingPolicy

public void setTilingPolicy(byte tilingPolicy)

Specifies the tiling policy that defines how the input is divided into sub-rectangles.

Default Value:

The default value is TILING_POLICY_SQUARIFIED

Parameters:

tilingPolicy - the tiling policy that should be used

Throws:

java.lang.IllegalArgumentException - if an unknown policy is specified

getNodeComparator

public java.util.Comparator getNodeComparator()

Returns the TreeMapLayouter.NodeWeightComparator that defines the order in which child nodes are placed inside their parent node.

Returns:

the TreeMapLayouter.NodeWeightComparator that defines the node order

See Also:

setNodeComparator(Comparator)

setNodeComparator

public void setNodeComparator(java.util.Comparator comp)

Specifies the TreeMapLayouter.NodeWeightComparator that defines the order in which child nodes are placed inside their parent node.

Default Value:

The default value is TreeMapLayouter.NodeWeightComparator. Nodes are ordered with respect to their weight (higher weight first).

Parameters:

comp - the TreeMapLayouter.NodeWeightComparator that defines the node order

Throws:

java.lang.IllegalArgumentException - if the given TreeMapLayouter.NodeWeightComparator is null

getMinimumNodeSize

public YDimension getMinimumNodeSize()

Returns the minimum size (height and width) a node in the tree map must have.

If the weight data induces that a node would get a width/height smaller than specified by the minimum size to fit into the preferred size, then the output size will be increased until all nodes fulfill the minimum size requirement. This scenario will mostly occur if the weights of nodes have a large range or if the specified preferred output size is small.

Returns:

the minimum node size

See Also:

setMinimumNodeSize(YDimension)

setMinimumNodeSize

public void setMinimumNodeSize(YDimension minimumNodeSize)

Specifies the minimum size (height and width) a node in the tree map must have.

If the weight data induces that a node would get a width/height smaller than specified by the minimum size to fit into the preferred size, then the output size will be increased until all nodes fulfill the minimum size requirement. This scenario will mostly occur if the weights of nodes have a large range or if the specified preferred output size is small.

Default Value:

The default value is YDimension. Minimum width and height are 10.0.

Parameters:

minimumNodeSize - the minimum node size

Throws:

java.lang.IllegalArgumentException - if the width or height of the given size is smaller than 5 or if the given minimum size is null

getPreferredSize

public YDimension getPreferredSize()

Returns the desired dimension of the root rectangle into which all nodes are placed.

If it is possible to arrange all nodes such that they fit into the preferred size, then the final result will exactly have this size. However, satisfying the specified spacing and minimum node size has higher priority. This means that the final output might become larger if necessary. On the other hand, it will never be smaller, even if it would be possible to generate a smaller result.

It is a good idea to specify a rather large size in the first place, except when having only a really small diagram. Otherwise, a valid size needs to be computed iteratively to satisfy minimum node width/height.

Returns:

the preferred size of the root rectangle

See Also:

setPreferredSize(YDimension)

setPreferredSize

public void setPreferredSize(YDimension preferredSize)

Specifies the desired dimension of the root rectangle into which all nodes are placed.

If it is possible to arrange all nodes such that they fit into the preferred size, then the final result will exactly have this size. However, satisfying the specified spacing and minimum node size has higher priority. This means that the final output might become larger if necessary. On the other hand, it will never be smaller, even if it would be possible to generate a smaller result.

It is a good idea to specify a rather large size in the first place, except when having only a really small diagram. Otherwise, a valid size needs to be computed iteratively to satisfy minimum node width/height.

Default Value:

The default value is YDimension. Preferred width and height are 600.

Parameters:

preferredSize - the preferred size of the root rectangle

Throws:

java.lang.IllegalArgumentException - if the given size is null or if its width/height value is less than or equal to zero

getAspectRatio

public double getAspectRatio()

Returns the target aspect ratio of the squarified tiling policy.

The aspect ratio must be greater than or equal to 1. A ratio of 1 means that the node rectangles should ideally be squares. The orientation of the rectangles does not matter. For example, a ratio of 2 means that rectangles with an aspect ratio of 1:2 or also 2:1 are desired.

This setting affects the ratio of a single node rectangle. To create a tree map with a certain overall aspect ratio, the preferred size can be specified accordingly.

This setting only has an effect if TILING_POLICY_SQUARIFIED is specified as tiling policy.

Returns:

the target aspect ratio for the squarified tiling policy

See Also:

setAspectRatio(double), TILING_POLICY_SQUARIFIED

setAspectRatio

public void setAspectRatio(double aspectRatio)

Specifies the target aspect ratio of the squarified tiling policy.

The aspect ratio must be greater than or equal to 1. A ratio of 1 means that the node rectangles should ideally be squares. The orientation of the rectangles does not matter. For example, a ratio of 2 means that rectangles with an aspect ratio of 1:2 or also 2:1 are desired.

This setting affects the ratio of a single node rectangle. To create a tree map with a certain overall aspect ratio, the preferred size can be specified accordingly.

This setting only has an effect if TILING_POLICY_SQUARIFIED is specified as tiling policy.

Default Value:

The default value is 1. The target is to draw square nodes.

Parameters:

aspectRatio - the target aspect ratio for the squarified tiling policy

Throws:

java.lang.IllegalArgumentException - if the given aspect ratio is smaller than 1

See Also:

TILING_POLICY_SQUARIFIED

getSpacing

public double getSpacing()

Returns the spacing between nodes of the same hierarchy.

This spacing enables to insert a padding between all nodes/rectangles on the same hierarchy. It is not inserted between a group node (border) and its children - use group node insets for that use case.

Returns:

the non-negative spacing between nodes

See Also:

setSpacing(double)

setSpacing

public void setSpacing(double spacing)

Specifies the spacing between nodes of the same hierarchy.

This spacing enables to insert a padding between all nodes/rectangles on the same hierarchy. It is not inserted between a group node (border) and its children - use group node insets for that use case.

Default Value:

The default value is 5.

Parameters:

spacing - the non-negative spacing between nodes

Throws:

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

Sample Graphs:

Spacing 5

Spacing 0

canLayout

public boolean canLayout(LayoutGraph graph)

Accepts all graphs.

To create meaningful tree maps, the graph should either contain hierarchical grouping information or be a tree graph that defines the hierarchy.

Specified by:

canLayout in interface Layouter

Parameters:

graph - the input graph

Returns:

true for all graphs

See Also:

Layouter.doLayout(LayoutGraph)

doLayout

public void doLayout(LayoutGraph graph)

Arranges the given input graph as a tree map.

To create meaningful tree maps, the graph should either contain hierarchical grouping information or be a tree graph that defines the hierarchy.

Specified by:

doLayout in interface Layouter

The given graph will not be copied during the layout process and the layout will be immediately applied to the given graph. Node sizes will be changed to create the tree map layout.

Parameters:

graph - the input graph

See Also:

Layouter.canLayout(LayoutGraph)