graph.algorithms.planarity

Class PQTreePlanarity<V extends Vertex,E extends Edge<V>>

java.lang.Object

graph.algorithms.planarity.PlanarityTestingAlgorithm<V,E>

graph.algorithms.planarity.PQTreePlanarity<V,E>

Type Parameters:

V - The vertex type

E - The edge type

public class PQTreePlanarity<V extends Vertex,E extends Edge<V>>
extends PlanarityTestingAlgorithm<V,E>

Implementation of the PQ tree planarity testing based on Booth and Lueker's algorithm

Author:

Renata

Constructor Summary

Constructors

Constructor and Description
PQTreePlanarity()
PQTreePlanarity(V s, V t)

Method Summary

Modifier and Type	Method and Description
java.util.Map<V,java.lang.Integer>	getStNumbers()
java.util.List<V>	getStOrder()
java.util.Map<V,java.util.List<E>>	getUpwardsEmbedding()
boolean	isPlannar(Graph<V,E> graph) Determines if the graph is planar
void	setStNumbers(java.util.Map<V,java.lang.Integer> stNumbers)

Methods inherited from class java.lang.Object

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

Constructor Detail

PQTreePlanarity

public PQTreePlanarity(V s,
                       V t)

PQTreePlanarity

public PQTreePlanarity()

Method Detail

isPlannar

public boolean isPlannar(Graph<V,E> graph)

Description copied from class: PlanarityTestingAlgorithm

Determines if the graph is planar

Specified by:

isPlannar in class PlanarityTestingAlgorithm<V extends Vertex,E extends Edge<V>>

Parameters:

graph - Graph whose planarity is being checked

Returns:

true if graph is planar, otherwise false

getUpwardsEmbedding

public java.util.Map<V,java.util.List<E>> getUpwardsEmbedding()

Returns:

the upwards embedding

getStOrder

public java.util.List<V> getStOrder()

Returns:

the stOrder

getStNumbers

public java.util.Map<V,java.lang.Integer> getStNumbers()

Returns:

the stNumbers

setStNumbers

public void setStNumbers(java.util.Map<V,java.lang.Integer> stNumbers)

Parameters:

stNumbers - stNumbers to set