Automatic Label Placement

Both types of graph elements, i.e., nodes and edges, can have one or more labels that can be used to show descriptive text for the element. The label's purpose is served best when it is both readable and also near its element, where readability most importantly results from the label being placed so that it does not overlap with other graph elements.

The yFiles library offers advanced labeling algorithms that automatically generate label arrangements that, whenever feasible, completely eliminate all overlaps, or minimize the number thereof otherwise. Labeling algorithms can be applied in two different scenarios: generic labeling and integrated labeling.

Labeling Scenarios

Generic labeling is independent of any layout algorithms and can be applied to any kind of diagram. It generates label placements without altering node positions, node sizes, or edge paths.

Integrated labeling, in contrast, is directly provided by some layout algorithms as an integrated part of the layout calculation. It allows to consider labels as part of the overall layout.

Integrated labeling's advantage is that, by design, it can prevent label overlaps completely. Generic labeling cannot always achieve this, since it has to deal with the existing node positions, node sizes, and edge paths. However, the graph's dimensions will remain constant or grow only minimally with generic labeling.

Additionally, generic labeling also supports placement of rotated labels, which covers both maintaining a preset rotation angle as well as finding edge label positions where the rotation is determined by the labeling algorithm, too.

Label Models

Both node label and edge label have associated a so-called "label model," that defines a set of valid positions where the label can be placed relative to its respective graph element. In the context of automatic label placement, all valid positions are at the same time "candidates" among which a labeling algorithm can choose the best match to ultimately place the label.

Note

In terms of minimization of overlaps, more candidates mean better prospects for the outcome of a generic labeling algorithm.

For both generic labeling as well as integrated edge labeling, labels and label models are set up using the API provided by IGraph. See also the Label Support section in the section called “Label Support”.

For generic labeling around a node, FreeNodeLabelModel is a much better choice for a node label model than any of the discrete node label models. However, FreeNodeLabelModel allows for unspecified label positions only, while the positions of the discrete node label models are all predefined.

For generic labeling, FreeEdgeLabelModel or SmartEdgeLabelModel with their large number of nearly continuous positions is the best choice for an edge label model, followed by the slider edge label models.

Integrated labeling also favors FreeEdgeLabelModel or SmartEdgeLabelModel, followed by the slider edge label models, since it does not work with the candidates initially. Instead, it first computes an optimal location for the label, and then tries to find the best matching label position for that location in the given label model.

Preferred Placement of Edge Labels

Class PreferredPlacementDescriptor can be used to configure preferred placement options and preferred rotation behavior for edge labels. When calculating edge label positions, the specified settings will be adhered to as good as possible by both the generic labeling algorithms as well as the layout algorithms that support integrated labeling.

Preferred placement options include, for example, whether an edge label shall be positioned

  • on or to the side of the path of its edge
  • near the source node, at the center of the edge path, or near the target node

Preferred rotation behavior includes, for example, whether

  • the edge label's rotation angle shall be interpreted absolute or relative to the slope of its corresponding edge segment
  • the rotation angle of an edge label on the right side of its edge shall be additionally modified to achieve a mirrored orientation compared to an otherwise identically configured edge label on the left

The edge label configurations supported by class PreferredPlacementDescriptor only make sense when the edge label is associated with a label model that supports label rotation and that does not restrict edge label placement to discrete positions. In particular, this applies to the "free" label models FreeEdgeLabelModel or SmartEdgeLabelModel, but also to the slider edge label models.

The following property defined in interface IEdgeLabelLayout returns the PreferredPlacementDescriptor instance that is associated with an edge label:

By default, the PreferredPlacementDescriptor instance that is associated with actual implementations of interface IEdgeLabelLayout, like, e.g., instances of class EdgeLabelLayoutImpl, is immutable. The immutability is a direct consequence of the descriptor instance being shared among newly created edge labels.

Important

Every attempted assignment to a property of such an immutable PreferredPlacementDescriptor instance will yield an exception.

To properly configure individual preferred placement options for an edge label, a dedicated descriptor instance needs to be associated with the label. The following code snippet shows how this can be achieved:

Example 10.41. Creating and associating a new PreferredPlacementDescriptor to configure individual preferred placement options for an edge label

// 'ell' is of type yWorks.yFiles.Layout.EdgeLabelLayoutImpl.

// Create a copy of the edge label's current descriptor using the copy 
// constructor of the class.
PreferredPlacementDescriptor prefPDesc = 
    new PreferredPlacementDescriptor(ell.PreferredPlacementDescriptor);
// Now configure individual preferred placement options on the copy.
...

// Make it immutable (optional).
prefPDesc.Freeze();

// Set the copy as the descriptor for the new edge label.
ell.PreferredPlacementDescriptor = prefPDesc;

