Describes the Hierarchical Layout algorithm.

HL samples

Describes the Hierarchical Layout algorithm (class IlvHierarchicalLayout from the package ilog.views.graphlayout.hierarchical).

The following sample drawings are produced with the Hierarchical Layout:

What types of graphs suit the HL?

Any type of graph, as follows:

Application domains for the HL

Application domains for the Hierarchical Layout include:

Features

Limitations

A brief description of the HL algorithm

This algorithm works in four steps:

Step 1: Leveling

The nodes are partitioned into groups. Each group of nodes forms a level. The objective is to group the nodes in such a way that the links always point from a level with smaller index to a level with larger index.

Step 2: Crossing reduction

The nodes are sorted within each level. The algorithm tries to keep the number of link crossings small when, for each level, the nodes are placed in this order on a line (see Level and position indexes). This ordering results in the relative position index of each node within its level.

Step 3: Node positioning

From the level indexes and position indexes, balanced coordinates for the nodes are calculated. For instance, for a layout where the link flow is from top to bottom, the nodes are placed along horizontal lines such that all nodes belonging to the same level have (approximately) the same y-coordinate. The nodes of a level with a smaller index have a smaller y-coordinate than the nodes of a level with a higher index. Within a level, the nodes with a smaller position index have a smaller x-coordinate than the nodes with a higher position index.

Step 4: Link routing

The shapes of the links are calculated such that the links bypass the nodes at the level lines. In many cases, it requires that a bend point is created whenever a link needs to cross a level line. In a top-to-bottom layout, these bend points have the same y-coordinate as the level line they cross. (These bend points also obtain a position index).

Level and position indexes shows how the Hierarchical Layout algorithm uses the level and position indexes to draw the graph.

You can set parameters for the steps of the layout algorithm in several ways. For instance, you can specify the level index that the algorithm must choose for a node in Step 1 or the relative node position within the level in Step 2. You can also specify the justification of the nodes within a level and the style of the link shapes.

Example of HL

The following example is a specification that uses the Hierarchical Layout algorithm. Since the Hierarchical Layout places nodes and links, it is usually not necessary to specify an additional link layout in CSS.

The specification can be loaded as a style file into an application that uses the IlvDiagrammer class (see Graph Layout in Rogue Wave JViews Diagrammer).

In some situations, a separate link layout renderer may be required:

In these cases, it is recommended to use the “hierarchical link layout”. The hierarchical link layout is not a separate layout algorithm. It is merely the feature of the link layout renderer to reuse the Hierarchical Layout as a link layout. The following CSS sample specifies the Hierarchical Layout algorithm as node and link layout renderer:

It is also possible to use the standard link layout (class IlvLinkLayout ) in the link layout renderer (the hierarchical parameter is set to "false" ). However in this case, the link layout determines the shapes of the links. The explanations pertaining to the shape of the links in Hierarchical Layout are valid only if the link layout is disabled.

In Java™, below is a code sample that uses the IlvHierarchicalLayout class. This code sample shows how to perform a Hierarchical Layout on a grapher directly without using a diagram component or any style sheet:

Overview of generic features

The IlvHierarchicalLayout class supports the following generic features defined in the IlvGraphLayout class (see Base class parameters and features):

The following paragraphs describe the particular way in which these parameters are used by this subclass.

Allowed time (HL)

The layout algorithm stops if the allowed time setting has elapsed. (For a description of this layout parameter in the IlvGraphLayout class, see Allowed time.) If the layout stops early because the allowed time has elapsed, the nodes and links are not moved from their positions before the layout call and the result code in the layout report is IlvGraphLayoutReport.STOPPED_AND_INVALID.

Layout of connected components (HL)

The layout algorithm can use the generic mechanism to lay out connected components. (For more information about this mechanism, see Layout of connected components.) When using this mechanism, each component is laid out in its own individual level structure. Nodes of the first level of one component can be placed at a different position than nodes of the first level of another component.

The generic mechanism to lay out connected components is, however, disabled by default. In this case, the layout algorithm can still handle disconnected graphs. It merges all components into a global level structure.

Link clipping (HL)

The layout algorithm can use a link clip interface to clip the end points of a link. (See Link clipping.)

This is useful if the nodes have a non-rectangular shape such as a triangle, rhombus, or circle. If no link clip interface is used, the links are normally connected to the bounding boxes of the nodes, not to the border of the node shapes. See Using a link clipping interface (HL) for details of the link clipping mechanism.

Link connection box (HL)

The layout algorithm can use a link connection box interface (see Link connection box) in combination with the link clip interface. If no link clip interface is used, the link connection box interface has no effect. For details, see Using a link connection box interface (HL).

Spline routing (HL)

The layout algorithm supports the generic spline routing mechanism (see Spline routing). If the style of a link is polyline or orthogonal and the link is a spline, it is routed by the generic spline routing mechanism when it is enabled.

Percentage of completion calculation (HL)

The layout algorithm calculates the estimated percentage of completion. This value can be obtained from the layout report during the run of the layout. (For a detailed description of this features, see Percentage of completion calculation and Graph layout event listeners.)

Preserve fixed links (HL)

The layout algorithm does not reshape the links that are specified as fixed. In fact, fixed links are ignored. (For more information about link parameters in the IlvGraphLayout class, see Preserve fixed links and Link style (TL).)

Preserve fixed nodes (HL)

The layout algorithm does not move the nodes that are specified as fixed. (For more information about node parameters in the IlvGraphLayout class, see Preserve fixed nodes.) Moreover, the layout algorithm ignores fixed nodes and also does not route the links that are incident to the fixed nodes. It can result in unwanted overlapping nodes and link crossings. However, this feature is useful for individual, disconnected components that can be laid out independently.

Save parameters to named properties (HL)

The layout algorithm is able to save its layout parameters into named properties. This can be used to save layout parameters to .ivl files. (For a detailed description of this feature, see Save parameters to named properties and Saving layout parameters and preferred layouts).

Stop immediately (HL)

The layout algorithm stops after cleanup if the method stopImmediately is called. (For a description of this method in the IlvGraphLayout class, see Stop immediately.) If the layout stops early because the allowed time has elapsed, the nodes and links are not moved from their positions before the layout call and the result code in the layout report is IlvGraphLayoutReport.STOPPED_AND_INVALID.

