y.layout.planar
Class GT

java.lang.Object
  y.layout.planar.GT

All Implemented Interfaces:

InitialPlanarSubgraph

public class GT
extends java.lang.Object
implements InitialPlanarSubgraph

This class implements a powerful planar-subgraph heuristic. The heuristic is an extension of the Goldschmidt/Takvorian Algorithm which is described in Eiglsperger/Kaufmann.

Nested Class Summary

static class	GT.EdgeListComparator
static class	GT.MIS1Comparator Defines ordering for edges in the the first Maximum Independent Set.
static class	GT.MIS2Comparator Defines ordering for edges in the second Maximum Independent Set.

Field Summary

protected GT.EdgeListComparator	edgeListComparator
protected Node	globalSink
protected Node	globalSource
protected Graph	graph
protected EdgeList	hiddenEdges
protected boolean	isValid
protected GT.MIS1Comparator	mis1Comparator
protected GT.MIS2Comparator	mis2Comparator
protected Edge	outerFaceDeterminationEdge
protected Node	outerFaceDeterminationNode
protected PlanarInformation	planar
protected VertexOrder	vertexOrder

Constructor Summary

GT()
Returns a new instance of GT.

Method Summary

protected void	calcMISIncidents(EdgeList MIS, NodeMap MISIncidents) Calculates form the independent set of edges, the edges incident to an node which are inside this independent set.
protected NodeList	calcOrdering(int[] orderNumbers, OverlapGraphMIS mis)
protected void	createCircularEdgeOrder(EdgeList MIS1, EdgeList MIS2, NodeMap downwardLink, NodeMap upwardLink, int[] orderNumbers) this method sorts each nodes incident edges according to the aim of yielding a planar embedding for a subgraph of the input graph It also assigns first incoming/outgoing.
void	createPlanarization(PlanarInformation p) This method planarizes a graph by finding (a maximum) planar sub- graph.
protected void	createReverseEdges()
void	dispose() Cleaning up resources.
boolean	getAllowRandomization() Returns if the algorithm will use randomization to improve the result.
EdgeList	getHiddenEdges() Returns a list of the edges that have been removed in order to gain a planarization of the input graph.
int	getIterations() Returns number of iterations when randomization is used.
Node	getSink() Returns the sink of the st-graph.
Node	getSource() Returns the source of the st-graph.
protected void	initOrdering(NodeMap downwardLink, NodeMap upwardLink, NodeList orderedNodes) Initializes data structures from an ordering.
void	setAllowRandomization(boolean value) Sets if the algorithm will use randomization to improve the result.
void	setIterations(int _iterations) Set number of iterations when randomization is used.
protected void	showEdgePartitionResult(java.util.ArrayList MIS1, java.util.ArrayList MIS2)
protected void	showGraphicDebug(EdgeList MIS1, EdgeList MIS2, int[] orderNumbers)
protected void	showIncidentEdges(NodeMap MIS1Incidents, NodeMap MIS2Incidents, EdgeMap downwardLink, EdgeMap upwardLink)
protected void	showVertexOrder(int[] orderNumbers)

Methods inherited from class java.lang.Object

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

Field Detail

edgeListComparator

protected GT.EdgeListComparator edgeListComparator

mis1Comparator

protected GT.MIS1Comparator mis1Comparator

mis2Comparator

protected GT.MIS2Comparator mis2Comparator

planar

protected PlanarInformation planar

graph

protected Graph graph

isValid

protected boolean isValid

vertexOrder

protected VertexOrder vertexOrder

outerFaceDeterminationEdge

protected Edge outerFaceDeterminationEdge

outerFaceDeterminationNode

protected Node outerFaceDeterminationNode

hiddenEdges

protected EdgeList hiddenEdges

globalSource

protected Node globalSource

globalSink

protected Node globalSink

Constructor Detail

GT

public GT()

Returns a new instance of GT.

Method Detail

setAllowRandomization

public void setAllowRandomization(boolean value)

Sets if the algorithm will use randomization to improve the result.

Parameters:

value - if true the undirected edges in the graph are directed.

getAllowRandomization

public boolean getAllowRandomization()

Returns if the algorithm will use randomization to improve the result.

setIterations

public void setIterations(int _iterations)

Set number of iterations when randomization is used.

getIterations

public int getIterations()

Returns number of iterations when randomization is used.

getHiddenEdges

public EdgeList getHiddenEdges()

Returns a list of the edges that have been removed in order to gain a planarization of the input graph. The createPlanarization method of this class must have been called earlier to compute the list of hidden edges. If not so, a runtime exception is thrown!

Specified by:

getHiddenEdges in interface InitialPlanarSubgraph

Returns:

an EdgeList keeping the hidden edges

Throws:

java.lang.RuntimeException - if createPlanarization has not been called prior to calling this method.

See Also:

createPlanarization(PlanarInformation)

getSource

public Node getSource()

Returns the source of the st-graph.

getSink

public Node getSink()

Returns the sink of the st-graph.

createPlanarization

public void createPlanarization(PlanarInformation p)

This method planarizes a graph by finding (a maximum) planar sub- graph. To gain a planar graph, sometimes some edges have to be removed in order to prevent crossings. The removed edges are returned by the method getHiddenEdges() below. A circular edge order is also computed. Note: the input graph is modified

Specified by:

createPlanarization in interface InitialPlanarSubgraph

Parameters:

p - the PlanarInformation object associated with the input graph

calcOrdering

protected NodeList calcOrdering(int[] orderNumbers,
                                OverlapGraphMIS mis)

Parameters:

orderNumbers -

mis -

initOrdering

protected void initOrdering(NodeMap downwardLink,
                            NodeMap upwardLink,
                            NodeList orderedNodes)

Initializes data structures from an ordering.

calcMISIncidents

protected void calcMISIncidents(EdgeList MIS,
                                NodeMap MISIncidents)

Calculates form the independent set of edges, the edges incident to an node which are inside this independent set.

createCircularEdgeOrder

protected void createCircularEdgeOrder(EdgeList MIS1,
                                       EdgeList MIS2,
                                       NodeMap downwardLink,
                                       NodeMap upwardLink,
                                       int[] orderNumbers)

this method sorts each nodes incident edges according to the aim of yielding a planar embedding for a subgraph of the input graph It also assigns first incoming/outgoing.

createReverseEdges

protected void createReverseEdges()

dispose

public void dispose()

Cleaning up resources.

showVertexOrder

protected void showVertexOrder(int[] orderNumbers)

showEdgePartitionResult

protected void showEdgePartitionResult(java.util.ArrayList MIS1,
                                       java.util.ArrayList MIS2)

showGraphicDebug

protected void showGraphicDebug(EdgeList MIS1,
                                EdgeList MIS2,
                                int[] orderNumbers)

showIncidentEdges

protected void showIncidentEdges(NodeMap MIS1Incidents,
                                 NodeMap MIS2Incidents,
                                 EdgeMap downwardLink,
                                 EdgeMap upwardLink)