The properties of class PreferredPlacementDescriptor to configure preferred placement options are:

An edge label can be placed at the side of the path of its edge. The actual side can be specified both absolute and relative:

Figure 10.100. Absolute and relative edge label placement

Absolute and relative edge label placement
Absolute and relative edge label placement
Absolute placement: left of the edge path when looking at the diagram. Relative placement: left of the edge path when looking from source to target along the edge path.

Note that the SideReference property provides the means to resolve the special case when the edge label's side is specified as an absolute placement and its corresponding edge segment happens to be horizontal, i.e., when there is no actual left or right "side."

The properties to configure preferred rotation behavior:

The arrow-shaped gradient in the background of the label denotes the orientation of its box. Note that in the right figure below the text of the left label is flipped: according to its box's orientation, the text would actually be upside-down, but to be readable it is automatically rendered correctly.

Figure 10.101. Absolute and relative edge label rotation

Absolute and relative edge label rotation
Absolute and relative edge label rotation
Absolute rotation: 0 degree when looking at the diagram. Relative rotation: 0 degree added to the slope of the edge segment that is nearest to the edge label.

In tutorial demo application PreferredLabelPlacementWindow the effects of the edge label configuration supported by class PreferredPlacementDescriptor can be tested in conjunction with both generic edge labeling and integrated edge labeling.

Generic Labeling

A generic labeling algorithm computes label positions for the labels from a given graph so that they, ideally, do not overlap with each other or with graph elements. It does so without altering nodes or edges in any way. Figure 10.102, “Class hierarchy for labeling algorithms” shows the class hierarchy of the generic labeling algorithms that are provided in the yWorks.yFiles.Layout.Labeling namespace.

Figure 10.102. Class hierarchy for labeling algorithms

Class hierarchy for labeling algorithms.

The set of labels that a generic labeling algorithm processes can be restricted to node labels only or to edge labels only:

bool PlaceNodeLabels { get; set; }
bool PlaceEdgeLabels { get; set; }
Description Properties to restrict the set of labels.

Optionally, they can also be configured to auto-flip edge labels to avoid that their text is upside-down:

bool AutoFlippingEnabled { get; set; }
Description Configures auto-flipping for upside-down edge labels.

The labeling algorithm uses the model that is associated with a label to get the available candidate positions. From this set of candidates it then chooses one that best matches the label position it has calculated. The label model's model parameter is then used to encode this position.

It is important to understand that the result of a labeling algorithm is one model parameter per processed label, which is directly stored with the label after calculation. This model parameter expresses the calculated label position with respect to the corresponding label model, and it is only valid in the context of this label model. To get the actual location of a label after the labeling algorithm has finished, both model parameter and corresponding label model are necessary.

The base class for all major layout algorithms, class CanonicMultiStageLayouter, allows to conveniently enable/disable generic labeling for each layout run. The labeling algorithm is then invoked after the actual layout algorithm has finished. Additionally, the labeling algorithm itself can also be set. Class CanonicMultiStageLayouter provides the following labeling-related properties:

bool LabelLayouterEnabled { get; set; }
Description Allows to enable/disable generic as well as integrated labeling.
ILayoutStage LabelLayouter { get; set; }
Description Determines the actual labeling algorithm to be used.

Generic labeling is set up using the label layout layout stage support provided by the base class of the layout algorithms, class CanonicMultiStageLayouter:

IncrementalHierarchicLayouter ihl = new IncrementalHierarchicLayouter();

// Setting up generic edge labeling.
AbstractLabelingAlgorithm labeler = new GreedyMISLabeling();
labeler.PlaceNodeLabels = false;
ihl.LabelLayouter = labeler;
ihl.LabelLayouterEnabled = true;

Using an Alternate Label Model

Instead of a label's actual label model, the generic labeling algorithms can also use an alternate label model when calculating valid positions for it. This can be useful, if the original label model is a free model, but the set of valid positions should be temporarily restricted, for example, to guarantee that an edge label is placed onto its associated edge.

To specify the alternate label models, a data provider holding such supplemental layout data must be bound to the graph. The data provider is expected to be registered with the graph using key LabelModelDpKey.

The following code shows how a data provider that returns an alternate label model for edge labels can be registered with a graph:

Example 10.42. Using alternate edge label models for labeling

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

// Add an implicit IMapper to the mapper registry of the graph.
// Use the "well-known" look-up key defined in class AbstractLabelingAlgorithm 
// as its tag.
// The key is then used by the layout algorithm to retrieve the supplemental
// data.
graph.MapperRegistry.AddMapper<IEdgeLabelLayout, IEdgeLabelModel>(
    AbstractLabelingAlgorithm.LabelModelDpKey,
    delegate(IEdgeLabelLayout ell) {
      return (ell.LabelModel is FreeEdgeLabelLayoutModel) ? 
          new RotatedSliderEdgeLabelLayoutModel(RotatedSliderMode.Center) : 
          // 'null' means that the label's actual label model is used.
          null;
    }
);

