A generic labeling algorithm for placing the labels of a graph.
Remarks
This algorithm can switch between two internal implementations. By default, it generates high quality label placements even for difficult instances. This especially holds 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 maximumDuration to 0. On the downside, the results will not be as good as the ones 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 Labelling Algorithm.
It is recommended to use IEdgeLabelLayoutModels and INodeLabelLayoutModels which allow free positioning of labels to achieve best results with this generic labeling algorithm.
Note that when used standalone and in conjunction with a PartitionGrid, care has to be taken to supply the correct cell positions. If a previous layout run has modified the partition grid, the originalPosition and originalHeight, may be out of date. In this case computedPosition and computedHeight need to be written back to the original values as this algorithm relies on them being correct. Likewise for the ColumnDescriptors.
This algorithm works according to the general labeling concept defined by LabelingBase.
Default Values of Properties
| affectedLabelsDpKey | null | All labels are considered to be selected. |
| customProfitModelRatio | 0.1 | The profit determined by the optimization strategy is more important than the currently specified profit model. |
| deterministic | true | Labeling results are deterministic. |
| edgeGroupOverlapAllowed | false | Edge labels are not allowed to overlap with edges of the same edge group. |
| maximumDuration | <code>0x7FFFFFFF</code> | There is no time limit. |
| optimizationStrategy | BALANCED | |
| placeEdgeLabels | true | Edge labels will be placed. |
| placeNodeLabels | true | Node labels will be placed. |
| removeEdgeOverlaps | false | Candidates overlapping with edges are allowed. |
| removeNodeOverlaps | false | Candidates overlapping with nodes are allowed. |
Type Details
- yfiles module
- layout-core
- yfiles-umd modules
- All layout modules, view-layout-bridge
- Legacy UMD name
- yfiles.labeling.GenericLabeling
See Also
Constructors
Creates a new instance of GenericLabeling with default settings.
Parameters
A map of options to pass to the method.
- deterministic - boolean
Whether or not this algorithm behaves deterministically. This option sets the deterministic property on the created object.
- maximumDuration - number
The time limit for this algorithm in milliseconds. This option sets the maximumDuration property on the created object.
- customProfitModelRatio - number
The ratio between the internal profit (ip) and the profit computed using the specified profit model (sp). This option sets the customProfitModelRatio property on the created object.
- optimizationStrategy - OptimizationStrategy
The optimization strategy which defines the importance of criteria when optimizing labeling results. This option sets the optimizationStrategy property on the created object.
- removeNodeOverlaps - boolean
Whether or not label candidates that overlap with nodes are removed. This option sets the removeNodeOverlaps property on the created object.
- removeEdgeOverlaps - boolean
Whether or not label candidates that overlap with edges are removed. This option sets the removeEdgeOverlaps property on the created object.
- reduceAmbiguity - boolean
Whether or not the number of ambiguous label placements is reduced by applying an additional optimization step. This option sets the reduceAmbiguity property on the created object.
- profitModel - IProfitModel
The IProfitModel for ranking the LabelCandidates for labels. This option sets the profitModel 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 to further reduce the number of label overlaps is applied. This option sets the reduceLabelOverlaps property on the created object.
- placeNodeLabels - boolean
Whether or not labels assigned to nodes are placed. This option sets the placeNodeLabels property on the created object.
- placeEdgeLabels - boolean
Whether or not labels assigned to edges are placed. This option sets the placeEdgeLabels property on the created object.
- affectedLabelsDpKey - Object
The IDataProvider key to mark labels as selected for placement. This option sets the affectedLabelsDpKey property on the created object.
- autoFlipping - boolean
Whether or not edge labels are automatically flipped if otherwise they would be upside-down. This option sets the autoFlipping property on the created object.
- edgeGroupOverlapAllowed - boolean
Whether or not edge labels may overlap with edges belonging to the same edge group as the label's edge. This option sets the edgeGroupOverlapAllowed property on the created object.
- coreLayout - ILayoutAlgorithm
The core layout algorithm that is wrapped by this stage. This option sets the coreLayout property on the created object.
Properties
Gets or sets the IDataProvider key to mark labels as selected for placement.
Remarks
If a IDataProvider is registered with this key, only the selected labels will be placed, while all other labels are considered fixed.
The registered IDataProvider needs to map from ILabelLayout to boolean where true indicates that a label should be placed and false indicates that a label should be ignored.
Default Value
null.All labels are considered to be selected.
See Also
Defined in
Gets or sets whether or not edge labels are automatically flipped if otherwise they would be upside-down.
Default Value
false.Edge labels being upside-down keep their orientation.
See Also
Sample Graphs
Defined in
Gets or sets the core layout algorithm that is wrapped by this stage.
Gets or sets the ratio between the internal profit (ip) and the profit computed using the specified profit model (sp).
Remarks
This ratio defines how to weight the two profit values (ip) and (sp). The overall ratio is then computed as ratio * sp + (1 - ratio) * ip. The profit of a LabelCandidate defines how likely it is that the candidate will be chosen as actual label position.
The ratio is defined to be a value from the interval [0,1].
Default Value
0.1.The profit determined by the optimization strategy is more important than the currently specified profit model.
Throws
- Exception({ name: 'ArgumentError' })
- if the given ratio is negative or larger than
1
See Also
Defined in
Gets or sets whether or not edge labels may overlap with edges belonging to the same edge group as the label's edge.
Remarks
Default Value
false.Edge labels are not allowed to overlap with edges of the same edge group.
See Also
Sample Graphs
Defined in
Gets or sets the time limit for this algorithm in milliseconds.
Remarks
0x7FFFFFFF denotes that there is no time limit. Values have to be greater than or equal to 0.Default Value
<code>0x7FFFFFFF</code>.There is no time limit.
Throws
- Exception({ name: 'ArgumentError' })
- if the given maximum duration is negative
0, a simple but fast internal algorithm is used.Gets or sets whether or not internal node labels are allowed to move.
Remarks
Default Value
false.Internal node labels will not be moved.
Sample Graphs
Defined in
Gets or sets the optimization strategy which defines the importance of criteria when optimizing labeling results.
Remarks
Default Value
Throws
- Exception({ name: 'ArgumentError' })
- if the given strategy is unknown
Defined in
Gets or sets whether or not labels assigned to edges are placed.
Default Value
true.Edge labels will be placed.
See Also
Defined in
Gets or sets whether or not labels assigned to nodes are placed.
Default Value
true.Node labels will be placed.
See Also
Defined in
Gets or sets the IProfitModel for ranking the LabelCandidates for labels.
Remarks
The profit model is used when calculating the profit of a candidate.
The higher the profit (rank) of a candidate is, the more likely it will be chosen as actual position by the algorithm.
Default Value
See Also
Defined in
Gets or sets whether or not the number of ambiguous label placements is reduced by applying an additional optimization step.
Remarks
A label position is considered to be ambiguous if it might not be possible to identify to which graph element the label belongs. For example, an edge label placed in between two edges is ambiguous.
Enabling this reduction step does not guarantee that no ambiguous placements are selected. The algorithm will try to avoid them if other good positions without ambiguity are available. Other aspects like preferred placement for edge labels will still be more important than the reduction of ambiguity.
Default Value
false.Ambiguous label placements might be selected.
Defined in
Gets or sets whether or not a post-processing step to further reduce the number of label overlaps is applied.
Default Value
false.Post-processing to reduce overlaps is disabled.
Defined in
Gets or sets whether or not label candidates that overlap with edges are removed.
Remarks
If overlapping candidates are not removed, they will be considered but get a penalty. Therefore, it is still less likely that an overlapping candidate is finally chosen.
The detection and removal of labels that overlap with edges may increase the runtime of this algorithm.
Default Value
false.Candidates overlapping with edges are allowed.
Sample Graphs
Overrides
Gets or sets whether or not label candidates that overlap with nodes are removed.
Remarks
If overlapping candidates are not removed, they will be considered but get a penalty. Therefore, it is still less likely that an overlapping candidate is finally chosen.
The detection and removal of labels that overlap with nodes may increase the runtime of this algorithm.
Default Value
false.Candidates overlapping with nodes are allowed.
Sample Graphs
Overrides
Methods
Places the labels in the graph after first executing the core layouter.
Parameters
A map of options to pass to the method.
- graph - LayoutGraph
- the input graph
See Also
Implements
Invokes the layout process of the core layout algorithm.
Remarks
Parameters
A map of options to pass to the method.
- graph - LayoutGraph
- the input graph
See Also
Defined in
Returns a INodeMap which assigns a profit value to each node in the conflict graph.
Remarks
As the conflict graph's nodes represent LabelCandidates, this mapping gives the profit value of label candidates. The assigned value is defined as the difference between the profit induced by the profit model and the candidate's overlap penalty.
The returned map is a mapping from each YNode (representing a label candidate) in the conflictGraph to a number representing the profit value of the candidate.
Returns
- ↪INodeMap
- a mapping from nodes (i.e. label candidates) to their profit value
Defined in
Creates the edges in the conflict graph, i.e., one edge between two nodes if the corresponding LabelCandidates intersect.
Remarks
The nodes of the conflict graph represent LabelCandidates. An edge between candidates signals that they overlap. A maximum independent set will be computed on the conflict graph to choose candidates such that no two candidates overlap.
This method may be overridden to change the structure of the conflict graph. Edges between two LabelCandidates in the conflict graph signal that the two candidates should not be selected together. By overriding this method, arbitrary reasons for indicating that two label candidates should not be chosen at the same time can be modeled.
See Also
Defined in
Indicates that an overlap between a LabelCandidate and an Edge of the input graph has been found.
Remarks
This method is called when finding overlaps while creating edges of the conflict graph. It will store a factor indicating how much the two elements overlap. The factor influences the profit assigned to the given label candidate.
This method may be overridden to realize a custom strategy for reacting to overlaps between label candidates and edges.
Parameters
A map of options to pass to the method.
- labelCandidate - LabelCandidate
- the LabelCandidate overlapping with the given Edge
- edge - Edge
- the Edge overlapping with the given LabelCandidate
- eSegment - LineSegment
- the LineSegment of the given edge overlapping with the given candidate
See Also
Defined in
Indicates that an overlap between a LabelCandidate and a NodeHalo of the input graph has been found.
Remarks
This method is called when finding overlaps while creating edges of the conflict graph. It will store a factor indicating how much the two elements overlap. The factor influences the profit assigned to the given label candidate.
This method may be overridden to realize a custom strategy for reacting to overlaps between label candidates and node halos.
Parameters
A map of options to pass to the method.
- labelCandidate - LabelCandidate
- the LabelCandidate overlapping with a node halo
- node - YNode
- haloRect - YRectangle
- the bounding box of the NodeHalo overlapping with the given label candidate
See Also
Defined in
Indicates that an overlap between two LabelCandidates has been found.
Remarks
This method is called when finding overlaps while creating edges of the conflict graph. It will store a factor indicating how much the two candidates overlap. The factor influences the penalty assigned when both candidates are chosen, i.e., the penalty for the corresponding overlap.
This method may be overridden to realize a custom strategy for reacting to overlaps among LabelCandidates.
Parameters
A map of options to pass to the method.
- candidate1 - LabelCandidate
- the first overlapping LabelCandidate
- candidate2 - LabelCandidate
- the second overlapping LabelCandidate
- edge - Edge
- the Edge in conflictGraph representing the found overlap
See Also
Defined in
Indicates that an overlap between a LabelCandidate and a YNode of the input graph has been found.
Remarks
This method is called when finding overlaps while creating edges of the conflict graph. It will store a factor indicating how much the two elements overlap. The factor influences the profit assigned to the given label candidate.
This method may be overridden to realize a custom strategy for reacting to overlaps between label candidates and nodes.
Parameters
A map of options to pass to the method.
- labelCandidate - LabelCandidate
- the LabelCandidate overlapping with the given node
- node - YNode
- the YNode overlapping with the given label candidate
- nodeBox - YRectangle
- the bounding box of the given node
See Also
Defined in
Indicates that an overlap between a LabelCandidate and the insets of a cell of the PartitionGrid has been found.
Remarks
This method is called when finding overlaps of label candidates and insets of the partition grid. It will store a factor indicating how much the two elements overlap. The factor influences the profit assigned to the given label candidate.
This method may be overridden to realize a custom strategy for reacting to overlaps between label candidates and partition grid insets.
Parameters
A map of options to pass to the method.
- labelCandidate - LabelCandidate
- the LabelCandidate overlapping with the PartitionGrid
- insetBox - YRectangle
- a YRectangle representing an inset region of the PartitionGrid that is overlapping with the given label candidate
See Also
Defined in
Indicates that the LabelCandidate is inside of the PartitionGrid.
Remarks
This method is called when the given LabelCandidate lies inside the partition grid. It will store a factor indicating how much the two elements overlap. The factor influences the profit assigned to the given label candidate.
This method may be overridden to realize a custom strategy for reacting to overlaps between label candidates and the partition grid.
Parameters
A map of options to pass to the method.
- labelCandidate - LabelCandidate
- the LabelCandidate overlapping with the PartitionGrid
- partitionGridBounds - YRectangle
- a YRectangle representing the bounds of the PartitionGrid
See Also
Defined in
Indicates that an overlap between a LabelCandidate and the PartitionGrid has been found.
Remarks
This method is called when finding overlaps of label candidates and lines of the partition grid. It will store a factor indicating how much the two elements overlap. The factor influences the profit assigned to the given label candidate.
This method may be overridden to realize a custom strategy for reacting to overlaps between label candidates and partition grid lines.
Parameters
A map of options to pass to the method.
- labelCandidate - LabelCandidate
- the LabelCandidate overlapping with the PartitionGrid
- lineSegment - LineSegment
- a LineSegment of the PartitionGrid that is overlapping with the given label candidate
See Also
Defined in
Returns the profit for placing a LabelCandidate with respect to the current profit model.
Remarks
Method getProfit on the current profit model will be invoked to compute the actual profit value.
The higher the profit (rank) of a candidate is, the more likely it will be chosen as actual position by the algorithm.
Parameters
A map of options to pass to the method.
- candidate - LabelCandidate
- a label candidate
Returns
- ↪number
- the profit value between
0and1
Defined in
Places the labels of the input graph using a IDataProvider registered to the input graph with the given key for determining which labels to place.
Remarks
Parameters
A map of options to pass to the method.
- graph - LayoutGraph
- The input graph.
- key - Object
- The optional IDataProvider key for label selection. If not specified, the current selection key is used.
Defined in
Places the labels of the input graph restricting the placement to labels contained in the given lists.
Remarks
Parameters
A map of options to pass to the method.
- graph - LayoutGraph
- the input graph
- nodeLabels - YList
- a list of INodeLabelLayouts defining the set of node labels that will be placed
- edgeLabels - YList
- a list of IEdgeLabelLayouts defining the set of edge labels that will be placed
Defined in
Fields
The mapping from the LabelCandidates to the corresponding nodes in the conflictGraph.
The conflict graph modeling LabelCandidates as nodes and edges between them as conflicts, i.e., overlaps among candidates.
The input graph that will be labeled.
Defined in
The mapping from each node in the conflictGraph to the corresponding LabelCandidate instance.
The mapping from nodes in the conflictGraph to a corresponding integer value (ID).