y.layout.planar
Class GT

java.lang.Object
  |
  +--y.layout.planar.GT

All Implemented Interfaces:

InitialPlanarSubgraph

public class GT

extends Object

implements InitialPlanarSubgraph

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

Field Summary

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

Constructor Summary

GT()
Returns a new instance of GT.

Method Summary

protected void	calcMISIncidents(EdgeList MIS, NodeMap MISIncidents) Calcultes form the indendent 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() This Method return 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 datastructures 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(ArrayList MIS1, 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 y.layout.planar.GT.EdgeListComparator edgeListComparator

mis1Comparator

protected y.layout.planar.GT.MIS1Comparator mis1Comparator

mis2Comparator

protected y.layout.planar.GT.MIS2Comparator mis2Comparator

planar

protected PlanarInformation planar

graph

protected Graph graph

isValid

protected boolean isValid

vertexOrder

protected VertexOrder vertexOrder

weight

protected EdgeMap weight

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()

This Method return a list of the edges that have been removed in order to gain a planarization of the input graph. The GT.createPlanarization(PlanarInformation) 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

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 datastructures from an ordering.

calcMISIncidents

protected void calcMISIncidents(EdgeList MIS,
                                NodeMap MISIncidents)

Calcultes form the indendent 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(ArrayList MIS1,
                                       ArrayList MIS2)

showGraphicDebug

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

showIncidentEdges

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