Important

One has to use the yFiles for Silverlight Algorithms label models here, i.e. one of the models from the namespace yWorks.yFiles.Layout.

Supplemental Layout Data

The generic labeling algorithms know a number of data provider keys which are used to retrieve supplemental layout data for the labels in a graph. The data is bound to the graph by means of a data provider which is registered using a given look-up key. Table 10.84, “Data provider look-up keys” lists all look-up keys that a generic labeling algorithm tests during the layout process in order to query supplemental data.

Binding supplemental layout data to a graph is described in the section called “Providing Supplemental Layout Data”.

Table 10.84. Data provider look-up keys

Key Element Type Value Type Description
LabelModelDpKey INodeLabelLayout INodeLabelModel For each INodeLabelLayout instance an INodeLabelModel instance that is used to determine valid label positions.
IEdgeLabelLayout IEdgeLabelModel For each IEdgeLabelLayout instance an IEdgeLabelModel instance that is used to determine valid label positions.

Integrated Labeling

Integrated labeling denotes automatic edge label placement as an integrated part of a layout algorithm. All edge labels of a graph are arranged in such a manner that there are no overlaps of edge labels with each other or with graph elements.

Table 10.85, “Layout support for integrated labeling” lists the major layout algorithms that provide support for integrated labeling.

Table 10.85. Layout support for integrated labeling

Layout Style Classname Note
Hierarchical IncrementalHierarchicLayouter With class IncrementalHierarchicLayouter, integrated labeling can be conveniently enabled using appropriate configuration properties. See the description of the hierarchical layout style for more information.
Orthogonal OrthogonalLayouter, DirectedOrthogonalLayouter, and OrthogonalGroupLayouter See the descriptions of orthogonal layout, directed orthogonal layout, and orthogonal layout of grouped graphs for more information.
Tree TreeLayouter, GenericTreeLayouter, and BalloonLayouter Integrated labeling can conveniently be enabled using appropriate configuration methods. See the descriptions of directed tree layout, generic tree layout, and balloon layout for more information.

Integrated labeling is most conveniently triggered using the corresponding properties of the layout algorithms that support it. For example:

IncrementalHierarchicLayouter ihl = new IncrementalHierarchicLayouter();

// Enabling integrated edge labeling.
ihl.IntegratedEdgeLabeling = true;

Example 10.43, “Using class LabelLayoutTranslator” shows how to configure integrated labeling in the absence of an appropriate configuration property using LabelLayoutTranslator. This class converts label layout information so that it is understood by a layout algorithm.

Example 10.43. Using class LabelLayoutTranslator

void UseIntegratedLabeling(CanonicMultiStageLayouter layouter) {
  // Use integrated labeling support, and let class LabelLayoutTranslator do 
  // the conversion of information held by an edge label's IEdgeLabelLayout 
  // object to data provider-based information that is understood by the 
  // algorithm.
  layouter.LabelLayouter = new LabelLayoutTranslator();
  layouter.LabelLayouterEnabled = true;
}

Through the following property LabelLayoutTranslator supports configuration of edge label auto-flip behavior:

bool AutoFlippingEnabled { get; set; }
Description Configures auto-flipping for upside-down edge labels.

Internal representation of label layout

As mentioned in the section called “Connecting Graph Models” the yFiles for Silverlight Algorithms component uses a different graph model than the yFiles for Silverlight Viewer component. The LayoutGraph which is used internally handles labels as simple boxes represented by INodeLabelLayout and IEdgeLabelLayout instances. Since the adapter classes automatically translate the viewer side ILabel instances and their position and label model parameters programmers usually don't have to care about these representations.

There are use cases, however, when a programmer has to use the internal representation:

// graph is of type yWorks.yFiles.Layout.LayoutGraph

// get the label layouts for all labels associated with the given edge
IEdgeLabelLayout[] labels = graph.GetLabelLayout(edge);
// retrieve some information for the first label
IEdgeLabelLayout layout = labels[0];
YOrientedRectangle box = layout.OrientedBox;
IEdgeLabelModel edgeLabelModel = layout.LabelModel;

The INodeLabelLayout and IEdgeLabelLayout implementations use the yFiles for Silverlight Algorithms label models, i.e. implementations of INodeLabelModel and IEdgeLabelModel, respectively. Again, the yFiles for Silverlight Viewer models are mapped automatically when the adapter classes are used.

Tutorial Demo Code

The layout module class LabelingModule.cs from the LayoutModulesWindow demo application presents the setup of a labeling algorithm in an application context.