Concepts

The task of a layout algorithm is a major undertaking that involves arbitrarily complex logic. However, there can be identified a number of well-defined (sub-)tasks that even completely different algorithms do in a similar manner. Factoring out such tasks so that they can be reused in varying contexts, greatly reduces the complexity of any layout algorithm.

The yFiles library allows to formulate complex layout processes by plugging together so-called "layout stages" that, among other things, can be used to handle such well-defined (sub-)tasks.

The Layout Stages Concept

A layout stage serves as a kind of container that encapsulates arbitrary layout functionality, and provides a general means to string together multiple stages into a compound layout process. Interface ILayoutStage defines the basis for a layout stage. It is a specialization of interface ILayouter, and thus can be used as a stand-alone layout provider as well as a part of a larger layout process.

Figure 10.2. ILayoutStage

ILayoutStage.

The property of interface ILayoutStage is used to establish a relationship to another ILayouter implementation, the so-called "core layouter." The core layouter's invocation is entirely bracketed by the layout stage's logic.

When used in the context of a larger layout process, the layout stage can easily be used to simplify the core layouter's task. It performs preprocessing steps on the input graph before the core layouter's invocation, and postprocessing steps thereafter.

Table 10.1, “Predefined layout stages” lists some of the predefined ILayoutStage implementations, most of them being part of the default compound layout process as described below. Further layout stages are described in the section called “Layout Stages”.

Table 10.1. Predefined layout stages

Classname Description
SelfLoopLayouter Calculates orthogonal edge paths for a graph's self-loops (reflexive edges).
ParallelEdgeLayouter Calculates edge paths for all edges with identical source node and target node. (Self-loops are not processed.)
OrientationLayouter Changes the orientation of a computed layout.
SubgraphLayouter Reduces the original graph to the subgraph that is induced by selected nodes.

Figure 10.3, “Layout stages complex” shows the class hierarchy for the layout stages.

Figure 10.3. Layout stages complex

Layout stages complex.

Default Compound Layout Process

The most prominent example for a complex layout process can be observed with abstract class CanonicMultiStageLayouter. It is the superclass for the yFiles major layout algorithms, and provides a conveniently configurable layout pipeline for performing preprocessing steps on the input graph before the core layouter's invocation, and postprocessing steps thereafter. The central role of CanonicMultiStageLayouter can also be seen in Figure 10.10, “The yFiles layout algorithms”.

All layout stages from Table 10.1, “Predefined layout stages” are part of the compound layout process defined by CanonicMultiStageLayouter. The following methods and properties of class CanonicMultiStageLayouter can be used for configuring the layout process:

void AppendStage(ILayoutStage stage)
void PrependStage(ILayoutStage stage)
void RemoveStage(ILayoutStage stage)
Description Methods to add and remove individual layout stages.
void EnableOnlyCore()
bool ComponentLayouterEnabled { get; set; }
bool SelfLoopLayouterEnabled { get; set; }
bool LabelLayouterEnabled { get; set; }
Description Methods and properties for enabling and disabling the predefined layout stages, and also for controlling their enabled state. (Excerpt.)
ILayoutStage ComponentLayouter { get; set; }
ILayoutStage SelfLoopLayouter { get; set; }
ILayoutStage LabelLayouter { get; set; }
Description Properties for predefined layout stages. (Excerpt.)

Providing Supplemental Layout Data

The yFiles layout algorithms support advanced functionality that can take into account even individual information for single graph elements. However, individual setup like, e.g., attaching a preferred edge length to each edge, is beyond the means a graph structure provides. Instead, a data provision scheme is used to provide the individual setup as supplemental information to a layout algorithm.

The supplemental data for the graph elements is bound to the graph using a so-called "data provider key." During layout calculation, the algorithm then retrieves the data provider that contains the data from the graph by using the same key.

Depending on the data provider key, the algorithm expects the returned data provider to hold values of specific type for either nodes or edges of the graph. Example 10.4, “Binding supplemental data (IGraph API)” shows the use of an IMapper as the data provider for an IGraph-based graph. The mapper returns an integral value for each edge indicating the edge's preferred length to the organic layout algorithm.

