
Search this API  
PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 
java.lang.Object y.layout.AbstractLayoutStage y.layout.labeling.AbstractLabelingAlgorithm y.layout.labeling.MISLabelingAlgorithm
public abstract class MISLabelingAlgorithm
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.
GreedyMISLabeling
,
SALabeling
Field Summary  

protected java.util.Map 
boxesToNodes
The mapping from the LabelCandidate s to the corresponding nodes in the conflictGraph . 
protected Graph 
conflictGraph
The conflict graph modeling LabelCandidate s 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 LabelCandidate s 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 LabelCandidate s 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.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 

public static final byte OPTIMIZATION_BALANCED
setOptimizationStrategy(byte)
,
Constant Field Valuespublic static final byte OPTIMIZATION_NODE_OVERLAP
setOptimizationStrategy(byte)
,
Constant Field Valuespublic static final byte OPTIMIZATION_LABEL_OVERLAP
setOptimizationStrategy(byte)
,
Constant Field Valuespublic static final byte OPTIMIZATION_EDGE_OVERLAP
setOptimizationStrategy(byte)
,
Constant Field Valuespublic static final byte OPTIMIZATION_PREFERRED_PLACEMENT
PreferredPlacementDescriptor
associated with edge labels.
setOptimizationStrategy(byte)
,
Constant Field Valuespublic static final byte OPTIMIZATION_NONE
protected LayoutGraph graph
protected Graph conflictGraph
LabelCandidate
s as nodes and edges between them as conflicts, i.e.,
overlaps among candidates.
createEdges()
protected NodeMap nodesToBoxes
conflictGraph
to the corresponding LabelCandidate
instance.
conflictGraph
protected java.util.Map boxesToNodes
LabelCandidate
s to the corresponding nodes in the conflictGraph
.
conflictGraph
protected NodeMap nodesToID
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 

protected MISLabelingAlgorithm()
MISLabelingAlgorithm
instance with default settings.
Method Detail 

public double getCustomProfitModelRatio()
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]
.
profit model
is null
or
if OPTIMIZATION_NONE
is chosen as optimization strategy
.[0,1]
) between the internal profit
and the profit calculated using the current profit modelsetCustomProfitModelRatio(double)
public void setCustomProfitModelRatio(double customProfitModelRatio)
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]
.
profit model
is null
or
if OPTIMIZATION_NONE
is chosen as optimization strategy
.customProfitModelRatio
 the ratio (from the interval [0,1]
) between the internal profit
and the profit calculated using the current profit model
java.lang.IllegalArgumentException
 if the given ratio is negative or larger than 1
AbstractLabelingAlgorithm.setProfitModel(ProfitModel)
,
setOptimizationStrategy(byte)
public byte getOptimizationStrategy()
Depending on the strategy, criteria like labelnode overlaps, labellabel 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.
optimization step
.setOptimizationStrategy(byte)
public void setOptimizationStrategy(byte optimizationStrategy)
Depending on the strategy, criteria like labelnode overlaps, labellabel 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.
optimization step
.OPTIMIZATION_BALANCED
optimizationStrategy
 one of the predefined optimization strategies
java.lang.IllegalArgumentException
 if the given strategy is unknownpublic void setRemoveNodeOverlaps(boolean flag)
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.
setRemoveNodeOverlaps
in class AbstractLabelingAlgorithm
NodeLabelModel.getDefaultParameter()
for node labels
and EdgeLabelModel.getDefaultParameter()
for edge labels).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.flag
 true
if candidates overlapping with nodes should be removed,
false
otherwisefalse  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 
public boolean getRemoveNodeOverlaps()
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.
getRemoveNodeOverlaps
in class AbstractLabelingAlgorithm
NodeLabelModel.getDefaultParameter()
for node labels
and EdgeLabelModel.getDefaultParameter()
for edge labels).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.true
if candidates overlapping with nodes are removed,
false
otherwisesetRemoveNodeOverlaps(boolean)
public void setRemoveEdgeOverlaps(boolean flag)
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.
setRemoveEdgeOverlaps
in class AbstractLabelingAlgorithm
NodeLabelModel.getDefaultParameter()
for node labels
and EdgeLabelModel.getDefaultParameter()
for edge labels).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.flag
 true
if candidates overlapping with edges should be removed,
false
otherwisefalse  all four candidate positions are allowed  true  only two of the four candidate positions are allowed, the others will be removed 
public boolean getRemoveEdgeOverlaps()
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.
getRemoveEdgeOverlaps
in class AbstractLabelingAlgorithm
NodeLabelModel.getDefaultParameter()
for node labels
and EdgeLabelModel.getDefaultParameter()
for edge labels).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.true
if candidates overlapping with edges are removed,
false
otherwisesetRemoveEdgeOverlaps(boolean)
public boolean isAmbiguityReductionEnabled()
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.
LabelCandidate
s.OPTIMIZATION_NONE
is selected as
optimization strategy
.true
if the algorithm tries to avoid ambiguous label placements,
false
otherwisesetAmbiguityReductionEnabled(boolean)
public void setAmbiguityReductionEnabled(boolean ambiguityReductionEnabled)
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.
LabelCandidate
s.OPTIMIZATION_NONE
is selected as
optimization strategy
.ambiguityReductionEnabled
 true
if the algorithm should try to avoid ambiguous label placements,
false
otherwiseprotected void createEdges()
LabelCandidate
s intersect.
The nodes of the conflict graph
represent LabelCandidate
s. 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 LabelCandidate
s 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.
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.conflictGraph
,
nodesToBoxes
,
boxesToNodes
,
nodesToID
protected NodeMap assignProfit()
NodeMap
which assigns a profit value to each node in the conflict graph
.
As the conflict graph's nodes represent LabelCandidate
s, 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.
protected void foundLabelOverlap(LabelCandidate candidate1, LabelCandidate candidate2, Edge edge)
LabelCandidate
s 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
LabelCandidate
s.
OPTIMIZATION_NONE
is chosen as
optimization strategy
.candidate1
 the first overlapping LabelCandidate
candidate2
 the second overlapping LabelCandidate
edge
 the Edge
in conflictGraph
representing the found overlapconflictGraph
,
createEdges()
protected void foundNodeOverlap(LabelCandidate labelCandidate, Node node, YRectangle nodeBox)
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.
OPTIMIZATION_NONE
is chosen as
optimization strategy
.labelCandidate
 the LabelCandidate
overlapping with the given nodenode
 the Node
overlapping with the given label candidatenodeBox
 the bounding box of the given nodeconflictGraph
,
createEdges()
protected void foundEdgeOverlap(LabelCandidate labelCandidate, Edge edge, LineSegment eSegment)
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.
OPTIMIZATION_NONE
is chosen as
optimization strategy
.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 candidateconflictGraph
,
createEdges()
protected void foundHaloOverlap(LabelCandidate labelCandidate, Node node, YRectangle haloRect)
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.
OPTIMIZATION_NONE
is chosen as
optimization strategy
.labelCandidate
 the LabelCandidate
overlapping with a node halonode
 the Node
whose NodeHalo
is overlapping with the given label candidatehaloRect
 the bounding box of the NodeHalo
overlapping with the given label candidateconflictGraph
,
createEdges()

© Copyright 20002022, yWorks GmbH. All rights reserved. 

PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 