Search this API

Class GreedyMISLabeling

  extended by y.layout.AbstractLayoutStage
      extended by y.layout.labeling.AbstractLabelingAlgorithm
          extended by y.layout.labeling.MISLabelingAlgorithm
              extended by y.layout.labeling.GreedyMISLabeling
All Implemented Interfaces:
Layouter, LayoutStage

public class GreedyMISLabeling
extends MISLabelingAlgorithm

A generic labeling algorithm for placing the labels of a graph, which reduces the labeling problem to the maximum independent set (MIS) problem and solves the problem using a greedy strategy.

Node labels and edge labels placed by the labeling algorithm

Thanks to the greedy strategy solving the MIS problem, this algorithm provides a very fast labeling algorithm (e.g. faster than SALabeling). Therefore, it is well suited for application on graphs with many labels where the quality of the placement is not highly important.

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.

See Also:

Field Summary
Fields inherited from class y.layout.labeling.MISLabelingAlgorithm
Fields inherited from class y.layout.labeling.AbstractLabelingAlgorithm
EPS, LABEL_MODEL_DPKEY, setCustomizedProfitModel
Fields inherited from interface y.layout.Layouter
Constructor Summary
          Creates a new instance of GreedyMISLabeling with default settings.
Method Summary
protected  NodeMap assignProfit()
          Returns a NodeMap which assigns a profit value to each node in the conflict graph.
Methods inherited from class y.layout.labeling.MISLabelingAlgorithm
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


public GreedyMISLabeling()
Creates a new instance of GreedyMISLabeling with default settings.

Method Detail


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.

This method is used for sorting the label candidates with respect to their profit value. It will be called only if the optimization strategy is set to MISLabelingAlgorithm.OPTIMIZATION_NONE. By overriding this method, custom profit values can be assigned to the nodes.

The returned map is a mapping from each Node (representing a label candidate) in the MISLabelingAlgorithm.conflictGraph to a Double value representing the profit of the candidate.

assignProfit in class MISLabelingAlgorithm
a mapping from nodes (i.e. label candidates) to their profit value

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