C

GenericLabeling

Show Usages
A generic labeling algorithm for placing the labels of a graph.

Remarks

Node labels and edge labels placed by the labeling algorithm

This algorithm places the labels of a graph without moving its nodes or edges. It can switch between two internal implementations. By default, it generates high quality label placements even for difficult instances. This especially holds true if the label models allow a large number of different LabelCandidates, i.e., there is a high potential for optimizations.

If the duration of the calculation is of utmost importance, the internal algorithm can be changed to a simpler implementation by setting stopDuration to ZERO. On the downside, the results will not be as good as those of the default mode.

In default mode, this algorithm reduces the labeling problem to the maximum independent set (MIS) problem and solves the problem using simulated annealing. It is inspired by the article from Christensen, Marks and Shieber: A General Cartographic Labeling Algorithm.

Concept

Generic labeling algorithms use the label candidate factory associated with a label (see nodeLabelCandidates for node labels and edgeLabelCandidates for edge labels). The factories are necessary to compute a set of LabelCandidates, i.e., candidate positions for a label. Then, one best matching candidate from the set will be selected by the algorithm. This selection depends on several preferences, e.g., the custom weights given by weight, the specified edgeLabelCandidateProcessors, as well as the associated EdgeLabelPreferredPlacement (for edge labels).

For high quality results, it is recommended to use free edge label candidates and free node label candidates which allow free positioning of labels. Note that this usually induces a higher runtime compared to using a more restricted candidate factory (e.g. addDiscreteCandidates).

Features

By combining this stage with a coreLayout, the labeling will take place after the core layout was executed (applyLayoutImpl). This is especially useful if the core layout does not support label handling.

Performance

Specifying a stopDuration can reduce the time the GenericLabeling algorithm takes to produce a result. The acceleration is achieved by loosening the requirements for terminating the incremental improvement of the label positions. It should be noted that the stopDuration is not a guarantee for the maximum time spent, as the algorithm still has to produce a valid result.

The qualityTimeRatio can be used to specify a preference for the balance between the quality of the calculated result and the time spent on calculating it.

Default Values of Properties

NameDefaultDescription
coreLayoutnull
defaultEdgeLabelingCostsLabelingOptimizationStrategy.BALANCED
The different types of preferences for the placement of the edge labels are balanced.
defaultNodeLabelingCostsLabelingOptimizationStrategy.BALANCED
The different types of preferences for the placement of the node labels are balanced.
deterministictrue
Labeling results are deterministic.
qualityTimeRatio1.0
scopeLabelingScope.ALL
All labels are affected.
stopDurationTimeSpan.MAX_VALUE
There is no time limit.

See Also

Developer's Guide

Members

Show:

Constructors

GenericLabeling

()
Creates a new instance of GenericLabeling with default settings.

Parameters

Properties

coreLayout

: ILayoutAlgorithm
Gets or sets the core ILayoutAlgorithm that is wrapped by this stage.
final

Property Value

the core layout routine

Default Value

The default value is: null

defaultEdgeLabelingCosts

: LabelingCosts
Gets or sets the default LabelingCosts for edge labels.

The labeling algorithm chooses from a set of valid label positions (specified by EdgeLabelCandidates). The LabelingCosts allow specifying preferences on the costs for different types of positions. For example, whether a position where a label crosses an edge should have a high cost and, thus, is less likely chosen by the algorithm (see edgeOverlapCost).

Use edgeLabelingCosts to specify individual labeling costs for an edge label. The default costs are only applied for labels without individual costs.

final

Property Value

The default labeling costs for edge labels.

Throws

Exception ({ name: 'ArgumentError' })
if the LabelingCosts are null

Default Value

The different types of preferences for the placement of the edge labels are balanced.

See Also

API
edgeLabelingCosts, EdgeLabelCandidates

defaultNodeLabelingCosts

: LabelingCosts
Gets or sets the default LabelingCosts for node labels.

The labeling algorithm chooses from a set of valid label positions (specified by NodeLabelCandidates). The LabelingCosts allow specifying preferences on the costs for different types of positions. For example, whether a position where a label crosses an edge should have a high cost and, thus, is less likely chosen by the algorithm (see edgeOverlapCost).

Use nodeLabelingCosts to specify individual costs for a node label. The default costs are only applied for labels without individual costs.

final

Property Value

The default labeling costs for node labels.

Throws

Exception ({ name: 'ArgumentError' })
if the LabelingCosts are null

Default Value

The different types of preferences for the placement of the node labels are balanced.

See Also

API
nodeLabelingCosts, NodeLabelCandidates

deterministic

: boolean
Gets or sets whether or not this algorithm behaves deterministically.
If enabled, it produces the same results given the same input graph and settings.
final

Property Value

true if this algorithm works deterministically, false otherwise

Default Value

The default value is: true
Labeling results are deterministic.

enabled

: boolean
Gets or sets a value that determines whether this stage should do anything but execute the coreLayout.

By default, when constructed, stages should be enabled. Users may disable a stage's functionality by setting this property to false.

