y.layout.planar
Class OverlapGraphMIS

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

public class OverlapGraphMIS
extends 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 calculaton 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 endnode's order number gained by sorting the vertices with createVertexOrder().
void	dispose() Disposes no longer needed node maps.
EdgeList	getHiddenEdges()
ArrayList	getMIS1()
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 calculaton class.

Parameters:

graph - the graph which defines the intervalls.

weight - weight in the MIS.

Method Detail

getMIS1

public ArrayList getMIS1()

getMIS2

public 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 endnode'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.