Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::PQLeaf< T, X, Y > Class Template Reference

The datastructure PQ-tree was designed to present a set of permutations on an arbitrary set of elements. More...

#include <ogdf/basic/pqtree/PQLeaf.h>

+ Inheritance diagram for ogdf::PQLeaf< T, X, Y >:

Public Member Functions

 PQLeaf (int count, PQNodeRoot::PQNodeStatus stat, PQLeafKey< T, X, Y > *keyPtr)
 
 PQLeaf (int count, PQNodeRoot::PQNodeStatus stat, PQLeafKey< T, X, Y > *keyPtr, PQNodeKey< T, X, Y > *infoPtr)
 The client may choose between two different constructors. More...
 
virtual ~PQLeaf ()
 The destructor does not delete any accompanying information class as PQLeafKey, PQNodeKey and PQInternalKey. More...
 
virtual PQInternalKey< T, X, Y > * getInternal () const
 getInternal() returns 0. More...
 
virtual PQLeafKey< T, X, Y > * getKey () const
 getKey() returns a pointer to the PQLeafKey of PQLeaf. More...
 
virtual PQNodeRoot::PQNodeMark mark () const
 Returns the variable m_mark. More...
 
virtual void mark (PQNodeRoot::PQNodeMark m)
 Sets the variable m_mark. More...
 
virtual bool setInternal (PQInternalKey< T, X, Y > *pointerToInternal)
 setInternal() accepts only pointers pointerToInternal = 0. More...
 
virtual bool setKey (PQLeafKey< T, X, Y > *pointerToKey)
 setKey() sets the pointer variable m_pointerToKey to the specified address of pointerToKey that is of type PQLeafKey. More...
 
virtual PQNodeRoot::PQNodeStatus status () const
 Returns the variable m_status in the derived class PQLeaf. More...
 
virtual void status (PQNodeRoot::PQNodeStatus s)
 Sets the variable m_status in the derived class PQLeaf. More...
 
virtual PQNodeRoot::PQNodeType type () const
 Returns the variable PQInternalNode::m_type in the derived class PQLeaf. More...
 
virtual void type (PQNodeRoot::PQNodeType)
 Sets the variable PQInternalNode::m_type in the derived class PQLeaf. More...
 
- Public Member Functions inherited from ogdf::PQNode< T, X, Y >
 PQNode (int count)
 The (second) constructor is called, if no information is available or neccessary. More...
 
 PQNode (int count, PQNodeKey< T, X, Y > *infoPtr)
 The (first) constructor combines the node with its information and will automatically set the PQBasicKey::m_nodePointer (see basicKey) of the element of type PQNodeKey. More...
 
virtual ~PQNode ()
 The destructor does not delete any accompanying information class as PQLeafKey, PQNodeKey and PQInternalKey. More...
 
bool changeEndmost (PQNode< T, X, Y > *oldEnd, PQNode< T, X, Y > *newEnd)
 The function changeEndmost() replaces the old endmost child oldEnd of the node by a new child newEnd. More...
 
bool changeSiblings (PQNode< T, X, Y > *oldSib, PQNode< T, X, Y > *newSib)
 The function changeSiblings() replaces the old sibling oldSib of the node by a new sibling newSib. More...
 
int childCount () const
 Returns the number of children of a node. More...
 
void childCount (int count)
 Sets the number of children of a node. More...
 
bool endmostChild () const
 The function endmostChild() checks if a node is endmost child of a Q-node. More...
 
PQNode< T, X, Y > * getEndmost (PQNode< T, X, Y > *other) const
 Returns one of the endmost children of node, if node is a Q-node. More...
 
PQNode< T, X, Y > * getEndmost (SibDirection side) const
 Returns one of the endmost children of node, if node is a Q-node. More...
 
PQNode< T, X, Y > * getNextSib (PQNode< T, X, Y > *other) const
 The function getNextSib() returns one of the siblings of the node. More...
 
PQNodeKey< T, X, Y > * getNodeInfo () const
 Returns the identification number of a node. More...
 
PQNode< T, X, Y > * getSib (SibDirection side) const
 The function getSib() returns one of the siblings of the node. More...
 
int identificationNumber () const
 Returns the identification number of a node. More...
 
