Incremental Hierarchical Layout

Class IncrementalHierarchicLayouter is a hierarchical layout provider that supports both incremental graph layout as well as "normal" hierarchical layout. It is a variant of the classic hierarchical layout providing a number of options similar to those of class HierarchicLayouter. Furthermore, this layout provider also supports incremental and "normal" hierarchical layout of hierarchically organized graphs.

Note that the non-incremental hierarchical layout which is provided by class IncrementalHierarchicLayouter is referred to as "layout from scratch."

Figure 5.31, “Sequence of incremental layouts” shows a sequence of incremental layouts generated by class IncrementalHierarchicalLayouter. Starting with a given graph, new graph elements are inserted optimally into the existing drawing from the step before. Note the emphasis for newly added elements.

Figure 5.31. Sequence of incremental layouts

Sequence of incremental layouts
Sequence of incremental layouts
Sequence of incremental layouts
Sequence of incremental layouts

The second major use case for incremental layout, the optimization of distinct parts from an existing hierarchical layout is shown in Figure 5.32, “Incremental layout used for optimization”. There, an entire subgraph is calculated anew and optimally placed into the given drawing.

Figure 5.32. Incremental layout used for optimization

Incremental layout used for optimization
Incremental layout used for optimization

Specifying Hints

Calculation of incremental hierarchical layouts heavily relies on the services of a so-called "hint factory." A hint factory is responsible for creating hint objects for both nodes and edges. These objects are then used by the incremental layout algorithm to optimally:

  • insert nodes into specified layers of the existing drawing
  • place nodes into suitable layers of the existing drawing
  • place nodes into suitable layers of the existing drawing with respect to their current coordinates (either both directions, or confined to only one direction)
  • route edges

When inserting nodes or routing edges according to their hint, nodes and edges from the graph that have no hint object associated preserve their original relative order both within layers as well as from layer to layer.

Class IncrementalHierarchicLayouter has a getter method that returns a hint factory object of type IncrementalHintsFactory. Code that shows the usage of a hint factory is presented in Example 5.20, “Getting and using a hint factory”.

Example 5.20. Getting and using a hint factory

// 'graph' is of type y.layout.LayoutGraph. 

// Create the incremental layout. 
IncrementalHierarchicLayouter ihl = new IncrementalHierarchicLayouter();
    
// Create a map to store the hints for the incremental layout mechanism. 
DataMap hintMap = Maps.createHashedDataMap();
graph.addDataProvider(IncrementalHierarchicLayouter.INCREMENTAL_HINTS_DPKEY, 
                      hintMap);

// Get the hint factory from the incremental layout algorithm. 
IncrementalHintsFactory hintsFactory = ihl.createIncrementalHintsFactory();

// Get a NodeList with those nodes that should be processed using incremental 
// layout semantics. 
NodeList incNL = getIncrementalNodeList();

// Associate the incremental nodes with hints from the hint factory. 
for (NodeCursor nc = incNL.nodes(); nc.ok(); nc.next()) {
  hintMap.set(nc.node(), hintsFactory.createLayerIncrementallyHint(nc.node()));
}

// Now, set incremental mode and invoke layout calculation. 
ihl.setLayoutMode(IncrementalHierarchicLayouter.LAYOUT_MODE_INCREMENTAL);
new BufferedLayouter(ihl).calcLayout(graph);

Supplemental Layout Data

In addition to the data provider keys known by class HierarchicLayouter (listed in Table 5.17, “Data provider look-up keys”), class IncrementalHierarchicLayouter knows further 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 5.19, “Data provider look-up keys” lists all look-up keys for IncrementalHierarchicLayouter.

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

Table 5.19. Data provider look-up keys

