graph.tree.pq

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

java.lang.Object

graph.tree.pq.PQTreeReduction<V,E>

Type Parameters:

V - The vertex type

E - The edge type

public class PQTreeReduction<V extends Vertex,E extends Edge<V>>
extends java.lang.Object

Implementation of the PQ-tree reduction procedure, as described by Booth and Lueker. Used in their planarity testing and embedding algorithm

Author:

Renata

Constructor Summary

Constructors

Constructor and Description
PQTreeReduction()

Method Summary

Modifier and Type	Method and Description
boolean	bubble(PQTree<V,E> pqTree, java.util.List<PQTreeNode> S) Implementation of the bubble procedure
java.util.Map<V,java.lang.Integer>	getReversalNum()
boolean	reduce(PQTree<V,E> pqTree, java.util.List<PQTreeNode> S, PQTreeNode pertRoot) Implementation of the reduction procedure

Methods inherited from class java.lang.Object

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

Constructor Detail

PQTreeReduction

public PQTreeReduction()

Method Detail

bubble

public boolean bubble(PQTree<V,E> pqTree,
                      java.util.List<PQTreeNode> S)

Implementation of the bubble procedure

Parameters:

pqTree - PQ-tree

S - A subset of all nodes

Returns:

Indicator whether the the procedure was successful

reduce

public boolean reduce(PQTree<V,E> pqTree,
                      java.util.List<PQTreeNode> S,
                      PQTreeNode pertRoot)

Implementation of the reduction procedure

Parameters:

pqTree - PQ-tree to be reduced

S - Subset of all nodes

pertRoot - Pertinent root

Returns:

true if the tree can be reduced, false otherwise

getReversalNum

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

Returns:

The number of reversals