Stages that can guarantee that the graph will not change can choose to not even execute the coreLayout when disabled.

final

moveInternalNodeLabels

: boolean
Gets or sets whether or not internal node labels are allowed to move.
A node label is internal if the label's boundaries are completely within the node's boundaries.
This setting will only have an effect if the scope is set to NODE_LABELS or ALL.
This feature only works in conjunction with NodeLabelCandidates instances that restrict the positioning of labels (i.e. non-free candidate factories).
final

Property Value

true if internal node labels may be moved, false otherwise

Default Value

The default value is: false
Internal node labels will not be moved.

Sample Graphs

ShownSetting: false - internal labels were not moved, even though they overlap

qualityTimeRatio

: number
Gets or sets the ratio of label placement quality versus running time.

The larger the ratio, the better the quality of the resulting label placement but the longer it may take to perform the calculation.

The value must lie within [0,1].

final

Property Value

a value between 0.0 (low quality, fast) and 1.0 (high quality, slow)

Throws

Exception ({ name: 'ArgumentError' })
if the specified ratio is outside the interval [0,1]

Default Value

The default value is: 1.0

reduceLabelOverlaps

: boolean
Gets or sets whether or not a post-processing step is applied to further reduce the number of label overlaps.
Applying this post-processing step may lead to label positions that do not correspond to a candidate provided by the associated candidate factory.
To further reduce overlaps, the post-processing may (slightly) violate the values specified by the EdgeLabelPreferredPlacement (e.g., it may violate the preferred distance of a label to its edge).
final

Property Value

true if a post-processing step for reducing the number of label overlaps is applied, false otherwise

Default Value

The default value is: false
Post-processing to reduce overlaps is disabled.

scope

: LabelingScope
Gets or sets which labels may be placed.
This setting has higher priority than any custom label selection. If this scope e.g. only allows for placing NODE_LABELS, edge labels marked via the selection will still be ignored. Otherwise, the selection will determine whether a label is placed or not.
conversionfinal

Default Value

The default value is: LabelingScope.ALL
All labels are affected.

See Also

Developer's Guide
API
scope

stopDuration

: TimeSpan
Gets or sets the time limit for this algorithm.
MAX_VALUE denotes that there is no time limit. Values have to be greater than or equal to ZERO.
Restricting the stop duration may lead to a lower result quality. Furthermore, the algorithm cannot guarantee to strictly observe the specified time limit.
If the stopDuration is set to ZERO a simple but fast internal algorithm is used.
conversionfinal

Throws

Exception ({ name: 'ArgumentError' })
if the given stop duration is negative

Default Value

The default value is: TimeSpan.MAX_VALUE
There is no time limit.

Methods

applyLayout

(graph: LayoutGraph)
Implementation of the ILayoutAlgorithm interface and main entry point for the layout calculation.
This implementation checks the enabled state and when it's not enabled, will delegate to the coreLayout, directly. When the stage is enabled, all the work will be delegated to applyLayoutImpl, instead.
final

Parameters

graph: LayoutGraph
The graph to apply the layout to.

applyLayoutImpl

(graph: LayoutGraph)
protected
Places the labels in the graph after first executing the coreLayout.
protected

Parameters

graph: LayoutGraph
the input graph

createLayoutData

(graph: LayoutGraph): GenericLabelingData<LayoutNode, LayoutEdge, LayoutNodeLabel, LayoutEdgeLabel>
Returns an instance of LayoutData<TNode, TEdge, TNodeLabel, TEdgeLabel> that can be used to perform item-specific configurations for the GenericLabeling.
The generic type arguments of the created layout data are compatible with instances of LayoutGraph, but the layout data is not bound to a specific graph instance. Therefore, the created layout data still has to be passed as an argument of applyLayout in order to be applied.

Parameters

graph: LayoutGraph
the graph that determines the generic type arguments of the created layout data

Return Value

GenericLabelingData<LayoutNode, LayoutEdge, LayoutNodeLabel, LayoutEdgeLabel>
an instance of layout data that can be used to perform item-specific configurations for the given GenericLabeling.

createLayoutData

(graph?: IGraph): GenericLabelingData<INode, IEdge, ILabel, ILabel>
Returns an instance of LayoutData<TNode, TEdge, TNodeLabel, TEdgeLabel> that can be used to perform item-specific configurations for the GenericLabeling.
The generic type arguments of the created layout data are compatible with instances of IGraph, but the layout data is not bound to a specific graph instance. Therefore, the created layout data still has to be passed as an argument of applyLayout in order to be applied.
This method is not available unless the module view-layout-bridge is loaded. Either load the module 'view-layout-bridge' explicitly or ensure that the LayoutExecutor type is available at runtime.

Parameters

graph?: IGraph
the graph that determines the generic type arguments of the created layout data

Return Value

GenericLabelingData<INode, IEdge, ILabel, ILabel>
an instance of layout data that can be used to perform item-specific configurations for the given GenericLabeling.

Constants

All constants are filtered. Go to Filters.