y.layout.planar
Class OverlapGraphMIS

java.lang.Object
  y.layout.planar.OverlapGraphMIS

public class OverlapGraphMIS
extends java.lang.Object

This class handles the computation of the two maximum independent sets for the planarization algorithm GT.

Constructor Summary

OverlapGraphMIS(Graph graph, EdgeMap weight)
Creates a new instance of the independent set calculation class.

Method Summary

void	computeMaximumIndependentSets(NodeList orderedNodes, int[] orderNumbers) computes two maximum independent sets of edges. here independent means that the edges do not overlap (with respect to their end node's order number gained by sorting the vertices with createVertexOrder().
void	dispose() Disposes no longer needed node maps.
EdgeList	getHiddenEdges()
java.util.ArrayList	getMIS1()
java.util.ArrayList	getMIS2()

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

OverlapGraphMIS

public OverlapGraphMIS(Graph graph,
                       EdgeMap weight)

Creates a new instance of the independent set calculation class.

Parameters:

graph - the graph which defines the intervals.

weight - weight in the MIS.

Method Detail

getMIS1

public java.util.ArrayList getMIS1()

getMIS2

public java.util.ArrayList getMIS2()

getHiddenEdges

public EdgeList getHiddenEdges()

computeMaximumIndependentSets

public void computeMaximumIndependentSets(NodeList orderedNodes,
                                          int[] orderNumbers)

computes two maximum independent sets of edges. here independent means that the edges do not overlap (with respect to their end node's order number gained by sorting the vertices with createVertexOrder(). the result is not equivalent to the maximum bipartite graph of the overlap graph! The independent sets are stored int MIS1 and MIS2.

dispose

public void dispose()

Disposes no longer needed node maps.