Uniform Length Edges (ULEL)
Describes the Uniform Length Edges Layout algorithm.
Provides samples of the layout and explains where it is likely to be used.
Lists the features and limitations of the layout.
Gives an explanation of the ULEL algorithm and a sample.
Lists the generic features and parameters of the Uniform Length Edges layout (ULEL).
Describes the specific parameters supported by ULEL and gives samples of their use.
Describes parameters for expert users.
Describes the use of a link clipping interface with the Uniform Length Edges Layout (ULEL).
General information about the ULEL
ULEL samples
These samples show the use of the Uniform Length Edges layout (class
IlvUniformLengthEdgesLayout from the package
ilog.views.graphlayout.uniformlengthedges).
The following sample drawings are produced with the Uniform Length Edges Layout (ULEL).
Small cyclic graph drawing produced with Uniform Length Edges Layout
Medium graph drawing (combination of cycles and trees) produced with the Uniform Length Edges Layout
Large graph drawing (combination of cycles and trees) produced with the Uniform Length Edges Layout
Large graph drawing (Sierpinski Triangle) produced with the Uniform Length Edges Layout in fast multilevel layout mode
What types of graphs suit the ULEL?
Any type of graph:
Application domains for ULEL
Application domains for Uniform Length Edges include:
Telecoms and networking (WAN diagrams)
Software management/software (re-)engineering (call graphs)
CASE tools (dependency diagrams)
Database and knowledge engineering (such as semantic networks, database query graphs, qualitative reasoning, and other artificial intelligence diagrams)
World Wide Web (Web hyperlink neighborhood)
Features and limitations of the ULEL
Features
Often provides a drawing without any or with only a few
link crossings and with equal length links for small- and medium-size graphs having few cycles. The maximum number of nodes for which you can use the algorithm depends on the connectivity of the graph and is difficult to predict.
On demand, the algorithm can take into account the size (width and height) of the nodes. Otherwise, they are more efficiently considered as points.
It is possible to specify the length for each link individually.
The algorithm provides three optional layout modes: incremental, nonincremental, and fast multilevel. The nonincremental and fast multilevel modes are in general faster and are recommended for large graphs. For details, see
Layout mode.
Limitations
The algorithm is not appropriate for all graphs. In particular, it produces bad results on some highly connected
cyclic graphs for which a planar drawing with equal-length links might not exist.
The computation time required to obtain an appropriate drawing grows relatively quickly with the size of the graph (that is, the number of nodes and links) and the layout process can become time-consuming for large graphs.
Overlapping nodes cannot always be avoided. Nevertheless, the layout algorithm often produces a drawing with no overlapping nodes.
The ULEL algorithm
This layout algorithm iteratively searches for a configuration of the graph where the length of the links is close to a user-defined or a default value.
Example of ULEL algorithm
In CSS
The following example of a specification in CSS uses the Uniform Length Edges Layout algorithm. Since the Uniform Length Edges Layout places nodes and reshapes the links, it is usually not necessary to specify an additional link layout in CSS. The specification in CSS can be loaded as a style file into an application that uses the
IlvDiagrammer class (see Graph Layout in Rogue Wave®
JViews Diagrammer).
SDM {
GraphLayout : "true";
LinkLayout : "false";
}
GraphLayout {
graphLayout : "UniformLengthEdges";
linkStyle : "STRAIGHT_LINE_STYLE";
preferredLinksLength : "30";
respectNodeSizes : "true";
layoutMode : "FAST_MULTILEVEL_MODE";
}
It is possible to enable the link layout additionally, and in this case, the link layout determines the shape of the links.
In Java
The following code sample uses the
IlvUniformLengthEdgesLayout class. This code sample shows how to perform a Uniform Length Edges Layout on a grapher directly without using a diagram component or any style sheet:
...
import ilog.views.*;
import ilog.views.graphlayout.*;
import ilog.views.graphlayout.uniformlengthedges.*;
...
IlvGrapher grapher = new IlvGrapher();
IlvManagerView view = new IlvManagerView(grapher);
... /* Fill in the grapher with nodes and links here */
IlvUniformLengthEdgesLayout layout = new
IlvUniformLengthEdgesLayout();
layout.attach(grapher);
try {
IlvUniformLengthEdgesLayoutReport layoutReport =
layout.performLayout();
int code = layoutReport.getCode();
System.out.println("Layout completed (" +
layoutReport.codeToString(code) + ")");
}
catch (IlvGraphLayoutException e) {
System.err.println(e.getMessage());
}
Important All explanations in the subsequent sections regarding the shape of the links in Uniform Length Edges Layout are valid only if the link layout is disabled.
Generic features and parameters of the ULEL
Overview (ULEL)
The
IlvUniformLengthEdgesLayout class supports the following generic parameters defined in the
IlvGraphLayout class (see
Base class parameters and features):
The following subsections describe the particular way in which these parameters are used by this subclass.
Allowed time (ULEL)
The layout algorithm stops if the allowed time setting has elapsed. (See
Allowed time.)
Animation (ULEL)
If animation is specified, a redraw is automatically performed after each step of the layout algorithm. (See
Animation.)
Layout of connected components (ULEL)
The layout algorithm can use the generic mechanism to lay out connected components. (For more information about this mechanism; see
Layout of connected components.)
Layout region (ULEL)
The layout algorithm can use the layout region setting (either your own or the default setting) to control the size and the position of the graph drawing. All three ways to specify the layout region are available for this subclass. (See
Layout region.)
By default, the Uniform Length Edges Layout algorithm does not use the layout region. (For details see also
Force fit to layout region (ULEL).)
Remember that if you are using the default settings, the visible area of the manager
view (an instance of
IlvManagerView) attached to the grapher is used as a layout region. If several manager views are attached, the first attached view is used. If no manager view is attached, the layout region is automatically estimated on the basis of the number and size of the nodes.
Link clipping (ULEL)
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 nonrectangular 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 with ULEL for details of the link clipping mechanism.
Link connection box (ULEL)
The layout algorithm can use a link connection box interface to calculate the center of a node. See
Link connection box.
It is used when the option to connect links to node centers or link clipping is enabled.
It is only used if the link style is straight line. It is also used for self-links and multilinks, depending on the self-link or multilink mode.
Preserve fixed links (ULEL)
The layout algorithm does not reshape the links that are specified as fixed. (See
Preserve fixed links and
Link style (ULEL).)
Preserve fixed nodes (ULEL)
The layout algorithm does not move the nodes that are specified as fixed. Moreover, the algorithm takes into account the fixed nodes when computing the position of the nonfixed nodes. (See
Preserve fixed nodes.)
Save parameters to named properties (ULEL)
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 (ULEL)
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 result code in the layout report is
IlvGraphLayoutReport.STOPPED_AND_VALID.
Specific parameters of ULEL
The following parameters are specific to the
IlvUniformLengthEdgesLayout class.
Link style (ULEL)
When the layout algorithm moves the nodes,
straight-line links (such as instances of
IlvLinkImage) will automatically “follow” the new positions of their end nodes. If the grapher contains other types of links (for example,
IlvPolylineLinkImage or
IlvSplineLinkImage), the shape of the link might not be appropriate because the intermediate points of the link are not moved. In this case, you can ask the layout algorithm to automatically remove all the intermediate points of the links (if any).
To specify that the algorithm automatically removes all the intermediate points of the links (if any):
In CSS
Add to the GraphLayout section:
linkStyle: "STRAIGHT_LINE_STYLE";
In Java
Use this method:
void setLinkStyle(int style)
The valid values for style are:
IlvUniformLengthEdgesLayout.NO_RESHAPE_STYLE None of the links is reshaped in any way.
IlvUniformLengthEdgesLayout.STRAIGHT_LINE_STYLE All the intermediate points of the links (if any) are removed. This value is the default.
NOTE If you use CSS in a diagram component (instance of IlvDiagrammer), you must specify the correct link class in the style sheet. We recommend that you use
IlvGeneralLink or
IlvSimpleLink as classes for links in this case. If you call layout on an IlvGrapher directly in Java, you can use the method
EnsureAppropriateLinkTypes or
EnsureAppropriateLinks defined in the class
IlvGraphLayoutUtil to replace inappropriate links 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.
NOTE If you call layout on an
IlvGrapher directly in Java, you can use the method
EnsureAppropriateLinkTypes or
EnsureAppropriateLinks defined in the class
IlvGraphLayoutUtil to replace inappropriate links 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.
Connect links to node center (ULEL)
This feature is shared by all subclasses of the Basic Link Style Layout. See
Connect links to node center for details.
Multilink and self-link features (ULEL)
These features are shared by all subclasses of the Basic Link Style Layout. See
Multilink and self-link features for details.
Number of iterations (ULEL)
The iterative computation of the layout algorithm is stopped if the time exceeds the allowed time (see
Allowed time) or if the number of iterations exceeds the allowed number of iterations.
To specify the number of iterations:
In CSS
Add to the GraphLayout section:
allowedNumberOfIterations: "5";
In Java
Use the method:
void setAllowedNumberOfIterations(int iterations)
Preferred length (ULEL)
The main objective of this layout algorithm is to obtain a layout where all the links have the same length, called the ““preferred length””.
To specify the preferred length:
Globally
In CSS Add to the GraphLayout section:
preferredLinksLength: "70.0";
It is also possible to specify a length for individual links. To do so:
Individually
In CSS Specify a rule that selects the link:
#link27 {
PreferredLength: "80.0";
}
If a specific length is not specified for a link, the global settings are used.
Globally
In Java Use the method:
void setPreferredLinksLength(float length)
The default value is 60.0.
It is also possible to specify a length for individual links.
Individually
In Java Use the method:
void setPreferredLength(Object link, float length)
To obtain the current value, use the method:
float getPreferredLength(Object link)
If a specific length is not specified for a link, the global settings are used.
Respect node sizes (ULEL)
By default, the layout algorithm ignores the size (width and height) of the nodes. For efficiency reasons, the nodes are approximated with points placed in the center of the bounding box of the nodes. When dealing with large nodes, the preferred length parameter can be increased in such a way that the nodes do not overlap.
To improve the support for graphs with heterogeneous node sizes, the algorithm provides a special mode in which the particular size of each node is taken into consideration.
To set this mode:
In CSS
Add to the GraphLayout section:
respectNodeSizes: "true";
In Java
Use the method:
void setRespectNodeSizes(boolean respect)
The default value is false.
Force fit to layout region (ULEL)
It is difficult to choose an appropriate size for the layout region of this layout algorithm. If the specified layout region is too small for a particular graph, the resulting layout is not the best. For this reason, by default, the Uniform Length Edges Layout algorithm does not use the layout region parameter.
It can use as much space as it needs to lay out the grapher.
To specify whether the layout algorithm must use the layout region:
In CSS
Add to the GraphLayout section:
forceFitToLayoutRegion: "true";
In Java
Use the method:
void setForceFitToLayoutRegion(boolean option)
The default value of the parameter is false.
Layout mode
To fit various needs, the algorithm provides three optional layout modes:
Incremental mode
The algorithm starts from the current position and iteratively tries to converge towards the optimal layout. In some cases, this mode avoids a major reorganization of the graph, which helps to preserve the mental map of the user as much as possible. However, it is not guaranteed and depends on how far the initial position of the nodes is from the position that satisfies the criteria of the algorithm.
Non-incremental mode
The algorithm is free to reorganize the graph without trying to stay close to the initial positions. Often, non-incremental mode is faster than incremental mode, although sometimes at the cost of lower quality.
Fast multilevel mode
The algorithm uses a multilevel graph decomposition strategy that leads to a significant gain in speed. This mode is usually the fastest for medium and large graphs.
The default value is IlvUniformLengthEdgesLayout.INCREMENTAL_MODE.
To set the layout mode:
In CSS
Add to the GraphLayout section:
layoutMode: "FAST_MULTILEVEL_MODE";
In Java
Use the method:
void setLayoutMode(int mode)
For experts: additional features of ULEL
Expert users can use the following parameters.
Maximum allowed move per iteration (ULEL)
At each iteration, the layout algorithm moves the nodes a relatively small amount. This amount must not be too large; otherwise, the algorithm might not converge. It must not be too small either or the number of necessary iterations and the running time increase.
The maximum amount of movement at each iteration is controlled by a parameter.
To set this parameter:
In CSS
Add to the GraphLayout section:
maxAllowedMovePerIteration: "10.0";
In Java
Use the method:
void setMaxAllowedMovePerIteration(float maxMove)
Typical values for this setting are 1 - 30, but it depends on the value of the PreferredLinksLength parameter. For example, if the setting for the PreferredLinksLength parameter is 1000, then a value of 100 for the MaxAllowedMovePerIteration parameter is still meaningful.
Link length weight (ULEL)
The layout algorithm is based on the computation of attraction and repulsion forces for each of the nodes and the iterative search of an equilibrium configuration. One of these forces is related to the objective of obtaining a link length close to the specified preferred length. The weight of this force, representing the total amount of force, is controlled by a parameter.
To set this parameter:
In CSS
Add to the GraphLayout section:
linkLengthWeight: "2.25";
In Java
Use the method:
void setLinkLengthWeight(float weight)
The default value is 1. Increasing this parameter can help obtain link lengths closer to the specified length, but increasing too much can increase the number of link crossings.
Additional node repulsion weight (ULEL)
An additional repulsion force can be computed between nodes that are not connected by a link. The weight of this force, representing the total amount of force, is controlled by a parameter.
To set this parameter:
In CSS
Add to the GraphLayout section:
additionalNodeRepulsionWeight: "3.5";
In Java
Use the methods:
void setAdditionalNodeRepulsionWeight(float weight)
The default value of this parameter is
0.2f. Increasing (or decreasing) the weight increases (or decreases) the priority that is given to maintaining the nodes at a distance larger than the node distance threshold (see
setNodeDistanceThreshold). However, increasing the weight also decreases the ability of the algorithm to reach convergence quickly.
The following figures enable you to compare the same graph laid out with additional repulsion disabled (
Additional repulsion disabled, produced with Uniform Length Edges Layout) and then enabled (
Additional repulsion enabled, produced with Uniform Length Edges Layout). You can see that the ““star”” configuration, where many nodes are connected to the same central node, is better displayed when additional repulsion is enabled.
Additional repulsion disabled, produced with Uniform Length Edges Layout
Additional repulsion enabled, produced with Uniform Length Edges Layout
Node distance threshold (ULEL)
The additional repulsion force between two nodes not connected by a link is computed only when their distance is smaller than a predefined distance.
To set this distance:
In CSS
Add to the GraphLayout section:
nodeDistanceThreshold: "4.0";
In Java
Use the method:
void setNodeDistanceThreshold(float threshold)
This additional force is computed only if the additional node repulsion weight is set to a value larger than the default value 0.
It is recommended that this threshold is set to a value smaller than the preferred length of the links.
Fast multilevel mode: maximum percentage of elapsed time for the refinement step (ULEL)
In fast multilevel mode, the algorithm performs a final refinement step. You can set the maximum percentage of the time already elapsed that must be spent on the final refinement step when the layout mode is FAST_MULTILEVEL_MODE. Increasing the value of this parameter can improve the quality of the layout, possibly at the cost of lower speed.
To set this parameter:
In CSS
Add to the GraphLayout section:
maxPercentageOfElapsedTimeForRefinement: "1000";
In Java
Use the method:
void setMaxPercentageOfElapsedTimeForRefinement(float percentage)
This parameter is only used in fast multilevel mode.
Fast multilevel mode: maximum percentage of total time allowed for the refinement step (ULEL)
In fast multilevel mode, the algorithm performs a final refinement step. You can set the maximum percentage of the total time allowed that must be spent on the final refinement step when the layout mode is FAST_MULTILEVEL_MODE. Increasing the value of this parameter can improve the quality of the layout, possibly at the cost of lower speed.
To set this parameter:
In CSS
Add to the GraphLayout section:
maxPercentageOfTotalAllowedTimeForRefinement: "10";
In Java
Use the method:
void setMaxPercentageOfTotalAllowedTimeForRefinement(float percentage)
This parameter is only used in fast multilevel mode.
Fast multilevel mode: maximum repeat for convergence (ULEL)
You can set the maximum number of attempts to reach convergence at each step when the layout mode is FAST_MULTILEVEL_MODE. Increasing the value of this parameter can improve the quality of the layout, possibly at the cost of lower speed.
To set this parameter:
In CSS
Add to the GraphLayout section:
maxRepeatForConvergence: "3";
In Java
Use the method:
void setMaxRepeatForConvergence(int repeat)
This parameter is only used in fast multilevel mode.
Using a link clipping interface with ULEL
By default, Uniform Length Edges Layout does not place the connection points of links. It relies on the link connectors of the nodes to determine the connection points. If no link connectors are installed at the nodes, the default behavior is to connect to a point at the border of the bounding box of the nodes. If the node has a nonrectangular shape such as a triangle, rhombus, or circle, you might 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.
Effect of link clipping interface
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 CSS
It is not possible to set the link clip interface. See
Link clipping.
In Java
Use the method
void setLinkClipInterface(IlvLinkClipInterface interface)
NOTE The link clip interface requires link connectors at the nodes of an
IlvGrapher that allow connector pins to be placed freely at the node border. It is recommended that you use
IlvFreeLinkConnector or
IlvClippingLinkConnector for link connectors to be used in combination with
IlvGrapher objects. The clip link connector updates the clipped connection points automatically during interactive node movements.
Copyright © 2018, Rogue Wave Software, Inc. All Rights Reserved.
