General Purpose Layout Documentation

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation; with no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts. A copy of the license is included in the section entitled "GNU Free Documentation License".


How does it work ?

The "General Purpose Layout" combines a tree algorithm and an energy algorithm backed by several optimization methods (mainly a modified-Newton method and Simulated Annealing algorithm).The structure of the graph is probed, and the graph is divided in linked components of two types : sub-trees and loops. Each component is drawn independently -- sub-trees using the tree algorithm, loops using the energy algorithm. The components are then combined together in a tree-like fashion.

What are the different options for ?

The "Ideal Distance" and "Y-ideal Distance" fields rule distances between nodes. In the tree-parts of the graph, "Ideal Distance" and "Y-ideal Distance" are respectively the horizontal and vertical distances between nodes. In the "loop-parts" of the graph, the energy algorithm tries to ensure a uniform distance equal to "Ideal Distance" between two linked nodes.

The field "Max Nb of Steps" allows you to set the maximum number of steps for the energy algorithm. One step corresponds to the modification of the position of one node. When setting the maximal number of steps you should remember that each node needs to be placed, and its position optimized, and that this is all the more costly that the structure of the loop is complex (high number of nodes / edges). If the number of steps specified is less than the number of nodes to place, the "Fast" option will be used instead.

The Fast option disables the use of the energy algorithm for drawing the loops when ticked. The nodes belonging to a loop are then uniformly placed on a circle, in an attempt to form a regular polygon. This option significantly speeds-up the algorithm. There are several cases in which you may want to choose this option :

if you know that the loops in your graph are indeed forming regular polygons ;

if you know that the loops in your graph are "small" (then this is likely to yield satisfactory results) ;

if you want to draw a large graph, and do not care for an optimal drawing of each loop.

The "Start Again" option allows you to restart the drawing algorithm from scratch without having to reset your model.

Redraw and Modifications to the Graph

When new nodes are added, only the newly formed or modified loops will be redrawn. If the new nodes can be placed without creating too many disturbances to the loop, the overall configuration will stay the same. However if the new nodes generate important modifications to the loop structure, the layout may change radically. If a redraw is toggled with no new nodes, the energy algorithm will try to improve the layout of each loop (assuming the "fast" option is off ; if the "fast" option is on, the result will be the same).

What performances to expect ?

This depends radically on your options choice. You have to keep in mind that the tree algorithm is fast and the energy algorithm slow. Drawing trees, mixed tree-loop structures with loops up to 3 nodes (or with bigger loops but the "Fast" option also on) will be fast -- less than 1 second for 100,000 nodes -- as no energy optimization is required. When the energy algorithm is used, the computational cost depends on the maximum number of steps allowed (field "Max Nb of Steps") and the number of nodes (about one second for the AntSimulation graph [60 nodes] with Max Nb of Steps = 25,000).