Flow direction (HL)

The flow direction parameter specifies the direction in which most of the links must point. If the flow direction is to the top or to the bottom, the node levels are oriented horizontally and the links mostly vertically. If the flow direction is to the left or to the right, the node levels are oriented vertically and the links mostly horizontally.

If the flow direction is to the bottom, the nodes of the level with index 0 are placed at the top border of the drawing. The nodes with level index 0 are usually the root nodes of the drawing (that is, the nodes without incoming links). If the flow direction is to the top, the nodes with level index 0 are placed at the bottom border of the drawing. If the flow direction is to the right, the nodes are placed at the left border of the drawing.

To specify the flow direction towards the bottom:

Add to the GraphLayout section:

In Java, use the method:

The valid values for the flow direction are:

In CSS, you omit the prefix IlvDirection when specifying the value of the flow direction.

Leveling strategy (HL)

The layout algorithm partitions the nodes into levels (see A brief description of the HL algorithm). The leveling strategy specifies how the levels are calculated. Besides the leveling strategy, layout constraints (see Layout constraints for HL), level indexes (see For experts: more indexes (HL)) as well as the incremental mode (see Incremental mode with HL) also affect the way the levels are calculated. If the incremental mode is disabled, the leveling strategy determines the levels of all nodes that are not subject to layout constraints and level index specifications.

To specify the leveling strategy:

Add to the GraphLayout section:

In Java™, use the method:

The valid values for the leveling strategy are:

In CSS, you omit the prefix IlvHierarchicalLayout when specifying the value of the leveling strategy.

Level justification (HL)

If the layout uses horizontal levels, the nodes of the same level are placed approximately at the same y-coordinate. The nodes can be justified, depending on whether the top border, the bottom border, or the center of all nodes of the same level have the same y-coordinate.

If the layout uses vertical levels, the nodes of the same level are placed approximately at the same x-coordinate. The nodes can be justified to be aligned at the left border, at the right border, or at the center of the nodes that belong to the same level.

To specify the level justification towards the top:

Add to the GraphLayout section:

Use the method:

If the flow direction is to the top or to the bottom, the valid values for the level justification are:

If the flow direction is to the left or to the right, the valid values for the level justification are:

In CSS, you omit the prefix IlvDirection when specifying the value of the flow direction.

Link style (HL)

The layout algorithm positions the nodes and routes the links. To avoid overlapping nodes and links, it creates bend points for the shapes of links. The link style parameter controls the position and number of bend points. The link style can be set globally, in which case all links have the same shape, or locally on each link such that different link shapes occur in the same drawing.

Link style and link shapes

Link styles work only when you use links that can be reshaped. Subclasses of IlvPolylineLinkImage or of IlvSplineLinkImage, (e.g., IlvGeneralLink ) can be reshaped. Furthermore, link styles work only if free link connectors are installed. Free link connectors are subclasses of IlvFreeLinkConnector. If you use a diagram component, the free link connectors are automatically installed when needed unless specified differently. If you call layout on an IlvGrapher directly in Java, the layout algorithm may raise an IlvInappropriateLinkException if links are neither a subclass of IlvPolylineLinkImage nor of IlvSplineLinkImage, or if connectors are not a subclass of IlvFreeLinkConnector. In this case, you can use the methods EnsureAppropriateLinkTypes, EnsureAppropriateLinkConnectors or EnsureAppropriateLinks defined in the class IlvGraphLayoutUtil to replace inappropriate links or link connectors automatically, either before layout or when the IlvInappropriateLinkException is caught. For details on these methods, see the Java API Reference Manual.For details on the graph model, see Using the graph model.

Global link style

To set the global link style:

Add to the GraphLayout section:

Use the method:

The valid values for the link style are:

In CSS, you omit the prefix IlvHierarchicalLayout when specifying the value of the link style.

Individual link style

All links have the same style of shape unless the global link style is MIXED_STYLE. Only when the global link style is MIXED_STYLE can each link have an individual link style.

To specify the style of an individual link:

First set the global link style to MIXED-STYLE, then specify a rule that selects the link, for instance:

Use the methods:

In this case, the link argument must be a graphic link (subclass of IlvLinkImage ).

The valid values for the link style of local links are the same as for the global link style:

Connector style (HL)

The layout algorithm positions the end points of links (the connector pins) at the nodes automatically. The connector style parameter specifies how these end points are calculated.

To specify the connector style:

Add to the GraphLayout section:

Use the method:

The valid values for style are:

In CSS, you omit the prefix IlvHierarchicalLayout when specifying the value of the connector style.

End point mode (HL)

Normally, the layout algorithm is free to choose the termination points of each link. However, if fixed-link connectors are used (for instance, IlvPinLinkConnector), the user can specify that the current fixed termination pin of a link must be used.

The layout algorithm provides two end point modes. You can set the end point mode globally, in which case all end points have the same mode, or locally on each link, in which case different end point modes occur in the same drawing.

Global end point mode

To set the global end point mode:

Add to the GraphLayout section:

Use the methods:

The valid values for mode are:

In CSS, you omit the prefix IlvHierarchicalLayout when specifying the value of the end point mode.

The connection points are automatically considered as fixed if they are connected to grapher pins.

Individual end point mode

All links have the same end point mode unless the global end point mode is IlvLinkLayout.MIXED_MODE. Only when the global end point mode is set to MIXED_MODE can each link have an individual end point mode.

To set the end point mode of an individual link:

First set the global point modes to MIXED_MODE, then specify a rule that selects the link, for instance:

Use the methods:

The valid values for mode are:

The connection points are automatically considered as fixed if they are connected to grapher pins.

Using a link connection box interface (HL)

By default, the connector style determines how the connection points of the links are distributed on the border of the bounding box of the nodes, symmetrically with respect to the middle of each side. Sometimes it can be necessary to place the connection points on a rectangle smaller or larger than the bounding box. For instance, it can happen when labels are displayed below or above nodes.

You can modify the position of the connection points of the links by providing a class that implements the IlvLinkConnectionBoxInterface. An example for the implementation of a link connection box interface is in Link connection box. To set a link connection box interface in Java, use the method:

