#include <ogdf/basic/pqtree/PQNode.h>
Public Member Functions  
PQTree ()  
virtual  ~PQTree () 
Destructor. More...  
bool  addNewLeavesToTree (PQInternalNode< T, X, Y > *father, SListPure< PQLeafKey< T, X, Y > * > &leafKeys) 
Adds a set of elements to the already existing set of elements of a PQtree. More...  
virtual void  CleanNode (PQNode< T, X, Y > *) 
virtual void  Cleanup () 
Removes the entire PQtree. More...  
virtual void  clientDefinedEmptyNode (PQNode< T, X, Y > *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 to make a valid cleanup of the nodes. More...  
virtual void  emptyAllPertinentNodes () 
Cleans up all flags that have been set in the pertinent nodes during the reduction process. More...  
void  emptyNode (PQNode< T, X, Y > *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< T, X, Y > *nodePtr, SListPure< PQLeafKey< T, X, Y > * > &leafKeys) 
Returns the keys stored in the leaves of the front of nodePtr . More...  
virtual int  Initialize (SListPure< PQLeafKey< T, X, Y > * > &leafKeys) 
Initializes the PQtree with a set of elements. More...  
virtual bool  Reduction (SListPure< PQLeafKey< T, X, Y > * > &leafKeys) 
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...  
PQNode< T, X, Y > *  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) 
Protected Member Functions  
virtual bool  addNodeToNewParent (PQNode< T, X, Y > *parent, PQNode< T, X, Y > *child) 
Adds a node child as a child to another node specified in parent . More...  
virtual bool  addNodeToNewParent (PQNode< T, X, Y > *parent, PQNode< T, X, Y > *child, PQNode< T, X, Y > *leftBrother, PQNode< T, X, Y > *rightBrother) 
Adds a node child to the children of another node specified in parent . More...  
virtual bool  Bubble (SListPure< PQLeafKey< T, X, Y > * > &leafKeys) 
Realizes a function described in [Booth]. More...  
virtual bool  checkIfOnlyChild (PQNode< T, X, Y > *child, PQNode< T, X, Y > *parent) 
Checks if child is the only child of parent . More...  
virtual PQNode< T, X, Y > *  clientLeftEndmost (PQNode< T, X, Y > *nodePtr) const 
virtual PQNode< T, X, Y > *  clientNextSib (PQNode< T, X, Y > *nodePtr, PQNode< T, X, Y > *other) const 
virtual int  clientPrintNodeCategorie (PQNode< T, X, Y > *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< T, X, Y > *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< T, X, Y > *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< T, X, Y > *  clientRightEndmost (PQNode< T, X, Y > *nodePtr) const 
virtual PQNode< T, X, Y > *  clientSibLeft (PQNode< T, X, Y > *nodePtr) const 
virtual PQNode< T, X, Y > *  clientSibRight (PQNode< T, X, Y > *nodePtr) const 
virtual void  destroyNode (PQNode< T, X, Y > *nodePtr) 
Marks a node as PQNodeRoot::PQNodeStatus::ToBeDeleted. More...  
virtual void  exchangeNodes (PQNode< T, X, Y > *oldNode, PQNode< T, X, Y > *newNode) 
Replaces the oldNode by the newNode in the tree. More...  
List< PQNode< T, X, Y > * > *  fullChildren (PQNode< T, X, Y > *nodePtr) 
virtual void  linkChildrenOfQnode (PQNode< T, X, Y > *installed, PQNode< T, X, Y > *newChild) 
Links the two endmost children of two different Qnodes via their sibling pointers together. More...  
List< PQNode< T, X, Y > * > *  partialChildren (PQNode< T, X, Y > *nodePtr) 
virtual bool  Reduce (SListPure< PQLeafKey< T, X, Y > * > &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< T, X, Y > *nodePtr) 
Removes the node nodePtr from the doubly linked list of its parent. More...  
virtual int  removeNodeFromTree (PQNode< T, X, Y > *parent, PQNode< T, X, Y > *child) 
The objective is to remove a node child from the PQtree. More...  
virtual bool  templateL1 (PQNode< T, X, Y > *nodePtr, bool isRoot) 
Template matching for leaves. More...  
virtual bool  templateP1 (PQNode< T, X, Y > *nodePtr, bool isRoot) 
Template matching for Pnodes with only full children. More...  
virtual bool  templateP2 (PQNode< T, X, Y > **nodePtr) 
Template matching for a Pnode with full and empty children that is the root of the pertinent subtree. More...  
virtual bool  templateP3 (PQNode< T, X, Y > *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< T, X, Y > **nodePtr) 
Template matching for a Pnode with full, empty and exactly one partial children. More...  
virtual bool  templateP5 (PQNode< T, X, Y > *nodePtr) 
Template matching for a Pnode with full, empty children and exactly one partial child. More...  
virtual bool  templateP6 (PQNode< T, X, Y > **nodePtr) 
Template matching for a Pnode with full, empty and exactly two partial children. More...  
virtual bool  templateQ1 (PQNode< T, X, Y > *nodePtr, bool isRoot) 
Template matching for Qnodes with only full children. More...  
virtual bool  templateQ2 (PQNode< T, X, Y > *nodePtr, bool isRoot) 
Template matching for Qnodes with a pertinent sequence of children on one side of the Qnode. More...  
virtual bool  templateQ3 (PQNode< T, X, Y > *nodePtr) 
Protected Attributes  
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< T, X, Y > * > *  m_pertinentNodes 
Stores all nodes that have been marked PQNodeRoot::PQNodeStatus::Full or PQNodeRoot::PQNodeStatus::Partial during a reduction. More...  
PQNode< T, X, Y > *  m_pertinentRoot 
a pointer to the root of the pertinent subtree. More...  
PQNode< T, X, Y > *  m_pseudoRoot 
a pointer to the virtual root of the pertinent subtree, in case that the pertinent root cannot be detected. More...  
PQNode< T, X, Y > *  m_root 
a pointer to the root of the $PQ$tree. More...  
Private Member Functions  
bool  checkChain (PQNode< T, X, Y > *nodePtr, PQNode< T, X, Y > *firstFull, PQNode< T, X, Y > **seqStart, PQNode< T, X, Y > **seqEnd) 
Checks whether all full children of a Qnode nodePtr form a consecutive sequence. More...  
void  copyFullChildrenToPartial (PQNode< T, X, Y > *nodePtr, PQNode< T, X, Y > *partialChild) 
Copies all full children of nodePtr to a new Pnode The node nodePtr has to be a Pnode. More...  
PQNode< T, X, Y > *  createNodeAndCopyFullChildren (List< PQNode< T, X, Y > * > *fullNodes) 
Copies the full children of a Pnode that are stored in the stack fullNodes to a new Pnode. More...  
void  removeBlock (PQNode< T, X, Y > *nodePtr, bool isRoot) 
Of every partial node that is found in the sequence of children of nodePtr , all children are removed from that partial node and included as children of nodePtr , occupying the place of the partial node in the sequence of children of nodePtr . More...  
void  sortExceptions (int Exceptions[], int arraySize) 
Sorts the exceptions before frontExcept() scans the frontier. More...  
ogdf::PQTree< T, X, Y >::PQTree 

inlinevirtual 
bool ogdf::PQTree< T, X, Y >::addNewLeavesToTree  (  PQInternalNode< T, X, Y > *  father, 
SListPure< PQLeafKey< T, X, Y > * > &  leafKeys  
) 
Adds a set of elements to the already existing set of elements of a PQtree.
These elements have to be of type PQLeafKey and are handed to the function in an array leafKeys. The father of the new elements that has to be an existing P or Qnode, has to be specified and is not allowed to have children.
The above mentioned facts are checked by the function addNodeToNewParent() and the process of adding a child to parent is interrupted with an error message returning 0 as soon none of the facts is fullfilled.
Enter the first element as PQLeaf to the [[parent]].
Enter all other elements as leaves to [[parent]].
Set the reference pointers if [[parent]] is a $P$node.
Set the endmost children if [[parent is a $Q$node.

protectedvirtual 
Adds a node child
as a child to another node specified in parent
.
The parent
of the new node has to be an existing P or Qnode and is not allowed to have children. In the case, that parent
has children, addNewNodeToParent() returns 0 printing an errormessage. In this case, use the overloaded function specifying the future siblings of child
.
child
to parent
, otherwise 0

protectedvirtual 
Adds a node child
to the children of another node specified in parent
.
The parent
of the new node has to be an existing P or Qnode and is allowed to have children. In case that parent
has children, the siblings of the new introduced child must be specified. If no siblings are specified, the function addNodeToNewParent(PQNode<T,X,Y>*,PQNode<T,X,Y>*) is called by default. If the parent
is not specified, the function assumes that child
is added as interior child to a Qnode.
The client of this function should observe the following facts:
parent
is a Pnode, than only one sibling is needed in order to enter the child
. If the client specifies two siblings in leftBrother
and rightBrother
, then an arbitrary one is choosen to be a sibling.parent
is a Qnode, two siblings must be specified if child
has to become an interior child of the Qnode. If just one sibling is specified, this implies that child
is about to become a new endmost child of parent
. So either leftBrother
or rightBrother
must store an existing endmost child of parent
.parent
is a zero pointer, addNodeToNewParents() assumes that child
is added as interior child to a Qnode. In this case both siblings of child
have to be specified. Observe however, that it is also legal to specify the parent in this case.The above mentioned facts are checked and the process of adding a child to parent
is interrupted with an error message returning 0 as soon none of the facts is fulfilled.
child
to parent
, otherwise 0

protectedvirtual 
Realizes a function described in [Booth].
It bubbles up from the pertinent leaves to the pertinent root in order to make sure that every pertinent node in the pertinent subtree has a valid pointer to its parent. If Bubble() does not succed in doing so, then the set of elements, stored in the leafKeys
cannot form a consecutive sequence.
Reimplemented in ogdf::MaxSequencePQTree< T, Y >, and ogdf::MaxSequencePQTree< edge, bool >.

private 
Checks whether all full children of a Qnode nodePtr
form a consecutive sequence.
If the full nodes do so, the procedure returns 1 as a result, otherwise 0.
The pointer firstFull
denotes just an arbirtary full child. Starting from this position, checkChain sweeps through the consecutive sequence, halting as soon as a nonfull child is detected. The two pointers seqStart
and seqEnd
are set within this function. They denote the first and last node of the consecutive sequence.
The client should observe that it is not possible to avoid the use of such a function. According to the procedure Bubble() children of Qnodes get unblocked as soon as they are adjacent to any pertinent sibling. This includes that chains of more than two partial children are regarded as unblocked as well. Such chains are of course not reducible and therefore have to be detected by the function checkChain().
The function is used by the function templateQ2() and templateQ3().

protectedvirtual 
Checks if child
is the only child of parent
.
If so, child
is connected to its grandparent, as long as parent is not the root of the tree. In case that parent
is the root of the tree and child
is its only child, the node child
becomes the new root of the tree. The parent then is completely removed from the tree and destroyed.
Before applying the function exchangeNodes(), the function removeChildFromSiblings() is applied. This is useful in case the node parent
has some ignored children and has to be reused within some extra algorithmic context.
child
was the only child of parent
, otherwise 0

inlinevirtual 
Reimplemented in ogdf::MaxSequencePQTree< T, Y >, and ogdf::MaxSequencePQTree< edge, bool >.

virtual 
Removes the entire PQtree.
It is called by the destructor. It scans all nodes of the tree and frees the memory used by the tree. It removes the memory allocated by the following datastructures:

inlinevirtual 
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 to make a valid cleanup of the nodes.
It will be called per default by the function emptyAllPertinentNodes().
Reimplemented in ogdf::MaxSequencePQTree< T, Y >, and ogdf::MaxSequencePQTree< edge, bool >.

inlineprotectedvirtual 

inlineprotectedvirtual 

protectedvirtual 
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.
With the help of this function it is possible to influence the layout of the nodes by using new, different lables depicting node categories in the Tree Interface.

protectedvirtual 
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.
With the help of this function it is possible to influence the information stored at nodes in the Tree Interface that concern the status of a node.

protectedvirtual 
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.
With the help of this function it is possible to influence the information stored at nodes in the Tree Interface that concern the type of a node.

inlineprotectedvirtual 

inlineprotectedvirtual 

inlineprotectedvirtual 

private 
Copies all full children of nodePtr
to a new Pnode The node nodePtr
has to be a Pnode.
The new Pnode is added to partialChild
as an endmost child of partialChild
. The node partialChild
has to be a Qnode and the new Pnode is added to the side of partialChild
where the pertinent children are.
The new Pnode is allocated by this function and referenced by the variable newNode
.
The function copyFullChildrenToPartial() is used by the functions templateP4(), templateP5(), and templateP6().

private 
Copies the full children of a Pnode that are stored in the stack fullNodes
to a new Pnode.
This new Pnode is created by the function and stored in newNode if there is more than one full child. If there is just one full child, it is not necessary to construct a new Pnode and the full child is stored in newNode. The newNode is the return value of the procedure.
This function is used by templateP2(), templateP3() and copyFullChildrenToPartial().

inlineprotectedvirtual 
Marks a node as PQNodeRoot::PQNodeStatus::ToBeDeleted.
This enables the function emptyAllPertinentNodes() to remove the node and free its memory.

virtual 
Cleans up all flags that have been set in the pertinent nodes during the reduction process.
All pertinent nodes have been stored in the private member stack m_pertinentNodes during the Bubble() phase or when processing one of the templates (see templateL1() to templateQ3()).
This function has to be called after a reduction has been processed.
Reimplemented in ogdf::booth_lueker::PlanarPQTree, ogdf::booth_lueker::EmbedPQTree, ogdf::MaxSequencePQTree< T, Y >, and ogdf::MaxSequencePQTree< edge, bool >.
void ogdf::PQTree< T, X, Y >::emptyNode  (  PQNode< T, X, Y > *  nodePtr  ) 

protectedvirtual 
Replaces the oldNode
by the newNode
in the tree.
This is a function used very often in the template matchings, normally in combination with the construction of a new node which has to conquer the place of an existing node in the tree.
This function can be used in all cases, so the parent of oldNode
is allowed to be either a Qnode or a Pnode and oldNode
may be any child of its parent.
The client should observe, that this function does not reset the pointer m_root. If necessary, this has to be done explicitly by the client himself.

virtual 
Returns the keys stored in the leaves of the front of nodePtr
.
A specified node nodePtr
of the PQtree is handed to the function and front() detects the leaves in the front of this node returning the elements represented by the leaves. These elements are stored in an array of keys named leafKeys
. Observe that front() uses leafKeys
[0] to store the first key.

inlineprotected 

virtual 
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 in ogdf::PlanarSubgraphPQTree.

protectedvirtual 
Links the two endmost children of two different Qnodes via their sibling pointers together.
The purpose of doing this is to combine the children of two Qnodes as children of only one Qnode. This function does not reset the pointers to the endmost children of the Qnode. This has to be done by the client of the function.

inlineprotected 

protectedvirtual 
Performs the reduction of the pertinent leaves with the help of the template matchings, designed by Booth and Lueker.
The reader should observe that this function can only be called after every pertinent node in the pertinent subtree has gotten a valid parent pointer. If this is not the case, the programm will be interrupted by runtime errors such as seqmentation faults. The pertinent nodes can get valid parent pointers by using the function Bubble(). If it returns 1, then it was succesful in giving each pertinent node in the pertinent subtree a valid parent pointer. If it returns 0, then some nodes do not have a valid parent pointer and the pertinent leaves are not reducable.
The function Reduce() starts with the pertinent leaves and stores them in a queue processNodes. Every time a node is processed, its parent is checked whether all its pertinent children are already processed. If this is the case, the parent is allowed to be processed as well and stored in the queue.
Processing a node means that the function Reduce() tries to apply one of the template matchings. In case that one template matching was successful, the node was reduced and Reduce() tries to reduce the next node. In case that no template matching was successfully applied, the tree is is irreducible. This causes the reduction process to be halted returning 0.

virtual 
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 in ogdf::PlanarSubgraphPQTree.

private 
Of every partial node that is found in the sequence of children of nodePtr
, all children are removed from that partial node and included as children of nodePtr
, occupying the place of the partial node in the sequence of children of nodePtr
.
Thereby, removeBlock() takes care, that the newly included full children of nodePtr
form a consecutive sequence with the already existing pertinent children of nodePtr
. The partial node itself is deleted afterwards.
This function is used by the functions templateQ2() and templateQ3().
The node nodePtr
is expected to be a Qnode with no, one or at most two partial children, such that the partial and full children of nodePtr
form a legal consecutive sequence, hence can be reduced.
Pointer to the first partial child

protectedvirtual 
Removes the node nodePtr
from the doubly linked list of its parent.
In case that nodePtr
is endmost child of an Qnode or child of a Pnode equiped with a valid reference pointer referenceParent to its parent (see PQNode), these pointers are considered as well and the adjacent siblings of nodePtr
have to cover nodePtr's
task.

protectedvirtual 
The objective is to remove a node child
from the PQtree.
To do so, the parent
of the node child
has to be known by the user. To indicate this, the parent has to be handed over by her.
This function has to be handled with great care by the user. It is not used in any of the functions of the class template PQTree and can only be accessed by inheritance.
This function does not check if parent
is the parent node of child
. This has to be guaranteed by the user. The reason for this riscfull approach lies in the details of the powerful data structure PQtree. In order to reach linear runtime, the internal children of a Qnode normally do not have valid parent pointers. So forcing this function to search the parent would cost in worst case linear runtime for one call of the function removeNodeFromTree(). Its up to the user to do better.
Calling removeNodeFromTree() with nullptr for parent
, will always terminate this function with an ERRORmessage and returning 1 as value.
The return value is an integer value used to indicate how many children the parent
after the removal of child
still has. The client should observe that internal nodes in the PQtree which have just one or no children at all do not make sense. However, the function removeNodeFromTree() does not check if parent
has less than two children after the removal of < child. So in case that parent
has less than two children, the user has to check this by herself and remove the parent
, probably using the function checkIfOnlyChild().
There are two reasons why the function removeNodeFromTree() does not check if parent
has less than two children after the removal of child:
parent
might not be known to parent
, hence removeNodeTree() would have to search, at the cost of linear time consumption, for the parent of parent
first before removing parent
from the tree.Observe that removeNodeFromTree() does not free the allocated memory of child
. This has to be done by the user after calling removeNodeFromTree(). It also offers the opportunity to reuse deleted nodes. Observe that the identification number of a node m_identificationNumber (see PQNode) cannot be changed.

inline 

private 

protectedvirtual 
Template matching for leaves.
The function requires as input any pointer to a node stored in nodePtr
. If the node stored in nodePtr
is a PQLeaf, templateL1() considers itself responsible for the node and will apply the template matching for pertinent leaves to nodePtr
. If the flag isRoot
is set to 1, it signalizes templateL1() that nodePtr
is the root of the pertinent subtree. In any other case the flag has to be 0.
If templateL1() was responsible for nodePtr
and the reduction was successful, the return value is 1. Otherwise the return value is 0.
The function updates the fullChildren stack of its parent, as long as nodePtr
is not the root of the pertinent subtree. Observe that nodePtr
needs a valid pointer to its parent. This can be achieved by using the function Bubble() or any other appropriate, user defined function.

protectedvirtual 
Template matching for Pnodes with only full children.
The function requires as input any pointer to a node stored in nodePtr
. If the node stored in nodePtr
is a Pnode with only full children, templateP1() considers itself responsible for the node and will apply the template matching for full Pnodes to nodePtr
. If the flag isRoot
is set to 1, it signalizes templateP1() that nodePtr
is the root of the pertinent subtree. In any other case the flag has to be 0.
If templateP1() was responsible for nodePtr
and the reduction was successful, the return value is 1. Otherwise the return value is 0.
If the Pnode is not the root of the pertinent subtree, the fullChildren stack of the parent of nodePtr
is updated. If the Pnode is the root of the pertinent subtree, nothing has to be done.

protectedvirtual 
Template matching for a Pnode with full and empty children that is the root of the pertinent subtree.
The function requires as input any pointer to a node stored in nodePtr
. If the node stored in nodePtr
is a Pnode with no partial children, templateP2() considers itself responsible for the node and will apply the template matching P2 to nodePtr
. Observe that the user calling this function has to make sure that nodePtr
is partial and is the root of the pertinent subtree.
If templateP2() was responsible for nodePtr
and the reduction was successful, the return value is 1. Otherwise the return value is 0.
The function templateP2() creates a new full Pnode that will be the new root of the pertinent subtree. It then copies all full children from nodePtr
to the new root of the pertinent subtree.

protectedvirtual 
Template matching for a Pnode with full and empty children that is not the root of the pertinent subtree.
The function requires as input any pointer to a node stored in nodePtr
. If the node stored in nodePtr
is a Pnode with no partial children, templateP3() considers itself responsible for the node and will apply the template matching P3 to nodePtr
. Observe that the user calling this function has to make sure that nodePtr
is partial and is not the root of the pertinent subtree.
If templateP3() was responsible for nodePtr
and the reduction was successful, the return value is 1. Otherwise the return value is 0.
The function templateP3() creates a new full Pnode, stored in newPnode and copies the full children of nodePtr
to newPnode. nodePtr
keeps all empty children and will be labeled empty. A new partial Qnode will be created and stored in newQnode. newQnode is placed at the position of nodePtr
in the tree and gets two children: nodePtr
itself and the newly created newPnode.

protectedvirtual 
Template matching for a Pnode with full, empty and exactly one partial children.
The Pnode has to be the root of the pertinent subtree. The function requires as input any pointer to a node stored in nodePtr
. If the node stored in nodePtr
is a Pnode with one partial child, templateP4() considers itself responsible for the node and will apply the template matching P4 to nodePtr
. Observe that the user calling this function has to make sure that nodePtr
is the root of the pertinent subtree.
If templateP4() was responsible for nodePtr
and the reduction was successful, the return value is 1. Otherwise the return value is 0.
The function templateP4() creates a new full Pnode, if neccessary, and copies the full children of nodePtr
to this Pnode. The new Pnode then is made endmost child of partialChild. The node partialChild is used to store the adress of the partial child of nodePtr
. The partialChild itself stays child of nodePtr
. Most of the here described action is done in the function copyFullChildrenToPartial().

protectedvirtual 
Template matching for a Pnode with full, empty children and exactly one partial child.
The Pnode is not allowed to be the root of the pertinent subtree. The function requires as input any pointer to a node stored in nodePtr
. If the node stored in nodePtr
is a Pnode with one partial child, templateP5() considers itself responsible for the node and will apply the template matching P5 to nodePtr
. Observe that the user calling this function has to make sure that nodePtr
is not the root of the pertinent subtree.
If templateP5() was responsible for nodePtr
and the reduction was successful, the return value is 1. Otherwise the return value is 0.

protectedvirtual 
Template matching for a Pnode with full, empty and exactly two partial children.
The Pnode must be the root of the pertinent subtree. The function requires as input any pointer to a node stored in nodePtr
. If the node stored in nodePtr
is a Pnode with two partial children, templateP6() considers itself responsible for the node and will apply the template matching P6 to nodePtr
. Observe that the user calling this function has to make sure that nodePtr
is the root of the pertinent subtree.
If templateP6() was responsible for nodePtr
and the reduction was successful, the return value is 1. Otherwise the return value is 0.
The function templateP6() creates, if neccessary, a new full Pnode and copies all the full children of nodePtr
to the new full Pnode, whereas all empty children stay children of nodePtr
. The new Pnode will be copied to one of the partial children as endmost child of this partial node. The children of the second partial node are copied to the first one, such that the pertinent nodes form a consecutive sequence.

protectedvirtual 
Template matching for Qnodes with only full children.
The function requires as input any pointer to a node stored in nodePtr
. If the node stored in nodePtr
is a Qnode with only full children, templateQ1() considers itself responsible for the node and will apply the template matching for full Qnodes to nodePtr
. If the flag isRoot
is set to 1, it signalizes templateQ1() that nodePtr
is the root of the pertinent subtree. In any other case the flag has to be 0.
If templateQ1() was responsible for nodePtr
and the reduction was successful, the return value is 1. Otherwise the return value is 0.
Different to the templateP1() for Pnodes, this function is not able to check if Qnode is full by comparing the number of children with the number of full children. The reason is the application of the m_pseudoRoot at certain steps in the matching algorithm. This m_pseudoRoot is used instead of the real root of the pertinent subtree in case that no parent pointer was found. But this implies that changing the number of the children of the pertinent root is not registered by the pertinent root. Hence we are not allowed to use the childCount of Qnodes.

protectedvirtual 
Template matching for Qnodes with a pertinent sequence of children on one side of the Qnode.
The function requires as input any pointer to a node stored in nodePtr
. If the node stored in nodePtr
is a Qnode with a pertinent sequence of children on one side of the Qnode, templateQ2() considers itself responsible for the node and will apply the template matching Q2 to nodePtr
. If the flag isRoot
is set to 1, it signalizes templateQ2() that nodePtr
is the root of the pertinent subtree. In any other case the flag has to be 0.
If templateQ2() was responsible for nodePtr
and the reduction was successful, the return value is 1. Otherwise the return value is 0.
Below a short description is given of all different cases that may occure and that are handled by the function templateQ2(), regardless whether the Qnode nodePtr
is root of the pertinent subtree or not. The description is somewhat trunkated and should be understood as a stenographic description of the labels of the children of nodePtr
when running through the children from one side to the other. Of course we leave the mirrorimages out.

protectedvirtual 
void ogdf::PQTree< T, X, Y >::writeGML  (  const char *  fileName  ) 
The function writeGML() prints the PQtree in the GML fileformat.
void ogdf::PQTree< T, X, Y >::writeGML  (  std::ostream &  os  ) 

protected 

protected 

protected 
Stores all nodes that have been marked PQNodeRoot::PQNodeStatus::Full or PQNodeRoot::PQNodeStatus::Partial during a reduction.
After the reduction has been finished succesfully, all pertinent nodes are reinitialized and prepared for the next reduction. This list also contains pertinent nodes that have been removed during a reduction. When detected in the stack, their memory is freed.

protected 

protected 

protected 