Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

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

The class template PQInternalNode is used to present P-nodes and Q-nodes in the PQ-Tree. More...

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

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

Public Member Functions

 PQInternalNode (int count, PQNodeRoot::PQNodeType typ, PQNodeRoot::PQNodeStatus stat)
 
 PQInternalNode (int count, PQNodeRoot::PQNodeType typ, PQNodeRoot::PQNodeStatus stat, PQInternalKey< T, X, Y > *internalPtr)
 
 PQInternalNode (int count, PQNodeRoot::PQNodeType typ, PQNodeRoot::PQNodeStatus stat, PQInternalKey< T, X, Y > *internalPtr, PQNodeKey< T, X, Y > *infoPtr)
 
 PQInternalNode (int count, PQNodeRoot::PQNodeType typ, PQNodeRoot::PQNodeStatus stat, PQNodeKey< T, X, Y > *infoPtr)
 
 ~PQInternalNode ()
 The destructor does not delete any accompanying information class as PQLeafKey, PQNodeKey and PQInternalKey. More...
 
virtual PQInternalKey< T, X, Y > * getInternal () const
 Returns a pointer to the PQInternalKey information. More...
 
virtual PQLeafKey< T, X, Y > * getKey () const
 Returns 0. An element of type PQInternalNode does not have a PQLeafKey. 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() sets the pointer variable m_pointerToInternal to the specified adress of pointerToInternal that is of type PQInternalKey. More...
 
virtual bool setKey (PQLeafKey< T, X, Y > *pointerToKey)
 Accepts only pointers pointerToKey = 0. More...
 
virtual PQNodeRoot::PQNodeStatus status () const
 Returns the variable m_status in the derived class PQInternalNode. More...
 
virtual void status (PQNodeRoot::PQNodeStatus s)
 Sets the variable m_status in the derived class PQInternalNode. More...
 
virtual PQNodeRoot::PQNodeType type () const
 Returns the variable m_type in the derived class PQInternalNode. More...
 
virtual void type (PQNodeRoot::PQNodeType t)
 Sets the variable m_type in the derived class PQInternalNode. 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 a PQInternalNode is QUEUEUD, BLOCKED or UNBLOCKED (see PQNode) during the first phase of the procedure Bubble(). More...
 
PQInternalKey< T, X, Y > * m_pointerToInternal
 m_pointerToInternal stores the adress of the corresponding internal information. More...
 
PQNodeRoot::PQNodeStatus m_status
 m_status is a variable storing the status of a PQInternalNode. More...
 
PQNodeRoot::PQNodeType m_type
 m_status is a variable storing the status of a PQInternalNode. 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::PQInternalNode< T, X, Y >

The class template PQInternalNode is used to present P-nodes and Q-nodes in the PQ-Tree.

This implementation does not provide different classes for both, P- and Q-nodes, although this might seem necessary in the first place. The reason why this is not done, is supported by the fact that the maintainance of both nodes in the tree is similar and using the same class for P- and Q-nodes makes the application of the templates by Booth and Lueker much easier.

The template class PQInternalNode offers the possibility of using four different kinds of constructors, depending on the usage of the different possible information classes PQInternalKey<T,X,Y> and PQNodeKey<T,X,Y>.

In all four cases the constructor expects an integer value count, setting the value of the variable m_identificationNumber in the base class, an integer value type setting the variable m_type of PQInternalNode and an integer value status setting the variable m_status of PQInternalNode.

Besides, the constructors accept additional information of type PQNodeKey and PQInternalKey. This information is not necessary when allocating an element of type PQInternalNode and results in the four constructors that handle all cases.

Using a constructor with the infoPtr storing the adress of an element of type PQNodeKey automatically sets the PQBasicKey::m_nodePointer (see basicKey) of this element of type PQNodeKey to the newly allocated PQInternalNode. See also PQNode since this is done in the base class.

Using a constructor with the PQInternalKeyPtr storing the adress of an element of type PQInternalKey automatically sets the PQBasicKey::m_nodePointer (see basicKey) of this element of type PQInternalKey to the newly allocated PQInternalNode.

Definition at line 76 of file PQInternalNode.h.

Constructor & Destructor Documentation

◆ PQInternalNode() [1/4]

template<class T , class X , class Y >
ogdf::PQInternalNode< T, X, Y >::PQInternalNode ( int  count,
PQNodeRoot::PQNodeType  typ,
PQNodeRoot::PQNodeStatus  stat,
PQInternalKey< T, X, Y > *  internalPtr,
PQNodeKey< T, X, Y > *  infoPtr 
)
inline

Definition at line 79 of file PQInternalNode.h.

◆ PQInternalNode() [2/4]

template<class T , class X , class Y >
ogdf::PQInternalNode< T, X, Y >::PQInternalNode ( int  count,
PQNodeRoot::PQNodeType  typ,
PQNodeRoot::PQNodeStatus  stat,
PQInternalKey< T, X, Y > *  internalPtr 
)
inline

Definition at line 95 of file PQInternalNode.h.

◆ PQInternalNode() [3/4]

template<class T , class X , class Y >
ogdf::PQInternalNode< T, X, Y >::PQInternalNode ( int  count,
PQNodeRoot::PQNodeType  typ,
PQNodeRoot::PQNodeStatus  stat,
PQNodeKey< T, X, Y > *  infoPtr 
)
inline

Definition at line 109 of file PQInternalNode.h.

◆ PQInternalNode() [4/4]

template<class T , class X , class Y >
ogdf::PQInternalNode< T, X, Y >::PQInternalNode ( int  count,
PQNodeRoot::PQNodeType  typ,
PQNodeRoot::PQNodeStatus  stat 
)
inline

Definition at line 122 of file PQInternalNode.h.

◆ ~PQInternalNode()

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

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 146 of file PQInternalNode.h.

Member Function Documentation

◆ getInternal()

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

Returns a pointer to the PQInternalKey information.

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

Definition at line 170 of file PQInternalNode.h.

◆ getKey()

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

Returns 0. An element of type PQInternalNode does not have a PQLeafKey.

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

Definition at line 150 of file PQInternalNode.h.

◆ mark() [1/2]

template<class T , class X , class Y >
virtual PQNodeRoot::PQNodeMark ogdf::PQInternalNode< 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 P- or Q-node is either marked BLOCKED, UNBLOCKED or QUEUED (see PQNode).

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

Definition at line 202 of file PQInternalNode.h.

◆ mark() [2/2]

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

Sets the variable m_mark.

Definition at line 205 of file PQInternalNode.h.

◆ setInternal()

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

setInternal() sets the pointer variable m_pointerToInternal to the specified adress of pointerToInternal that is of type PQInternalKey.

Observe that pointerToInternal has to be instantiated by the client. The function setInternal() does not instantiate the corresponding variable in the derived class. Nevertheless, using this function will automatically set the PQBasicKey::m_nodePointer of the element of type PQInternalKey to this PQInternalNode. The return value is always 1 unless pointerInternal was equal to 0.

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

Definition at line 183 of file PQInternalNode.h.

◆ setKey()

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

Accepts only pointers pointerToKey = 0.

The function setKey() is designed to set a specified pointer variable in a derived class of PQNode to the adress stored in pointerToKey that is of type PQLeafKey. The class template PQInternalNode does not store informations of type PQLeafKey.

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

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

Definition at line 164 of file PQInternalNode.h.

◆ status() [1/2]

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

Returns the variable m_status in the derived class PQInternalNode.

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 be overloaded by the client.

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

Definition at line 217 of file PQInternalNode.h.

◆ status() [2/2]

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

Sets the variable m_status in the derived class PQInternalNode.

Definition at line 220 of file PQInternalNode.h.

◆ type() [1/2]

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

Returns the variable m_type in the derived class PQInternalNode.

The type of a PQInternalNode is either PNode or QNode (see PQNodeRoot).

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

Definition at line 227 of file PQInternalNode.h.

◆ type() [2/2]

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

Sets the variable m_type in the derived class PQInternalNode.

Definition at line 230 of file PQInternalNode.h.

Member Data Documentation

◆ m_mark

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

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

Definition at line 239 of file PQInternalNode.h.

◆ m_pointerToInternal

template<class T , class X , class Y >
PQInternalKey<T,X,Y>* ogdf::PQInternalNode< T, X, Y >::m_pointerToInternal
private

m_pointerToInternal stores the adress of the corresponding internal information.

That is information not supposed to be available for leaves of the PQ-tree. The internal information must be of type PQInternalKey. The PQInternalKey information can be overloaded by the client in order to present different information classes, needed in the different applications of PQ-trees.

Definition at line 251 of file PQInternalNode.h.

◆ m_status

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

m_status is a variable storing the status of a PQInternalNode.

A P- or Q-node can be either FULL, PARTIAL or EMPTY (see PQNode).

Definition at line 258 of file PQInternalNode.h.

◆ m_type

template<class T , class X , class Y >
PQNodeRoot::PQNodeType ogdf::PQInternalNode< T, X, Y >::m_type
private

m_status is a variable storing the status of a PQInternalNode.

A P- or Q-node can be either FULL, PARTIAL or EMPTY (see PQNode).

Definition at line 265 of file PQInternalNode.h.


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