A generic labeling algorithm for placing the labels of a graph.
Remarks
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
| defaultEdgeLabelingCosts | BALANCED | The different types of preferences for the placement of the edge labels are balanced. |
| defaultNodeLabelingCosts | BALANCED | The different types of preferences for the placement of the node labels are balanced. |
| deterministic | true | Labeling results are deterministic. |
| qualityTimeRatio | 1.0 | |
| scope | ALL | All labels are affected. |
| stopDuration | MAX_VALUE | There is no time limit. |
Type Details
- yFiles module
- algorithms
See Also
Constructors
Creates a new instance of GenericLabeling with default settings.
Parameters
A map of options to pass to the method.
- fillEmptyScope - boolean
- A value that specifies whether the algorithm should consider all labels to be in scope This option sets the fillEmptyScope property on the created object.
- deterministic - boolean
- Whether or not this algorithm behaves deterministically. This option sets the deterministic property on the created object.
- defaultEdgeLabelingCosts - LabelingCosts
- The default LabelingCosts for edge labels. This option either sets the value directly or recursively sets properties to the instance of the defaultEdgeLabelingCosts property on the created object.
- defaultNodeLabelingCosts - LabelingCosts
- The default LabelingCosts for node labels. This option either sets the value directly or recursively sets properties to the instance of the defaultNodeLabelingCosts property on the created object.
- stopDuration - TimeSpan
- The time limit for this algorithm. This option sets the stopDuration property on the created object.
- moveInternalNodeLabels - boolean
- Whether or not internal node labels are allowed to move. This option sets the moveInternalNodeLabels property on the created object.
- reduceLabelOverlaps - boolean
- Whether or not a post-processing step is applied to further reduce the number of label overlaps. This option sets the reduceLabelOverlaps property on the created object.
- qualityTimeRatio - number
- The ratio of label placement quality versus running time. This option sets the qualityTimeRatio property on the created object.
- scope - LabelingScope
- Which labels may be placed. This option sets the scope property on the created object.
- enabled - boolean
- coreLayout - ILayoutAlgorithm
- The core ILayoutAlgorithm that is wrapped by this stage. This option sets the coreLayout property on the created object.
Properties
Gets or sets the core ILayoutAlgorithm that is wrapped by this stage.
Default Value
null.Property Value
See Also
Implements
Gets or sets the default LabelingCosts for edge labels.
Remarks
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.
Default Value
The different types of preferences for the placement of the edge labels are balanced.
Property Value
Throws
- Exception({ name: 'ArgumentError' })
- if the
are null
See Also
Gets or sets the default LabelingCosts for node labels.
Remarks
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.
Default Value
The different types of preferences for the placement of the node labels are balanced.
Property Value
Throws
- Exception({ name: 'ArgumentError' })
- if the
are null
See Also
Gets or sets whether or not this algorithm behaves deterministically.
Remarks
Default Value
true.Labeling results are deterministic.
Property Value
true if this algorithm works deterministically, false otherwiseGets or sets a value that determines whether this stage should do anything but execute the coreLayout.
Remarks
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.
See Also
Implements
Get or sets a value that specifies whether the algorithm should consider all labels to be in scope
Remarks
true if the algorithm should consider all labels to be in scope when no scope is specified, false if the algorithm should do nothing in such cases.Default Value
true.Without any scope specification all labels are interpreted as being in scope
Gets or sets whether or not internal node labels are allowed to move.
Remarks
Default Value
false.Internal node labels will not be moved.
Property Value
true if internal node labels may be moved, false otherwiseSample Graphs
Gets or sets the ratio of label placement quality versus running time.
Remarks
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].
Default Value
1.0.Property Value
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]
Gets or sets whether or not a post-processing step is applied to further reduce the number of label overlaps.
Default Value
false.Post-processing to reduce overlaps is disabled.
Property Value
true if a post-processing step for reducing the number of label overlaps is applied, false otherwiseGets or sets which labels may be placed.
Default Value
See Also
Gets or sets the time limit for this algorithm.
Remarks
Default Value
Throws
- Exception({ name: 'ArgumentError' })
- if the given stop duration is negative
See Also
Methods
Implementation of the ILayoutAlgorithm interface and main entry point for the layout calculation.
Remarks
Parameters
A map of options to pass to the method.
- graph - LayoutGraph
- The graph to apply the layout to.
See Also
Implements
Places the labels in the graph after first executing the coreLayout.
Parameters
A map of options to pass to the method.
- graph - LayoutGraph
- the input graph
See Also
Implements
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.
Remarks
Parameters
A map of options to pass to the method.
- graph - LayoutGraph
- the graph that determines the generic type arguments of the created layout data
Returns
- ↪GenericLabelingData<LayoutNode,LayoutEdge,LayoutNodeLabel,LayoutEdgeLabel>
- an instance of layout data that can be used to perform item-specific configurations for the given GenericLabeling.
Returns an instance of LayoutData<TNode,TEdge,TNodeLabel,TEdgeLabel> that can be used to perform item-specific configurations for the GenericLabeling.
Remarks
Parameters
A map of options to pass to the method.
- graph - IGraph
- the graph that determines the generic type arguments of the created layout data
Returns
- ↪GenericLabelingData<INode,IEdge,ILabel,ILabel>
- an instance of layout data that can be used to perform item-specific configurations for the given GenericLabeling.
LayoutExecutor type is available at runtime.Can be used in custom implementations of modifyWeights to query the calculated overlap costs for the given LabelCandidates.
Remarks
The overlap cost between two LabelCandidates specifies the degree to which the candidates are considered to be overlapping, with 1 being interpreted as fully overlapping candidates, 0 as non-overlapping candidates and fractions of 1 as partially overlapping candidates.
Two LabelCandidates are less likely to both be chosen by the algorithm, the more they are overlapping.
Parameters
A map of options to pass to the method.
- candidate1 - LabelCandidate
- one of the two label candidates
- candidate2 - LabelCandidate
- the other of the two label candidates
Returns
- ↪number
- the degree to which the candidates should be considered overlapping
See Also
modifyCandidates
(graph: LayoutGraph, nodeLabelToCandidates: IMapper<LayoutNodeLabel,IEnumerable<LabelCandidate>>, edgeLabelToCandidates: IMapper<LayoutEdgeLabel,IEnumerable<LabelCandidate>>)Callback method to influence the label candidates available to the labeling algorithm before the algorithm is applied.
Remarks
Parameters
A map of options to pass to the method.
- graph - LayoutGraph
- the input graph
- nodeLabelToCandidates - IMapper<LayoutNodeLabel,IEnumerable<LabelCandidate>>
- a mapping from node labels to their respective label candidates
- edgeLabelToCandidates - IMapper<LayoutEdgeLabel,IEnumerable<LabelCandidate>>
- a mapping from edge labels to their respective label candidates
modifyWeights
(graph: LayoutGraph, nodeLabelToCandidates: IMapper<LayoutNodeLabel,IEnumerable<LabelCandidate>>, edgeLabelToCandidates: IMapper<LayoutEdgeLabel,IEnumerable<LabelCandidate>>)Callback method to influence the choice of LabelCandidates immediately before the final label positions are chosen.
Remarks
Parameters
A map of options to pass to the method.
- graph - LayoutGraph
- the input graph
- nodeLabelToCandidates - IMapper<LayoutNodeLabel,IEnumerable<LabelCandidate>>
- a mapping from node labels to their respective label candidates
- edgeLabelToCandidates - IMapper<LayoutEdgeLabel,IEnumerable<LabelCandidate>>
- a mapping from edge labels to their respective label candidates
See Also
Can be used in custom implementations of modifyWeights to set custom overlap penalties for the given LabelCandidates.
Remarks
The overlap costs between two LabelCandidates specifies the degree to which the candidates are considered to be overlapping, with 1 being interpreted as fully overlapping candidates, 0 as non-overlapping candidates and fractions of 1 as partially overlapping candidates.
Two LabelCandidates are less likely to both be chosen by the algorithm, the more they are overlapping.
Parameters
A map of options to pass to the method.
- candidate1 - LabelCandidate
- one of the two label candidates
- candidate2 - LabelCandidate
- the other of the two label candidates
- value - number
- the degree to which the candidates should be considered overlapping
See Also
Constants
EDGE_LABEL_CANDIDATE_PROCESSOR_DATA_KEY
: EdgeLabelDataKey<function(IEnumerable<LabelCandidate>,LayoutEdgeLabel):void>The EdgeLabelDataKey<EdgeLabelCandidateProcessor> key used to associate an edge label candidate processor delegate with an edge label to modify the weights calculated during the GenericLabeling.
See Also
A data key for publishing the chosen candidates for all affected edge labels.
Remarks
See Also
The EdgeLabelDataKey<TValue> key to specify candidates for each edge label.
Remarks
EdgeLabelCandidates provide the valid positions for their label, the best of which will be chosen as the final placement of the label by GenericLabeling.
If no IMapper<K,V> is registered with this key, the label is considered to be free.
The EdgeLabelDataKey<LabelingCosts> key to specify LabelingCosts for each edge label.
Remarks
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).
If no IMapper<K,V> is registered with this key, the edge label uses the defaultEdgeLabelingCosts.
See Also
NODE_LABEL_CANDIDATE_PROCESSOR_DATA_KEY
: NodeLabelDataKey<function(IEnumerable<LabelCandidate>,LayoutNodeLabel):void>The NodeLabelDataKey<NodeLabelCandidateProcessor> key used to associate an node label candidate processor delegate with a node label to modify the weights calculated during the GenericLabeling.
See Also
A data key for publishing the chosen candidates for all affected node labels.
Remarks
See Also
The NodeLabelDataKey<TValue> key to specify candidates for each node label.
Remarks
NodeLabelCandidates provide the valid positions for their label, the best of which will be chosen as the final placement of the label by GenericLabeling.
If no IMapper<K,V> is registered with this key, the label is considered to be free.
See Also
The NodeLabelDataKey<LabelingCosts> key to specify LabelingCosts for each node label.
Remarks
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).
If no IMapper<K,V> is registered with this key, the node label uses the defaultNodeLabelingCosts.