A base class for generic labeling algorithms which solve the labeling problem by reducing it to the maximum independent set (MIS) problem.
Remarks
Default Values of Properties
customProfitModelRatio | 0.1 | The profit determined by the optimization strategy is more important than the currently specified profit model. |
optimizationStrategy | BALANCED
| |
reduceAmbiguity | false | Ambiguous label placements might be selected. |
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.MISLabelingBase
See Also
Constructors
Creates a new MISLabelingBase instance with default settings.
Parameters
A map of options to pass to the method.
- 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
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 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
BALANCED.Throws
- Exception({ name: 'ArgumentError' })
- if the given strategy is unknown
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
SimpleProfitModel.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.
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
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
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
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
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
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
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
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
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
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
0
and1
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.
See Also
The conflict graph modeling LabelCandidates as nodes and edges between them as conflicts, i.e., overlaps among candidates.
See Also
The input graph that will be labeled.
The mapping from each node in the conflictGraph to the corresponding LabelCandidate instance.
See Also
The mapping from nodes in the conflictGraph to a corresponding integer value (ID).