Incremental Diagram Layout
Adding new items to an existing diagram without changing the overall picture
Arranging graph elements by hand in a clear and readable way that emphasizes the specific features of a diagram is cumbersome and labor-intensive. So obviously, one would use an automatic layout algorithm. In an interactive scenario, however, there is a hidden pitfall.
When the user is allowed to create or remove elements, applying a basic automatic layout algorithm can have a big disadvantage. Small changes in data, e.g., adding a single new element, may lead to dramatic changes in the resulting drawing. However, the main objective of such use cases is usually to preserve the users' mental map of the diagram. Therefore, it is essential to keep the positions of the existing elements as stable as possible. Figure 1 shows a diagram that is arranged hierarchically. In this kind of layout, the algorithm emphasizes the edge flow by placing nodes above their successors subject to the flow direction. In Figure 2, a new node is inserted in a way that disturbs the flow, which causes a major re-arrangement.
An automatic layout algorithm that inserts new elements into an existing diagram without re-arranging the existing ones is called an incremental layout algorithm. In Figure 4, the new node is placed in the same position as before, but this time an incremental algorithm is applied. Note that the existing nodes are moved slightly, but without changing their relative positions. This strategy allows inserting space for the new node and keeping the edges as straight as possible.
Automatic layout algorithms are one of the key features of the commercial programming library yFiles. All major layout styles support incremental layout. Most notably are the flagship algorithms incremental layout (as shown in this example) and force-directed layout. yFiles also supports a so-called partial layout that arranges a sub-set of the diagram and fits it into the otherwise unchanged diagram.
yFiles comes with an Incremental Hierarchic Layout Sample Application. This application demonstrates the incremental mode of the hierarchic layout and visualizes the different layers in the background. Users can add new nodes and edges or change the layers of existing elements. After each user action, a new layout run is applied to ensure that the diagram is always well-organized without changing the current drawing too much.
The source code of the Incremental Hierarchic Layout Sample Application is part of all yFiles packages and available on the yWorks Github repository: