The class template MaxSequencePQTree is designed to compute a maximal consecutive sequence of pertinent leaves in a PQtree. More...
#include <ogdf/planarity/planar_subgraph_fast/MaxSequencePQTree.h>
Public Member Functions  
MaxSequencePQTree ()  
~MaxSequencePQTree ()  
virtual void  CleanNode (PQNode< T, whaInfo *, Y > *nodePtr) 
Frees the memory allocated for the node information class of a node in the PQTree.  
virtual void  clientDefinedEmptyNode (PQNode< T, whaInfo *, Y > *nodePtr) 
Does a clean up of a node. Called by emptyAllPertinentNodes.  
int  determineMinRemoveSequence (SListPure< PQLeafKey< T, whaInfo *, Y > * > &leafKeys, SList< PQLeafKey< T, whaInfo *, Y > * > &eliminatedKeys) 
Computes the maximal pertinent sequence S' of elements of the set S, that can be reduced in a PQtree.  
virtual void  emptyAllPertinentNodes () 
Does a clean up after a reduction.  
Public Member Functions inherited from ogdf::PQTree< T, whaInfo *, Y >  
PQTree ()  
virtual  ~PQTree () 
Destructor.  
bool  addNewLeavesToTree (PQInternalNode< T, whaInfo *, Y > *father, SListPure< PQLeafKey< T, whaInfo *, Y > * > &leafKeys) 
Adds a set of elements to the already existing set of elements of a PQtree.  
virtual void  Cleanup () 
Removes the entire PQtree.  
void  emptyNode (PQNode< T, whaInfo *, Y > *nodePtr) 
Cleans up all stacks, flags and pointers of a pertinent node that has been visited during the reduction process.  
virtual void  front (PQNode< T, whaInfo *, Y > *nodePtr, SListPure< PQLeafKey< T, whaInfo *, Y > * > &leafKeys) 
Returns the keys stored in the leaves of the front of nodePtr .  
virtual int  Initialize (SListPure< PQLeafKey< T, whaInfo *, Y > * > &leafKeys) 
Initializes the PQtree with a set of elements.  
virtual bool  Reduction (SListPure< PQLeafKey< T, whaInfo *, 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.  
PQNode< T, whaInfo *, Y > *  root () const 
Returns a pointer of the root node of the PQTree.  
void  writeGML (const char *fileName) 
The function writeGML() prints the PQtree in the GML fileformat.  
void  writeGML (std::ostream &os) 
Protected Member Functions  
virtual bool  Bubble (SListPure< PQLeafKey< T, whaInfo *, Y > * > &leafKeys) 
The function Bubble() is an overloaded function of the base template class PQTree.  
PQNode< T, whaInfo *, Y > *  GetParent (PQNode< T, whaInfo *, Y > *nodePtr) 
Computes for the node nodePtr its valid parent in the PQtree.  
Protected Member Functions inherited from ogdf::PQTree< T, whaInfo *, Y >  
virtual bool  addNodeToNewParent (PQNode< T, whaInfo *, Y > *parent, PQNode< T, whaInfo *, Y > *child) 
Adds a node child as a child to another node specified in parent .  
virtual bool  addNodeToNewParent (PQNode< T, whaInfo *, Y > *parent, PQNode< T, whaInfo *, Y > *child, PQNode< T, whaInfo *, Y > *leftBrother, PQNode< T, whaInfo *, Y > *rightBrother) 
Adds a node child to the children of another node specified in parent .  
virtual bool  Bubble (SListPure< PQLeafKey< T, whaInfo *, Y > * > &leafKeys) 
Realizes a function described in [Booth].  
virtual bool  checkIfOnlyChild (PQNode< T, whaInfo *, Y > *child, PQNode< T, whaInfo *, Y > *parent) 
Checks if child is the only child of parent .  
virtual PQNode< T, whaInfo *, Y > *  clientLeftEndmost (PQNode< T, whaInfo *, Y > *nodePtr) const 
virtual PQNode< T, whaInfo *, Y > *  clientNextSib (PQNode< T, whaInfo *, Y > *nodePtr, PQNode< T, whaInfo *, Y > *other) const 
virtual int  clientPrintNodeCategorie (PQNode< T, whaInfo *, 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.  
virtual const char *  clientPrintStatus (PQNode< T, whaInfo *, 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.  
virtual const char *  clientPrintType (PQNode< T, whaInfo *, 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.  
virtual PQNode< T, whaInfo *, Y > *  clientRightEndmost (PQNode< T, whaInfo *, Y > *nodePtr) const 
virtual PQNode< T, whaInfo *, Y > *  clientSibLeft (PQNode< T, whaInfo *, Y > *nodePtr) const 
virtual PQNode< T, whaInfo *, Y > *  clientSibRight (PQNode< T, whaInfo *, Y > *nodePtr) const 
virtual void  destroyNode (PQNode< T, whaInfo *, Y > *nodePtr) 
Marks a node as PQNodeRoot::PQNodeStatus::ToBeDeleted.  
virtual void  exchangeNodes (PQNode< T, whaInfo *, Y > *oldNode, PQNode< T, whaInfo *, Y > *newNode) 
Replaces the oldNode by the newNode in the tree.  
List< PQNode< T, whaInfo *, Y > * > *  fullChildren (PQNode< T, whaInfo *, Y > *nodePtr) 
virtual void  linkChildrenOfQnode (PQNode< T, whaInfo *, Y > *installed, PQNode< T, whaInfo *, Y > *newChild) 
Links the two endmost children of two different Qnodes via their sibling pointers together.  
List< PQNode< T, whaInfo *, Y > * > *  partialChildren (PQNode< T, whaInfo *, Y > *nodePtr) 
virtual bool  Reduce (SListPure< PQLeafKey< T, whaInfo *, Y > * > &leafKeys) 
Performs the reduction of the pertinent leaves with the help of the template matchings, designed by Booth and Lueker.  
virtual void  removeChildFromSiblings (PQNode< T, whaInfo *, Y > *nodePtr) 
Removes the node nodePtr from the doubly linked list of its parent.  
virtual int  removeNodeFromTree (PQNode< T, whaInfo *, Y > *parent, PQNode< T, whaInfo *, Y > *child) 
The objective is to remove a node child from the PQtree.  
virtual bool  templateL1 (PQNode< T, whaInfo *, Y > *nodePtr, bool isRoot) 
Template matching for leaves.  
virtual bool  templateP1 (PQNode< T, whaInfo *, Y > *nodePtr, bool isRoot) 
Template matching for Pnodes with only full children.  
virtual bool  templateP2 (PQNode< T, whaInfo *, Y > **nodePtr) 
Template matching for a Pnode with full and empty children that is the root of the pertinent subtree.  
virtual bool  templateP3 (PQNode< T, whaInfo *, Y > *nodePtr) 
Template matching for a Pnode with full and empty children that is not the root of the pertinent subtree.  
virtual bool  templateP4 (PQNode< T, whaInfo *, Y > **nodePtr) 
Template matching for a Pnode with full, empty and exactly one partial children.  
virtual bool  templateP5 (PQNode< T, whaInfo *, Y > *nodePtr) 
Template matching for a Pnode with full, empty children and exactly one partial child.  
virtual bool  templateP6 (PQNode< T, whaInfo *, Y > **nodePtr) 
Template matching for a Pnode with full, empty and exactly two partial children.  
virtual bool  templateQ1 (PQNode< T, whaInfo *, Y > *nodePtr, bool isRoot) 
Template matching for Qnodes with only full children.  
virtual bool  templateQ2 (PQNode< T, whaInfo *, Y > *nodePtr, bool isRoot) 
Template matching for Qnodes with a pertinent sequence of children on one side of the Qnode.  
virtual bool  templateQ3 (PQNode< T, whaInfo *, Y > *nodePtr) 
Protected Attributes  
SListPure< PQNode< T, whaInfo *, Y > * >  cleanUp 
Used to store all pertinent Nodes of the pertinent subtree before removing the minimal pertinent subsequence.  
SListPure< PQNode< T, whaInfo *, Y > * >  eliminatedNodes 
Used to store all eliminated nodes (status == PQNodeRoot::PQNodeStatus::Eliminated) of the PQTree.  
Protected Attributes inherited from ogdf::PQTree< T, whaInfo *, Y >  
int  m_identificationNumber 
Stores the total number of nodes that have been allocated.  
int  m_numberOfLeaves 
Stores the number of leaves.  
List< PQNode< T, whaInfo *, Y > * > *  m_pertinentNodes 
Stores all nodes that have been marked PQNodeRoot::PQNodeStatus::Full or PQNodeRoot::PQNodeStatus::Partial during a reduction.  
PQNode< T, whaInfo *, Y > *  m_pertinentRoot 
a pointer to the root of the pertinent subtree.  
PQNode< T, whaInfo *, Y > *  m_pseudoRoot 
a pointer to the virtual root of the pertinent subtree, in case that the pertinent root cannot be detected.  
PQNode< T, whaInfo *, Y > *  m_root 
a pointer to the root of the $PQ$tree.  
Private Member Functions  
int  alpha1beta1Number (PQNode< T, whaInfo *, Y > *nodePtr, PQNode< T, whaInfo *, Y > **aChild) 
Returns alpha_1 = beta_1 = sum_{i in P(nodePtr )} w_i  max_{i in P(nodePtr )}{(w_i = a_i)}, where P(nodePtr ) denotes the set of all pertinent children of the node nodePtr regardless whether nodePtr is a P or a Qnode.  
void  aNumQnode (PQNode< T, whaInfo *, Y > *nodePtr, int sumAllW) 
Computes the anumber of the partial Qnode nodePtr .  
void  findMinWHASequence (ArrayBuffer< PQNode< T, whaInfo *, Y > * > &archiv, SList< PQLeafKey< T, whaInfo *, Y > * > &eliminatedKeys) 
Checks the [w,h,a]number of the pertinent root.  
void  haNumPnode (PQNode< T, whaInfo *, Y > *nodePtr) 
Computes the h and anumber of a Pnode nodePtr .  
void  haNumQnode (PQNode< T, whaInfo *, Y > *nodePtr) 
Computes the h and anumber of the partial Qnode nodePtr .  
void  hNumQnode (PQNode< T, whaInfo *, Y > *nodePtr, int sumAllW) 
Computes the hnumber of the partial Qnode nodePtr .  
void  markPertinentChildren (PQNode< T, whaInfo *, Y > *nodePtr, PQNodeRoot::PQNodeStatus label, whaType deleteType) 
Marks all full and/or partial children of nodePtr as either an a, b, h or wnode.  
int  setAchildren (PQNode< T, whaInfo *, Y > *hChild2, PQNode< T, whaInfo *, Y > *hChild2Sib) 
Traces all children of the largest consecutive sequence of pertinent children of a Qnode.  
int  setHchild (PQNode< T, whaInfo *, Y > *hChild1) 
Processes the children of a Qnode, marking a full sequence of children with at most incident partial child on one side of the Qnode, as bnodes respectively as hnode.  
int  sumPertChild (PQNode< T, whaInfo *, Y > *nodePtr) 
Returns w = sum_{i in P(nodePtr )}w_i, where nodePtr is any pertinent node of the PQtree.  
The class template MaxSequencePQTree is designed to compute a maximal consecutive sequence of pertinent leaves in a PQtree.
In order to achieve this goal, the class template MaxSequencePQTree is a derived class form the class template PQTree. We assume that the reader is familiar with the data structure of a PQTree and therefore give only a very brief overview of the functionality of this data structure.
The PQTree is a tool to represent the permutations of a set U in which various subsets of U occur consecutively. More precisely, the PQtree together with a package of efficient algorithms, all included in this template class PQTree, finds permissible permutations on the set U. The permissible permutations are those, in which certain subsets S of U occur as consecutive subsets. A PQtree represents an equivalence class of permissible permutations and as the elements of any subset S are constraint to appear together, the number of permissible permutations is reduced. The corresponding PQtree operation is called reduction with respect to S.
In case that a set S of U of pertinent elements is not reducible, it might be a necessary to compute a maximal subset S' of S deleting the elements of S  S' from the PQtree such that the elements of S' are reducible in the PQtree. The class template MaxSequencePQTree provides the user the functionality of computing a subset S'. In fact, MaxSequencePQTree depicts the user the elements of S  S'$ that have to be deleted in order to get a reducible PQtree. However, the class template MaxSequencePQTree does not delete the elements of S  S'. It is up the client using this class to manage the deletion of S  S'.
All computation done by this class to obtain a maximal pertinent sequence is done according to the rules presented in [Jayakumar, Thulasiraman, Swamy, 1989]. For detailed information about the computation, we refer kindly to the authors paper.
The declaration of the template class MaxSequencePQTree.
The formal parameter X of the base class template PQTree was designed to hold the general node information PQNodeKey available at every node of the tree. The class template MaxSequencePQTree defines this parameter to be of type whaInfo. This allows the class template to store informations needed during the computation of a maximal pertinent sequence at every node.
T  the userdefined type of an element in the above mentioned set U. 
Y  the userdefined type of the information only available for internal nodes PQInternalKey 
Definition at line 97 of file MaxSequencePQTree.h.

inline 
Definition at line 101 of file MaxSequencePQTree.h.

inline 
Definition at line 103 of file MaxSequencePQTree.h.

private 
Returns alpha_1 = beta_1 = sum_{i in P(nodePtr
)} w_i  max_{i in P(nodePtr
)}{(w_i = a_i)}, where P(nodePtr
) denotes the set of all pertinent children of the node nodePtr
regardless whether nodePtr
is a P or a Qnode.
Depicts the anumber if just one child of nodePtr
is made anode. This child is returned by the function alpha1beta1Number() using the pointer aChild
.
Definition at line 1500 of file MaxSequencePQTree.h.

private 
Computes the anumber of the partial Qnode nodePtr
.
Furthermore sets the children aChild, hChild1 and hChild2 of the node information class whaInfo* of nodePtr
.
It Checks for consecutive sequences between all children of the Qnode nodePtr
. The children which form a consecutive sequence are stored in a stack called sequence that is emptied, as soon as the end of the sequence is reached. When the stack is emptied, we count for the pertinent leaves in the front of the sequence, and update if necessary the sequence holding the maximum number of pertinent leaves in its frontier.
Observe that if the sequence ends with a partial node, this node may form a consecutive sequence with its other siblings. Hence the partial node is pushed back onto the stack sequence after the stack has been emptied.
Definition at line 1278 of file MaxSequencePQTree.h.

protectedvirtual 
The function Bubble() is an overloaded function of the base template class PQTree.
This overloaded version of Bubble() covers several tasks.
Definition at line 386 of file MaxSequencePQTree.h.

virtual 
Frees the memory allocated for the node information class of a node in the PQTree.
It is an overloaded function of PQTree and called before deallocating the memory of the node nodePtr
(by emptyAllPertinentNodes or the destructor).
Reimplemented from ogdf::PQTree< T, whaInfo *, Y >.
Definition at line 469 of file MaxSequencePQTree.h.

virtual 
Does a clean up of a node. Called by emptyAllPertinentNodes.
The function clientDefinedEmptyNode() is the overloaded virtual function of the template base class PQTree called by default by the function emptyAllPertinentNodes() of PQTree. The overloaded function handles the different labels used during the computation and reduction of the maximal pertinent sequence.
Reimplemented from ogdf::PQTree< T, whaInfo *, Y >.
Definition at line 477 of file MaxSequencePQTree.h.
int ogdf::MaxSequencePQTree< T, Y >::determineMinRemoveSequence  (  SListPure< PQLeafKey< T, whaInfo *, Y > * > &  leafKeys, 
SList< PQLeafKey< T, whaInfo *, Y > * > &  eliminatedKeys  
) 
Computes the maximal pertinent sequence S' of elements of the set S, that can be reduced in a PQtree.
The function expects the set S stored in an SListPure<PQLeafKey*> called leafKeys
. Since the elements of S  S' have to be removed from the PQtree by the client, the function determineMinRemoveSequence() returns the elements of S  S' in an array of type PQLeafKey** called EliminatedElements. The return value of the function is S  S'.
In order to compute the maximal pertinent sequence the function determineMinRemoveSequence() computes the [w,h,a]number of every pertinent node in the pertinent subtree of the PQtree. If the minimum of the h and anumber of the root of the pertinent subtree is not 0, then the PQtree is not reducible. According to the [w,h,a]numbering, this procedure computes a minimal number of pertinent leaves that have to be removed from of the PQtree to gain reducibility.
The user should observe that removing the leaves from the PQtree, depicted by the pointers to their information class stored in EliminatedElements is a necessary but not sufficient action to gain reducibility. The client calling this function has to make sure that nodes, where the complete frontier has been removed during the process must be removed as well. This can easily be done using functions of the base class PQTree such as checkIfOnlyChild().
Definition at line 530 of file MaxSequencePQTree.h.

virtual 
Does a clean up after a reduction.
The function emptyAllPertinentNodes() is the overloaded virtual function of the template base class PQTree. This function handles all necessary cleanup after the computation of the maximal pertinent sequence and the reduction of the maximal pertinent sequence and frees the memory of all nodes that are no longer in the PQtree.
Most nodes that are regarded for deletion are marked with the status PQNodeRoot::PQNodeStatus::ToBeDeleted. This causes a valid removal by the function PQTree<T,whaInfo*,Y>::emptyAllPertinentNodes() if the node is contained in the stack m_pertinentNodes of the base template class. Otherwise, the function emptyAllPertinentNodes() has to remove the nodes directly from the tree.
The function emptyAllPertinentNodes() differs the following nodes by their labels or status.
This function handles another important fact. During the reduction of the maximal pertinent sequence, PQNodeRoot::PQNodeStatus::Partial nodes have been introduced into the PQtree, that do not have a node information. This function detects these nodes equipping them with the container class of type PQNodeKey.
Reimplemented from ogdf::PQTree< T, whaInfo *, Y >.
Definition at line 491 of file MaxSequencePQTree.h.

private 
Checks the [w,h,a]number of the pertinent root.
In case that the min{a,h} = 0, where a, h belong to the pertinent root, the PQtree is reducible and nothing needs to be done. In case that min{a,h} > 0, a min{a,h} number of leaves have to be removed from the tree in order to achieve reducibility for the set S.
Knowing precisely the [w,h,a]number of every pertinent node, this can be achieved in a top down manner, according to the rules presented in Jayakumar et al. The procedure findMinWHASequence() implements this using the stack of nodes called archiv
. This archiv contains all pertinent nodes. Since parents have been stored on top of their children in the stack which supports the top down method of the procedure.
The procedure findMinWHASequence() is called by the procedure determineMinRemoveSequence().
Returns an SList eliminatedKeys
of pointers to PQLeafKey, describing the leaves that have to be removed.
Definition at line 661 of file MaxSequencePQTree.h.

protected 
Computes for the node nodePtr
its valid parent in the PQtree.
The parent pointer is needed during the Bubble() phase.
In case that nodePtr
does not have a valid pointer to its parent, it points to a node that is not contained in the tree anymore. Since we do not free the memory of such nodes, using the parent pointer of nodePtr
does not cause runtime errors. The previous parent of nodePtr
itself is marked as PQNodeRoot::PQNodeStatus::Eliminated, denoting a node that has been removed from the tree. Since such a nodePtr
with a nonvalid parent pointer can only appear somewhere between the children of a Qnode, the function GetParent() sweeps through the siblings of nodePtr
to get a valid parent pointer from the endmost child, thereby updating the parent pointers of all the siblings between the endmost child and nodePtr
. Since the number of children of Qnodes corresponds to the number of cutvertices in the bushform, the total number of children updated by GetParent() is in O(n) for every call of Bubble(). Hence the complexity of the update procedure is bounded by O(n^2).
Definition at line 1569 of file MaxSequencePQTree.h.

private 
Computes the h and anumber of a Pnode nodePtr
.
Definition at line 1053 of file MaxSequencePQTree.h.

private 
Computes the h and anumber of the partial Qnode nodePtr
.
Furthermore sets the children aChild, hChild1 and hChild2 of the node information class whaInfo* of nodePtr
.
Definition at line 1141 of file MaxSequencePQTree.h.

private 
Computes the hnumber of the partial Qnode nodePtr
.
Furthermore sets the child hChild1 of the node information class whaInfo* of nodePtr
.
Definition at line 1153 of file MaxSequencePQTree.h.

private 
Marks all full and/or partial children of nodePtr
as either an a, b, h or wnode.
nodePtr  a pointer to the node 
label  Describes which children have to be marked. Can be either PQNodeRoot::PQNodeStatus::Full, PQNodeRoot::PQNodeStatus::Partial or PQNodeRoot::PQNodeStatus::Pertinent. 
deleteType  Can be either whaType::W, whaType::B, whaType::H or whaType::A 
The function markPertinentChildren() uses just a pointer currentNode for tracing the pertinent children of nodePtr
.
Definition at line 1019 of file MaxSequencePQTree.h.

private 
Traces all children of the largest consecutive sequence of pertinent children of a Qnode.
Notice, that it does not mark a single node as anode, but a sequence of full children with possible a partial child at each end as bnodes, respectively as hnodes.
hChild2  the first node of the sequence 
hChild2Sib  its pertinent sibling It allows immediate scanning of the sequence. 
Definition at line 944 of file MaxSequencePQTree.h.

private 
Processes the children of a Qnode, marking a full sequence of children with at most incident partial child on one side of the Qnode, as bnodes respectively as hnode.
The pointer hChild1
depicts the endmost child of the Qnode, where the sequence starts.
hChild1  of the Qnode 
Definition at line 887 of file MaxSequencePQTree.h.

private 
Returns w = sum_{i in P(nodePtr
)}w_i, where nodePtr
is any pertinent node of the PQtree.
Definition at line 1546 of file MaxSequencePQTree.h.

protected 
Used to store all pertinent Nodes of the pertinent subtree before removing the minimal pertinent subsequence.
Necessary for updates and cleanups after a reduction on the maximal pertinent sequence was successful.
Definition at line 252 of file MaxSequencePQTree.h.

protected 
Used to store all eliminated nodes (status == PQNodeRoot::PQNodeStatus::Eliminated) of the PQTree.
An eliminated node is one that has been removed during the application of the template matching algorithm from the PQtree. These nodes are kept (and their memory is not freed) in order to find out if a node has a valid parent pointer.
Definition at line 261 of file MaxSequencePQTree.h.