y.layout.labeling
Class MISLabelingAlgorithm

java.lang.Object
  |
  +--y.layout.AbstractLayoutStage
        |
        +--y.layout.labeling.AbstractLabelingAlgorithm
              |
              +--y.layout.labeling.MISLabelingAlgorithm

All Implemented Interfaces:

Layouter, LayoutStage

Direct Known Subclasses:

GreedyMISLabeling, SALabeling

public abstract class MISLabelingAlgorithm

extends AbstractLabelingAlgorithm

Solving labeling problem by reducing it to the maximum independent set problem.

Field Summary

protected Graph	conflictGraph the conflict graph
protected NodeMap	nodesToBoxes
protected NodeMap	nodesToID
protected static boolean	showGraph

Fields inherited from interface y.layout.Layouter

EDGE_ID_DPKEY, NODE_ID_DPKEY, SELECTED_EDGES, SELECTED_NODES

Constructor Summary

MISLabelingAlgorithm()

Method Summary

protected NodeMap	assignProfit() Creates a node map which assigns to each node the profit.
void	createConflictGraph(y.layout.labeling.Label[] labels) Creates the conflict graph.
protected void	createEdges() Creates one edge bewtween two nodes if the corresponding label candidates are intersecting.
protected void	createNodes(y.layout.labeling.Label[] labels) Creates one node in the conflict graph for each label candidate.
protected void	intersectionSL()
protected void	label(LayoutGraph graph, y.layout.labeling.Label[] labels) Performs labeling by solving a MIS.
void	propagateSolution(y.layout.labeling.Label[] labels, NodeList mis) Places the labels according to the independent set.
protected abstract NodeList	solveMIS(y.layout.labeling.Label[] labels) Here the maximum independent set problem should be solved.

Methods inherited from class y.layout.labeling.AbstractLabelingAlgorithm

canLayout, doLayout, getPlaceEdgeLabels, getPlaceNodeLabels, getProfit, getRects, getRemoveEdgeOverlaps, getRemoveNodeOverlaps, getSelectionKey, isEdgeGroupOverlapAllowed, isStoreRects, label, label, label, removeEdgesOverlaps, removeNodesOverlaps, setEdgeGroupOverlapAllowed, setPlaceEdgeLabels, setPlaceNodeLabels, setProfitModel, setRemoveEdgeOverlaps, setRemoveNodeOverlaps, setSelection, setStoreRects

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

Field Detail

conflictGraph

protected Graph conflictGraph

the conflict graph

nodesToBoxes

protected NodeMap nodesToBoxes

nodesToID

protected NodeMap nodesToID

showGraph

protected static boolean showGraph

Constructor Detail

MISLabelingAlgorithm

public MISLabelingAlgorithm()

Method Detail

label

protected void label(LayoutGraph graph,
                     y.layout.labeling.Label[] labels)

Performs labeling by solving a MIS.

Specified by:

label in class AbstractLabelingAlgorithm

createConflictGraph

public void createConflictGraph(y.layout.labeling.Label[] labels)

Creates the conflict graph.

solveMIS

protected abstract NodeList solveMIS(y.layout.labeling.Label[] labels)

Here the maximum independent set problem should be solved. The nodes which are choosen to be in the maximum independent set are returned in a list.

propagateSolution

public void propagateSolution(y.layout.labeling.Label[] labels,
                              NodeList mis)

Places the labels according to the independent set. Labels which have no candidate position in the independent set are placed in a minimum overlaping fashion.

createNodes

protected void createNodes(y.layout.labeling.Label[] labels)

Creates one node in the conflict graph for each label candidate.

createEdges

protected void createEdges()

Creates one edge bewtween two nodes if the corresponding label candidates are intersecting.

intersectionSL

protected void intersectionSL()

assignProfit

protected NodeMap assignProfit()

Creates a node map which assigns to each node the profit.