Search this API

y.layout.labeling
Class GreedyMISLabeling

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.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:
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
GreedyMISLabeling()
          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

GreedyMISLabeling

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

Method Detail

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.

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.

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

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