Gives information on the Topological Mesh Layout (TML) algorithm (class IlvTopologicalMeshLayout from the package ilog.views.graphlayout.topologicalmesh).

TML samples

The following sample drawings were produced with TML.

What types of graphs suit the TML?

Application domains for the TML

Application domains of the Topological Mesh Layout include:

Features

Limitations

TML is a heuristic approach for the layout of cyclic graph, either planar graphs or nonplanar graphs. TML is very simple to use. However, to use all the functionality of TML, you should understand its basic concepts.

When laying out a general graph, producing a drawing with a minimum number of link crossings is a mathematically NP-complete problem. The search space (and time) grows exponentially with the graph size. Traditionally, most of the existing layout algorithms use node coordinates from the beginning, searching for a coordinate set to minimize the cost function, which is mainly the number of link crossings. These coordinates can be constrained on a grid, but the number of combinations to explore is still enormous.

In contrast, TML uses a two-step approach that drastically reduces the number of combinations to explore. The first step of TML deals only with the pure topology (that is, the connectivity) of the graph without taking into consideration the node coordinates. This first step is called topological optimization. It chooses one of the cycles of the graph to be used in the second step.

In the second step, called node placement, the result of the first step is used to compute the coordinates of the nodes using a deterministic, high-speed barycenter algorithm. Of course, the problem still remains NP-complete and large graphs cannot be processed. In practice, however, you will often get better results for “mesh” graphs with TML than with many other algorithms.

Step 1: Topological optimization

Input

The topology of the graph (its connectivity or the neighborhood relationships between nodes).

Output

A set of possible outer cycles, ordered decreasingly by their lengths. The length of a cycle is the number of nodes in the cycle.

Explanation

This step determines what cycles of the graph, if used as an outer cycle for drawing the graph during nodes placement, will allow a drawing with a minimum number of link crossings. An optimization algorithm tries to minimize a heuristic cost function that estimates the number of link crossings for each solution, based on pure topology (graph connectivity)

Step 2: Node placement

Input

The output of topological optimization and the graph.

Output

A set of coordinates for the nodes. The coordinates are assigned to the nodes to obtain the graph drawing.

Explanation

This step is a variant of the “barycentric” layout algorithm. It takes a cycle from the output of topological optimization and draws it as a regular polygon. Then, it iteratively moves each node (except those on the regular polygon) at the “barycenter” of its neighbors (the nodes to which it is connected). This procedure always converges, and the final result is a graph drawing where the number of link crossings is dependent only on the choice of the outer cycle.

Example of TML

Below is an example of specification in CSS using the Topological Mesh Layout algorithm. Since the Topological Mesh 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 JViews Diagrammer).

Below is a code sample using the IlvTopologicalMeshLayout class. This code sample shows how to perform a Topological Mesh Layout on a grapher directly without using a diagram component or any style sheet:

It is possible to enable the link layout additionally, and in this case, the link layout determines the shape of the links.

Overview (TML)

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

Note that all the methods allowing the modification of these parameters are overridden in this subclass. This class keeps track of the changes for parameters that may affect the result of Topological Optimization separately from the parameters that may affect only the nodes placement step. In this way, the Topological Optimization step is not repeated. The previous results are used if no parameters were modified since the last time the layout was successfully performed on the same graph using the same layout instance.

Allowed time (TML)

The Topological Optimization step of TML stops if the allowed time setting has elapsed. In the same manner, the Nodes Placement step of TML stops if the allowed time is exceeded. (See Allowed time.)

You can specify separate time settings for each step. Each step is stopped if its specified time limit is exceeded. To learn how to do this, see Optimization iterations and allowed time (TML) and Node placement iterations and allowed time (TML).

Animation (TML)

In TML, the animation parameter (see Animation) is used only in the Nodes Placement step. If specified, a redraw will be automatically performed after each iteration of the step. This is useful to better understand what is happening during the step and especially if you want to be able to choose the fixed nodes in a manual refinement procedure. (See Using fixed nodes (TML).)

Layout of connected components (TML)

The layout algorithm can use the generic mechanism to lay out connected components. (For more information about this mechanism, see Layout of connected components.)

If the generic connected component layout mechanism is disabled, the algorithm lays out only the connected component that contains the starting node.

Layout region (TML)

The Nodes Placement step of TML first draws the outer cycle computed in the Topological Optimization step as a regular polygon. It uses the layout region setting (either your own or the default setting) to choose the size and the position of the polygon. The remaining nodes are moved inside this polygon. All three ways to specify the layout region are available for this subclass. (See Layout region.)

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.

If TML produces a layout with overlapping nodes, one possible way to correct the problem is to increase the size of the layout region. (For details, see Using the layout region parameter (TML).)

Link clipping (TML)

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 the TML for details of the link clipping mechanism in TML.

Link connection box (TML)

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. See IlvBasicLinkStyleLayout.supportsLinkConnectionBox() for details.

Memory savings (TML)

As with all classes supporting this parameter, a certain amount of memory savings can be obtained by selecting this option. Note that using this option does not change the resulting layout. It just slows down the computation. (See Memory savings.)

