Search this API

y.layout.labeling
Class SALabeling

java.lang.Object
  extended by y.layout.AbstractLayoutStage
      extended by y.layout.labeling.AbstractLabelingAlgorithm
          extended by y.layout.labeling.MISLabelingAlgorithm
              extended by 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, 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)

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