Example 10.4. Binding supplemental data (IGraph API)

// 'graph' is of type yWorks.yFiles.UI.Model.IGraph.

// Create an implicit IMapper and add it to the mapper registry of the graph
// using a so-called data provider look-up key as its tag.
// The key is then used by the layout algorithm to retrieve the supplemental
// data.
graph.MapperRegistry.AddMapper<IEdge, int>(
    SmartOrganicLayouter.PreferredEdgeLengthDpKey,
    delegate(IEdge e) { return (int)(200 * GetLength(e)); }
);

// Invoke organic layout on the graph.
SmartOrganicLayouter sol = new SmartOrganicLayouter();
graph.ApplyLayout(sol);

Abort Mechanism for Layout Calculations

Class AbortHandler provides an abort mechanism for layout calculations. This mechanism can be used to trigger early termination as well as instant termination of a layout calculation.

The abort handler for a graph is specified through a data provider that is bound to the graph. The data provider is expected to be registered with the graph using key AbortHandlerDpKey. Once an abort handler is attached to a graph, any layout algorithm with support for the abort mechanism working on this graph can be stopped or canceled using the abort handler's methods.

AbortHandler CreateForGraph(LayoutGraph graph)
Description Returns a graph's attached abort handler or creates a new one and attaches it.
void Stop()
void Cancel()
Description Methods to trigger termination of layout calculations.

Stopping the layout calculation results in early, but not immediate, termination where the layout algorithm still delivers a consistent result.

Canceling, in contrast, will end layout calculation instantly, throwing an AlgorithmAbortedException and all work done so far by the algorithm will be discarded. This may lead to an inconsistent state of the graph. It is thus recommended to only cancel layout algorithms that work on a copy of the graph to avoid corrupting the original graph.

Furthermore, when layout calculation is ended instantly, the state of the ILayouter instance may become corrupted. Hence, a new instance has to be created after each cancelation.

If a graph that has an AbortHandler attached is processed by multiple layout algorithms (or multiple times by one layout algorithm), then the attached handler has to be reset between algorithm runs:

void Reset()
Description Resets the abort handler's state so that any requests for early termination are discarded.

Otherwise, previous requests for early termination may lead to an undesired early termination of a subsequent algorithm run.

Automatic layout calculation for a diagram in conjunction with an abort handler that has a runtime threshold configured can be conveniently invoked using class LayoutExecutor as outlined in the following code snippet. LayoutExecutor uses the given AbortHandler object and performs all necessary setup prior to the layout calculation. It registers a data provider holding the abort handler with the proper graph and also resets the abort handler's state.

Example 10.5. Using an abort handler in conjunction with class LayoutExecutor

// 'graphControl' is of type yWorks.yFiles.UI.GraphControl.

// Create a layout algorithm.
IncrementalHierarchicLayouter ihl = new IncrementalHierarchicLayouter();

// Create an abort handler.
AbortHandler handler = new AbortHandler();

// Specify a runtime threshold before the layout algorithm is stopped...
handler.StopDuration = 30000;

// ... OR specify a runtime threshold before it is canceled.
handler.CancelDuration = 30000;
          
try {
  var layoutExecutor = new LayoutExecutor(graphControl, ihl) {
                             // Use the abort handler created before.
                             AbortHandler = handler;

                             Duration = TimeSpan.FromMilliseconds(500),
                             UpdateContentRect = true };

  // Start layout calculation here.
  layoutExecutor.Start();
}
catch (Exception exception) {
  Console.WriteLine(exception);
}

The following layout algorithms and routing algorithms of the yFiles for Silverlight library have built-in support for the abort mechanism:

Table 10.2. Support for abort mechanism in yFiles algorithms

  Classname
Layout algorithms IncrementalHierarchicLayouter
CircularLayouter
SmartOrganicLayouter
OrthogonalLayouter, OrthogonalGroupLayouter, DirectedOrthogonalLayouter, and CompactOrthogonalLayouter
Layout stages ComponentLayouter
ParallelEdgeLayouter
Routing algorithms EdgeRouter

Tutorial demo application AbortHandlerWindow shows how to create and use an abort handler when performing a layout calculation.