Key Element Type Value Type Description
INCREMENTAL_HINTS_DPKEY Node, Edge Object For each incrementally added node or edge a hint object that marks the respective graph element to be inserted into the hierarchical layout in an optimal manner. The hint object is created by a hint factory, like, e.g., the hint factory that is returned by method createIncrementalHintsFactory().
LAYER_VALUE_HOLDER_DPKEY Node IntValueHolder For each node an IntValueHolder implementation that is used by the layout algorithm to return the index of the actual layer a node has been assigned to.
NODE_LAYOUT_DESCRIPTOR_DPKEY Node NodeLayoutDescriptor For each node a NodeLayoutDescriptor object that configures a number of node-related options.
EDGE_LAYOUT_DESCRIPTOR_DPKEY Edge EdgeLayoutDescriptor For each edge an EdgeLayoutDescriptor object that configures a number of edge-related options.
SWIMLANE_DESCRIPTOR_DPKEY Node SwimLaneDescriptor For each node a SwimLaneDescriptor object that configures a number of swimlane-related options.
SOURCE_GROUPID_KEY Edge Object For each edge an arbitrary Object indicating the group its source end is affiliated with.
TARGET_GROUPID_KEY Edge Object For each edge an arbitrary Object indicating the group its target end is affiliated with.
SOURCE_PORT_CONSTRAINT_KEY Edge PortConstraint For each edge a PortConstraint object encoding its source end's port constraint.
TARGET_PORT_CONSTRAINT_KEY Edge PortConstraint For each edge a PortConstraint object encoding its target end's port constraint.
NODE_DP_KEY Node PortCandidateSet For each node a PortCandidateSet object encoding the set of allowed anchor locations for edges.
SOURCE_PCLIST_DPKEY Edge Collection For each edge a java.util.Collection of PortCandidate objects that encode the subset of desired anchor locations where the source port likes to connect to.
TARGET_PCLIST_DPKEY Edge Collection For each edge a java.util.Collection of PortCandidate objects that encode the subset of desired anchor locations where the target port likes to connect to.
GROUP_DPKEY Node boolean For each node a boolean value indicating whether it is a group node or not.
NODE_ID_DPKEY Node Object For each node an Object that serves as a unique ID.
PARENT_NODE_ID_DPKEY Node Object For each node an Object indicating the group node it belongs to. The Object matches the unique ID of a group node that is in the same graph.

Important

The data provider that is registered using the look-up key INCREMENTAL_HINTS_DPKEY holds data for both types of graph elements. Hence, neither NodeMap nor EdgeMap implementations can be used as the basis for this data provider.

An alternative basis for the data provider would be, e.g., a DataMap as returned by method createHashedDataMap(), or any custom DataProvider implementation that is not restricted to one type of graph element.

Setup of a graph's hierarchical organization and using the grouping keys (GROUP_DPKEY, NODE_ID_DPKEY, and PARENT_NODE_ID_DPKEY) is described in detail in the section called “Setup for Layout”.

Layout Options

Unlike the classic hierarchical layout algorithm this specialized layout algorithm offers only few options that are directly accessible for configuration.

Layout Mode (see API)

Determines the general layout mode.

When the layout is calculated incrementally, a data provider that holds so-called hint objects for each graph element that should be processed using incremental semantics is looked up. The data provider is expected to be registered with the graph using key INCREMENTAL_HINTS_DPKEY.

Incrementally
Sets the layout algorithm to incremental mode, i.e., elements that are marked for incremental processing will be inserted into the already calculated layout of the remaining part of the graph in an optimal manner.
From Scratch
Sets the layout algorithm to recompute the entire layout from scratch. This is similar to the services provided by class HierarchicLayouter, i.e., a "normal" layout calculation is started. Layout from scratch is the default setting for the "Layout Mode" feature.

Node Layout Descriptor (see API)

Sets the default NodeLayoutDescriptor instance that is used for all nodes that have no individual layout descriptor associated. Some of the layout and drawing options that can be set for a node by means of this descriptor are listed in the section called “Related Classes”.

