y.layout.labeling
Class GreedyMISLabeling

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