com.yworks.yfiles.layout.labeling

Class AbstractMISLabeling

java.lang.Object

com.yworks.yfiles.layout.AbstractLayoutStage

com.yworks.yfiles.layout.labeling.AbstractLabeling

com.yworks.yfiles.layout.labeling.AbstractMISLabeling

All Implemented Interfaces:

ILayoutAlgorithm, ILayoutStage

Direct Known Subclasses:

GenericLabeling

public abstract class AbstractMISLabeling
extends AbstractLabeling

A base class for generic labeling algorithms which solve the labeling problem by reducing it to the maximum independent set (MIS) problem.

Different optimization strategies are available; an optimization strategy defines which criteria the algorithm should try to optimize. For example, reducing the number of overlaps between labels and nodes may be considered more important than reducing the number of overlaps between labels and edges.

See Also:

GenericLabeling

Field Summary

Fields

Modifier and Type	Field and Description
protected Map<Object,Object>	boxesToNodes The mapping from the LabelCandidates to the corresponding nodes in the conflictGraph.
protected Graph	conflictGraph The conflict graph modeling LabelCandidates as nodes and edges between them as conflicts, i.e., overlaps among candidates.
protected LayoutGraph	graph The input graph that will be labeled.
protected INodeMap	nodesToBoxes The mapping from each node in the conflictGraph to the corresponding LabelCandidate instance.
protected INodeMap	nodesToID The mapping from nodes in the conflictGraph to a corresponding integer value (ID).

Fields inherited from class com.yworks.yfiles.layout.labeling.AbstractLabeling

LABEL_MODEL_DPKEY

Constructor Summary

Constructors

Constructor and Description
AbstractMISLabeling() Creates a new AbstractMISLabeling instance with default settings.

Method Summary

Modifier and Type	Method and Description
protected INodeMap	assignProfit() Returns a INodeMap which assigns a profit value to each node in the conflict graph.
protected void	createEdges() Creates the edges in the conflict graph, i.e., one edge between two nodes if the corresponding LabelCandidates intersect.
protected void	foundEdgeOverlap(LabelCandidate labelCandidate, Edge edge, LineSegment eSegment) Indicates that an overlap between a LabelCandidate and an Edge of the input graph has been found.
protected void	foundHaloOverlap(LabelCandidate labelCandidate, Node node, YRectangle haloRect) Indicates that an overlap between a LabelCandidate and a NodeHalo of the input graph has been found.
protected void	foundLabelOverlap(LabelCandidate candidate1, LabelCandidate candidate2, Edge edge) Indicates that an overlap between two LabelCandidates has been found.
protected void	foundNodeOverlap(LabelCandidate labelCandidate, Node node, YRectangle nodeBox) Indicates that an overlap between a LabelCandidate and a Node of the input graph has been found.
double	getCustomProfitModelRatio() Gets the ratio between the internal profit (ip) and the profit computed using the specified profit model (sp).
OptimizationStrategy	getOptimizationStrategy() Gets the optimization strategy which defines the importance of criteria when optimizing labeling results.
boolean	isAmbiguityReductionEnabled() Gets whether or not the number of ambiguous label placements is reduced by applying an additional optimization step.
boolean	isEdgeOverlapsRemovalEnabled() Gets whether or not label candidates that overlap with edges are removed.
boolean	isNodeOverlapsRemovalEnabled() Gets whether or not label candidates that overlap with nodes are removed.
void	setAmbiguityReductionEnabled(boolean value) Sets whether or not the number of ambiguous label placements is reduced by applying an additional optimization step.
void	setCustomProfitModelRatio(double value) Sets the ratio between the internal profit (ip) and the profit computed using the specified profit model (sp).
void	setEdgeOverlapsRemovalEnabled(boolean value) Sets whether or not label candidates that overlap with edges are removed.
void	setNodeOverlapsRemovalEnabled(boolean value) Sets whether or not label candidates that overlap with nodes are removed.
void	setOptimizationStrategy(OptimizationStrategy value) Sets the optimization strategy which defines the importance of criteria when optimizing labeling results.

Methods inherited from class com.yworks.yfiles.layout.labeling.AbstractLabeling

applyLayout, getAffectedLabelsDpKey, getProfit, getProfitModel, isAutoFlippingEnabled, isEdgeGroupOverlapAllowed, isEdgeLabelPlacementEnabled, isInternalNodeLabelMovingEnabled, isLabelOverlapsReducingEnabled, isNodeLabelPlacementEnabled, label, label, label, setAffectedLabelsDpKey, setAutoFlippingEnabled, setEdgeGroupOverlapAllowed, setEdgeLabelPlacementEnabled, setInternalNodeLabelMovingEnabled, setLabelOverlapsReducingEnabled, setNodeLabelPlacementEnabled, setProfitModel

Methods inherited from class com.yworks.yfiles.layout.AbstractLayoutStage

applyLayoutCore, getCoreLayout, setCoreLayout

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

boxesToNodes

protected Map<Object,Object> boxesToNodes

The mapping from the LabelCandidates to the corresponding nodes in the conflictGraph.

See Also:

conflictGraph

conflictGraph

protected Graph conflictGraph

The conflict graph modeling LabelCandidates as nodes and edges between them as conflicts, i.e., overlaps among candidates.

See Also:

createEdges()

graph

protected LayoutGraph graph

The input graph that will be labeled.

nodesToBoxes

protected INodeMap nodesToBoxes

The mapping from each node in the conflictGraph to the corresponding LabelCandidate instance.

See Also:

conflictGraph

nodesToID

protected INodeMap nodesToID

The mapping from nodes in the conflictGraph to a corresponding integer value (ID).

The ID denotes the actual label which a LabelCandidate (i.e. a node in the conflict graph) belongs to.

Constructor Detail

AbstractMISLabeling

public AbstractMISLabeling()

Creates a new AbstractMISLabeling instance with default settings.

Method Detail

assignProfit

protected INodeMap assignProfit()

Returns a INodeMap which assigns a profit value to each node in the conflict graph.

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 Node (representing a label candidate) in the conflictGraph to a Double representing the profit value of the candidate.

Returns:

a mapping from nodes (i.e. label candidates) to their profit value

createEdges

protected void createEdges()

Creates the edges in the conflict graph, i.e., one edge between two nodes if the corresponding LabelCandidates intersect.

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.

This method will calculate all intersections among label candidates of the conflict graph. During this process, methods foundEdgeOverlap(LabelCandidate, Edge, LineSegment), foundHaloOverlap(LabelCandidate, Node, YRectangle), foundLabelOverlap(LabelCandidate, LabelCandidate, Edge) and foundNodeOverlap(LabelCandidate, Node, YRectangle) will be invoked when finding an intersection of a certain type. The mentioned methods will influence the profit of label candidates. This should be kept in mind when overriding this method.

See Also:

conflictGraph, nodesToBoxes, boxesToNodes, nodesToID

foundEdgeOverlap

protected void foundEdgeOverlap(LabelCandidate labelCandidate,
                                Edge edge,
                                LineSegment eSegment)

Indicates that an overlap between a LabelCandidate and an Edge of the input graph has been found.

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.

This method has no effect if OptimizationStrategy.NONE is chosen as optimization strategy.

Parameters:

labelCandidate - the LabelCandidate overlapping with the given Edge

edge - the Edge overlapping with the given LabelCandidate

eSegment - the LineSegment of the given edge overlapping with the given candidate

See Also:

conflictGraph, createEdges()

foundHaloOverlap

protected void foundHaloOverlap(LabelCandidate labelCandidate,
                                Node node,
                                YRectangle haloRect)

Indicates that an overlap between a LabelCandidate and a NodeHalo of the input graph has been found.

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.

This method has no effect if OptimizationStrategy.NONE is chosen as optimization strategy.

Parameters:

labelCandidate - the LabelCandidate overlapping with a node halo

node - the Node whose NodeHalo is overlapping with the given label candidate

haloRect - the bounding box of the NodeHalo overlapping with the given label candidate

See Also:

conflictGraph, createEdges()

foundLabelOverlap

protected void foundLabelOverlap(LabelCandidate candidate1,
                                 LabelCandidate candidate2,
                                 Edge edge)

Indicates that an overlap between two LabelCandidates has been found.

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.

This method has no effect if OptimizationStrategy.NONE is chosen as optimization strategy.

Parameters:

candidate1 - the first overlapping LabelCandidate

candidate2 - the second overlapping LabelCandidate

edge - the Edge in conflictGraph representing the found overlap

See Also:

conflictGraph, createEdges()

foundNodeOverlap

protected void foundNodeOverlap(LabelCandidate labelCandidate,
                                Node node,
                                YRectangle nodeBox)

Indicates that an overlap between a LabelCandidate and a Node of the input graph has been found.

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.

This method has no effect if OptimizationStrategy.NONE is chosen as optimization strategy.

Parameters:

labelCandidate - the LabelCandidate overlapping with the given node

node - the Node overlapping with the given label candidate

nodeBox - the bounding box of the given node

See Also:

conflictGraph, createEdges()

getCustomProfitModelRatio

public double getCustomProfitModelRatio()

Gets the ratio between the internal profit (ip) and the profit computed using the specified profit model (sp).

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].

Throws:

IllegalArgumentException - if the given ratio is negative or larger than 1

This ratio has no effect if the profit model is null or if OptimizationStrategy.NONE is chosen as optimization strategy.

Default Value:

The default value is 0.1. The profit determined by the optimization strategy is more important than the currently specified profit model.

Returns:

the ratio (from the interval [0,1]) between the internal profit and the profit calculated using the current profit model

See Also:

AbstractLabeling.setProfitModel(IProfitModel), setOptimizationStrategy(OptimizationStrategy), setCustomProfitModelRatio(double)

getOptimizationStrategy

public OptimizationStrategy getOptimizationStrategy()

Gets the optimization strategy which defines the importance of criteria when optimizing labeling results.

Depending on the strategy, criteria like label-node overlaps, label-label overlaps and others are more or less important. For example, if the number of overlaps between labels and nodes is the most important criterion for the result, strategy OptimizationStrategy.NODE_OVERLAP should be chosen.

Throws:

IllegalArgumentException - if the given strategy is unknown

The runtime can be lowered when skipping the optimization step.

Default Value:

The default value is OptimizationStrategy.BALANCED

Returns:

one of the predefined optimization strategies

See Also:

setOptimizationStrategy(OptimizationStrategy)

isAmbiguityReductionEnabled

public boolean isAmbiguityReductionEnabled()

Gets whether or not the number of ambiguous label placements is reduced by applying an additional optimization step.

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.

Applying the ambiguity reduction step may significantly increase the running time of the labeling algorithm, especially for graphs with a large number of labels and label models with a high number of LabelCandidates.

This setting has no effect if OptimizationStrategy.NONE is selected as optimization strategy.

Default Value:

The default value is false. Ambiguous label placements might be selected.

Returns:

true if the algorithm tries to avoid ambiguous label placements, false otherwise

See Also:

setAmbiguityReductionEnabled(boolean)

isEdgeOverlapsRemovalEnabled

public boolean isEdgeOverlapsRemovalEnabled()

Gets whether or not label candidates that overlap with edges are removed.

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.

Overrides:

isEdgeOverlapsRemovalEnabled in class AbstractLabeling

If this feature is enabled and all candidates of a label overlap with some edge, then the label model's default parameter will be used to determine the actual placement (DefaultParameter for node labels and DefaultParameter for edge labels).

It is recommended to enable this feature only in conjunction with OptimizationStrategy.NONE set as optimization strategy, i.e., without optimization. If used together with optimization, the optimization strategy may be restricted too much and not deliver as good results as it could otherwise do.

Default Value:

The default value is false. Candidates overlapping with edges are allowed.

Returns:

true if candidates overlapping with edges are removed, false otherwise

See Also:

setEdgeOverlapsRemovalEnabled(boolean)

isNodeOverlapsRemovalEnabled

public boolean isNodeOverlapsRemovalEnabled()

Gets whether or not label candidates that overlap with nodes are removed.

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.

Overrides:

isNodeOverlapsRemovalEnabled in class AbstractLabeling

If this feature is enabled and all candidates of a label overlap with some node, then the label model's default parameter will be used to determine the actual placement (DefaultParameter for node labels and DefaultParameter for edge labels).

It is recommended to enable this feature only in conjunction with OptimizationStrategy.NONE set as optimization strategy, i.e., without optimization. If used together with optimization, the optimization strategy may be restricted too much and not deliver as good results as it could otherwise do.

Default Value:

The default value is false. Candidates overlapping with nodes are allowed.

Returns:

true if candidates overlapping with nodes are removed, false otherwise

See Also:

setNodeOverlapsRemovalEnabled(boolean)

setAmbiguityReductionEnabled

public void setAmbiguityReductionEnabled(boolean value)

Sets whether or not the number of ambiguous label placements is reduced by applying an additional optimization step.

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.

Applying the ambiguity reduction step may significantly increase the running time of the labeling algorithm, especially for graphs with a large number of labels and label models with a high number of LabelCandidates.

This setting has no effect if OptimizationStrategy.NONE is selected as optimization strategy.

Default Value:

The default value is false. Ambiguous label placements might be selected.

Parameters:

value - true if the algorithm tries to avoid ambiguous label placements, false otherwise

See Also:

isAmbiguityReductionEnabled()

setCustomProfitModelRatio

public void setCustomProfitModelRatio(double value)

Sets the ratio between the internal profit (ip) and the profit computed using the specified profit model (sp).

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].

Throws:

IllegalArgumentException - if the given ratio is negative or larger than 1

This ratio has no effect if the profit model is null or if OptimizationStrategy.NONE is chosen as optimization strategy.

Default Value:

The default value is 0.1. The profit determined by the optimization strategy is more important than the currently specified profit model.

Parameters:

value - the ratio (from the interval [0,1]) between the internal profit and the profit calculated using the current profit model

See Also:

AbstractLabeling.setProfitModel(IProfitModel), setOptimizationStrategy(OptimizationStrategy), getCustomProfitModelRatio()

setEdgeOverlapsRemovalEnabled

public void setEdgeOverlapsRemovalEnabled(boolean value)

Sets whether or not label candidates that overlap with edges are removed.

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.

Overrides:

setEdgeOverlapsRemovalEnabled in class AbstractLabeling

If this feature is enabled and all candidates of a label overlap with some edge, then the label model's default parameter will be used to determine the actual placement (DefaultParameter for node labels and DefaultParameter for edge labels).

It is recommended to enable this feature only in conjunction with OptimizationStrategy.NONE set as optimization strategy, i.e., without optimization. If used together with optimization, the optimization strategy may be restricted too much and not deliver as good results as it could otherwise do.

Default Value:

The default value is false. Candidates overlapping with edges are allowed.

Parameters:

value - true if candidates overlapping with edges are removed, false otherwise

See Also:

isEdgeOverlapsRemovalEnabled()

setNodeOverlapsRemovalEnabled

public void setNodeOverlapsRemovalEnabled(boolean value)

Sets whether or not label candidates that overlap with nodes are removed.

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.

Overrides:

setNodeOverlapsRemovalEnabled in class AbstractLabeling

If this feature is enabled and all candidates of a label overlap with some node, then the label model's default parameter will be used to determine the actual placement (DefaultParameter for node labels and DefaultParameter for edge labels).

It is recommended to enable this feature only in conjunction with OptimizationStrategy.NONE set as optimization strategy, i.e., without optimization. If used together with optimization, the optimization strategy may be restricted too much and not deliver as good results as it could otherwise do.

Default Value:

The default value is false. Candidates overlapping with nodes are allowed.

Parameters:

value - true if candidates overlapping with nodes are removed, false otherwise

See Also:

isNodeOverlapsRemovalEnabled()

setOptimizationStrategy

public void setOptimizationStrategy(OptimizationStrategy value)

Sets the optimization strategy which defines the importance of criteria when optimizing labeling results.

Depending on the strategy, criteria like label-node overlaps, label-label overlaps and others are more or less important. For example, if the number of overlaps between labels and nodes is the most important criterion for the result, strategy OptimizationStrategy.NODE_OVERLAP should be chosen.

Throws:

IllegalArgumentException - if the given strategy is unknown

The runtime can be lowered when skipping the optimization step.

Default Value:

The default value is OptimizationStrategy.BALANCED

Parameters:

value - one of the predefined optimization strategies

See Also:

getOptimizationStrategy()