y.layout.labeling
Class AbstractLabelingAlgorithm

java.lang.Object
  y.layout.AbstractLayoutStage
      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, NODE_TYPE_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)