virtual void mark (PQNodeMark)=0
 mark() sets the variable PQLeaf::m_mark in the derived class PQLeaf and PQInternalNode. More...
 
PQNode< T, X, Y > * parent () const
 The function parent() returns a pointer to the parent of a node. More...
 
PQNode< T, X, Y > * parent (PQNode< T, X, Y > *newParent)
 Sets the parent pointer of a node. More...
 
PQNodeType parentType () const
 Returns the type of the parent of a node. More...
 
void parentType (PQNodeType newParentType)
 Sets the type of the parent of a node. More...
 
int pertChildCount () const
 Returs the number of pertinent children of a node. More...
 
void pertChildCount (int count)
 Sets the number of pertinent children of a node. More...
 
SibDirection putSibling (PQNode< T, X, Y > *newSib)
 The default function putSibling() stores a new sibling at a free sibling pointer of the node. More...
 
SibDirection putSibling (PQNode< T, X, Y > *newSib, SibDirection preference)
 The function putSibling() with preference stores a new sibling at a free sibling pointer of the node. More...
 
PQNode< T, X, Y > * referenceChild () const
 Returns a pointer to the reference child if node is a P-node. More...
 
PQNode< T, X, Y > * referenceParent () const
 Returns the pointer to the parent if node is a reference child. More...
 
bool setNodeInfo (PQNodeKey< T, X, Y > *pointerToInfo)
 Sets the pointer m_pointerToInfo to the specified adress of pointerToInfo. More...
 
virtual void status (PQNodeStatus)=0
 Sets the variable PQLeaf::m_status in the derived class PQLeaf and PQInternalNode. More...
 
virtual void type (PQNodeType)=0
 Sets the variable PQInternalNode::m_type in the derived class PQLeaf and PQInternalNode. More...
 

Private Attributes

PQNodeRoot::PQNodeMark m_mark
 m_mark is a variable, storing if the PQLeaf is QUEUEUD, BLOCKED or UNBLOCKED (see PQNode) during the first phase of the procedure Bubble(). More...
 
PQLeafKey< T, X, Y > * m_pointerToKey
 m_pointerToKey stores the adress of the corresponding PQLeafKey. More...
 
PQNodeRoot::PQNodeStatus m_status
 m_status is a variable storing the status of a PQLeaf. More...
 

Additional Inherited Members

- Protected Attributes inherited from ogdf::PQNode< T, X, Y >
List< PQNode< T, X, Y > * > * fullChildren
 Stores all full children of a node during a reduction. More...
 
int m_childCount
 
int m_debugTreeNumber
 Needed for debuging purposes. More...
 
PQNode< T, X, Y > * m_firstFull
 Stores a pointer to the first full child of a Q-node. More...
 
int m_identificationNumber
 Each node that has been introduced once into the tree gets a unique number. More...
 
PQNode< T, X, Y > * m_leftEndmost
 
PQNode< T, X, Y > * m_parent
 Is a pointer to the parent. More...
 
PQNodeType m_parentType
 Stores the type of the parent which can be either a P- or Q-node. More...
 
int m_pertChildCount
 Stores the number of pertinent children of the node. More...
 
int m_pertLeafCount
 Stores the number of pertinent leaves in the frontier of the node. More...
 
PQNodeKey< T, X, Y > * m_pointerToInfo
 Stores a pointer to the corresponding information of the node. More...
 
PQNode< T, X, Y > * m_referenceChild
 Stores a pointer to one child, the reference child of the doubly linked cirkular list of children of a P-node. More...
 
PQNode< T, X, Y > * m_referenceParent
 Is a pointer to the parent, in case that the parent is a P-node and the node itself is its reference child. More...
 
PQNode< T, X, Y > * m_rightEndmost
 Stores the right endmost child of a Q-node. More...
 
PQNode< T, X, Y > * m_sibLeft
 Stores a pointer ot the left sibling of PQNode. More...
 
PQNode< T, X, Y > * m_sibRight
 Stores a pointer ot the right sibling of PQNode. More...
 
List< PQNode< T, X, Y > * > * partialChildren
 Stores all partial children of a node during a reduction. More...
 

Detailed Description

template<class T, class X, class Y>
class ogdf::PQLeaf< T, X, Y >

The datastructure PQ-tree was designed to present a set of permutations on an arbitrary set of elements.

