Generic Tree Layout

Class GenericTreeLayouter defines a generic basis for tree layout that supports a multitude of different styles and arrangements. Major aspects of layout calculation can be customized for an invocation both globally for the entire tree, but also individually per subtree. This powerful scheme allows entirely different layout styles to be applied to the subtrees of a given tree.

Supplemental Layout Data

Class GenericTreeLayouter knows a number of data provider keys which are used to retrieve supplemental layout data for a graph's elements. The data is bound to the graph by means of a data provider, which is registered using a given look-up key. Table 10.58, “Data provider look-up keys” lists all look-up keys for GenericTreeLayouter.

Binding supplemental layout data to a graph is described in the section called “Providing Supplemental Layout Data”.

Table 10.58. Data provider look-up keys

Key Element Type Value Type Description
ChildComparatorDpKey node IComparer For each node an IComparer object that is used to sort the outgoing edges.
EdgeLabelLayoutDpKey edge LabelLayoutData[] For each edge an array of LabelLayoutData objects that encode size and preferred placement for all labels of the edge.
NodeLabelLayoutDpKey node LabelLayoutData[] For each node an array of LabelLayoutData objects that encode size and preferred placement for all labels of the node.
NodePlacerDpKey node INodePlacer For each node a INodePlacer implementation that places the node itself and its subtree.
PortAssignmentDpKey node IPortAssignment For each node a IPortAssignment implementation that assigns ports to the edges of a node.
SourcePortConstraintDpKey edge PortConstraint For each edge a PortConstraint object encoding its source end's port constraint.
TargetPortConstraintDpKey edge PortConstraint For each edge a PortConstraint object encoding its target end's port constraint.
GroupDpKey node bool For each node a boolean value indicating whether it is a group node or not.
GroupNodeInsetsDpKey node Insets For each group node an Insets object that encodes the group node's insets.
NodeHaloDpKey node NodeHalo A NodeHalo object that specifies the halo sizes at each side of a node.

Layout Options

GenericTreeLayouter delegates major aspects of layout calculation to implementations for interfaces INodePlacer and IPortAssignment:

  • INodePlacer is responsible for recursively arranging a subtree's root node together with its children (starting at the leaf nodes of a tree),
  • IPortAssignment encapsulates edge port assignment for a node's edges.

Classes DefaultNodePlacer and DefaultPortAssignment are used as the default implementations for INodePlacer and IPortAssignment, respectively.

Both INodePlacer as well as IPortAssignment implementations can be registered with GenericTreeLayouter to handle all nodes, i.e., act globally on the entire tree, or to handle only a specific root node, i.e., act locally on a subtree. To specify the node placer or port assignment for each subtree individually, data providers holding such supplemental layout data must be bound to the graph. The data providers are expected to be registered with the graph using keys NodePlacerDpKey and PortAssignmentDpKey, respectively.

Note that in the absence of an individual node placer or port assignment implementation the respective default implementation will be used for a given node. The following properties can be used to register default node placer and port assignment implementations:

INodePlacer DefaultNodePlacer { get; set; }
Description Determines the globally used node placer implementation.
IPortAssignment DefaultPortAssignment { get; set; }
Description Determines the globally used port assignment implementation.

Node Placer Implementations

In addition to class DefaultNodePlacer, namespace yWorks.yFiles.Layout.Tree contains further predefined node placer implementations that provide a variety of subtree arrangement schemes. Their common superclass, abstract class AbstractRotatableNodePlacer, enables these node placers to transparently deal with child nodes that are actually rotated subtrees. Figure 10.69, “Node placer hierarchy” depicts the node placer class hierarchy.

Figure 10.69. Node placer hierarchy

Node placer hierarchy.

Table 10.59, “Node placer implementations” lists the predefined node placer implementations that extend abstract class AbstractNodePlacer.

Table 10.59. Node placer implementations

Classname Description
ARNodePlacer All subtrees are placed such that a given aspect ratio for the entire tree is obeyed.
DefaultNodePlacer Child nodes are placed horizontally aligned below their root node. The bus-like routing for all edges to the child nodes extends horizontally.

Table 10.60, “Node placer implementations that support rotation” lists predefined node placer implementations that support rotated subtrees. Note that the given descriptions assume a "canonic subtree orientation," where child nodes are placed (more or less) below their root node.

Table 10.60. Node placer implementations that support rotation

Classname Description
AssistantPlacer Applies a composite placement scheme where two kinds of nodes are differentiated; see below for a more detailed description.
BusPlacer Child nodes are placed evenly distributed to the left and right of their root node and also in a second line below the root node. The nodes within each line are horizontally aligned. The bus-like routing for all edges to the child nodes extends horizontally.
DelegatingNodePlacer Applies a composite placement scheme where two node placers are used to each arrange one half of the child nodes.
DoubleLinePlacer Child nodes are placed staggered in two lines below their root node, each line containing one half of the nodes. The nodes within each line are horizontally aligned. The bus-like routing for all edges to the child nodes extends horizontally.
FreePlacer Child nodes can be placed anywhere, their coordinates are not modified. The bus-like routing for all edges to the child nodes extends horizontally.
LayeredNodePlacer Subtrees can be placed such that child nodes from the same layer (i.e., nodes having the same BFS distance to the tree's root node) are aligned.
LeftRightPlacer Child nodes are placed below their root node to the left and right of the downward extending bus-like routing for all edges to the child nodes.
SimpleNodePlacer Child nodes are placed horizontally aligned below their root node. The bus-like routing for all edges to the child nodes extends horizontally.

AbstractRotatableNodePlacer provides support for eight different subtree orientation schemes which are expressed using suitable modification matrices of type Matrix. Figure 10.70, “Supported subtree orientations” shows all orientations beginning with the so-called "canonic subtree orientation." Note that the rotations provided by nested class AbstractRotatableNodePlacer.Matrix are using mathematical rotation sense, i.e., they are counter-clockwise.

Figure 10.70. Supported subtree orientations

Supported subtree orientations
Supported subtree orientations
Supported subtree orientations
Supported subtree orientations
Default orientation (a.k.a. canonic subtree orientation): Default 90 degree: Rot90 90 degree, mirrored vertically: MirVertRot90 Mirrored vertically: MirVert
Supported subtree orientations
Supported subtree orientations
Supported subtree orientations
Supported subtree orientations
Mirrored horizontally: MirHor 90 degree, mirrored horizontally: MirHorRot90 270 degree: Rot270 180 degree: Rot180

A concrete subclass of AbstractRotatableNodePlacer is given the modification matrix that describes the desired subtree orientation at initialization time. API Excerpt 10.1, “Matrix-related configuration support provided by class AbstractRotatableNodePlacer” lists the methods/constructors that provide matrix-related configuration support.

API Excerpt 10.1. Matrix-related configuration support provided by class AbstractRotatableNodePlacer

// Constructor.
public AbstractRotatableNodePlacer(Matrix modificationMatrix)

// Getter for the current modification matrix.
Matrix ModificationMatrix { get; }

Figure 10.71, “Subtree arrangement with NodePlacer implementations” shows arrangements of an example (sub)tree (in canonic subtree orientation) using different node placer implementations. Note the (sub)tree's emphasized root node.

Figure 10.71. Subtree arrangement with NodePlacer implementations

Subtree arrangement with NodePlacer implementations
Subtree arrangement with NodePlacer implementations
Subtree arrangement with NodePlacer implementations
SimpleNodePlacer LeftRightPlacer FreePlacer
 
Subtree arrangement with NodePlacer implementations
Subtree arrangement with NodePlacer implementations
  DoubleLinePlacer BusPlacer

Class AssistantPlacer uses a data provider that holds boolean values which denote whether a node is a so-called "assistant" or not. The data provider is bound to the tree using the look-up key AssistantDpKey. Assistants are placed using LeftRightPlacer, non-assistants are placed using another node placer which can be configured using a setter method. Figure 10.72, “Subtree arrangement provided by AssistentPlacer” depicts the supported arrangements for the so-called non-assistant nodes.

Figure 10.72. Subtree arrangement provided by AssistentPlacer

Subtree arrangement provided by AssistentPlacer
Subtree arrangement provided by AssistentPlacer
Using SimpleNodePlacer for non-assistants. Using DoubleLinePlacer for non-assistants.

Advanced Layout Concepts

Integrated Labeling

Besides the generic labeling support as described in the section called “Generic Labeling”, which is available with all yFiles layout algorithms, generic tree layout additionally features integrated labeling.

Integrated labeling is available for both node labels and edge labels. They are taken into consideration when determining the shape of a subtree. With this strategy it is guaranteed that no label will overlap other objects in the diagram. The following properties can be used to enable integrated labeling:

bool IntegratedEdgeLabeling { get; set; }
bool IntegratedNodeLabeling { get; set; }
Description Enables/disables integrated edge labeling and node labeling, respectively.

See also the section called “Integrated Labeling”.

Tip

Optimal label placement with integrated labeling can be achieved using FreeEdgeLabelModel as the label model for the edges. As explained in the section called “Label Models”, this edge label model is ideally suited in combination with integrated labeling and yields the best match for a label location that is computed by GenericTreeLayouter.

Port Constraints

Obeying port constraints for edges is part of the responsibilities of a node placer implementation. A node placer determines:

  • the source ports of all edges that connect a subtree's root node to its child nodes
  • the target port of the edge that connects to the subtree's root node

The predefined node placer implementations from the yWorks.yFiles.Layout.Tree namespace obey both types of port constraints, weak and strong. The port constraints are retrieved from data providers that are bound to the graph using the look-up keys SourcePortConstraintDpKey and TargetPortConstraintDpKey, respectively.

By means of interface IPortAssignment the ports of all edges adjacent to a given tree node can be assigned. To this end, method AssignPorts is called immediately before a subtree's node placer is invoked. Obviously, assigning edge ports at a tree node is confined to the target port of the incoming edge from the parent node, and the source ports of all outgoing edges to child nodes.

Node Halos

GenericTreeLayouter by default supports node halos as soon as they are declared using the data provider key NodeHaloDpKey. During layout calculation, it takes any specified additional paddings around nodes into consideration and keeps the areas clear of other graph elements. The labels of a node and its adjacent edge segments are not affected and can still be placed inside or cross the node's halo.

Incremental Layout

GenericTreeLayouter can be used in combination with a System.Collections.IComparer implementation that allows to dynamically determine the sequence of child nodes in a subtree. Supplied with a root node's outgoing tree edges, the comparer decides on their precedence. Based on this scheme, the comparer that is conveniently returned by class DefaultNodePlacer provides support for incrementally inserting new child nodes at optimal positions with respect to already arranged child nodes.

Comparers can be registered both to handle all nodes, i.e., act globally on the entire tree, or to handle only a specific root node, i.e., act locally on a subtree. The following property can be used to configure the default comparer for an entire tree:

IComparer DefaultChildComparator { get; set; }
Description Sets the default IComparer implementation for a tree.

To specify comparers individually for each subtree, a data provider holding such supplemental layout data must be bound to the graph. The data provider is expected to be registered with the graph using key ChildComparatorDpKey.

Class DefaultNodePlacer provides a suitable default comparer that can conveniently be used to support incremental tree layout scenarios with subtrees. The comparer enables dynamic rearrangement of all child nodes in a given subtree according to their relative coordinates. Example 10.31, “Setup for incremental layout with GenericTreeLayouter” demonstrates the setup of GenericTreeLayouter using the default node placer and port assignment implementations, and additionally registering the default comparer from class DefaultNodePlacer.

Example 10.31. Setup for incremental layout with GenericTreeLayouter

// Create a GenericTreeLayouter object that uses default node placer and 
// port assignment implementations, i.e., classes DefaultNodePlacer and 
// DefaultPortAssignment, respectively.
GenericTreeLayouter gtl = new GenericTreeLayouter();
// Register the comparer returned by class DefaultNodePlacer to take care of 
// the sequences of child nodes in each subtree.
gtl.DefaultChildComparator =
    ((DefaultNodePlacer)gtl.DefaultNodePlacer).CreateComparator();

Grouping Support

By default, GenericTreeLayouter supports layout of tree structures where entire subtrees are contained in group nodes. Both position and dimension of group nodes will be calculated by the algorithm. The GroupingSupported property can be used to control this functionality.

Additional size requirements of group nodes (e.g., special insets or space for custom labels) can be specified for each group node separately by means of a data provider that provides Insets objects. The data provider must be registered with the input graph using the key GroupNodeInsetsDpKey.

Tutorial Demo Code

The GenericTreeDemo tutorial demo application provides an extensive presentation of the powerful features that are offered by GenericTreeLayouter. The effects of the predefined node placer and port assignment implementations can be interactively explored and configuration aspects can be seen in the code. The demo also shows the incremental tree layout capabilities of GenericTreeLayouter.