y.layout.labeling
Class MISLabelingAlgorithm

java.lang.Object
  y.layout.AbstractLayoutStage
      y.layout.labeling.AbstractLabelingAlgorithm
          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()