Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::MaxSequencePQTree< T, Y > Class Template Reference

The class template MaxSequencePQTree is designed to compute a maximal consecutive sequence of pertinent leaves in a PQ-tree. More...

#include <ogdf/planarity/planar_subgraph_fast/MaxSequencePQTree.h>

+ Inheritance diagram for ogdf::MaxSequencePQTree< T, Y >:

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. More...
 
virtual void clientDefinedEmptyNode (PQNode< T, whaInfo *, Y > *nodePtr)
 Does a clean up of a node. Called by emptyAllPertinentNodes. More...
 
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 PQ-tree. More...
 
virtual void emptyAllPertinentNodes ()
 Does a clean up after a reduction. More...
 
- Public Member Functions inherited from ogdf::PQTree< T, whaInfo *, Y >
 PQTree ()
 
virtual ~PQTree ()
 Destructor. More...
 
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 PQ-tree. More...
 
virtual void Cleanup ()
 Removes the entire PQ-tree. More...
 
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. More...
 
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. More...
 
virtual int Initialize (SListPure< PQLeafKey< T, whaInfo *, Y > * > &leafKeys)
 Initializes the PQ-tree with a set of elements. More...
 
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. More...
 
PQNode< T, whaInfo *, Y > * root () const
 Returns a pointer of the root node of the PQTree. More...
 
void writeGML (const char *fileName)
 The function writeGML() prints the PQ-tree in the GML fileformat. More...
 
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. More...
 
PQNode< T, whaInfo *, Y > * GetParent (PQNode< T, whaInfo *, Y > *nodePtr)
 Computes for the node nodePtr its valid parent in the PQ-tree. More...
 
- 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. More...
 
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. More...
 
virtual bool checkIfOnlyChild (PQNode< T, whaInfo *, Y > *child, PQNode< T, whaInfo *, Y > *parent)
 Checks if child is the only child of parent. More...
 
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. More...
 
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. More...
 
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. More...
 
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. More...
 
virtual void exchangeNodes (PQNode< T, whaInfo *, Y > *oldNode, PQNode< T, whaInfo *, Y > *newNode)
 Replaces the oldNode by the newNode in the tree. More...
 
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 Q-nodes via their sibling pointers together. More...
 
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. More...
 
virtual void removeChildFromSiblings (PQNode< T, whaInfo *, Y > *nodePtr)
 Removes the node nodePtr from the doubly linked list of its parent. More...
 
virtual int removeNodeFromTree (PQNode< T, whaInfo *, Y > *parent, PQNode< T, whaInfo *, Y > *child)
 The objective is to remove a node child from the PQ-tree. More...
 
virtual bool templateL1 (PQNode< T, whaInfo *, Y > *nodePtr, bool isRoot)
 Template matching for leaves. More...
 
virtual bool templateP1 (PQNode< T, whaInfo *, Y > *nodePtr, bool isRoot)
 Template matching for P-nodes with only full children. More...
 
virtual bool templateP2 (PQNode< T, whaInfo *, Y > **nodePtr)
 Template matching for a P-node with full and empty children that is the root of the pertinent subtree. More...
 
virtual bool templateP3 (PQNode< T, whaInfo *, Y > *nodePtr)
 Template matching for a P-node with full and empty children that is not the root of the pertinent subtree. More...
 
virtual bool templateP4 (PQNode< T, whaInfo *, Y > **nodePtr)
 Template matching for a P-node with full, empty and exactly one partial children. More...
 
virtual bool templateP5 (PQNode< T, whaInfo *, Y > *nodePtr)
 Template matching for a P-node with full, empty children and exactly one partial child. More...
 
virtual bool templateP6 (PQNode< T, whaInfo *, Y > **nodePtr)
 Template matching for a P-node with full, empty and exactly two partial children. More...
 
virtual bool templateQ1 (PQNode< T, whaInfo *, Y > *nodePtr, bool isRoot)
 Template matching for Q-nodes with only full children. More...
 
virtual bool templateQ2 (PQNode< T, whaInfo *, Y > *nodePtr, bool isRoot)
 Template matching for Q-nodes with a pertinent sequence of children on one side of the Q-node. More...
 
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. More...
 
SListPure< PQNode< T, whaInfo *, Y > * > eliminatedNodes
 Used to store all eliminated nodes (status == PQNodeRoot::PQNodeStatus::Eliminated) of the PQTree. More...
 
- Protected Attributes inherited from ogdf::PQTree< T, whaInfo *, Y >
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, whaInfo *, Y > * > * m_pertinentNodes
 Stores all nodes that have been marked PQNodeRoot::PQNodeStatus::Full or PQNodeRoot::PQNodeStatus::Partial during a reduction. More...
 
PQNode< T, whaInfo *, Y > * m_pertinentRoot
 a pointer to the root of the pertinent subtree. More...
 
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. More...
 
PQNode< T, whaInfo *, Y > * m_root
 a pointer to the root of the $PQ$-tree. More...
 

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 Q-node. More...
 
void aNumQnode (PQNode< T, whaInfo *, Y > *nodePtr, int sumAllW)
 Computes the a-number of the partial Q-node nodePtr. More...
 
void findMinWHASequence (ArrayBuffer< PQNode< T, whaInfo *, Y > * > &archiv, SList< PQLeafKey< T, whaInfo *, Y > * > &eliminatedKeys)
 Checks the [w,h,a]-number of the pertinent root. More...
 
void haNumPnode (PQNode< T, whaInfo *, Y > *nodePtr)
 Computes the h- and a-number of a P-node nodePtr. More...
 
void haNumQnode (PQNode< T, whaInfo *, Y > *nodePtr)
 Computes the h- and a-number of the partial Q-node nodePtr. More...
 
void hNumQnode (PQNode< T, whaInfo *, Y > *nodePtr, int sumAllW)
 Computes the h-number of the partial Q-node nodePtr. More...
 
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 w-node. More...
 
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 Q-node. More...
 
int setHchild (PQNode< T, whaInfo *, Y > *hChild1)
 Processes the children of a Q-node, marking a full sequence of children with at most incident partial child on one side of the Q-node, as b-nodes respectively as h-node. More...
 
int sumPertChild (PQNode< T, whaInfo *, Y > *nodePtr)
 Returns w = sum_{i in P(nodePtr)}w_i, where nodePtr is any pertinent node of the PQ-tree. More...
 

Detailed Description

template<class T, class Y>
class ogdf::MaxSequencePQTree< T, Y >

The class template MaxSequencePQTree is designed to compute a maximal consecutive sequence of pertinent leaves in a PQ-tree.

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 PQ-Tree and therefore give only a very brief overview of the functionality of this data structure.

The PQ-Tree is a tool to represent the permutations of a set U in which various subsets of U occur consecutively. More precisely, the PQ-tree 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 PQ-tree 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 PQ-tree 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 PQ-tree such that the elements of S' are reducible in the PQ-tree. 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 PQ-tree. 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.

Template Parameters
Tthe user-defined type of an element in the above mentioned set U.
Ythe user-defined type of the information only available for internal nodes PQInternalKey

Definition at line 96 of file MaxSequencePQTree.h.

Constructor & Destructor Documentation

◆ MaxSequencePQTree()

template<class T , class Y >
ogdf::MaxSequencePQTree< T, Y >::MaxSequencePQTree ( )
inline

Definition at line 101 of file MaxSequencePQTree.h.

◆ ~MaxSequencePQTree()

template<class T , class Y >
ogdf::MaxSequencePQTree< T, Y >::~MaxSequencePQTree ( )
inline

Definition at line 103 of file MaxSequencePQTree.h.

Member Function Documentation

◆ alpha1beta1Number()