Preserve fixed links (TML)

TML does not reshape the links that are specified as fixed. (See Preserve fixed links. See also Link style (TML).)

Preserve fixed nodes (TML)

TML 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.)

If TML produces a layout with overlapping nodes, you can use the fixed nodes mechanism to correct the problem. (For details, see Using fixed nodes (TML).)

Save parameters to named properties (TML)

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

Stop immediately (TML)

The layout algorithm stops after cleanup if the method IlvTopologicalMeshLayout 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_INVALID.

The following parameters are specific to the IlvTopologicalMeshLayout class.

Link style (TML)

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 may not be appropriate because the intermediate points of the link will not be 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 layout algorithm automatically remove all the intermediate points of the links (if any):

Add to the GraphLayout section:

Use the method:

The valid values for style are:

Connect links to node center (TML)

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 (TML)

This feature is shared by all subclasses of the Basic Link Style Layout. See Multilink and self-link features for details.

Optimization iterations and allowed time (TML)

The iterative computation performed in the Topological Optimization step is stopped if the number of iterations exceeds the allowed number of iterations for optimization or the time exceeds the allowed time for optimization (or, of course, if the general layout time has elapsed; see Allowed time (TML)).

To specify the parameters:

Add to the GraphLayout section:

Use the methods:

The time is in milliseconds. The default value is 28000 (28 seconds).

Node placement iterations and allowed time (TML)

The iterative computation performed in the Nodes Placement step is stopped if the number of iterations exceeds the allowed number of iterations or the time exceeds the allowed time for node placement (or, of course, if the general layout time has elapsed; see Allowed time (TML)).

To specify these parameters:

Add to the GraphLayout section:

Use the methods:

The time is in milliseconds. The default value is 28000 (28 seconds).

Node placement algorithm (TML)

Two barycentric algorithms are implemented for the Nodes Placement step of TML.

To specify the algorithm:

Add to the GraphLayout section:

Use the method:

The valid values for option are:

In most cases, both algorithms are fairly quick. We recommend that you use the SLOW_GOOD version, which is the default value. Compare the layouts of the same graph in Node placement algorithm: SLOW_GOOD and Node placement algorithm: QUICK_BAD to get an idea of the difference between these algorithms.

In CSS, you omit the prefix IlvTopologicalMeshLayout when specifying the value of the nodes placement.

Outer cycle (TML)

The Topological Optimization step of TML computes a set of cycles that can be used as the outer cycle in the Nodes Placement step. By default, the longest cycle is actually used (that is, the cycle containing the largest number of nodes). However, you may find it useful to try a different outer cycle. To do so in Java, use the method:

The valid values for cycleId range from zero to the number of cycles computed by the Topological Optimization step minus one. This number is returned by the method:

If the number is not in this range, the value zero is used.

You can use these methods only after having performed the layout successfully. Otherwise, no outer cycle is defined.

When the layout is performed again with a new outer cycle, only the Nodes Placement step of TML is performed, and not the time-consuming the Topological Optimization step. This is true if the topology of the graph has not been changed (that is, no nodes or links were added or removed), and no parameters that affect the Topological Optimization step have been changed.

Layout using 1st outer cycle, Layout using 2nd outer cycle, Layout using 3rd outer cycle, and Layout using 4th outer cycle show various layouts produced for the same graph when the cycleId parameter is changed:

After performing the layout on a graph, you may want to improve the quality of the layout by making some manual refinements. The subsequent sections describe several ways to refine your layouts. When the layout is performed again after the refinements have been applied, only the Nodes placement step of TML is redone. The results of the Topological Optimization are reused. This is an important benefit of TML because the algorithm can recompute a layout using new parameters very quickly, without performing the time-consuming Topological Optimization step again.

Using fixed nodes (TML)

One reason for applying manual refinements is to avoid overlapping nodes. To do this, you can use the fixed nodes mechanism. (See Preserve fixed nodes.)

Take a look at the original layout shown in The original layout with TML. Several overlapping nodes exist in the original layout because the nodes are concentrated in a small region and do not use the available space inside the outer cycle.

To correct the problem, you can perform the following steps:

Using the outer cycle parameter (TML)

By default, the Nodes Placement step of TML produces a layout using the longest outer cycle computed in the Topological Optimization step. (The length of a cycle is the number of nodes that compose the cycle.) Sometimes, a better layout can be obtained using a different choice of the outer cycle. This process of changing the outer cycle parameter and performing the layout again (see Outer cycle (TML)a) is a manual refinement procedure that can also be used to avoid overlapping nodes.

Note that performing the layout with a new outer cycle requires very little CPU time.

Using the layout region parameter (TML)

Often, overlapping nodes can be avoided by simply increasing the size of the layout region (see Layout region (TML)). Layout with small layout region and overlapping nodes shows a graph drawing where several nodes overlap because the layout region is too small for the graph. Layout with larger layout region and no overlapping nodes shows the same graph after increasing the size of the layout region. As you can see, now there are no overlapping nodes.

By default, TML 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 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.

To set a link clip interface:

It is not possible to set the link clip interface. See Link clipping.

Use the method: