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

Solving labeling problem by reducing it to the maximum independent set problem.

Field Summary

protected Map	boxesToNodes
protected Graph	conflictGraph the conflict graph
protected LayoutGraph	graph
protected NodeMap	nodesToBoxes holds for each node in the conflictGraph the corresponding LabelCandidate
protected NodeMap	nodesToID holds for each node in the conflictGraph the corresponding integer index of the Label[]
static byte	OPTIMIZATION_BALANCED Use a balanced optimization strategy.
static byte	OPTIMIZATION_EDGE_OVERLAP Use an optimization strategy that especially reduces overlaps between labels and edges.
static byte	OPTIMIZATION_LABEL_OVERLAP Use an optimization strategy that especially reduces overlaps between labels.
static byte	OPTIMIZATION_NODE_OVERLAP Use an optimization strategy that especially reduces overlaps between labels and nodes.
static byte	OPTIMIZATION_NONE Use no optimization strategy.

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, SELECTED_EDGES, SELECTED_NODES

Constructor Summary

MISLabelingAlgorithm()

Method Summary

protected NodeMap	assignProfit() Creates a node map which assigns to each node the profit.
protected void	createEdges() Creates one edge between two nodes if the corresponding label candidates are intersecting.
protected void	foundEdgeOverlap(LabelCandidate lc, Edge e, LineSegment eSegment) Calculates the overlapping factor between a label candidate and an edge segment.
protected void	foundLabelOverlap(LabelCandidate lc1, LabelCandidate lc2, Edge e) Calculates the overlapping factor between two label candidates.
protected void	foundNodeOverlap(LabelCandidate lc, Node n, YRectangle nBox) Calculates the overlapping factor between a label candidate and a node.
double	getCustomProfitModelRatio() Returns the custom profit model ratio.
byte	getOptimizationStrategy() Returns the optimization strategy of the labeling algorithm.
void	setCustomProfitModelRatio(double customProfitModelRatio) If an optimization strategy is set (see setOptimizationStrategy(byte)) as well as a profit model (see AbstractLabelingAlgorithm.setProfitModel(y.layout.ProfitModel)), the specified ratio (0 <= customProfitModelRatio <= 1) determines the ratio between the internal profit (ip) depending on the used optimization strategy as well as the profit returned by the specified profit model (sp), i.e., overall profit = customProfitModelRatio * sp + (1 - customProfitModelRatio) * ip.
void	setOptimizationStrategy(byte optimizationStrategy) Sets the optimization strategy of the labeling algorithm.

Methods inherited from class y.layout.labeling.AbstractLabelingAlgorithm

canLayout, checkGroupNodeSize, checkNodeSize, doLayout, getPlaceEdgeLabels, getPlaceNodeLabels, getProfit, getProfitModel, getRects, getRemoveEdgeOverlaps, getRemoveNodeOverlaps, getSelectionKey, isApplyPostprocessing, isAutoFlippingEnabled, isEdgeGroupOverlapAllowed, isMoveInternalNodeLabels, isStoreRects, isUseAlternativeSideHandling, label, label, label, setApplyPostprocessing, setAutoFlippingEnabled, setEdgeGroupOverlapAllowed, setMoveInternalNodeLabels, setPlaceEdgeLabels, setPlaceNodeLabels, setProfitModel, setRemoveEdgeOverlaps, setRemoveNodeOverlaps, 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

Use a balanced optimization strategy.

See Also:

Constant Field Values

OPTIMIZATION_NODE_OVERLAP

public static final byte OPTIMIZATION_NODE_OVERLAP

Use an optimization strategy that especially reduces overlaps between labels and nodes.

See Also:

Constant Field Values

OPTIMIZATION_LABEL_OVERLAP

public static final byte OPTIMIZATION_LABEL_OVERLAP

Use an optimization strategy that especially reduces overlaps between labels.

See Also:

Constant Field Values

OPTIMIZATION_EDGE_OVERLAP

public static final byte OPTIMIZATION_EDGE_OVERLAP

Use an optimization strategy that especially reduces overlaps between labels and edges.

See Also:

Constant Field Values

OPTIMIZATION_NONE

public static final byte OPTIMIZATION_NONE

Use no optimization strategy.

See Also:

Constant Field Values

graph

protected LayoutGraph graph

conflictGraph

protected Graph conflictGraph

the conflict graph

nodesToBoxes

protected NodeMap nodesToBoxes

holds for each node in the conflictGraph the corresponding LabelCandidate

boxesToNodes

protected Map boxesToNodes

nodesToID

protected NodeMap nodesToID

holds for each node in the conflictGraph the corresponding integer index of the Label[]

Constructor Detail

MISLabelingAlgorithm

public MISLabelingAlgorithm()

Method Detail

getCustomProfitModelRatio

public double getCustomProfitModelRatio()

Returns the custom profit model ratio.

See Also:

setCustomProfitModelRatio(double)

setCustomProfitModelRatio

public void setCustomProfitModelRatio(double customProfitModelRatio)

If an optimization strategy is set (see setOptimizationStrategy(byte)) as well as a profit model (see AbstractLabelingAlgorithm.setProfitModel(y.layout.ProfitModel)), the specified ratio (0 <= customProfitModelRatio <= 1) determines the ratio between the internal profit (ip) depending on the used optimization strategy as well as the profit returned by the specified profit model (sp), i.e., overall profit = customProfitModelRatio * sp + (1 - customProfitModelRatio) * ip.

Parameters:

customProfitModelRatio - specifies the ratio.

See Also:

AbstractLabelingAlgorithm.setProfitModel(y.layout.ProfitModel), setOptimizationStrategy(byte)

getOptimizationStrategy

public byte getOptimizationStrategy()

Returns the optimization strategy of the labeling algorithm. Possible values are: OPTIMIZATION_NONE, OPTIMIZATION_BALANCED, OPTIMIZATION_NODE_OVERLAP, OPTIMIZATION_EDGE_OVERLAP and OPTIMIZATION_LABEL_OVERLAP.

setOptimizationStrategy

public void setOptimizationStrategy(byte optimizationStrategy)

Sets the optimization strategy of the labeling algorithm.

Parameters:

optimizationStrategy - possible values are OPTIMIZATION_NONE, OPTIMIZATION_BALANCED, OPTIMIZATION_NODE_OVERLAP, OPTIMIZATION_EDGE_OVERLAP and OPTIMIZATION_LABEL_OVERLAP. By default OPTIMIZATION_BALANCED is set.

createEdges

protected void createEdges()

Creates one edge between two nodes if the corresponding label candidates are intersecting.

assignProfit

protected NodeMap assignProfit()

Creates a node map which assigns to each node the profit.

foundLabelOverlap

protected void foundLabelOverlap(LabelCandidate lc1,
                                 LabelCandidate lc2,
                                 Edge e)

Calculates the overlapping factor between two label candidates. Default value is 1.0.

foundNodeOverlap

protected void foundNodeOverlap(LabelCandidate lc,
                                Node n,
                                YRectangle nBox)

Calculates the overlapping factor between a label candidate and a node.

foundEdgeOverlap

protected void foundEdgeOverlap(LabelCandidate lc,
                                Edge e,
                                LineSegment eSegment)

Calculates the overlapping factor between a label candidate and an edge segment.