template<class T , class Y >
int ogdf::MaxSequencePQTree< T, Y >::alpha1beta1Number ( PQNode< T, whaInfo *, Y > *  nodePtr,
PQNode< T, whaInfo *, Y > **  aChild 
)
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 Q-node.

Depicts the a-number if just one child of nodePtr is made a-node. This child is returned by the function alpha1beta1Number() using the pointer aChild.

Definition at line 1588 of file MaxSequencePQTree.h.

◆ aNumQnode()

template<class T , class Y >
void ogdf::MaxSequencePQTree< T, Y >::aNumQnode ( PQNode< T, whaInfo *, Y > *  nodePtr,
int  sumAllW 
)
private

Computes the a-number of the partial Q-node 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 Q-node 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 1348 of file MaxSequencePQTree.h.

◆ Bubble()

template<class T , class Y >
bool ogdf::MaxSequencePQTree< T, Y >::Bubble ( SListPure< PQLeafKey< T, whaInfo *, Y > * > &  leafKeys)
protectedvirtual

The function Bubble() is an overloaded function of the base template class PQTree.

This overloaded version of Bubble() covers several tasks.

  1. It bubbles the tree up from the pertinent leaves, stored in an SListPure of type PQLeafKey, to find all pertinent nodes. Every pertinent node is stored in the stack cleanUp for a valid cleanup after the reduction step.
  2. It makes sure that every pertinent node has a valid parent pointer. (Different to the original Bubble() that only tests if every node has a valid parent pointer)
Parameters
leafKeysa SListPure to the PQLeafKey's of the pertinent leaves.

Reimplemented from ogdf::PQTree< T, whaInfo *, Y >.

Definition at line 395 of file MaxSequencePQTree.h.

◆ CleanNode()

template<class T , class Y >
void ogdf::MaxSequencePQTree< T, Y >::CleanNode ( PQNode< T, whaInfo *, Y > *  nodePtr)
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 483 of file MaxSequencePQTree.h.

◆ clientDefinedEmptyNode()

template<class T , class Y >
void ogdf::MaxSequencePQTree< T, Y >::clientDefinedEmptyNode ( PQNode< T, whaInfo *, Y > *  nodePtr)
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 493 of file MaxSequencePQTree.h.

◆ determineMinRemoveSequence()

template<class T , class Y >
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 PQ-tree.

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 PQ-tree 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 PQ-tree. If the minimum of the h- and a-number of the root of the pertinent subtree is not 0, then the PQ-tree 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 PQ-tree to gain reducibility.

The user should observe that removing the leaves from the PQ-tree, 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 553 of file MaxSequencePQTree.h.

◆ emptyAllPertinentNodes()

template<class T , class Y >
void ogdf::MaxSequencePQTree< T, Y >::emptyAllPertinentNodes
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 PQ-tree.

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 PQ-tree, 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 510 of file MaxSequencePQTree.h.

◆ findMinWHASequence()

template<class T , class Y >
void ogdf::MaxSequencePQTree< T, Y >::findMinWHASequence ( ArrayBuffer< PQNode< T, whaInfo *, Y > * > &  archiv,
SList< PQLeafKey< T, whaInfo *, Y > * > &  eliminatedKeys 
)
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 PQ-tree 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 692 of file MaxSequencePQTree.h.

◆ GetParent()

template<class T , class Y >
PQNode< T, whaInfo *, Y > * ogdf::MaxSequencePQTree< T, Y >::GetParent ( PQNode< T, whaInfo *, Y > *  nodePtr)
protected

Computes for the node nodePtr its valid parent in the PQ-tree.

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 non-valid parent pointer can only appear somewhere between the children of a Q-node, 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 Q-nodes 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 1662 of file MaxSequencePQTree.h.

◆ haNumPnode()

template<class T , class Y >
void ogdf::MaxSequencePQTree< T, Y >::haNumPnode ( PQNode< T, whaInfo *, Y > *  nodePtr)
private

Computes the h- and a-number of a P-node nodePtr.

