Search this API

y.layout.labeling
Class AbstractLabelingAlgorithm

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

public abstract class AbstractLabelingAlgorithm
extends AbstractLayoutStage

An abstract base class for generic labeling algorithms which place labels of graphs.

Labeling algorithms compute positions for labels in a given graph. The main goal is to place labels such that they do not overlap with other graph elements. Labeling algorithms do not modify positions of nodes and edges.

Concept

Generic labeling algorithms use the model associated with a label (i.e. node label model for nodes and edge label model for edges). The models are necessary to compute a set of LabelCandidates, i.e., candidate positions for a label. Then, one best matching candidate from the set will be selected. This selection depends on several preferences, e.g., if overlaps with nodes are not allowed, candidates encoding overlapping positions will be ignored.

After one LabelCandidate has been chosen, the label model's parameter is used for encoding the label position. Therefore, the result of a generic labeling algorithm is one model parameter per label. The parameter is stored with the label and expresses the label position with respect to the underlying label model.

Features

This class provides a general frame, offering functionality which can be shared by other generic labeling algorithms.

To only place labels or a subset of labels, the main labeling methods label(LayoutGraph), label(LayoutGraph, Object) and label(LayoutGraph, YList, YList) are offered.

As this class represents an AbstractLayoutStage, it allows usage as a generic labeling stage. By combining it with a core layouter, the labeling will take place after the core layouter was executed (doLayout(LayoutGraph)). This is especially useful if the core layouter does not support label handling.

 

Field Summary
protected static double EPS
          Constant for internal use only.
static java.lang.Object LABEL_MODEL_DPKEY
          A DataProvider key for mapping models to edge/node labels The NodeLabelModels and EdgeLabelModels linked to NodeLabelLayouts and EdgeLabelLayouts by this DataProvider are taken as replacement models.
protected  boolean setCustomizedProfitModel
          For internal use only.
 
Fields inherited from interface y.layout.Layouter
EDGE_ID_DPKEY, NODE_ID_DPKEY, SELECTED_EDGES, SELECTED_NODES
 
Constructor Summary
protected AbstractLabelingAlgorithm()
          Creates a new AbstractLabelingAlgorithm instance with default settings.
 
Method Summary
 boolean canLayout(LayoutGraph graph)
          Accepts all graphs whose nodes have sizes greater than 0 and that the specified core layout algorithm can handle.
protected  void checkGroupNodeSize(GraphLayout layout, java.lang.Object node)
          Checks whether or not the given group node's width or height is zero or negative.