To specify individual descriptors for nodes, a data provider holding such supplemental layout data can be bound to the graph. The data provider is expected to be registered with the graph using key NODE_LAYOUT_DESCRIPTOR_DPKEY. Note that in the absence of an individual descriptor the default NodeLayoutDescriptor instance will be used.

Edge Layout Descriptor (see API)

Sets the default EdgeLayoutDescriptor instance that is used for all edges that have no individual layout descriptor associated. Some of the layout and drawing options that can be set for an edge by means of this descriptor are listed in the section called “Related Classes”.

To specify individual descriptors for edges, a data provider holding such supplemental layout data can be bound to the graph. The data provider is expected to be registered with the graph using key EDGE_LAYOUT_DESCRIPTOR_DPKEY. Note that in the absence of an individual descriptor the default EdgeLayoutDescriptor instance will be used.

Drawing Style Options

Minimum Layer Distance (see API)

Determines the minimal distance between adjacent layers.

Node To Node Distance (see API)

Determines the minimal distance between two adjacent nodes that reside in the same layer.

Edge To Edge Distance (see API)

Determines the distance between two adjacent edge segments in one layer.

Node To Edge Distance (see API)

Determines the minimal distance between an edge and an adjacent node in one layer.

Advanced Layout Features

Class IncrementalHierarchicLayouter basically supports the same or very similar functionality (including knowledge and usage of corresponding data provider keys) as the classic hierarchical group layout algorithm, respectively the classic hierarchical layout algorithm, including:

  • port constraints
  • edge/port grouping (bus-style edge routing)
  • hierarchically organized graphs

All of these advanced features are observed as soon as there are data providers registered with a graph using appropriate look-up keys.

Figure 5.33, “Advanced Layout Features” shows examples for port constraints and edge/port grouping (bus-style edge routing). Both features are described in the section called “Advanced Layout Features”.

Figure 5.33. Advanced Layout Features

Advanced Layout Features
Advanced Layout Features
Strong port constraints. Multiple different edge group configurations resulting in bus style edge routings.

In addition to the support provided for port constraints, incremental hierarchical layout also supports the concept of port candidates. See the section called “Port Candidates” for a detailed description of that concept.

Layout of Hierarchically Organized Graphs

IncrementalHierarchicLayouter supports different layer assignment policies for graphs with grouped nodes. The layering for both incremental as well as "normal" layout can be determined in either of two ways:

  • flat, i.e., nodes are assigned to layers regardless of nesting level within group nodes
  • recursively, i.e., layer assignment is computed from the most nested group up to the nodes in the root graph

Figure 5.34, “Flat vs. recursive layer assignment” compares the layer assignment policies. When layer assignment is done "flat," the group nodes of a graph and their adjacent edges are ignored. In particular, this means that the layering of grouped nodes can be influenced by nodes outside of the group node. In constrast, when using recursive layer assignment, grouped nodes are processed without interference from nodes outside of their group node.

Figure 5.34. Flat vs. recursive layer assignment

Flat vs. recursive layer assignment
Flat vs. recursive layer assignment
Flat vs. recursive layer assignment
"Flat" layer assignment policy where group nodes and their adjacent edges are ignored. Recursive layer assignment policy. Recursive layer assignment policy with compaction enabled.

Recursive processing of the grouped nodes is the default behavior. Example 5.21, “Setting up "flat" layer assignment” shows how to set up "flat" layer assignment with IncrementalHierarchicLayouter.

Example 5.21. Setting up "flat" layer assignment

// Set up IHL for hierarchically organized graphs.
IncrementalHierarchicLayouter ihl = new IncrementalHierarchicLayouter();
ihl.setRecursiveGroupLayeringEnabled(false);

Recursive layer assignment optionally uses a compaction step where empty layers next to group nodes are filled with nodes from layers below these group nodes. When compaction is disabled, an alignment policy is used to specify where "ordinary" nodes that are in a layer with group nodes are placed relative to these group nodes. API Excerpt 5.9, “Setter methods for recursive layering options” lists the methods for configuring these options.

