Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::PQNode< T, X, Y > Class Template Referenceabstract

The class template PQBasicKey is an abstract base class. More...

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

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

Public Member Functions

 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...
 
virtual PQInternalKey< T, X, Y > * getInternal () const =0
 getInternal() returns a pointer to the PQInternalKey information of a node, in case that the node is supposed to have PQInternalKey information, such as elements of the derived class template PQInternalNode. More...
 
virtual PQLeafKey< T, X, Y > * getKey () const =0
 getKey() returns a pointer to the PQLeafKeyof a node, in case that the node is supposed to have a key, such as elements of the derived class template PQLeaf. 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 PQNodeMark mark () const =0
 mark() returns the variable PQLeaf::m_mark in the derived class PQLeaf and PQInternalNode. 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...
 
virtual bool setInternal (PQInternalKey< T, X, Y > *pointerToInternal)=0
 
virtual bool setKey (PQLeafKey< T, X, Y > *pointerToKey)=0
 Sets a specified pointer variable in a derived class to the specified adress of pointerToKey that is of type PQLeafKey. More...
 
bool setNodeInfo (PQNodeKey< T, X, Y > *pointerToInfo)
 Sets the pointer m_pointerToInfo to the specified adress of pointerToInfo. More...
 
virtual PQNodeStatus status () const =0
 Returns the variable PQLeaf::m_status in the derived class PQLeaf and PQInternalNode. More...
 
virtual void status (PQNodeStatus)=0
 Sets the variable PQLeaf::m_status in the derived class PQLeaf and PQInternalNode. More...
 
virtual PQNodeType type () const =0
 Returns the variable PQInternalNode::m_type 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...
 

Protected Attributes

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...
 

Friends

class PQTree< T, X, Y >
 All members and member function of PQNode are needed by the class template PQTree. More...
 

Detailed Description

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

The class template PQBasicKey is an abstract base class.

It enables the user of the PQ-tree to store different informations at every node of the tree.

The implementation of the PQ-tree provides the storage of three different types of information.

  • General information that is stored at P- and Q-nodes and leaves likewise (see also PQNodeKey).
  • Information that is only supported for internal nodes (see also internalKey).
  • The keys of the leaves (see also leafKey). The keys are constructed to carry the elements of a user defined set of any type, where permissible permutations have to be found. In order to use the datastructure PQ-tree as class template PQTree, the user has to specify a set of arbitrary elements that form the leaves of the PQ-tree. The keys function as storage class of the elements of the set.

All three storage classes are derived class templates of PQBasicKey. The class PQBasicKey has a pointer PQBasicKey::m_nodePointer to a PQNode, beeing either a leaf or an internal PQInternalNode. The base class itself does not provide any storage of the informations, it is hidden in the derived classes. PQBasicKey only declares a few pure virtual functions that are overloaded in the derived classes and which give access to the information stored in the derived classes.

The information stored in an element of a derived class of PQBasicKey is assigned to a unique node in the PQ-tree. This unique node can be identified with the PQBasicKey::m_nodePointer. The maintenance of this pointer is left to the user in the derived concrete classes PQNodeKey and internalKey. By keeping the responsibillity for these classes by the client, nodes with certain informations can be accessed by the client in constant time. This makes the adaption of algorithms fast and easy.

Only the derived concrete class template leafKey is treated in a different way by the class template PQTree. When initializing the PQTree with a set of elements of type leafKey, the class template PQTree sets the pointer PQBasicKey::m_nodePointer of every element. This is due to the fact that a PQ-tree is always defined over some set, whose elements are stored in the leaves. Hence the class PQtree expects such a set and supports its maintainance. Storing extra information at every node may be omitted and makes the PQtree easy applicable.

We now give a short overview of the class template declaration PQBasicKey. The class template PQBasicKey is used as a base class template that specifies three different types of information. The type of information used at a node is depending on the type of the node. These informations have to be specified by the user.

The formal type parameters of the class template PQBasicKey are categorized as follows.

  • T is a formal type parameter for the information stored in leafKey.
  • X is a formal type parameter for the information stored in PQNodeKey.
  • Y is a formal type parameter for the information stored in internalKey.

The class template PQBasicKey contains a few pure virtual member functions that are overloaded in the derived class leafKey, PQNodeKey and internalKey. These functions enable the client to access the information stored at a node.

Definition at line 108 of file PQBasicKey.h.

Constructor & Destructor Documentation

◆ PQNode() [1/2]

template<class T , class X , class Y >
ogdf::PQNode< T, X, Y >::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.

Definition at line 571 of file PQNode.h.

◆ PQNode() [2/2]

template<class T , class X , class Y >
ogdf::PQNode< T, X, Y >::PQNode ( int  count)
explicit

The (second) constructor is called, if no information is available or neccessary.

Definition at line 602 of file PQNode.h.

◆ ~PQNode()

template<class T , class X , class Y >
virtual ogdf::PQNode< T, X, Y >::~PQNode ( )
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 85 of file PQNode.h.

Member Function Documentation

◆ changeEndmost()

template<class T , class X , class Y >
bool ogdf::PQNode< T, X, Y >::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.

If the node is a Q-node, then it must have two valid pointers to its endmost children. If one of the endmost children is oldEnd, it is replaced by newEnd. The function changeEndmost() returns 1 if it succeeded in replacing oldEnd by newEnd. Otherwise the function returns 0, leaving with an error message.

Definition at line 521 of file PQNode.h.

◆ changeSiblings()

template<class T , class X , class Y >
bool ogdf::PQNode< T, X, Y >::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.

If the node has oldSib as sibling, then it changes the sibling pointer that references to oldSib and places newSib at its position. The function changeSiblings() returns 1 if it succeeded in replacing oldSib by newSib. Otherwise the function returns 0, leaving with an error message.

Definition at line 549 of file PQNode.h.

◆ childCount() [1/2]

template<class T , class X , class Y >
int ogdf::PQNode< T, X, Y >::childCount ( ) const
inline

Returns the number of children of a node.

Definition at line 197 of file PQNode.h.

◆ childCount() [2/2]

template<class T , class X , class Y >
void ogdf::PQNode< T, X, Y >::childCount ( int  count)
inline

Sets the number of children of a node.

Definition at line 200 of file PQNode.h.

◆ endmostChild()

template<class T , class X , class Y >
bool ogdf::PQNode< T, X, Y >::endmostChild ( ) const
inline

The function endmostChild() checks if a node is endmost child of a Q-node.

This is 1 if one of the sibling pointers m_sibLeft or m_sibRight is 0. If the node is endmost child of a Q-node, then it has a valid parent pointer.

Definition at line 121 of file PQNode.h.

◆ getEndmost() [1/2]

template<class T , class X , class Y >
PQNode<T,X,Y>* ogdf::PQNode< T, X, Y >::getEndmost ( PQNode< T, X, Y > *  other) const
inline

Returns one of the endmost children of node, if node is a Q-node.

The function getEndmost() accepts as input a pointer to a PQNode stored in other. The returned endmost child is unequal to the one specified in other. In case that an arbitrary endmost child should be looked up, set other = 0. This makes the function getEndmost() return an arbitrary endmost child (it returns the left endmost child).

Definition at line 134 of file PQNode.h.

◆ getEndmost() [2/2]

template<class T , class X , class Y >
PQNode<T,X,Y>* ogdf::PQNode< T, X, Y >::getEndmost ( SibDirection  side) const
inline

Returns one of the endmost children of node, if node is a Q-node.

The function accepts an integer denoting a direction causing the function to return either the left or the endmost child.

Definition at line 148 of file PQNode.h.

◆ getInternal()

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

getInternal() returns a pointer to the PQInternalKey information of a node, in case that the node is supposed to have PQInternalKey information, such as elements of the derived class template PQInternalNode.

The internal information is of type PQInternalKey.

Implemented in ogdf::PQInternalNode< T, X, Y >, and ogdf::PQLeaf< T, X, Y >.

◆ getKey()

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

getKey() returns a pointer to the PQLeafKeyof a node, in case that the node is supposed to have a key, such as elements of the derived class template PQLeaf.

The key contains information and is of type PQLeafKey.

Implemented in ogdf::PQInternalNode< T, X, Y >, and ogdf::PQLeaf< T, X, Y >.

◆ getNextSib()

template<class T , class X , class Y >
PQNode<T,X,Y>* ogdf::PQNode< T, X, Y >::getNextSib ( PQNode< T, X, Y > *  other) const
inline

The function getNextSib() returns one of the siblings of the node.

The function getNextSib() accepts as input a pointer to a PQNode stored in other. The returned sibling is unequal to the one specified in other. In case that no sibling has been looked up before, set other = 0. This makes the function getNextSib() return an arbitrary sibling (it returns the left sibling).

Definition at line 183 of file PQNode.h.

◆ getNodeInfo()

template<class T , class X , class Y >
PQNodeKey<T,X,Y>* ogdf::PQNode< T, X, Y >::getNodeInfo ( ) const
inline

Returns the identification number of a node.

Definition at line 158 of file PQNode.h.

◆ getSib()

template<class T , class X , class Y >
PQNode<T,X,Y>* ogdf::PQNode< T, X, Y >::getSib ( SibDirection  side) const
inline

The function getSib() returns one of the siblings of the node.

It accepts an integer denoting a dircetion causing the function to return either the left or the right sibling.

Definition at line 165 of file PQNode.h.

◆ identificationNumber()

template<class T , class X , class Y >
int ogdf::PQNode< T, X, Y >::identificationNumber ( ) const
inline

Returns the identification number of a node.

Definition at line 194 of file PQNode.h.

◆ mark() [1/2]

template<class T , class X , class Y >
virtual PQNodeMark ogdf::PQNode< T, X, Y >::mark ( ) const
pure virtual

mark() returns the variable PQLeaf::m_mark in the derived class PQLeaf and PQInternalNode.

In a derived class this function has to return the designation used in the first pass of Booth and Luekers algorithm called Bubble(). A node then is either marked BLOCKED, UNBLOCKED or QUEUED (see PQNode).

Implemented in ogdf::PQInternalNode< T, X, Y >, and ogdf::PQLeaf< T, X, Y >.

◆ mark() [2/2]

template<class T , class X , class Y >
virtual void ogdf::PQNode< T, X, Y >::mark ( PQNodeMark  )
pure virtual

mark() sets the variable PQLeaf::m_mark in the derived class PQLeaf and PQInternalNode.

Implemented in ogdf::booth_lueker::EmbedIndicator.

◆ parent() [1/2]

template<class T , class X , class Y >
PQNode<T,X,Y>* ogdf::PQNode< T, X, Y >::parent ( ) const
inline

The function parent() returns a pointer to the parent of a node.

Warning
After reducing the PQ-tree, some nodes may not have valid parent pointers anymore. This is no fault, the datastructur was designed this way. See also Booth and Lueker.

Definition at line 209 of file PQNode.h.

◆ parent() [2/2]

template<class T , class X , class Y >
PQNode<T,X,Y>* ogdf::PQNode< T, X, Y >::parent ( PQNode< T, X, Y > *  newParent)
inline

Sets the parent pointer of a node.

This function is needed in more ellaborated algorithms implemented as derivation of the class template PQTree. Here, the parent pointer probably is always needed and therefore has to be set within special functions, used in a pre-run before applying the bubble Phase of the PQTree.

Definition at line 218 of file PQNode.h.

◆ parentType() [1/2]

template<class T , class X , class Y >
PQNodeType ogdf::PQNode< T, X, Y >::parentType ( ) const
inline

Returns the type of the parent of a node.

Definition at line 224 of file PQNode.h.

◆ parentType() [2/2]

template<class T , class X , class Y >
void ogdf::PQNode< T, X, Y >::parentType ( PQNodeType  newParentType)
inline

Sets the type of the parent of a node.

This does not change the type of the parent!

Definition at line 230 of file PQNode.h.

◆ pertChildCount() [1/2]

template<class T , class X , class Y >
int ogdf::PQNode< T, X, Y >::pertChildCount ( ) const
inline

Returs the number of pertinent children of a node.

Definition at line 233 of file PQNode.h.

◆ pertChildCount() [2/2]

template<class T , class X , class Y >
void ogdf::PQNode< T, X, Y >::pertChildCount ( int  count)
inline

Sets the number of pertinent children of a node.

Definition at line 236 of file PQNode.h.

◆ putSibling() [1/2]

template<class T , class X , class Y >
SibDirection ogdf::PQNode< T, X, Y >::putSibling ( PQNode< T, X, Y > *  newSib)
inline

The default function putSibling() stores a new sibling at a free sibling pointer of the node.

This is only possible, if the node has at most one sibling. The function then detects a non used sibling pointer and places newSib onto it. putSibling() returns 0 if there have been two siblings detected, occupying the two possible pointers. In this case the new sibling newSib cannot be stored. If there was at a maximum one sibling stored, the function will place newSib on the free pointer and return either LEFT or RIGHT, depending wich pointer has been used.

This function will always scan the pointer to the left brother first.

Definition at line 251 of file PQNode.h.

◆ putSibling() [2/2]

template<class T , class X , class Y >
SibDirection ogdf::PQNode< T, X, Y >::putSibling ( PQNode< T, X, Y > *  newSib,
SibDirection  preference 
)
inline

The function putSibling() with preference stores a new sibling at a free sibling pointer of the node.

This is only possible, if the node has at most one sibling. The function then detects a non used sibling pointer and places newSib onto it. putSibling() returns 0 if there have been two siblings detected, occupying the two possible pointers. In this case the new sibling newSib could not be stored. If there was at a maximum one sibling stored, the function will place newSib on the free pointer and return either LEFT or RIGHT, depending wich pointer has been used.

This function scans the brother first, which has been specified in the preference. If the preference has value LEFT, it scans the pointer to the left brother first. If the value is RIGHT, it scans the pointer to the right brother first.

Definition at line 279 of file PQNode.h.

◆ referenceChild()

template<class T , class X , class Y >
PQNode<T,X,Y>* ogdf::PQNode< T, X, Y >::referenceChild ( ) const
inline

Returns a pointer to the reference child if node is a P-node.

Definition at line 298 of file PQNode.h.

◆ referenceParent()

template<class T , class X , class Y >
PQNode<T,X,Y>* ogdf::PQNode< T, X, Y >::referenceParent ( ) const
inline

Returns the pointer to the parent if node is a reference child.

Definition at line 301 of file PQNode.h.

◆ setInternal()

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

◆ setKey()

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

Sets a specified pointer variable in a derived class to the specified adress of pointerToKey that is of type PQLeafKey.

If a derived class, such as PQInternalNode, is not supposed to 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.

If a derived class, such as PQLeaf is supposed to store informations of type PQLeafKey, pointerToKey has to be instantiated by the client. The function setKey() does not instantiate the corresponding variable in the derived class. The return value is always 1 unless pointerKey was equal to 0.

Implemented in ogdf::PQInternalNode< T, X, Y >, and ogdf::PQLeaf< T, X, Y >.

◆ setNodeInfo()

template<class T , class X , class Y >
bool ogdf::PQNode< T, X, Y >::setNodeInfo ( PQNodeKey< T, X, Y > *  pointerToInfo)
inline

Sets the pointer m_pointerToInfo to the specified adress of pointerToInfo.

Definition at line 304 of file PQNode.h.

◆ status() [1/2]

template<class T , class X , class Y >
virtual PQNodeStatus ogdf::PQNode< T, X, Y >::status ( ) const
pure virtual

Returns the variable PQLeaf::m_status in the derived class PQLeaf and PQInternalNode.

Its objective is to manage 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 is 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 probably has to be overloaded by the client.

Implemented in ogdf::PQInternalNode< T, X, Y >, and ogdf::PQLeaf< T, X, Y >.

◆ status() [2/2]

template<class T , class X , class Y >
virtual void ogdf::PQNode< T, X, Y >::status ( PQNodeStatus  )
pure virtual

Sets the variable PQLeaf::m_status in the derived class PQLeaf and PQInternalNode.

Implemented in ogdf::booth_lueker::EmbedIndicator.

◆ type() [1/2]

template<class T , class X , class Y >
virtual PQNodeType ogdf::PQNode< T, X, Y >::type ( ) const
pure virtual

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

Its objective it to manage the type of a node. node the current node is. The type of a node in the class template PQTree is either PNode, QNode or leaf (see PQNode). There may be of course more types such as sequence indicators.

Observe that the derived class template PQLeaf does not have a variable PQInternalNode::m_type, since it obviously is of type leaf.

Implemented in ogdf::PQInternalNode< T, X, Y >, and ogdf::PQLeaf< T, X, Y >.

◆ type() [2/2]

template<class T , class X , class Y >
virtual void ogdf::PQNode< T, X, Y >::type ( PQNodeType  )
pure virtual

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

Implemented in ogdf::booth_lueker::EmbedIndicator.

Friends And Related Function Documentation

◆ PQTree< T, X, Y >

template<class T , class X , class Y >
friend class PQTree< T, X, Y >
friend

All members and member function of PQNode are needed by the class template PQTree.

Therefore the class PQTree was made friendof PQNode, since this prevents the use of a large amount of extra public functions.

Definition at line 58 of file PQNode.h.

Member Data Documentation

◆ fullChildren

template<class T , class X , class Y >
List<PQNode<T,X,Y>*>* ogdf::PQNode< T, X, Y >::fullChildren
protected

Stores all full children of a node during a reduction.

Definition at line 502 of file PQNode.h.

◆ m_childCount

template<class T , class X , class Y >
int ogdf::PQNode< T, X, Y >::m_childCount
protected

Definition at line 416 of file PQNode.h.

◆ m_debugTreeNumber

template<class T , class X , class Y >
int ogdf::PQNode< T, X, Y >::m_debugTreeNumber
protected

Needed for debuging purposes.

The PQ-trees can be visualized with the help of the Tree Interface and the m_debugTreeNumber is needed to print out the tree in the correct file format.

Definition at line 424 of file PQNode.h.

◆ m_firstFull

template<class T , class X , class Y >
PQNode<T,X,Y>* ogdf::PQNode< T, X, Y >::m_firstFull
protected

Stores a pointer to the first full child of a Q-node.

Definition at line 449 of file PQNode.h.

◆ m_identificationNumber

template<class T , class X , class Y >
int ogdf::PQNode< T, X, Y >::m_identificationNumber
protected

Each node that has been introduced once into the tree gets a unique number.

If the node is removed from the tree during a reduction or with the help of one of the functions that is provided by the class template PQtree, its number is not reused. This always allows exact identification of nodes during any process that is envoked on the PQ-tree. We strongly recommend users who construct the tree with the help of the construction functions and who instantiate the nodes by them selves to do the same.

Definition at line 437 of file PQNode.h.

◆ m_leftEndmost

template<class T , class X , class Y >
PQNode<T,X,Y>* ogdf::PQNode< T, X, Y >::m_leftEndmost
protected

Definition at line 451 of file PQNode.h.

◆ m_parent

template<class T , class X , class Y >
PQNode<T,X,Y>* ogdf::PQNode< T, X, Y >::m_parent
protected

Is a pointer to the parent.

Observe that this pointer may not be up to date after a few applications of the reduction.

Definition at line 458 of file PQNode.h.

◆ m_parentType

template<class T , class X , class Y >
PQNodeType ogdf::PQNode< T, X, Y >::m_parentType
protected

Stores the type of the parent which can be either a P- or Q-node.

Definition at line 440 of file PQNode.h.

◆ m_pertChildCount

template<class T , class X , class Y >
int ogdf::PQNode< T, X, Y >::m_pertChildCount
protected

Stores the number of pertinent children of the node.

Definition at line 443 of file PQNode.h.

◆ m_pertLeafCount

template<class T , class X , class Y >
int ogdf::PQNode< T, X, Y >::m_pertLeafCount
protected

Stores the number of pertinent leaves in the frontier of the node.

Definition at line 446 of file PQNode.h.

◆ m_pointerToInfo

template<class T , class X , class Y >
PQNodeKey<T,X,Y>* ogdf::PQNode< T, X, Y >::m_pointerToInfo
protected

Stores a pointer to the corresponding information of the node.

Definition at line 498 of file PQNode.h.

◆ m_referenceChild

template<class T , class X , class Y >
PQNode<T,X,Y>* ogdf::PQNode< T, X, Y >::m_referenceChild
protected

Stores a pointer to one child, the reference child of the doubly linked cirkular list of children of a P-node.

With the help of this pointer, it is possible to access the children of the P-node

Definition at line 466 of file PQNode.h.

◆ m_referenceParent

template<class T , class X , class Y >
PQNode<T,X,Y>* ogdf::PQNode< T, X, Y >::m_referenceParent
protected

Is a pointer to the parent, in case that the parent is a P-node and the node itself is its reference child.

The pointer is needed in order to identify the reference child among all children of a P-node.

Definition at line 474 of file PQNode.h.

◆ m_rightEndmost

template<class T , class X , class Y >
PQNode<T,X,Y>* ogdf::PQNode< T, X, Y >::m_rightEndmost
protected

Stores the right endmost child of a Q-node.

Definition at line 477 of file PQNode.h.

◆ m_sibLeft

template<class T , class X , class Y >
PQNode<T,X,Y>* ogdf::PQNode< T, X, Y >::m_sibLeft
protected

Stores a pointer ot the left sibling of PQNode.

If PQNode is child of a Q-node and has no left sibling, m_sibLeft is set to 0. If PQNode is child of a P-node, all children of the P-node are linked in a circular list. In the latter case, m_sibLeft is never 0.

Definition at line 486 of file PQNode.h.

◆ m_sibRight

template<class T , class X , class Y >
PQNode<T,X,Y>* ogdf::PQNode< T, X, Y >::m_sibRight
protected

Stores a pointer ot the right sibling of PQNode.

If PQNode is child of a Q-node and has no right sibling, m_sibRight is set to 0. If PQNode is child of a P-node, all children of the P-node are linked in a circular list. In the latter case, m_sibRight is never 0.

Definition at line 495 of file PQNode.h.

◆ partialChildren

template<class T , class X , class Y >
List<PQNode<T,X,Y>*>* ogdf::PQNode< T, X, Y >::partialChildren
protected

Stores all partial children of a node during a reduction.

Definition at line 505 of file PQNode.h.


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