Definition at line 1104 of file MaxSequencePQTree.h.

◆ haNumQnode()

template<class T , class Y >
void ogdf::MaxSequencePQTree< T, Y >::haNumQnode ( PQNode< T, whaInfo *, Y > *  nodePtr)
private

Computes the h- and a-number of the partial Q-node nodePtr.

Furthermore sets the children aChild, hChild1 and hChild2 of the node information class whaInfo* of nodePtr.

Definition at line 1200 of file MaxSequencePQTree.h.

◆ hNumQnode()

template<class T , class Y >
void ogdf::MaxSequencePQTree< T, Y >::hNumQnode ( PQNode< T, whaInfo *, Y > *  nodePtr,
int  sumAllW 
)
private

Computes the h-number of the partial Q-node nodePtr.

Furthermore sets the child hChild1 of the node information class whaInfo* of nodePtr.

Definition at line 1213 of file MaxSequencePQTree.h.

◆ markPertinentChildren()

template<class T , class Y >
void ogdf::MaxSequencePQTree< T, Y >::markPertinentChildren ( PQNode< T, whaInfo *, Y > *  nodePtr,
PQNodeRoot::PQNodeStatus  label,
whaType  deleteType 
)
private

Marks all full and/or partial children of nodePtr as either an a-, b-, h- or w-node.

Parameters
nodePtra pointer to the node
labelDescribes which children have to be marked. Can be either PQNodeRoot::PQNodeStatus::Full, PQNodeRoot::PQNodeStatus::Partial or PQNodeRoot::PQNodeStatus::Pertinent.
deleteTypeCan 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 1067 of file MaxSequencePQTree.h.

◆ setAchildren()

template<class T , class Y >
int ogdf::MaxSequencePQTree< T, Y >::setAchildren ( PQNode< T, whaInfo *, Y > *  hChild2,
PQNode< T, whaInfo *, Y > *  hChild2Sib 
)
private

Traces all children of the largest consecutive sequence of pertinent children of a Q-node.

Notice, that it does not mark a single node as a-node, but a sequence of full children with possible a partial child at each end as b-nodes, respectively as h-nodes.

Parameters
hChild2the first node of the sequence
hChild2Sibits pertinent sibling It allows immediate scanning of the sequence.
Returns
the number of pertinent children of the Q-node according to the [w,h,a]-numbering.

Definition at line 988 of file MaxSequencePQTree.h.

◆ setHchild()

template<class T , class Y >
int ogdf::MaxSequencePQTree< T, Y >::setHchild ( PQNode< T, whaInfo *, Y > *  hChild1)
private

Processes the children of a Q-node, marking a full sequence of children with at most incident partial child on one side of the Q-node, as b-nodes respectively as h-node.

The pointer hChild1 depicts the endmost child of the Q-node, where the sequence starts.

Parameters
hChild1of the Q-node
Returns
number of pertinent children, corresponding to the [w,h,a]-numbering.

Definition at line 930 of file MaxSequencePQTree.h.

◆ sumPertChild()

template<class T , class Y >
int ogdf::MaxSequencePQTree< T, Y >::sumPertChild ( PQNode< T, whaInfo *, Y > *  nodePtr)
private

Returns w = sum_{i in P(nodePtr)}w_i, where nodePtr is any pertinent node of the PQ-tree.

Definition at line 1640 of file MaxSequencePQTree.h.

Member Data Documentation

◆ cleanUp

template<class T , class Y >
SListPure<PQNode<T,whaInfo*,Y>*> ogdf::MaxSequencePQTree< T, Y >::cleanUp
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 254 of file MaxSequencePQTree.h.

◆ eliminatedNodes

template<class T , class Y >
SListPure<PQNode<T,whaInfo*,Y>*> ogdf::MaxSequencePQTree< T, Y >::eliminatedNodes
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 PQ-tree. 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 263 of file MaxSequencePQTree.h.


The documentation for this class was generated from the following file: