Search this API

y.layout.labeling
Class MISLabelingAlgorithm

java.lang.Object
  extended by y.layout.AbstractLayoutStage
      extended by y.layout.labeling.AbstractLabelingAlgorithm
          extended by y.layout.labeling.MISLabelingAlgorithm
All Implemented Interfaces:
Layouter, LayoutStage
Direct Known Subclasses:
GreedyMISLabeling, SALabeling

public abstract class MISLabelingAlgorithm
extends AbstractLabelingAlgorithm

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:
GreedyMISLabeling, SALabeling
 

Field Summary
protected  java.util.Map 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  NodeMap nodesToBoxes
          The mapping from each node in the conflictGraph to the corresponding LabelCandidate instance.
protected  NodeMap nodesToID
          The mapping from nodes in the conflictGraph to a corresponding integer value (ID).
static byte OPTIMIZATION_BALANCED
          An optimization strategy aiming at a good balance between the available optimization options.
static byte OPTIMIZATION_EDGE_OVERLAP
          An optimization strategy that especially reduces overlaps between labels and edges.
static byte OPTIMIZATION_LABEL_OVERLAP
          An optimization strategy that especially reduces overlaps between labels.
static byte OPTIMIZATION_NODE_OVERLAP
          An optimization strategy that especially reduces overlaps between labels and nodes as well as labels and node halos.
static byte OPTIMIZATION_NONE
          Use no optimization strategy.
static byte OPTIMIZATION_PREFERRED_PLACEMENT
          An optimization strategy that mainly tries to satisfy the preferences described by a PreferredPlacementDescriptor associated with edge labels.
 
Fields inherited from class y.layout.labeling.AbstractLabelingAlgorithm
EPS, LABEL_MODEL_DPKEY, setCustomizedProfitModel
 
Fields inherited from interface y.layout.Layouter
EDGE_ID_DPKEY, NODE_ID_DPKEY, NODE_TYPE_DPKEY, SELECTED_EDGES, SELECTED_NODES
 
Constructor Summary
protected MISLabelingAlgorithm()
          Creates a new MISLabelingAlgorithm instance with default settings.
 
Method Summary
protected  NodeMap assignProfit()
          Returns a NodeMap 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()
          Returns the ratio between the internal profit (ip) and the profit computed using the specified profit model (sp).
 byte getOptimizationStrategy()
          Returns the optimization strategy which defines the importance of criteria when optimizing labeling results.
 boolean getRemoveEdgeOverlaps()
          Returns whether or not label candidates that overlap with edges are removed.
 boolean getRemoveNodeOverlaps()
          Returns whether or not label candidates that overlap with nodes are removed.
 boolean isAmbiguityReductionEnabled()
          Returns whether or not the number of ambiguous label placements is reduced by applying an additional optimization step.
 void setAmbiguityReductionEnabled(boolean ambiguityReductionEnabled)
          Specifies whether or not the number of ambiguous label placements is reduced by applying an additional optimization step.
 void setCustomProfitModelRatio(double customProfitModelRatio)
          Specifies the ratio between the internal profit (ip) and the profit computed using the specified profit model (sp).
 void setOptimizationStrategy(byte optimizationStrategy)
          Specifies the optimization strategy which defines the importance of criteria when optimizing labeling results.
 void setRemoveEdgeOverlaps(boolean flag)
          Specifies whether or not label candidates that overlap with edges are removed.
 void setRemoveNodeOverlaps(boolean flag)
          Specifies whether or not label candidates that overlap with nodes are removed.
 
Methods inherited from class y.layout.labeling.AbstractLabelingAlgorithm
canLayout, checkGroupNodeSize, checkNodeSize, doLayout, getPlaceEdgeLabels, getPlaceNodeLabels, getProfit, getProfitModel, getRects, getSelectionKey, isApplyPostprocessing, isAutoFlippingEnabled, isEdgeGroupOverlapAllowed, isMoveInternalNodeLabels, isStoreRects, isUseAlternativeSideHandling, label, label, label, setApplyPostprocessing, setAutoFlippingEnabled, setEdgeGroupOverlapAllowed, setMoveInternalNodeLabels, setPlaceEdgeLabels, setPlaceNodeLabels, setProfitModel, setSelection, setStoreRects, setUseAlternativeSideHandling
 
Methods inherited from class y.layout.AbstractLayoutStage
canLayoutCore, doLayoutCore, getCoreLayouter, setCoreLayouter
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

OPTIMIZATION_BALANCED

public static final byte OPTIMIZATION_BALANCED
An optimization strategy aiming at a good balance between the available optimization options.

See Also:
setOptimizationStrategy(byte), Constant Field Values

OPTIMIZATION_NODE_OVERLAP

public static final byte OPTIMIZATION_NODE_OVERLAP
An optimization strategy that especially reduces overlaps between labels and nodes as well as labels and node halos.

See Also:
setOptimizationStrategy(byte), Constant Field Values

OPTIMIZATION_LABEL_OVERLAP

public static final byte OPTIMIZATION_LABEL_OVERLAP
An optimization strategy that especially reduces overlaps between labels.

See Also:
setOptimizationStrategy(byte), Constant Field Values

OPTIMIZATION_EDGE_OVERLAP

public static final byte OPTIMIZATION_EDGE_OVERLAP
An optimization strategy that especially reduces overlaps between labels and edges.

See Also:
setOptimizationStrategy(byte), Constant Field Values

OPTIMIZATION_PREFERRED_PLACEMENT

public static final byte OPTIMIZATION_PREFERRED_PLACEMENT
An optimization strategy that mainly tries to satisfy the preferences described by a PreferredPlacementDescriptor associated with edge labels.

See Also:
setOptimizationStrategy(byte), Constant Field Values

OPTIMIZATION_NONE

public static final byte OPTIMIZATION_NONE
Use no optimization strategy.

See Also:
Constant Field Values

graph

protected LayoutGraph graph
The input graph that will be labeled.


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()

nodesToBoxes

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

See Also:
conflictGraph

boxesToNodes

protected java.util.Map boxesToNodes
The mapping from the LabelCandidates to the corresponding nodes in the conflictGraph.

See Also:
conflictGraph

nodesToID

protected NodeMap 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

MISLabelingAlgorithm

protected MISLabelingAlgorithm()
Creates a new MISLabelingAlgorithm instance with default settings.

Method Detail

getCustomProfitModelRatio

public double getCustomProfitModelRatio()
Returns 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].

 
This ratio has no effect if the profit model is null or if OPTIMIZATION_NONE is chosen as optimization strategy.
Returns:
the ratio (from the interval [0,1]) between the internal profit and the profit calculated using the current profit model
See Also:
setCustomProfitModelRatio(double)

setCustomProfitModelRatio

public void setCustomProfitModelRatio(double customProfitModelRatio)
Specifies 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].

 
This ratio has no effect if the profit model is null or if OPTIMIZATION_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:
customProfitModelRatio - the ratio (from the interval [0,1]) between the internal profit and the profit calculated using the current profit model
Throws:
java.lang.IllegalArgumentException - if the given ratio is negative or larger than 1
See Also:
AbstractLabelingAlgorithm.setProfitModel(ProfitModel), setOptimizationStrategy(byte)

getOptimizationStrategy

public byte getOptimizationStrategy()
Returns 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 OPTIMIZATION_NODE_OVERLAP should be chosen.

 
The runtime can be lowered when skipping the optimization step.
Returns:
one of the predefined optimization strategies
See Also:
setOptimizationStrategy(byte)

setOptimizationStrategy

public void setOptimizationStrategy(byte optimizationStrategy)
Specifies 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 OPTIMIZATION_NODE_OVERLAP should be chosen.

 
The runtime can be lowered when skipping the optimization step.
Default Value:
The default value is OPTIMIZATION_BALANCED
Parameters:
optimizationStrategy - one of the predefined optimization strategies
Throws:
java.lang.IllegalArgumentException - if the given strategy is unknown

setRemoveNodeOverlaps

public void setRemoveNodeOverlaps(boolean flag)
Specifies 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:
setRemoveNodeOverlaps in class AbstractLabelingAlgorithm
 
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 (NodeLabelModel.getDefaultParameter() for node labels and EdgeLabelModel.getDefaultParameter() for edge labels).
 
It is recommended to enable this feature only in conjunction with OPTIMIZATION_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:
flag - true if candidates overlapping with nodes should be removed, false otherwise
Sample Graphs:

false - all four candidate positions are allowed, even though two are overlapping

true - the candidate position left and above the node are overlapping and thus removed

getRemoveNodeOverlaps

public boolean getRemoveNodeOverlaps()
Returns 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:
getRemoveNodeOverlaps in class AbstractLabelingAlgorithm
 
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 (NodeLabelModel.getDefaultParameter() for node labels and EdgeLabelModel.getDefaultParameter() for edge labels).
 
It is recommended to enable this feature only in conjunction with OPTIMIZATION_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.
Returns:
true if candidates overlapping with nodes are removed, false otherwise
See Also:
setRemoveNodeOverlaps(boolean)

setRemoveEdgeOverlaps

public void setRemoveEdgeOverlaps(boolean flag)
Specifies 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:
setRemoveEdgeOverlaps in class AbstractLabelingAlgorithm
 
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 (NodeLabelModel.getDefaultParameter() for node labels and EdgeLabelModel.getDefaultParameter() for edge labels).
 
It is recommended to enable this feature only in conjunction with OPTIMIZATION_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:
flag - true if candidates overlapping with edges should be removed, false otherwise
Sample Graphs:

false - all four candidate positions are allowed

true - only two of the four candidate positions are allowed, the others will be removed

getRemoveEdgeOverlaps

public boolean getRemoveEdgeOverlaps()
Returns 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:
getRemoveEdgeOverlaps in class AbstractLabelingAlgorithm
 
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 (NodeLabelModel.getDefaultParameter() for node labels and EdgeLabelModel.getDefaultParameter() for edge labels).
 
It is recommended to enable this feature only in conjunction with OPTIMIZATION_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.
Returns:
true if candidates overlapping with edges are removed, false otherwise
See Also:
setRemoveEdgeOverlaps(boolean)

isAmbiguityReductionEnabled

public boolean isAmbiguityReductionEnabled()
Returns 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 OPTIMIZATION_NONE is selected as optimization strategy.
Returns:
true if the algorithm tries to avoid ambiguous label placements, false otherwise
See Also:
setAmbiguityReductionEnabled(boolean)

setAmbiguityReductionEnabled

public void setAmbiguityReductionEnabled(boolean ambiguityReductionEnabled)
Specifies 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 OPTIMIZATION_NONE is selected as optimization strategy.
Default Value:
The default value is false. Ambiguous label placements might be selected.
Parameters:
ambiguityReductionEnabled - true if the algorithm should try to avoid ambiguous label placements, false otherwise

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

assignProfit

protected NodeMap assignProfit()
Returns a NodeMap 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

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 OPTIMIZATION_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 OPTIMIZATION_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()

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 OPTIMIZATION_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 OPTIMIZATION_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()

© Copyright 2000-2022,
yWorks GmbH.
All rights reserved.