The link connection box interface provides each node with a link connection box and tangential shift offsets. The Hierarchical Layout uses the link connection box but does not use the tangential offsets.

The following figure illustrates the effects of customizing the connection box. On the left is the result without any connection box interface. The picture on the right shows the effect if the connection box interface returns the dashed rectangle for the blue node.

Using a link clipping interface (HL)

By default, the Hierarchical Layout places the connection points of links at the border of the bounding box of the nodes. If the node has a non-rectangular shape such as a triangle, rhombus, or circle, you may want the connection points to be placed exactly on the border of the shape. This can be achieved by specifying a link clip interface. The link clip interface allows you to correct the calculated connection point so that it lies on the border of the shape. The following figure shows an example.

You can modify the position of the connection points of the links by providing a class that implements the IlvLinkClipInterface. An example for the implementation of a link clip interface is in Link clipping. To set a link clip interface in Java, use the method:

The connector style, the link connection box interface, and the link clip interface work together in the following way: by respecting the connector style, the proposed connection points are calculated on the rectangle obtained from the link connection box interface (or on the bounding box of the node, if no link connection box interface was specified). Then, the proposed connection point is passed to the link clip interface and the returned connection points are used to connect the link to the node.

The following figure shows an example of the combined effect.

If the links are clipped at the red node in previous figure (left), they appear unsymmetrical with respect to the node shape, because the relevant part of the node (here: the triangle) is not in the center of the bounding box of the node, but the proposed connection points are calculated with respect to the bounding box. This can be corrected by using a link connection box interface to explicitly specify a smaller connection box for the relevant part of the node (previous figure, right) such that the proposed connection points are placed symmetrically around the apex of the triangle of the node.

For experts: thick links (HL)

If evenly spaced pins are used as connector style, the links can be evenly spaced with respect to the link center or with respect to the link border. The difference is only visible when links that connect to the same node have different widths. For instance, when the link width indicates the cost or capacity of a flow in the application, many different link widths can occur.

Figure Using the link width shows the effect of using different link widths. In the drawing on the left, the center of the links are evenly distributed at the left node. Each link has the same space available at the node side. Therefore, the thick links appear closer to each other than do the thinner links and the offsets between the link borders are different. In the drawing on the right, the thick links have more space available than do the thinner links. The offset between the link border (at the segments that connect to the left node) is constant because the link width is considered in the calculation of the connection points.

To enable the connector calculation to respect the link width:

Add to the GraphLayout section for instance the statement:

Call:

The link width setting is disabled by default. The link width has no effect if the connector styles CENTERED_PINS or CLIPPED_PINS are used.

Port sides parameter (HL)

The Hierarchical Layout algorithm produces a layout where most of the link flows are in the same direction. If the flow direction is toward the bottom, usually the incoming links are connected to the top side of the node and the outgoing links are connected to the bottom side of the node. It is also possible to specify on which side a link connects to the node.

To simplify the explanations of port sides, port sides are referred to by the compass directions north, south, east, and west. The specified link flow direction is always toward south and the first level is toward north. If the flow direction is toward the bottom, north is at the top, south at the bottom, east on the right, and west on the left side of the drawing. If the flow direction is toward right, north is on the left, south on the right, east at the top, and west at the bottom.

The figure Link connections to port sides shows a drawing where the links connect to the larger middle node at the specified port sides. A compass icon shows the compass directions in these drawings.

You can set at which side the link connects to its source node.

To set at which side the link connects to its source node:

Specify a rule that selects the link, for instance:

Use the method:

In a similar way, you can set at which side the link connects to its destination node.

To set at which side the link connects to its destination node:

Specify a rule that selects the link, for instance:

Use the method:

The valid values for side are:

In CSS, you omit the prefix IlvHierarchicalLayout when specifying the value of the port side.

To retrieve the current choice for a link, use the methods:

The port sides east and west work well with the orthogonal link style. Polyline links with these port sides sometimes have unnecessary bends. Furthermore, if port sides are specified, the connector style CLIPPED_PINS must not be used.

Port index parameter (HL)

Instead of asking the layout algorithm to decide at which point a link connects to the node border, you can specify where the links connect to the node. You cannot specify the exact location, but you can specify the relative location compared to the connection points of the other links. You can do so by using a port index. Figure Sample layout with ports and orthogonal link style shows a sample layout with ports at many nodes.

Links that have the same port index connect at the same point of the node. The ports are evenly distributed at the node sides, in a similar way as with the connector style EVENLY_SPACED_PINS. The ports are ordered according to their indexes. On the north and south side of a node, the port indexes increase toward the east. On the east and west sides of a node, the port indexes increase toward the south. By using port indexes in this way, it is easier to rotate a graph by simply changing the flow direction without updating all the port specifications.

Figure Port index numbering conventions in relation to flow direction shows how the port indexes depend on the flow direction.

Port numbers are normally used in combination with port sides. Therefore, you must specify how many ports are available on each side of a node.

To specify the number of ports:

Write a rule that selects the node, for instance:

Alternatively, you can write:

Both are equivalent.

Use the method:

For example, to use four ports on each side of a specific node, use the calls:

The node side is specified again by EAST, WEST, NORTH, and SOUTH. To retrieve the retrieve the number of ports available at the node, use the method:

After the number of ports per side is specified, you can choose which port each link connects to.

To choose the port side and the port index for a link:

Specify a rule that selects the link, for instance:

To specify the connection at the source node, use the methods:

To specify the connection at the destination node, use the methods:

To obtain the current port index of a link, use the methods:

Using the port side and port index specifications are additional constraints for the layout algorithm. The more constraints are specified, the more difficult it is to calculate a layout. Therefore, if too many links have a specified port index, this resulting layout might have more link crossings and be less balanced.

Fork link shapes (HL)

If several links start at the same position and are orthogonally routed, it is sometimes preferred that the links share the first two link segments. The shape of a link bundle of this kind looks like a fork. To enable the fork shape mode for outgoing links, call:

To enable the fork shape mode for incoming links:

Add to the GraphLayout section:

Call:

These statements are effective only if the links are routed orthogonally. The fork appears only at those links that start or end exactly at the same point. Specifying setFromFork(true) by itself does not force the links to start at the same point. To force links to start or end at the same point, use the center connector style (see Connector style (HL)) or specify the same port for the links (see Port index parameter (HL)).