API Excerpt 5.9. Setter methods for recursive layering options

// Layer compaction.
void setGroupCompactionEnabled(boolean groupCompactionEnabled)

// Group node-relative alignment policy.
void setGroupAlignmentPolicy(byte groupAlignmentPolicy)

IncrementalHierarchicLayouter's support for hierarchically organized graphs currently does not support the following features for edge ends that directly connect to group nodes: port constraints, port candidates, and edge/port grouping (bus-style edge routing). Also, swimlane layout in conjunction with hierarchically organized graphs is not supported yet.

Please see also the section called “Layout of Hierarchically Organized Graphs” below.

Integrated Labeling

Integrated labeling can be enabled or disabled using the methods from API Excerpt 5.10, “Method to enable/disable integrated labeling”.

API Excerpt 5.10. Method to enable/disable integrated labeling

// Getter and setter for integrated labeling. 
boolean isIntegratedEdgeLabelingEnabled()

void setIntegratedEdgeLabelingEnabled(boolean enabled)

Swimlane Layout

IncrementalHierarchicLayouter provides support for so-called "swimlane" layout. This type of layout uses the notion of adjacent lanes into which nodes are placed. The lanes are oriented with the general layout direction, i.e., perpendicular to the layers of the hierarchical layout, and each of the nodes of the graph is specifically assigned to a single lane.

Figure 5.35, “Swimlanes” shows the result of a swimlane layout calculated by IncrementalHierarchicLayouter where the layout direction is from top to bottom. The lanes of the swimlane layout are indicated by vertical lines. Nodes are placed into a lane according to the label text.

Figure 5.35. Swimlanes

Swimlane layout

Assigning the nodes of a graph to specific swimlanes is achieved with the help of class SwimLaneDescriptor. Each node is associated with an object of this type by means of a node map, which is then registered as a data provider with the graph using the SWIMLANE_DESCRIPTOR_DPKEY look-up key. The SwimLaneDescriptor object is given a java.lang.Comparable object at creation time that is used to determine the order of the swimlanes. This general setup for swimlane layout using IncrementalHierarchicLayouter is outlined in Example 5.22, “Setting up swimlane layout”.

Example 5.22. Setting up swimlane layout

public NodeMap setupSwimlaneInformation(Graph graph) {
  NodeMap swimLaneMap = graph.createNodeMap();
  graph.addDataProvider(
    IncrementalHierarchicLayouter.SWIMLANE_DESCRIPTOR_DPKEY, swimLaneMap);
  
  for (NodeCursor nc = graph.nodes(); nc.ok(); nc.next()) {
    SwimLaneDescriptor sld = 
      new SwimLaneDescriptor(graph.getLabelText(nc.node()));
    
    // More swimlane-specific configuration here...
    
    swimLaneMap.set(nc.node(), sld);
  }
  return swimLaneMap;
}

Swimlane layout is demonstrated in the tutorial demo applications SwimLaneLayoutWithoutAView.java and SimpleSwimLaneLayouterDemo.java.

Returning Layer Indices

Class IncrementalHierarchicLayouter will return the layer index for every node, when the graph has a data provider registered with it that can be looked up using the key LAYER_VALUE_HOLDER_DPKEY. The data provider is expected to hold IntValueHolder objects, which are retrieved and filled with the layer indices after layout calculation. Class IntValueHolderAdapter can be used as a convenient means to appropriately wrap a NodeMap for that task.

Related Classes

Classes NodeLayoutDescriptor and EdgeLayoutDescriptor can be used to configure the layout result of an invocation of class IncrementalHierarchicLayouter. If set individually for single graph elements by means of a data provider, the layout result can be customized in the most detailed way. For example, the following options can be set for nodes and edges, respectively:

  • relative alignment of nodes within their layer
  • preferred minimum distance from obstacles (both nodes and edges)
  • orthogonal vs. poly-line routing for edges
  • minimum length of first and last edge segment, respectively

API Excerpt 5.11, “Setter methods from class NodeLayoutDescriptor” lists some of the methods from class NodeLayoutDescriptor that can be used for node configuration.

API Excerpt 5.11. Setter methods from class NodeLayoutDescriptor

// Setter methods from NodeLayoutDescriptor. 
void setLayerAlignment(double alignment)

void setMinimumDistance(double distance)
void setMinimumLayerHeight(double height)

void setNodeLabelMode(byte mode)

API Excerpt 5.12, “Setter methods from class EdgeLayoutDescriptor” lists some of the setter methods from class EdgeLayoutDescriptor that can be used for edge configuration.

API Excerpt 5.12. Setter methods from class EdgeLayoutDescriptor

// Setter methods from EdgeLayoutDescriptor. 
void setMinimumDistance(double distance)

void setMinimumFirstSegmentLength(double length)
void setMinimumLastSegmentLength(double length)
void setMinimumLength(double length)
void setMinimumSlope(double slope)

void setOrthogonallyRouted(boolean orthogonal)

Layout of Hierarchically Organized Graphs

Due to the nature of class IncrementalHierarchicLayouter's layout capabilities, which cover both non-incremental as well as incremental layout, the layout of a graph with grouped nodes will most likely differ from what class HierarchicGroupLayouter, which supports non-incremental hierarchical layout of hierarchically organized graphs only, yields.

Figure 5.36, “Hierarchical layout of grouped nodes: HierarchicGroupLayouter vs. IncrementalHierarchicLayouter” compares the hierarchical layout of a graph with grouped nodes as calculated by class HierarchicGroupLayouter with the outcome of a from-scratch layout by class IncrementalHierarchicLayouter for the same graph (using "flat" layer assignment policy). The most notable difference can be seen with the group nodes which are always placed into a single distinct layer by HierarchicGroupLayouter whereas they can span multiple layers when placed by IncrementalHierarchicLayouter.

Figure 5.36. Hierarchical layout of grouped nodes: HierarchicGroupLayouter vs. IncrementalHierarchicLayouter

Hierarchical layout of grouped nodes: HierarchicGroupLayouter vs. IncrementalHierarchicLayouter
Hierarchical layout of grouped nodes: HierarchicGroupLayouter vs. IncrementalHierarchicLayouter
Hierarchical layout of grouped nodes calculated by class HierarchicGroupLayouter. Hierarchical "from-scratch" layout of grouped nodes calculated by class IncrementalHierarchicLayouter.

IncrementalHierarchicLayouter's support for incrementally calculating layouts of hierarchically organized graphs enables smooth transitions when realizing collapsing and expanding of group nodes. Figure 5.37, “Incremental hierarchical layout when group nodes are collapsed and expanded” presents the results of both these operations. The resulting folder node and group node, respectively, is incrementally inserted into the existing layout.

Figure 5.37. Incremental hierarchical layout when group nodes are collapsed and expanded

Incremental hierarchical layout when group nodes are collapsed and expanded
Incremental hierarchical layout when group nodes are collapsed and expanded
Incremental hierarchical layout when group nodes are collapsed and expanded
Original hierarchical layout with group nodes. Collapsed group node incrementally inserted into the layout. Previously collapsed group node expanded and incrementally inserted.

Incremental hierarchical layout of graphs with grouped nodes is demonstrated in the tutorial demo application IncrementalHierarchicGroupDemo.java.

Tutorial Demo Code

Using both the incremental as well as the classic layout functionality of class IncrementalHierarchicLayouter is presented in detail in the following tutorial demo applications:

Configuration of the incremental hierarchical layout algorithm can also be observed in IncrementalHierarchicLayoutModule.java.