y.layout.labeling
Class SALabeling

java.lang.Object
  y.layout.AbstractLayoutStage
      y.layout.labeling.AbstractLabelingAlgorithm
          y.layout.labeling.MISLabelingAlgorithm
              y.layout.labeling.SALabeling

All Implemented Interfaces:

Layouter, LayoutStage

public class SALabeling
extends MISLabelingAlgorithm

A generic labeling algorithm for placing the labels of a graph.

Node labels and edge labels placed by the labeling algorithm

This algorithm reduces the labeling problem to the maximum independent set (MIS) problem and solves the problem using simulated annealing. It is inspired by the article from Christensen, Marks and Shieber: A General Cartographic Labelling Algorithm.

Due to the simulated annealing technique, this implementation is able to generate highly optimized label assignments. For difficult labeling instances, this algorithm will likely produce higher quality results than the simpler GreedyMISLabeling. This especially holds if the label models allow a large number of different LabelCandidates, i.e., if there is a high potential for optimizations. However, the runtime of this algorithm may be slower compared to that of GreedyMISLabeling.

It is recommended to use EdgeLabelModels and NodeLabelModels which allow free positioning of labels to achieve best results with this generic labeling algorithm. If possible, SmartEdgeLabelModel and SmartNodeLabelModel are recommended.

This algorithm works according to the general labeling concept defined by AbstractLabelingAlgorithm.

If the maximal duration is set to 0, this implementation automatically switches to the simpler but faster GreedyMISLabeling.

See Also:

AbstractLabelingAlgorithm

Field Summary

Fields inherited from class y.layout.labeling.MISLabelingAlgorithm

boxesToNodes, conflictGraph, graph, nodesToBoxes, nodesToID, OPTIMIZATION_BALANCED, OPTIMIZATION_EDGE_OVERLAP, OPTIMIZATION_LABEL_OVERLAP, OPTIMIZATION_NODE_OVERLAP, OPTIMIZATION_NONE, OPTIMIZATION_PREFERRED_PLACEMENT

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

SALabeling()
Creates a new instance of SALabeling with default settings.

Method Summary

long	getMaximalDuration() Returns the time limit for this algorithm in milliseconds.
boolean	isDeterministicModeEnabled() Returns whether or not this algorithm behaves deterministically.
void	setDeterministicModeEnabled(boolean deterministicModeEnabled) Specifies whether or not this algorithm behaves deterministically.
void	setMaximalDuration(long maximumDuration) Specifies the time limit for this algorithm in milliseconds.

Methods inherited from class y.layout.labeling.MISLabelingAlgorithm

assignProfit, createEdges, foundEdgeOverlap, foundHaloOverlap, foundLabelOverlap, foundNodeOverlap, getCustomProfitModelRatio, getOptimizationStrategy, getRemoveEdgeOverlaps, getRemoveNodeOverlaps, isAmbiguityReductionEnabled, setAmbiguityReductionEnabled, setCustomProfitModelRatio, setOptimizationStrategy, setRemoveEdgeOverlaps, setRemoveNodeOverlaps

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

Constructor Detail

SALabeling

public SALabeling()

Creates a new instance of SALabeling with default settings.

Method Detail

isDeterministicModeEnabled

public boolean isDeterministicModeEnabled()

Returns whether or not this algorithm behaves deterministically. If enabled, it produces the same results given the same input graph and settings.

Returns:

true if this algorithm works deterministically, false otherwise

See Also:

setDeterministicModeEnabled(boolean)

setDeterministicModeEnabled

public void setDeterministicModeEnabled(boolean deterministicModeEnabled)

Specifies whether or not this algorithm behaves deterministically. If enabled, it produces the same results given the same input graph and settings.

Default Value:

The default value is true. Labeling results are deterministic.

Parameters:

deterministicModeEnabled - true if this algorithm should work deterministically, false otherwise

setMaximalDuration

public void setMaximalDuration(long maximumDuration)

Specifies the time limit for this algorithm in milliseconds.

Integer.MAX_VALUE denotes that there is no time limit. Values have to be greater than or equal to 0.

Restricting the maximum duration may lead to a lower result quality. Furthermore, the algorithm can not guarantee to strictly observe the specified time limit.

Default Value:

The default value is Integer.MAX_VALUE. There is no time limit.

Parameters:

maximumDuration - a non-negative value representing the time limit in milliseconds

Throws:

java.lang.IllegalArgumentException - if the given maximum duration is negative

getMaximalDuration

public long getMaximalDuration()

Returns the time limit for this algorithm in milliseconds.

Integer.MAX_VALUE denotes that there is no time limit. Values have to be greater than or equal to 0.

Restricting the maximum duration may lead to a lower result quality. Furthermore, the algorithm can not guarantee to strictly observe the specified time limit.

Returns:

a non-negative value representing the time limit in milliseconds

See Also:

setMaximalDuration(long)