protected  void checkNodeSize(GraphLayout layout, java.lang.Object node)
          Checks whether or not the given node's width or height is zero or negative.
 void doLayout(LayoutGraph graph)
          Places the labels in the graph after first executing the core layouter.
 boolean getPlaceEdgeLabels()
          Returns whether or not labels assigned to edges are placed.
 boolean getPlaceNodeLabels()
          Returns whether or not labels assigned to nodes are placed.
 double getProfit(LabelCandidate candidate)
          Returns the profit for placing a LabelCandidate with respect to the current profit model.
 ProfitModel getProfitModel()
          Returns the ProfitModel for ranking the LabelCandidates for labels.
 YList getRects()
          Returns the set of all generated candidate rectangles.
 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.
 java.lang.Object getSelectionKey()
          Returns the DataProvider key to mark labels as selected for placement.
 boolean isApplyPostprocessing()
          Returns whether or not a post-processing step to reduce the number of label overlaps is applied.
 boolean isAutoFlippingEnabled()
          Returns whether or not edge labels are automatically flipped if otherwise they would be upside-down.
 boolean isEdgeGroupOverlapAllowed()
          Returns whether or not edge labels may overlap with edges belonging to the same edge group as the label's edge.
 boolean isMoveInternalNodeLabels()
          Returns whether or not internal node labels are allowed to move.
 boolean isStoreRects()
          Returns whether the candidate rectangles should be stored to be retrieved.
 boolean isUseAlternativeSideHandling()
          Deprecated. use PreferredPlacementDescriptor.getSideReference() instead
 void label(LayoutGraph graph)
          Places the labels of the given graph using the label selection defined by the DataProvider registered with the current selection key.
 void label(LayoutGraph graph, java.lang.Object key)
          Places the labels of the input graph using a DataProvider registered to the input graph with the given key for determining which labels to place.
 void label(LayoutGraph graph, YList nodeLabels, YList edgeLabels)
          Places the labels of the input graph restricting the placement to labels contained in the given lists.
 void setApplyPostprocessing(boolean applyPostprocessing)
          Specifies whether or not a post-processing step to reduce the number of label overlaps is applied.
 void setAutoFlippingEnabled(boolean enabled)
          Specifies whether or not edge labels are automatically flipped if otherwise they would be upside-down.
 void setEdgeGroupOverlapAllowed(boolean edgeGroupOverlapAllowed)
          Specifies whether or not edge labels may overlap with edges belonging to the same edge group as the label's edge.
 void setMoveInternalNodeLabels(boolean moveInternalNodeLabels)
          Specifies whether or not internal node labels are allowed to move.
 void setPlaceEdgeLabels(boolean enable)
          Specifies whether or not labels assigned to edges are placed.
 void setPlaceNodeLabels(boolean enable)
          Specifies whether or not labels assigned to nodes are placed.
 void setProfitModel(ProfitModel model)
          Specifies the ProfitModel for ranking the LabelCandidates for labels.
 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.
 void setSelection(java.lang.Object key)
          Specifies the DataProvider key to mark labels as selected for placement.
 void setStoreRects(boolean s)
          Sets whether the candidate rectangles should be stored to be retrieved.
 void setUseAlternativeSideHandling(boolean useAlternativeSideHandling)
          Deprecated. use PreferredPlacementDescriptor.setSideReference(byte) with PreferredPlacementDescriptor.SIDE_IS_ABSOLUTE_WITH_LEFT_IN_NORTH or PreferredPlacementDescriptor.SIDE_IS_ABSOLUTE_WITH_RIGHT_IN_NORTH as argument instead
 
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

LABEL_MODEL_DPKEY

public static final java.lang.Object LABEL_MODEL_DPKEY
A DataProvider key for mapping models to edge/node labels

The NodeLabelModels and EdgeLabelModels linked to NodeLabelLayouts and EdgeLabelLayouts by this DataProvider are taken as replacement models. This means that the original model is internally replaced by another model when computing valid positions for the label. A model parameter that fits the calculated position of the replacement model best is set for the original label model.

 
This feature is especially useful to restrict a free model. For example, to place a label upon its associated edge, a centered RotatedSliderEdgeLabelModel can be used as replacement model.
 
If there is no DataProvider registered with this key, then the original models will be used.

setCustomizedProfitModel

protected boolean setCustomizedProfitModel
For internal use only.


EPS

protected static final double EPS
Constant for internal use only.

See Also:
Constant Field Values
Constructor Detail

AbstractLabelingAlgorithm

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

Method Detail

getProfitModel

public ProfitModel getProfitModel()
Returns the ProfitModel for ranking the LabelCandidates for labels.

The profit model is used when calculating the profit of a candidate.

Returns:
a ProfitModel instance for ranking label candidates
See Also:
setProfitModel(ProfitModel)

isMoveInternalNodeLabels

public boolean isMoveInternalNodeLabels()
Returns whether or not internal node labels are allowed to move.

A node label is internal if the label's boundaries are completely within the node's boundaries.

 
This setting will only have an effect if node labeling is enabled.
 
This feature only works in conjunction with NodeLabelModels that restrict the positioning of labels (i.e. non-free label models).
Returns:
true if internal node labels may be moved, false otherwise
See Also:
setMoveInternalNodeLabels(boolean)

setMoveInternalNodeLabels

public void setMoveInternalNodeLabels(boolean moveInternalNodeLabels)
Specifies whether or not internal node labels are allowed to move.

A node label is internal if the label's boundaries are completely within the node's boundaries.

 
This setting will only have an effect if node labeling is enabled.
 
This feature only works in conjunction with NodeLabelModels that restrict the positioning of labels (i.e. non-free label models).
Default Value:
The default value is false. Internal node labels will not be moved.
Parameters:
moveInternalNodeLabels - true if internal node labels may be moved, false otherwise
Sample Graphs:

false - internal labels were not moved, even though they overlap

true - internal labels were moved

isApplyPostprocessing

public boolean isApplyPostprocessing()
Returns whether or not a post-processing step to reduce the number of label overlaps is applied.

 
The overlap reduction process is only applied to edge labels whose EdgeLabelModel is of type FreeEdgeLabelModel and node labels whose NodeLabelModel is of type FreeNodeLabelModel.
Returns:
true if a post-processing step for reducing the number of label overlaps is applied, false otherwise
See Also:
setApplyPostprocessing(boolean)

setApplyPostprocessing

public void setApplyPostprocessing(boolean applyPostprocessing)
Specifies whether or not a post-processing step to reduce the number of label overlaps is applied.

 
The overlap reduction process is only applied to edge labels whose EdgeLabelModel is of type FreeEdgeLabelModel and node labels whose NodeLabelModel is of type FreeNodeLabelModel.
Default Value:
The default value is false. Post-processing to reduce overlaps is disabled.
Parameters:
applyPostprocessing - true if a post-processing step for reducing the number of label overlaps should be applied, false otherwise

isUseAlternativeSideHandling

public boolean isUseAlternativeSideHandling()
Deprecated. use PreferredPlacementDescriptor.getSideReference() instead

Returns whether or not the preference on which side of an edge a corresponding label should be placed is interpreted by human perception instead of always following the edge from source to target.

 
The alternative side handling is only applied to edge labels whose edge label model is FreeEdgeLabelModel.
Returns:
true, if the preferred side for an edge label is interpreted according to human perception, false otherwise

setUseAlternativeSideHandling

public void setUseAlternativeSideHandling(boolean useAlternativeSideHandling)
Deprecated. use PreferredPlacementDescriptor.setSideReference(byte) with PreferredPlacementDescriptor.SIDE_IS_ABSOLUTE_WITH_LEFT_IN_NORTH or PreferredPlacementDescriptor.SIDE_IS_ABSOLUTE_WITH_RIGHT_IN_NORTH as argument instead

Specifies whether or not the preference on which side of an edge a corresponding label should be placed is interpreted by human perception instead of always following the edge from source to target.

 
The alternative side handling is only applied to edge labels whose edge label model is FreeEdgeLabelModel.
Parameters:
useAlternativeSideHandling - true, if the preferred side for an edge label should be interpreted according to human perception, false otherwise

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.

 
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).
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 candidates left and above the node are overlapping and will thus be removed

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.

 
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).
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, even though some are overlapping with an edge

true - only two of the four candidate positions are allowed, the others will be 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.

 
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).
Returns:
true if candidates overlapping with nodes are removed, false otherwise
See Also:
setRemoveNodeOverlaps(boolean)

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.

 
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).
Returns:
true if candidates overlapping with edges are removed, false otherwise
See Also:
setRemoveEdgeOverlaps(boolean)

setPlaceNodeLabels

public void setPlaceNodeLabels(boolean enable)
Specifies whether or not labels assigned to nodes are placed.

 
This setting has higher priority than any custom label selection. If it is disabled, node labels marked via the selection will still be ignored. If enabled, then the selection may determine whether a label is placed or not.
Default Value:
The default value is true. Node labels will be placed.
Parameters:
enable - true if node labels should be placed, false otherwise
See Also:
getPlaceNodeLabels(), setSelection(Object)

setPlaceEdgeLabels

public void setPlaceEdgeLabels(boolean enable)
Specifies whether or not labels assigned to edges are placed.

 
This setting has higher priority than any custom label selection. If it is disabled, edge labels marked via the selection will still be ignored. If enabled, then the selection may determine whether a label is placed or not.
Default Value:
The default value is true. Edge labels will be placed.
Parameters:
enable - true if edge labels should be placed, false otherwise
See Also:
getPlaceEdgeLabels(), setSelection(Object)

getPlaceNodeLabels

public boolean getPlaceNodeLabels()
Returns whether or not labels assigned to nodes are placed.

 
This setting has higher priority than any custom label selection. If it is disabled, node labels marked via the selection will still be ignored. If enabled, then the selection may determine whether a label is placed or not.
Returns:
true if node labels should be placed, false otherwise
See Also:
setSelection(Object), setPlaceNodeLabels(boolean)

getPlaceEdgeLabels

public boolean getPlaceEdgeLabels()
Returns whether or not labels assigned to edges are placed.

 
This setting has higher priority than any custom label selection. If it is disabled, edge labels marked via the selection will still be ignored. If enabled, then the selection may determine whether a label is placed or not.
Returns:
true if edge labels should be placed, false otherwise
See Also:
setSelection(Object), setPlaceEdgeLabels(boolean)

setSelection

public void setSelection(java.lang.Object key)
Specifies the DataProvider key to mark labels as selected for placement.

If a DataProvider is registered with this key, only the selected labels will be placed, while all other labels are considered fixed.

The registered DataProvider needs to map from LabelLayout to Boolean where true indicates that a label should be placed and false indicates that a label should be ignored.

 
The specified selection will be ignored when invoking the algorithm via label(LayoutGraph, Object) or label(LayoutGraph, YList, YList). Furthermore, if node labeling or edge labeling is disabled, the selection does not have any effect on the respective labels.
Default Value:
The default value is null. All labels are considered to be selected.
Parameters:
key - the DataProvider key for marking labels as selected or null if all labels should be considered selected

getSelectionKey

public java.lang.Object getSelectionKey()
Returns the DataProvider key to mark labels as selected for placement.

If a DataProvider is registered with this key, only the selected labels will be placed, while all other labels are considered fixed.

The registered DataProvider needs to map from LabelLayout to Boolean where true indicates that a label should be placed and false indicates that a label should be ignored.

 
The specified selection will be ignored when invoking the algorithm via label(LayoutGraph, Object) or label(LayoutGraph, YList, YList). Furthermore, if node labeling or edge labeling is disabled, the selection does not have any effect on the respective labels.
Returns:
the DataProvider key for marking labels as selected or null if all labels should be considered selected

isAutoFlippingEnabled

public boolean isAutoFlippingEnabled()
Returns whether or not edge labels are automatically flipped if otherwise they would be upside-down.

 
This feature has an effect only if labels have a free model (e.g. SmartEdgeLabelModel).
Returns:
true, if edge labels automatically flip, false otherwise

setAutoFlippingEnabled

public void setAutoFlippingEnabled(boolean enabled)
Specifies whether or not edge labels are automatically flipped if otherwise they would be upside-down.

 
This feature has an effect only if labels have a free model (e.g. SmartEdgeLabelModel).
Default Value:
The default value is false. Edge labels being upside-down keep their orientation.
Parameters:
enabled - true, if edge labels should automatically flip, false otherwise
Sample Graphs:

false

true

canLayout

public boolean canLayout(LayoutGraph graph)
Accepts all graphs whose nodes have sizes greater than 0 and that the specified core layout algorithm can handle. If there is no core layout algorithm specified, all general graphs without zero-sized nodes are accepted.

Parameters:
graph - the input graph
Returns:
true if the core layout algorithm can handle the given graph and this graph doesn't contain nodes with size 0, false otherwise
See Also:
Layouter.doLayout(LayoutGraph)

doLayout

public void doLayout(LayoutGraph graph)
Places the labels in the graph after first executing the core layouter.

 
Calls method label(LayoutGraph) to perform the actual labeling.
Parameters:
graph - the input graph
See Also:
label(LayoutGraph)

checkNodeSize

protected void checkNodeSize(GraphLayout layout,
                             java.lang.Object node)
                      throws java.lang.IllegalArgumentException
Checks whether or not the given node's width or height is zero or negative.

This method is called in doLayout(LayoutGraph) before the core layout algorithm is invoked. It can be overridden to remove/change this check.

Parameters:
layout - a graph layout object
node - the node
Throws:
java.lang.IllegalArgumentException - if width or height of the node object is zero or negative
See Also:
checkGroupNodeSize(GraphLayout, Object)

checkGroupNodeSize

protected void checkGroupNodeSize(GraphLayout layout,
                                  java.lang.Object node)
                           throws java.lang.IllegalArgumentException
Checks whether or not the given group node's width or height is zero or negative.

This method is called in doLayout(LayoutGraph) before the core layout algorithm is invoked. It can be overridden to remove/change this check.

Parameters:
layout - a graph layout object
node - the group node
Throws:
java.lang.IllegalArgumentException - if width or height of the group node object is zero or negative
See Also:
checkNodeSize(GraphLayout, Object)

label

public void label(LayoutGraph graph)
Places the labels of the given graph using the label selection defined by the DataProvider registered with the current selection key.

Only selected labels will be placed.

Parameters:
graph - the input graph
See Also:
label(LayoutGraph, Object)

label

public void label(LayoutGraph graph,
                  java.lang.Object key)
Places the labels of the input graph using a DataProvider registered to the input graph with the given key for determining which labels to place.

Instead of considering the current selection key, the DataProvider registered with the given key will be used for selecting labels. Invoking this method has the same effect as first specifying the key as selection key and then invoking label(LayoutGraph).

Parameters:
graph - the input graph
key - the DataProvider key for label selection

label

public void label(LayoutGraph graph,
                  YList nodeLabels,
                  YList edgeLabels)
Places the labels of the input graph restricting the placement to labels contained in the given lists.

The selection will not be considered; the given lists will define the selection of labels that are to be placed.

 
If node labeling or edge labeling is disabled, then the labels of the respective given list will not be placed.
Parameters:
graph - the input graph
nodeLabels - a list of NodeLabelLayouts defining the set of node labels that will be placed
edgeLabels - a list of EdgeLabelLayouts defining the set of edge labels that will be placed

setProfitModel

public void setProfitModel(ProfitModel model)
Specifies the ProfitModel for ranking the LabelCandidates for labels.

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:
The default value is LabelRanking
Parameters:
model - a ProfitModel instance for ranking label candidates
See Also:
ProfitModel, LabelRanking, getProfit(LabelCandidate)

getProfit

public double getProfit(LabelCandidate candidate)
Returns the profit for placing a LabelCandidate with respect to the current profit model.

Method ProfitModel.getProfit(LabelCandidate) 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.

 
If the current profit model is null, then the profit will be 1, except if the candidate's parameter is of type SliderEdgeLabelModel; in that case, the position of the label on the edge will be taken into consideration for the profit calculation.
Parameters:
candidate - a label candidate
Returns:
the profit value between 0 and 1

getRects

public YList getRects()
Returns the set of all generated candidate rectangles.

 
For internal debug use only.

setStoreRects

public void setStoreRects(boolean s)
Sets whether the candidate rectangles should be stored to be retrieved.

 
For internal debug use only.

isStoreRects

public boolean isStoreRects()
Returns whether the candidate rectangles should be stored to be retrieved.

 
For internal debug use only.

isEdgeGroupOverlapAllowed

public boolean isEdgeGroupOverlapAllowed()
Returns whether or not edge labels may overlap with edges belonging to the same edge group as the label's edge.

An edge group is a set of edges which share a common bus near the target or source node. They are defined using DataProviders registered with PortConstraintKeys.SOURCE_GROUPID_KEY and PortConstraintKeys.TARGET_GROUPID_KEY.

Returns:
true if edge labels may overlap with edges of the same edge group, false otherwise
See Also:
setEdgeGroupOverlapAllowed(boolean), PortConstraintKeys.SOURCE_GROUPID_KEY, PortConstraintKeys.TARGET_GROUPID_KEY

setEdgeGroupOverlapAllowed

public void setEdgeGroupOverlapAllowed(boolean edgeGroupOverlapAllowed)
Specifies whether or not edge labels may overlap with edges belonging to the same edge group as the label's edge.

An edge group is a set of edges which share a common bus near the target or source node. They are defined using DataProviders registered with PortConstraintKeys.SOURCE_GROUPID_KEY and PortConstraintKeys.TARGET_GROUPID_KEY.

Default Value:
The default value is false. Edge labels are not allowed to overlap with edges of the same edge group.
Parameters:
edgeGroupOverlapAllowed - true if edge labels may overlap with edges of the same edge group, false otherwise
See Also:
PortConstraintKeys.SOURCE_GROUPID_KEY, PortConstraintKeys.TARGET_GROUPID_KEY
Sample Graphs:

true (assume that labels need to be placed left of edges)

false (assume that labels need to be placed left of edges)

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