These elements are the leafs of a PQ-tree. The client has to specify, what kind of elements he uses. The element of a node is stored in the PQLeafKey of a PQLeaf. The PQLeaf is the only concrete class template of the abstract base class template PQNode that is allowed to have a key.

Definition at line 48 of file PQLeaf.h.

Constructor & Destructor Documentation

◆ PQLeaf() [1/2]

template<class T , class X , class Y >
ogdf::PQLeaf< T, X, Y >::PQLeaf ( int  count,
PQNodeRoot::PQNodeStatus  stat,
PQLeafKey< T, X, Y > *  keyPtr,
PQNodeKey< T, X, Y > *  infoPtr 
)
inline

The client may choose between two different constructors.

In both cases the constructor expects an integer value count, setting the value of the variable m_identificationNumber in the base class, an integer value status setting the variable m_status of PQLeaf and a pointer to an element of type PQLeafKey.

One of the constructors expects additional information of type PQNodeKey and will automatically set the PQBasicKey::m_nodePointer (see basicKey) of the element of type PQNodeKey to the newly allocated PQLeaf (see also PQNode). The second constructor is called, if no information for the PQLeaf is available or necessary. Both constructors will automatically set the PQBasicKey::m_nodePointer of the keyPtr to the newly allocated PQLeaf.

Definition at line 67 of file PQLeaf.h.

◆ PQLeaf() [2/2]

template<class T , class X , class Y >
ogdf::PQLeaf< T, X, Y >::PQLeaf ( int  count,
PQNodeRoot::PQNodeStatus  stat,
PQLeafKey< T, X, Y > *  keyPtr 
)
inline

Definition at line 81 of file PQLeaf.h.

◆ ~PQLeaf()

template<class T , class X , class Y >
virtual ogdf::PQLeaf< T, X, Y >::~PQLeaf ( )
inlinevirtual

The destructor does not delete any accompanying information class as PQLeafKey, PQNodeKey and PQInternalKey.

This has been avoided, since applications may need the existence of these information classes after the corresponding node has been deleted. If the deletion of an accompanying information class should be performed with the deletion of a node, either derive a new class with an appropriate destructor, or make use of the function CleanNode() of the class template PQTree.

Definition at line 104 of file PQLeaf.h.

Member Function Documentation

◆ getInternal()

template<class T , class X , class Y >
virtual PQInternalKey<T,X,Y>* ogdf::PQLeaf< T, X, Y >::getInternal ( ) const
inlinevirtual

getInternal() returns 0.

The function is designed to return a pointer to the PQInternalKey information of a node, in case that the node is supposed to have internal information. The class template PQLeaf does not have PQInternalKey information.

Implements ogdf::PQNode< T, X, Y >.

Definition at line 146 of file PQLeaf.h.

◆ getKey()

template<class T , class X , class Y >
virtual PQLeafKey<T,X,Y>* ogdf::PQLeaf< T, X, Y >::getKey ( ) const
inlinevirtual

getKey() returns a pointer to the PQLeafKey of PQLeaf.

The adress of the PQLeafKey is stored in the private variable m_pointerToKey. The key contains informations of the element that is represented by the PQLeaf in the PQ-tree and is of type PQLeafKey.

Implements ogdf::PQNode< T, X, Y >.

Definition at line 113 of file PQLeaf.h.

◆ mark() [1/2]

template<class T , class X , class Y >
virtual PQNodeRoot::PQNodeMark ogdf::PQLeaf< T, X, Y >::mark ( ) const
inlinevirtual

Returns the variable m_mark.

The variable m_mark describes the designation used in the first pass of Booth and Luekers algorithm called Bubble(). A PQLeaf is either marked BLOCKED, UNBLOCKED or QUEUED (see PQNode).

Implements ogdf::PQNode< T, X, Y >.

Definition at line 177 of file PQLeaf.h.

◆ mark() [2/2]

template<class T , class X , class Y >
virtual void ogdf::PQLeaf< T, X, Y >::mark ( PQNodeRoot::PQNodeMark  m)
inlinevirtual

Sets the variable m_mark.

Definition at line 180 of file PQLeaf.h.

◆ setInternal()

template<class T , class X , class Y >
virtual bool ogdf::PQLeaf< T, X, Y >::setInternal ( PQInternalKey< T, X, Y > *  pointerToInternal)
inlinevirtual

setInternal() accepts only pointers pointerToInternal = 0.

The function setInternal() is designed to set a specified pointer variable in a derived class of PQNode to the adress stored in pointerToInternal. which is of type PQInternalKey. The class template PQLeaf does not store informations of type PQInternalKey.

setInternal() ignores the informations as long as pointerToInternal = 0. The return value then is 1. In case that pointerToInternal != 0, the return value is 0.

Implements ogdf::PQNode< T, X, Y >.

Definition at line 162 of file PQLeaf.h.

◆ setKey()

template<class T , class X , class Y >
virtual bool ogdf::PQLeaf< T, X, Y >::setKey ( PQLeafKey< T, X, Y > *  pointerToKey)
inlinevirtual

setKey() sets the pointer variable m_pointerToKey to the specified address of pointerToKey that is of type PQLeafKey.

Observe that pointerToKey has to be instantiated by the client. The function setKey() does not instantiate the corresponding variable in the derived class. Using this function will automatically set the PQBasicKey::m_nodePointer of the element of type key (see PQLeafKey) to this PQLeaf. The return value is always 1 unless pointerKey was equal to 0.

Implements ogdf::PQNode< T, X, Y >.

Definition at line 127 of file PQLeaf.h.

◆ status() [1/2]

template<class T , class X , class Y >
virtual PQNodeRoot::PQNodeStatus ogdf::PQLeaf< T, X, Y >::status ( ) const
inlinevirtual

Returns the variable m_status in the derived class PQLeaf.

The functions manage the status of a node in the PQ-tree. A status is any kind of information of the current situation in the frontier of a node (the frontier of a node are all descendant leaves of the node). A status can be anything such as EMPTY, FULL or PARTIAL (see PQNode). Since there might be more than those three possibilities, (e.g. in computing planar subgraphs) this function may to be overloaded by the client.

Implements ogdf::PQNode< T, X, Y >.

Definition at line 193 of file PQLeaf.h.

◆ status() [2/2]

template<class T , class X , class Y >
virtual void ogdf::PQLeaf< T, X, Y >::status ( PQNodeRoot::PQNodeStatus  s)
inlinevirtual

Sets the variable m_status in the derived class PQLeaf.

Definition at line 196 of file PQLeaf.h.

◆ type() [1/2]

template<class T , class X , class Y >
virtual PQNodeRoot::PQNodeType ogdf::PQLeaf< T, X, Y >::type ( ) const
inlinevirtual

Returns the variable PQInternalNode::m_type in the derived class PQLeaf.

The type of a node is either PNode, QNode or leaf (see PQNodeRoot). Since the type of an element of type PQLeaf is leaf every input is ignored and the return value will always be leaf.

Implements ogdf::PQNode< T, X, Y >.

Definition at line 205 of file PQLeaf.h.

◆ type() [2/2]

template<class T , class X , class Y >
virtual void ogdf::PQLeaf< T, X, Y >::type ( PQNodeRoot::PQNodeType  )
inlinevirtual

Sets the variable PQInternalNode::m_type in the derived class PQLeaf.

Definition at line 208 of file PQLeaf.h.

Member Data Documentation

◆ m_mark

template<class T , class X , class Y >
PQNodeRoot::PQNodeMark ogdf::PQLeaf< T, X, Y >::m_mark
private

m_mark is a variable, storing if the PQLeaf is QUEUEUD, BLOCKED or UNBLOCKED (see PQNode) during the first phase of the procedure Bubble().

Definition at line 217 of file PQLeaf.h.

◆ m_pointerToKey

template<class T , class X , class Y >
PQLeafKey<T,X,Y>* ogdf::PQLeaf< T, X, Y >::m_pointerToKey
private

m_pointerToKey stores the adress of the corresponding PQLeafKey.

This PQLeafKey can be overloaded by the client in order to represent different sets of elements, where possible permutations have to be examined by the PQ-tree.

Definition at line 226 of file PQLeaf.h.

◆ m_status

template<class T , class X , class Y >
PQNodeRoot::PQNodeStatus ogdf::PQLeaf< T, X, Y >::m_status
private

m_status is a variable storing the status of a PQLeaf.

A PQLeaf can be either FULL or EMPTY (see PQNode).

Definition at line 232 of file PQLeaf.h.


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