There are two spacing parameters for the fork shape:

Add to the GraphLayout section:

Sets the minimum length of the segment that is directly near the node.

Sets the preferred length of the fork axis per branch (the second segment next to the node).

If the fork has five branches, the entire axis has the preferred length five times the specified parameter. The preferred fork axis length is only a hint for the layout algorithm. If enough space is available, the algorithm enlarges the fork axis to avoid unnecessary link bends. If there is not enough space, the algorithm can calculate a fork axis that is smaller than the preferred one.

Fork link shapes can sometimes look ambiguous, in particular when a link starts at the same point where another link ends. In this case, it is impossible to recognize whether the arrowhead belongs to one or the other link.

Link priority parameter (HL)

The layout algorithm tries to place the nodes such that all links are short, point in the flow direction, and do not cross each other. However, it is not always possible. Often, links cannot have the same length. If the graph has cycles, some links must be reversed against the flow direction. If the graph is a nonplanar graph, some links have to cross each other.

The link priority parameter controls which links must be selected if long, reversed, or crossing links are necessary. Links with a low priority are more likely to be selected than links with a high priority. It does not mean that low-priority links are always longer, reversed, or crossed. The graph can have a structure such that no long, reversed, or crossing links are necessary.

To set the link priority:

Specify a rule that selects the link, for instance:

Use the methods.

The default value of the link priority is 1.0. Negative link priorities are not allowed.

For an example of using the link priority, consider a cycle A->B->C->D->E->A. It is impossible to lay out this graph without reversing any link. Therefore, the layout algorithm selects one link to be reversed. To control which link is selected, you can give one link a lower priority than the others. This link is then reversed. In figure Working with link priorities, the bottom layout shows the use of the link priority. The link C->D was given the priority 0.5, while all the other links have the priority 1.0. Therefore C-D is reversed. The top layout in Working with link priorities shows what happens when all links have the same priority. Link E->A is reversed.

The use of link priorities is important in combination with ports. Links with “from” ports on the south side and “to” ports on the north side are preferably laid out opposite to the flow direction. Such a feedback link can cause parts of the drawing to tip over. The figure Using link priorities and ports shows an example. The red link is a feedback link with port specifications. To obtain the correct result as shown in the right side of the following figure, you would set the priority of the feedback link to a very low value.

Spacing parameters (HL)

The spacing of the layout is controlled by three kinds of spacing parameters: the minimum offset between nodes, the minimum offset between parallel segments of links, and the minimum offset between a node border and a bend point of a link or a link segment that is parallel to this border. The offset between parallel segments of links is at the same time the offset between bend points of links. All three kinds of parameter occur in both directions: horizontally and vertically.

To set the spacing parameters:

Add to the GraphLayout section:

For a layout with horizontal levels (the flow direction is to the top or to the bottom), the horizontal node offset is the minimum distance between nodes of the same level. The vertical node offset is the minimum distance between nodes of different levels, that is, the minimum distance between the levels. For non-orthogonal link styles, the horizontal link offset is basically the minimum distance between bend points of links. The horizontal node-link offset is the minimum distance between the node border and the bend point of a link. For horizontal levels, the vertical link offset and the vertical node-link offset play a role only if the link shapes are orthogonal.

Similarly, for a layout with vertical levels (the flow direction is to the left or to the right), the vertical node offset controls node distances within the levels. The horizontal node offset is the minimum distance between the levels. In this case, the vertical link offset and the vertical node-link offset always play a role, while the horizontal link offset and the horizontal node-link offset impact the layout only with orthogonal links.

For orthogonal links, the horizontal link offset is the minimum distance between parallel, vertical link segments. The vertical link offset is the minimum distance between parallel, horizontal link segments. However, the layout algorithm cannot always satisfy these offset requirements. If a node is tiny but has many incident links, it can be impossible to place the links orthogonally with the specified minimum link distance on the node border. In this case, the algorithm places some link segments closer than the specified link offset.

In some circumstances you, might need to use a sequence of layouts on the same graph. For example:

The Hierarchical Layout normally works non-incrementally. It performs a layout from scratch and moves all nodes to new positions and reroutes all links. The previous positions of nodes have no influence on the result of the layout. Hence, even a small change can cause a large effect on the next layout.

But the Hierarchical Layout also supports incremental sequences of layout that “do not change very much.” It can place the nodes close to their previous positions, so that you can more easily identify the parts that had already been laid out in the original graph. Incremental mode takes the previous positions of the nodes into account. In this mode, the algorithm preserves the relative order of the levels and the nodes within the levels in the subsequent layout. It does not preserve the absolute positions of the nodes, but it tries to detect the structure of the previous layout by examining the node coordinates. For instance, if two nodes are in the same level, then they stay in the same level after an incremental layout. If a node is in a higher level than another node, it stays in the higher level.

The following figure illustrates the difference between an incremental and nonincremental layout.

Incremental mode is disabled by default.

To enable incremental mode:

Add to the GraphLayout section:

Phases of the incremental mode

The layout algorithm analyzes the drawing in incremental mode in the following way:

The following figure shows the result of the incremental phases.

Expert parameters of the incremental mode

Each phase of the incremental mode can be parameterized. These layout parameters are effective only if incremental mode is enabled.

Minimizing long link crossings

The incremental layout tries to preserve the shape of long links that cross several levels. It implies that link crossings between long links are not resolved. If crossings of long links are not wanted, it might be better to reroute long links from scratch. The following figure shows four hierarchy trees, with the original layout at the upper left. The lower right shows the result if long links are rerouted, and the upper right shows the result if the shape of long links is preserved.

To reroute long links from scratch, you must enable the crossing reduction mechanism for long links:

The crossing reduction of long links determines only the shape of the links. It does not influence the order of the other nodes within the levels.

Minimizing all link crossings

Optionally, you can apply a crossing reduction to all nodes within each level. In this case, the incremental layout determines from the node coordinates which nodes belong to the same level, but it might reorder the nodes within the levels completely to avoid link crossings. It also reorders the long links in this case. The previous figure, lower left shows the result. Notice that the order of the nodes “F,” “G,” and “H” have changed to resolve the link crossings.

