The TML algorithm

TML is a heuristical 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 Java
Below is a code sample using the IlvTopologicalMeshLayout class. This code sample shows how to perform a Topological Mesh Layout: 
 ...
import ilog.views.*;
import ilog.views.eclipse.graphlayout.GraphModel;
import ilog.views.eclipse.graphlayout.runtime.*;
import ilog.views.eclipse.graphlayout.runtime.topologicalmesh.*;
 ...

IlvTopologicalMeshLayout layout = new IlvTopologicalMeshLayout();
GraphModel graphModel = new GraphModel(myGrapherEditPart);
layout.attach(graphModel);
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());
}
layout.detach();
graphModel.dispose();
It is possible to enable the link layout additionally, and in this case, the link layout determines the shape of the links.
Important
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
PREVIOUS  NEXT