The TML algorithm

> > > > >

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

In CSS

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

SDM {
    GraphLayout : "true";
    LinkLayout  : "false";
}

 GraphLayout {
    enabled                               : "true";
    graphLayout                           : "TopologicalMesh";
    allowedOptimizationTime               : "20000";
    allowedNumberOfOptimizationIterations : "5";
    allowedNodesPlacementTime             : "20000";
    nodesPlacementAlgorithm               : "SLOW_GOOD";
     linkStyle                                       : "STRAIGHT_LINE_STYLE";
         }

In Java™

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:

 ...
import ilog.views.*;
import ilog.views.graphlayout.*;
import ilog.views.graphlayout.topologicalmesh.*;
 ...
IlvGrapher grapher = new IlvGrapher();
IlvManagerView view = new IlvManagerView(grapher);

 ... /*   Fill in the grapher with nodes and links here */

IlvTopologicalMeshLayout layout = new IlvTopologicalMeshLayout();
layout.attach(grapher);
try {
        IlvTopologicalMeshLayoutReport layoutReport =
              (IlvTopologicalMeshLayoutReport)layout.performLayout();

        int code = layoutReport.getCode();

        System.out.println("Layout completed (" +
          layoutReport.codeToString(code) + ")");
}
catch (IlvGraphLayoutException e) {
        System.err.println(e.getMessage());
}

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

Important

All explanations in the subsequent sections regarding the shape of the links in Topological Mesh Layout are valid only if the link layout is disabled.

Current section

Topological Mesh Layout (TML)