To enable the crossing reduction for all nodes:

Setting absolute level positioning

The incremental layout tries to place the nodes in absolute positions that are close to the previous positions. It tries to avoid nodes moving a long distance, because even if the relative order of the nodes within the levels does not change, long distances can be confusing for users. It is much easier to keep a mental map of the diagram if the nodes remain close to the previous positions.

The following figure illustrates node repositioning with and without taking the previous positions into account. The incremental layout of the original graph (upper left) results in the graph at the upper right, which is easier to recognize as being the same graph than is the graph at the bottom.

The absolute level positioning feature is enabled by default, but it can be disabled.

To disable the absolute level positioning feature:

Write the statement:

Call

With this statement, the layout does not try to place the nodes close to the previous positions. It places the nodes such that the layout is balanced. However, to create a perfect balance, the layout might need to move a few nodes so far apart that you no longer recognize the diagram (see the following figure, bottom).

Setting absolute level position range and tendency

If absolute level positioning is enabled, it competes with the aesthetic criteria to create a balanced layout. Because nodes must stay close to their previous positions, the diagram after incremental layout might be unbalanced and unsymmetrical. The Hierarchical Layout algorithm uses a heuristic that you can influence by two parameters, the absolute level position range and tendency.

The absolute level positioning feature is enabled by default, but it can be disabled.

To disable the absolute level positioning feature:

Add in the GraphLayout section:

Call:

This statement specifies that within the range of 100 coordinate units from the old position of the node, the balance is the only criteria for the placement. This means that a node whose optimal position is less than 100 coordinate units away from its previous position is placed exactly at its optimal position. Nodes whose optimal position is farther away are placed at a position that is a compromise between previous position and optimal position. See the following figure, right.

To set the absolute level position tendency:

Add in the GraphLayout section:

Call:

This statement specifies that when the optimal position of a node is far away from its previous position, its position is 70% influenced by its previous position and 30% influenced by its optimal position. Imagine a rubber band that tries to pull a node to its previous position, and another rubber band that tries to pull the same node to its optimally balanced position. The level position tendency 70 means that one rubber band pulls with 70% of the force towards the previous position, and the other rubber band pulls with 30% towards the optimal position. Increasing the tendency means that the node stays closer to its old position, decreasing it means that the node moves closer to its optimal position. If you set the tendency to 0%, it has the same effect as disabling the incremental absolute level positioning (see the following figure).

Marking nodes for incremental layout

Incremental layout normally treats all nodes and links of the drawing in the same way. However, you might have added nodes and links to the drawing programmatically, and the new nodes and links do not have meaningful coordinates yet. Perhaps you have placed them all at the origin (0,0), or at random coordinates. In this case, you need an incremental layout that takes into account the coordinates of all nodes that were previously laid out while ignoring the coordinates of the new nodes.

The incremental mode of the Hierarchical Layout allows you to specify in Java which nodes cannot be laid out incrementally by calling the method:

If you call this statement, the node or link is marked such that its coordinates are ignored during the next incremental layout. The positions of marked nodes and links are calculated from scratch. The mark is valid only until the next layout and is automatically cleared afterward.

The Hierarchical Layout algorithm supports relative position constraintson nodes. Such a constraint is a rule on how a particular node (or a group of nodes) must be placed with respect to the other nodes. The constraints influence the relative positions. For example, you can force node A to be on the left side of node B, so the position of A is expressed relative to the position of B. It is theoretically possible to specify contradicting constraints: if you specify that node A must be on the left side of B and B must be on the left side of A, then these constraints are not solvable at the same time. If A is on the left side of B, then B must be on the right side of A. The Hierarchical Layout algorithm tries to detect and resolve constraint conflicts automatically. It ignores those constraints that are infeasible. Since the automatic constraint resolution is time consuming, it is recommended to specify nonconflicting constraints when possible.

Constraints must be used only if the incremental mode is disabled. In fact, the incremental mode is implemented with additional constraints that are added internally. Hence, if you use constraints during the incremental mode, it is likely that the system detects so many constraint conflicts that you get unexpected results.

Constraints must be used carefully. The more constraints are specified, the more difficult it is to calculate a layout. Therefore, this resulting layout can have more link crossings and be less balanced than a graph with no constraints.

Each type of constraint is represented by a subclass of IlvHierarchicalConstraint. The following constraint types are available:

There are two ways to specify constraints in a style sheet:

When you do not use a diagram component with style sheet capabilities, you can still use constraints.

Writing style rules that specify constraints is very powerful but complex. It is illustrated in section For experts: specifying constraints in CSS directly (HL). This topic concentrates on specifying constraints in an external file.

In the CSS file, you can write:

This means that the layout constraints are specified in a separate file named Constraints.txt. This file contains the constraint in a very simple format, for example:

The complete example can be found at:

The style files are in the subdirectory data. The example shows how to specify constraints by loading an external file as well as how to specify constraints by writing style rules directly.

You can add constraints to the Hierarchical Layout in Java™. You allocate a new constraint object and call this method on the IlvHierarchicalLayout instance:

You can add as many constraints as you want. The constraints are respected during the subsequent layout calls until you remove them. To remove the most recent constraint, call:

To remove a specific constraint, call:

To remove all existing constraints, call:

You can retrieve the constraints that were added to a Hierarchical Layout with the method:

Node groups

Some constraints affect single nodes. Other constraints affect groups of nodes. The class IlvNodeGroup is a convenient way to specify a group of nodes in Java. You can create a group of nodes in the following way:

A node group has a similar functionality to a vector. You can ask for the size and elements of the group, remove elements from the group, or check whether a node already belongs to the group. You can also convert a vector of nodes into a group:

In Step 1 of the layout algorithm (the leveling phase), the nodes are partitioned into levels. These levels are indexed starting from 0. For instance, when the flow direction is to the bottom, the nodes of the level index 0 are placed at the topmost horizontal level line and the nodes with larger level index are placed at a position lower than the nodes with smaller level index (see Level and position indexes). The layout algorithm calculates these level indexes automatically.

You can choose how the levels are partitioned by specifying the range of the level index for some nodes. The nodes are placed in the levels whose index is in the specified range. You have to specify the minimum and maximum index of the level.

To specify the minimum and maximum index of the level:

In the constraint file, specify:

This specification forces the graphic of the model node with ID “node11” to be placed between the minimum level 5 and the maximum level 7, that is, either in level 5, level 6, or level 7.

Call:

Notice that in this case, node contains the graphic node (subclass of IlvGraphic ). If you want to place the node exactly at level 5, call:

Alternatively, you can call:

which has the same meaning.

If you want to force the node to level 5 and above, set UNSPECIFIED as the maximum level.

In the constraint file, specify:

Call:

If you want to force the node to level 5 and below (that is, level 0, ..., 5), set UNSPECIFIED as the minimum level; for example, in Java:

In this particular case, you could also use zero (0) as the minimum level because the level indexes start at 0.

You can apply the constraint to a group of several nodes at once. It has the same effect as specifying the constraint for each single node of the group, but it is more memory efficient and convenient. For instance, if you want to force the group of three nodes to the levels 5 - 7:

To specify these parameters:

In the constraint file, specify:

Create a IlvNodeGroup object (see Node groups) of the three nodes and add it to the constraint in the following way:

The level index is a special case of a level range constraint (see Level range constraints (HL)). It forces the node to one particular level. For your convenience, you can specify the level index of a node directly by the method:

You pass a single node as the first argument (not a node group). The default index value is -1. If the default value is used, or if a node is set to a negative level index, the level index is considered to be unspecified. In this case the layout algorithm automatically calculates an appropriate level index during the leveling phase of the algorithm.

To obtain the specified level index for a node, use the method:

However, this method returns the value that was set by setSpecNodeLevelIndex. If the level index was specified by allocating a corresponding level range constraint that has the same meaning, getSpecNodeLevelIndex still returns -1.

If you want to force several nodes to the same level with fixed index, you can set the level index parameter of these nodes accordingly (see Level index parameter (HL)) or use a level range constraint (see Level range constraints (HL)). However, if you want to force several nodes to the same level without forcing them to a specific level index, you cannot use these mechanisms. You must use a same level constraint.

To set the same level constraint:

In the constraint file, specify:

Call:

This forces node1 and node2 to be placed in the same level, but it does not constrain them to any particular level.

The following figure illustrates the placement of nodes at the same level.

An alternative way to force a group of nodes to be at the same level is by specifying a group spread constraint with a spread size of zero (0). In general, the group spread constraint forces a group of nodes to k+1 subsequent levels. The number k is the spread size. It does not select the lowest or highest level index of the group, but requires only that the nodes are placed no more than k levels apart. Hence, if k=0, all nodes of the group are placed at the same level.

To illustrate the general group spread constraint on nodes with ID “nodeA’, “nodeB” and “nodeC”:

In the constraint file, specify:

To use the group spread constraint on graphic nodes (subclasses of IlvGraphic), call:

The constraint is satisfied if the highest level index for nodeA, nodeB, and nodeC is no more than two levels apart from the smallest level index of the nodes. For instance, the constraint is satisfied if the level indexes for nodeA, nodeB, and nodeC are 1, 2, 3; or if they are 7, 8, 9; or if they are 16, 14, 15. The constraint is also satisfied if all three nodes are placed at level 5, or if two of the nodes are placed at level 15 and the third node at level 13. The constraint is not satisfied if the level indexes for nodeA, nodeB, and nodeC are 3, 5, 6, because in this case the highest index (6) is more than two levels away from the lowest index (3).

If the flow direction is towards the bottom, level 0 is topmost in the drawing. In this layout, you can specify by relative level constraints that a node is above or below another node. If the flow direction is towards the right, level 0 is leftmost in the drawing. Here you can specify by relative level constraints that a node is left or right of another node.

In the constraint file, specify:

In Java™, call:

This forces nodeA to be placed at a level with a smaller index than nodeB. Since relative level constraints compete with each other, you must specify the priority of the constraint. In fact, links also impose constraints on the system, and the link priority has the same impact as the constraint priority. A link with priority 10 forces its (usually) source node (unless ports are specified) into a lower level than its target node. To force the source node into a higher level than the target node, you need to create a constraint with a higher priority than the link. For instance, to ensure that the constraints are satisfied even if there are many links, you can use link priorities 0 - 10 and constraint priorities 1000 - 10,000.

You can also create a relative level constraint between groups of nodes.

In the constraint file, specify a comma-separated list of nodes, such as

Call:

In Step 2 of the layout algorithm (the crossing reduction phase), the nodes are ordered within the levels. All nodes that belong to the same level get a position index starting from 0. For instance, when the flow direction is to the bottom, the node with the position index 0 is placed in the leftmost position within its level. The nodes with a larger position index are placed farther to the right than the nodes with a smaller position index in the same level. The nodes of different levels are independent. The node of the first level with the position index 0 is to the left of the node of the first level with the position index 1, but not necessarily to the left of a node of another level with position index 0. Long links crossing a level also obtain a position index (see Level and position indexes). The layout algorithm calculates these position indexes automatically.

You can affect how the nodes are positioned within each level by specifying the position index of some nodes. The nodes are placed at the specified position within their level.

To specify the position index of a node in Java™, use the method:

The default value is -1. If the default value is used, if a node is set to a negative position index, or if a node is set to a position index that is larger than the number of nodes of its level, the layout automatically calculates an appropriate position index during the crossing reduction step.

To obtain the current position index of a node, use the method:

Working with absolute node position indexes is inconvenient in certain situations. For example, if two nodes belong to the same level, you might want to force one node to a position with a lower index than the other node without fixing the absolute positions of the nodes. You can achieve it by using a relative position constraint.

The relative position constraint forces a specific order upon the nodes of a level, but it does not specify which nodes are directly neighbored. For instance, a relative position constraint can force nodeA to be placed somewhere at a lower position than nodeB, but there can be many nodes between nodeA and nodeB.

In the constraint file, specify:

Call:

This forces nodeA to a lower position than nodeB. If the flow direction is towards the bottom, the nodes are in horizontal levels; hence the constraint means that nodeA is placed at the left side of nodeB. If the flow direction is towards the right, the nodes are in vertical levels; hence the constraint means that nodeA is placed below nodeB.

The relative position constraint has an effect only if both nodes actually belong to the same level. To achieve it, you can, for instance, use a same level constraint in addition. There is no way to influence the relative position of nodes that belong to different levels.

Similar to the relative level constraint, the relative position constraint can be applied to node groups. These constraints also have priorities that indicate which constraints dominate if a constraint conflict occurs. The higher the priority, the more likely the constraint is satisfied when resolving constraint conflicts.

To force nodes to be directly neighbored, use the side-by-side constraint.

In the constraint file, specify:

You can create a side-by-side constraint on a group of type IlvNodeGroup (see Node groups):

If the node group consists of just two nodes, it forces the two nodes to be placed side by side. However, it does not specify which node is at the lower node position and which node is at the higher node position. If the group consists of more than two nodes, it forces the nodes to be placed at consecutive positions such that all nodes are clustered together. A node that does not belong to the group cannot be placed between the nodes of the group.

For example, assume that the group contains the three nodes A, B, C. The constraint is satisfied if the position indexes of A, B, and C are 3, 4, 5 or 9, 7, 8. However, if node D is placed between A and B (say, D has position 4, A has position 3, and C has position 5), then the constraint is not satisfied because D does not belong to the same group.

The side-by-side constraint has an effect only if the nodes actually belong to the same level. To achieve it, you can, for instance, use a same level constraint in addition.

Side-by-side constraints have priorities that decide how to resolve constraint conflicts. The higher the priority, the more likely the constraint is satisfied.

You can use side-by-side constraints to create nested clusters. For example, in Java:

The first constraint specifies that nodeA, nodeB, nodeC, and nodeD must be clustered. The second constraint specifies that nodeB and nodeC are clustered inside the larger cluster. This means that no other node can be placed between the four nodes and, furthermore, nodeA or nodeD cannot be placed between nodeB and nodeC. The following figure shows four solutions that satisfy both constraints.

To force a node to the first level, you can specify:

However, you cannot specify a level index for the last level because it is unknown at the beginning of layout how many levels are created. It is unwise to specify:

because it creates many empty levels between the levels used and the last one. Even though these empty levels are removed in postprocessing steps, it influences the speed and quality of the layout. (In fact, the algorithm runs out of memory if you set the specified level index unreasonably high.)

By using constraints you can achieve the same effect more efficiently.

To force a node to the first level:

In the constraint file, specify:

In Java™, call:

To force a node to the last level:

In the constraint file, specify:

Call:

With compass directions as a convenient reference (see Port sides parameter (HL)), the first level indicates the north pole and the last level indicates the south pole. You can also specify extremity constraints for the east and west sides:

The west extremity constraint forces the node to the lowest position index within its level, and the east extremity constraint forces the node to the highest position index within its level. The position indexes specify the relative position within the level. For instance, a node with west extremity constraint is the leftmost node within its level, if the flow direction is towards the bottom. However, it does not affect other levels; there can be a node in another level that is still placed farther to the left.

The following figure illustrates some extremity constraints.

Swimlanes are rectangular areas orthogonal to the levels.

You can use swimlanes if the nodes are partitioned into groups, to indicate which nodes belong to a certain group. The nodes in the same swimlane are placed so that it is possible to draw a surrounding rectangle around them. Swimlanes allow you to organize the graph in a table-like manner. For example, you can have a workflow diagram where nodes represent actions; the swimlanes could then represent the departments that perform these actions. Each node can belong to only one swimlane.

To assign a group of nodes to a swimlane:

In the constraint file, specify:

In Java™, call:

All nodes of the node vector are placed in the same swimlane rectangle. If a graph has many swimlane rectangles, the relative order of these swimlanes is determined automatically. The size of the swimlane rectangle depends on the nodes that belong to the swimlane. However, you can specify the relative order, relative size, and the margins of the swimlane as well by using the constructor:

The relative size indicates how large this swimlane is compared to the other swimlanes. Assume that the flow direction is towards the bottom. In this case, the relative size indicates the width of the swimlane. All swimlanes with the same relative size have the same width. A swimlane with a relative size that is twice the value of another swimlane will have twice the width of the other swimlane. The actual number of this parameter does not matter, only how large the value is compared to the other swimlanes. If you do not want to restrict the size of the swimlane, set the value to 0. In this case, the width of the swimlane is independent of the other swimlanes.

The minimum margin is the margin of the swimlane in absolute coordinates. If the flow direction is towards the bottom, then the west minimum margin is the minimum horizontal distance between the leftmost node of the swimlane and the left swimlane border, and the east minimum margin is the minimum horizontal distance between the rightmost node of the swimlane and the right swimlane border.

The position index indicates the order of the swimlanes. Just as nodes have position indexes, the swimlanes are placed sequentially at relative positions numbered from 0 to n. In a top-down layout, the swimlane with position 0 is the leftmost swimlane, and the swimlanes with higher position indexes are placed farther to the right. If the swimlanes have the position index -1, the layout algorithm determines the appropriate position automatically.

A swimlane constraint is always evaluated, even if the incremental mode is enabled. The constraint has a higher priority than the relative position constraint and the side-by-side constraint. You can specify side-by-side constraints for a group of nodes that belong to the same swimlane, but side-by-side constraints of nodes of different swimlanes are ignored. You can specify relative position constraints between nodes of the same swimlane. You can also specify relative position constraints between one entire swimlane group and another swimlane group, which effectively orders the swimlanes. But relative position constraints are ignored if they would require breaking the swimlanes apart. The swimlane constraint dominates the specified position indexes and the extremity constraints, that is, if a swimlane constraint is used, you cannot specify position indexes or east/west extremity constraints for any node.

The following summary indicates how to specify constraints:

A set of constraints can cause conflicts. This means that not all of the constraints can be satisfied at the same time. For instance, it is impossible to force two nodes into the same level by an IlvSameLevelConstraint while forcing one of the nodes to a higher level than the other node by an IlvRelativeLevelConstraint. In this case, one of the two constraints must be ignored during layout.

In general, constraint conflicts are resolved by ignoring the constraints with the lowest priority while the constraints with the highest priority get satisfied. The following rules explain the constraint priorities in detail.

Constraints that you specify can become invalid. For instance, if you add a constraint that node A must be to the left side of node B, but you remove A from the graph, then this constraint becomes invalid. It simply does not make sense any more, even though it does not conflict with any other constraint. The layout instance automatically removes invalid constraints from time to time because they are a waste of memory. The validation check is done during layout. Forcing a validation check is normally not necessary but if you want to do it, call:

It removes all invalid constraints from the Hierarchical Layout and cleans up the memory. The constraint validation does not check which constraints have conflicts. The main effect of the validation is that the constraint system uses less memory afterward.

SDM applications that use style files (CSS files) can specify an external constraint file that refers to the constrained nodes by their node IDs. Alternatively, it is possible to specify the constraints in the CSS file directly.

The general mechanism for specifying constraints in CSS directly is:

The meaning is that the selected node participates in the constraint with the specified name. The constraint name is an arbitrary string that identifies the constraint. The name is needed because several nodes usually participate in the same constraint; therefore, several such style rules are required to specify the constraint completely.

For example, to specify a relative-level constraint between the nodes with ID activity1 and participant1, use the following style rules:

The constraint property LowerRelativeLevelConstraing indicates that this rule specifies the lower node of a relative-level constraint. The property HigherRelativeLevelConstraint indicates that this rule specifies the higher node of a relative-level constraint. The constraint name “ ConstraintA ” is used to distinguish this relative-level constraint from other constraints of the same type. The parameter 5000 is the priority of this constraint.

All constraint types can be specified similarly. The constraint name is arbitrary, except for the extremity constraint: Here, only the names “ EAST ”, “ WEST ”, “ NORTH ” and “ SOUTH ” are allowed as constraint names, and they indicate at the same time the side of the constraint.

A sample CSS sheet with various constraint specifications can be found at:

<installdir>/jviews-diagrammer/codefragments/graphlayout/hierarchicallayout/constraints/resources/SampleCSS.css.

For further details about specifying constraints in Java™, see the class IlvGraphLayoutRenderer.

The following table lists all constraint properties that are available in CSS.

The Hierarchical Layout allows you to specify the level index and the position index of a node.

Specify the level and position index of a node with ID “ node1 ” in the following way:

You specify the level and position index of a graphic node in the following way:

How these indexes are used depends on the graph topology and the additional constraints. For example, the specified level index can be in conflict with some IlvLevelRangeConstraint or IlvSameLevelConstraint. In this case, the constraint priorities determine how the conflict is resolved (see Constraint priorities (HL)). If the incremental mode is enabled, the specified node level and position index are ignored, since the incremental mode tries to preserve old node positions. It is also possible to obtain the indexes of nodes that were calculated during layout.

Calculated level index

The layout algorithm allows you to access the level index that was calculated for a node by a previous layout. Use the method:

If the node was never laid out, this method returns -1. Otherwise, it returns the previous level index of the node.

In an application that specifies layout parameters entirely in Java, the method can be used to specify the level index for the next layout in the following way:

It ensures that the node is placed at the same level as in the previous layout.

If the graph is detached from the layout algorithm, the calculated level index of a node is set back to -1.

Calculated position index

The layout algorithm allows you to access the position index within a level that was calculated for a node by a previous layout. Use the method:

If the node was never laid out, this method returns -1. Otherwise, it returns the previous position index of the node within its level.

To ensure that the node is placed at the same level at the same relative position as in the previous layout, use the following code in an application that specifies layout parameters entirely in Java:

This example code works only if the generic connected component layout is disabled and the port sides EAST or WEST are not used in the layout.

If the graph is detached from the layout algorithm, the calculated position index of a node is set back to -1.

A graph that is a node in another graph is called a subgraph. Links that connect nodes of different subgraphs are called intergraph links. In Recursive hierarchical layout on nested graph with polyline link style, all red links are intergraph links and all black links are normal links. This is explained in detail in Nested layouts.

Hierarchical layout can treat a nested graph at once, placing all nested nodes and routing all links including the intergraph links.

Hierarchical layout can even place the labels in the nested graph.

To enable recursive mode:

Add to the GraphLayout section:

Use this method:

and call performLayout with the third parameter set to true in the following way:

Recursive layout mode requires that all subgraphs are laid out in the same style (for example, they must all use the same flow direction). This is automatically the case when calling layout.performLayout(force, redraw, true) and it is also the case when using CSS without specifying individual graph layouts per subgraph. If different layout styles are needed per subgraph, you must specify an individual layout per subgraph as described in Individual layout styles per subgraph and in Advanced recursion: mixing different layouts in a nested graph.

In this case, hierarchical layout cannot route the intergraph links and you must use a Link Layout algorithm to route the intergraph links.

Setting layout parameters in recursive mode

When you use CSS, the layout parameters are specified in CSS as usual, and the SDM engine handles the internal details automatically.

When you want to specify layout parameters in Java™ code, in recursive layout mode, the hierarchical layout is attached to the top-level graph. Global layout parameters must be set on this layout instance. Layout parameters per node or per link must be set in the following way:

This means that layout parameters per node or per link cannot be set on the top-level layout, but on a sublayout retrieved by means of IlvRecursiveLayout from the top-level layout.

Layout constraints in recursive layout mode work only between nodes that belong to the same subgraph. Constraints among nodes of different subgraphs are ignored. The concepts EAST, WEST, NORTH, SOUTH of extremity constraints are interpreted relative to the subgraph, not relative to the global graph. Similarly to the layout parameters per node or per link, the constraint must be installed at the layout instance of the subgraph of the node.

Swimlane constraints do not work in recursive layout mode at all.

Label layout

If recursive layout mode is enabled, hierarchical layout can also place the node and link labels. This feature is useful, because placing labels after a recursive layout can change the bounds of subgraphs again and would therefore require the hierarchical layout to rerun. Therefore, an annealing label layout is integrated into the hierarchical layout that is executed during recursive layout mode.

When recursive layout mode is used, label layout is automatically used. Keep label layout enabled if nodes or links in subgraphs have labels. It can be disabled if there are no labels.

To disable label layout:

To set label descriptors, you can access this label layout by using the following code:

If the labels are contained in a subgraph, use the following code:

For more details on how to use IlvAnnealingLabelLayout, see Annealing label layout. For more details on how to use IlvRecursiveLayout, see Recursive layout.