#include <ogdf/planarity/planar_subgraph_fast/PlanarSubgraphPQTree.h>
Public Types  
using  PlanarLeafKey = booth_lueker::PlanarLeafKey< whaInfo * > 
Public Member Functions  
PlanarSubgraphPQTree ()  
virtual  ~PlanarSubgraphPQTree () 
virtual int  Initialize (SListPure< PlanarLeafKey * > &leafKeys) 
Initializes a new PQtree with a set of leaves. More...  
int  Initialize (SListPure< PQLeafKey< edge, whaInfo *, bool > * > &leafKeys) override 
Initializes the PQtree with a set of elements. More...  
virtual bool  Reduction (SListPure< PlanarLeafKey * > &leafKeys, SList< PQLeafKey< edge, whaInfo *, bool > * > &eliminatedKeys) 
Reduces a set of leaves. More...  
bool  Reduction (SListPure< PQLeafKey< edge, whaInfo *, bool > * > &leafKeys) override 
Tests whether permissible permutations of the elements of U exist such that the elements of a subset S of U, stored in leafKeys , form a consecutive sequence. More...  
void  ReplaceRoot (SListPure< PlanarLeafKey * > &leafKeys) 
Replaces the pertinent subtree by a set of new leaves. More...  
Public Member Functions inherited from ogdf::MaxSequencePQTree< edge, bool >  
MaxSequencePQTree ()  
~MaxSequencePQTree ()  
virtual void  CleanNode (PQNode< edge, whaInfo *, bool > *nodePtr) 
Frees the memory allocated for the node information class of a node in the PQTree. More...  
virtual void  clientDefinedEmptyNode (PQNode< edge, whaInfo *, bool > *nodePtr) 
Does a clean up of a node. Called by emptyAllPertinentNodes. More...  
int  determineMinRemoveSequence (SListPure< PQLeafKey< edge, whaInfo *, bool > * > &leafKeys, SList< PQLeafKey< edge, whaInfo *, bool > * > &eliminatedKeys) 
Computes the maximal pertinent sequence S' of elements of the set S, that can be reduced in a PQtree. More...  
virtual void  emptyAllPertinentNodes () 
Does a clean up after a reduction. More...  
Public Member Functions inherited from ogdf::PQTree< edge, whaInfo *, bool >  
PQTree ()  
virtual  ~PQTree () 
Destructor. More...  
bool  addNewLeavesToTree (PQInternalNode< edge, whaInfo *, bool > *father, SListPure< PQLeafKey< edge, whaInfo *, bool > * > &leafKeys) 
Adds a set of elements to the already existing set of elements of a PQtree. More...  
virtual void  Cleanup () 
Removes the entire PQtree. More...  
void  emptyNode (PQNode< edge, whaInfo *, bool > *nodePtr) 
Cleans up all stacks, flags and pointers of a pertinent node that has been visited during the reduction process. More...  
virtual void  front (PQNode< edge, whaInfo *, bool > *nodePtr, SListPure< PQLeafKey< edge, whaInfo *, bool > * > &leafKeys) 
Returns the keys stored in the leaves of the front of nodePtr . More...  
PQNode< edge, whaInfo *, bool > *  root () const 
Returns a pointer of the root node of the PQTree. More...  
void  writeGML (const char *fileName) 
The function writeGML() prints the PQtree in the GML fileformat. More...  
void  writeGML (std::ostream &os) 
Private Member Functions  
void  removeEliminatedLeaves (SList< PQLeafKey< edge, whaInfo *, bool > * > &eliminatedKeys) 
Removes the leaves that have been marked for elimination from the PQtree. More...  
void  ReplaceFullRoot (SListPure< PlanarLeafKey * > &leafKeys) 
Replaces a pertinet subtree by a set of new leaves if the root is full. More...  
void  ReplacePartialRoot (SListPure< PlanarLeafKey * > &leafKeys) 
Replaces a pertinet subtree by a set of new leaves if the root is partial. More...  
Additional Inherited Members  
Protected Member Functions inherited from ogdf::MaxSequencePQTree< edge, bool >  
virtual bool  Bubble (SListPure< PQLeafKey< edge, whaInfo *, bool > * > &leafKeys) 
The function Bubble() is an overloaded function of the base template class PQTree. More...  
PQNode< edge, whaInfo *, bool > *  GetParent (PQNode< edge, whaInfo *, bool > *nodePtr) 
Computes for the node nodePtr its valid parent in the PQtree. More...  
Protected Member Functions inherited from ogdf::PQTree< edge, whaInfo *, bool >  
virtual bool  addNodeToNewParent (PQNode< edge, whaInfo *, bool > *parent, PQNode< edge, whaInfo *, bool > *child) 
Adds a node child as a child to another node specified in parent . More...  
virtual bool  addNodeToNewParent (PQNode< edge, whaInfo *, bool > *parent, PQNode< edge, whaInfo *, bool > *child, PQNode< edge, whaInfo *, bool > *leftBrother, PQNode< edge, whaInfo *, bool > *rightBrother) 
Adds a node child to the children of another node specified in parent . More...  
virtual bool  checkIfOnlyChild (PQNode< edge, whaInfo *, bool > *child, PQNode< edge, whaInfo *, bool > *parent) 
Checks if child is the only child of parent . More...  
virtual PQNode< edge, whaInfo *, bool > *  clientLeftEndmost (PQNode< edge, whaInfo *, bool > *nodePtr) const 
virtual PQNode< edge, whaInfo *, bool > *  clientNextSib (PQNode< edge, whaInfo *, bool > *nodePtr, PQNode< edge, whaInfo *, bool > *other) const 
virtual int  clientPrintNodeCategorie (PQNode< edge, whaInfo *, bool > *nodePtr) 
If the user wishes to use different flags in a derived class of PQTree that are not available in this implementation, he can overload this function. More...  
virtual const char *  clientPrintStatus (PQNode< edge, whaInfo *, bool > *nodePtr) 
If the user wishes to use different status in a derived class of PQTree that are not available in this implementation, he can overload this function. More...  
virtual const char *  clientPrintType (PQNode< edge, whaInfo *, bool > *nodePtr) 
If the user wishes to use different types in a derived class of PQTree that are not available in this implementation, he can overload this function. More...  
virtual PQNode< edge, whaInfo *, bool > *  clientRightEndmost (PQNode< edge, whaInfo *, bool > *nodePtr) const 
virtual PQNode< edge, whaInfo *, bool > *  clientSibLeft (PQNode< edge, whaInfo *, bool > *nodePtr) const 
virtual PQNode< edge, whaInfo *, bool > *  clientSibRight (PQNode< edge, whaInfo *, bool > *nodePtr) const 
virtual void  destroyNode (PQNode< edge, whaInfo *, bool > *nodePtr) 
Marks a node as PQNodeRoot::PQNodeStatus::ToBeDeleted. More...  
virtual void  exchangeNodes (PQNode< edge, whaInfo *, bool > *oldNode, PQNode< edge, whaInfo *, bool > *newNode) 
Replaces the oldNode by the newNode in the tree. More...  
List< PQNode< edge, whaInfo *, bool > * > *  fullChildren (PQNode< edge, whaInfo *, bool > *nodePtr) 
virtual void  linkChildrenOfQnode (PQNode< edge, whaInfo *, bool > *installed, PQNode< edge, whaInfo *, bool > *newChild) 
Links the two endmost children of two different Qnodes via their sibling pointers together. More...  
List< PQNode< edge, whaInfo *, bool > * > *  partialChildren (PQNode< edge, whaInfo *, bool > *nodePtr) 
virtual bool  Reduce (SListPure< PQLeafKey< edge, whaInfo *, bool > * > &leafKeys) 
Performs the reduction of the pertinent leaves with the help of the template matchings, designed by Booth and Lueker. More...  
virtual void  removeChildFromSiblings (PQNode< edge, whaInfo *, bool > *nodePtr) 
Removes the node nodePtr from the doubly linked list of its parent. More...  
virtual int  removeNodeFromTree (PQNode< edge, whaInfo *, bool > *parent, PQNode< edge, whaInfo *, bool > *child) 
The objective is to remove a node child from the PQtree. More...  
virtual bool  templateL1 (PQNode< edge, whaInfo *, bool > *nodePtr, bool isRoot) 
Template matching for leaves. More...  
virtual bool  templateP1 (PQNode< edge, whaInfo *, bool > *nodePtr, bool isRoot) 
Template matching for Pnodes with only full children. More...  
virtual bool  templateP2 (PQNode< edge, whaInfo *, bool > **nodePtr) 
Template matching for a Pnode with full and empty children that is the root of the pertinent subtree. More...  
virtual bool  templateP3 (PQNode< edge, whaInfo *, bool > *nodePtr) 
Template matching for a Pnode with full and empty children that is not the root of the pertinent subtree. More...  
virtual bool  templateP4 (PQNode< edge, whaInfo *, bool > **nodePtr) 
Template matching for a Pnode with full, empty and exactly one partial children. More...  
virtual bool  templateP5 (PQNode< edge, whaInfo *, bool > *nodePtr) 
Template matching for a Pnode with full, empty children and exactly one partial child. More...  
virtual bool  templateP6 (PQNode< edge, whaInfo *, bool > **nodePtr) 
Template matching for a Pnode with full, empty and exactly two partial children. More...  
virtual bool  templateQ1 (PQNode< edge, whaInfo *, bool > *nodePtr, bool isRoot) 
Template matching for Qnodes with only full children. More...  
virtual bool  templateQ2 (PQNode< edge, whaInfo *, bool > *nodePtr, bool isRoot) 
Template matching for Qnodes with a pertinent sequence of children on one side of the Qnode. More...  
virtual bool  templateQ3 (PQNode< edge, whaInfo *, bool > *nodePtr) 
Protected Attributes inherited from ogdf::MaxSequencePQTree< edge, bool >  
SListPure< PQNode< edge, whaInfo *, bool > * >  cleanUp 
Used to store all pertinent Nodes of the pertinent subtree before removing the minimal pertinent subsequence. More...  
SListPure< PQNode< edge, whaInfo *, bool > * >  eliminatedNodes 
Used to store all eliminated nodes (status == PQNodeRoot::PQNodeStatus::Eliminated) of the PQTree. More...  
Protected Attributes inherited from ogdf::PQTree< edge, whaInfo *, bool >  
int  m_identificationNumber 
Stores the total number of nodes that have been allocated. More...  
int  m_numberOfLeaves 
Stores the number of leaves. More...  
List< PQNode< edge, whaInfo *, bool > * > *  m_pertinentNodes 
Stores all nodes that have been marked PQNodeRoot::PQNodeStatus::Full or PQNodeRoot::PQNodeStatus::Partial during a reduction. More...  
PQNode< edge, whaInfo *, bool > *  m_pertinentRoot 
a pointer to the root of the pertinent subtree. More...  
PQNode< edge, whaInfo *, bool > *  m_pseudoRoot 
a pointer to the virtual root of the pertinent subtree, in case that the pertinent root cannot be detected. More...  
PQNode< edge, whaInfo *, bool > *  m_root 
a pointer to the root of the $PQ$tree. More...  
Definition at line 52 of file PlanarSubgraphPQTree.h.
Definition at line 54 of file PlanarSubgraphPQTree.h.

inline 
Definition at line 56 of file PlanarSubgraphPQTree.h.

inlinevirtual 
Definition at line 58 of file PlanarSubgraphPQTree.h.

virtual 
Initializes a new PQtree with a set of leaves.

inlineoverridevirtual 
Initializes the PQtree with a set of elements.
These elements have to be template classes of the class template PQLeafKey and are handed to the function in an array leafKeys
. The function constructs the universal PQtree. If the numberOfElements > 1, the universal PQtree consists of one Pnode as root (stored in m_root) and all leaves gathered underneath the Pnode, symbolizing all kinds of permutations. If numberOfElements = 1, the universal PQtree consists of a single PQLeaf, being the root of the tree.
Observe that the first element has to be stored in leafKeys
[0] and the last one in leafKeys
[numberOfElements1].
Reimplemented from ogdf::PQTree< edge, whaInfo *, bool >.
Definition at line 63 of file PlanarSubgraphPQTree.h.

virtual 
Reduces a set of leaves.

inlineoverridevirtual 
Tests whether permissible permutations of the elements of U exist such that the elements of a subset S of U, stored in leafKeys
, form a consecutive sequence.
If there exists such a permutation, the PQtree is reduced and Reduction() returns 1.
This function gets a list leafKeys
of pointers to elements of type PQLeafKey, representing all elements of S.
Reimplemented from ogdf::PQTree< edge, whaInfo *, bool >.
Definition at line 74 of file PlanarSubgraphPQTree.h.

private 
Removes the leaves that have been marked for elimination from the PQtree.
This function handles the difficult task of cleaning up after every reduction.
After a reduction is complete, different kind of garbage has to be handled.

private 
Replaces a pertinet subtree by a set of new leaves if the root is full.

private 
Replaces a pertinet subtree by a set of new leaves if the root is partial.
void ogdf::PlanarSubgraphPQTree::ReplaceRoot  (  SListPure< PlanarLeafKey * > &  leafKeys  ) 
Replaces the pertinent subtree by a set of new leaves.