|
|||
|
|
|
|||
|
|
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. | |
| virtual PQInternalKey< T, X, Y > * | getInternal () const |
| Returns a pointer to the PQInternalKey information. | |
| virtual PQLeafKey< T, X, Y > * | getKey () const |
| Returns 0. An element of type PQInternalNode does not have a PQLeafKey. | |
| virtual PQNodeRoot::PQNodeMark | mark () const |
| Returns the variable m_mark. | |
| virtual void | mark (PQNodeRoot::PQNodeMark m) |
| Sets the variable m_mark. | |
| 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. | |
| virtual bool | setKey (PQLeafKey< T, X, Y > *pointerToKey) |
Accepts only pointers pointerToKey = 0. | |
| virtual PQNodeRoot::PQNodeStatus | status () const |
| Returns the variable m_status in the derived class PQInternalNode. | |
| virtual void | status (PQNodeRoot::PQNodeStatus s) |
| Sets the variable m_status in the derived class PQInternalNode. | |
| virtual PQNodeRoot::PQNodeType | type () const |
| Returns the variable m_type in the derived class PQInternalNode. | |
| virtual void | type (PQNodeRoot::PQNodeType t) |
| Sets the variable m_type in the derived class PQInternalNode. | |
| 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. | |
| 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. | |
| virtual | ~PQNode () |
| The destructor does not delete any accompanying information class as PQLeafKey, PQNodeKey and PQInternalKey. | |
| 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. | |
| 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. | |
| int | childCount () const |
| Returns the number of children of a node. | |
| void | childCount (int count) |
| Sets the number of children of a node. | |
| bool | endmostChild () const |
| The function endmostChild() checks if a node is endmost child of a Q-node. | |
| 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. | |
| PQNode< T, X, Y > * | getEndmost (SibDirection side) const |
| Returns one of the endmost children of node, if node is a Q-node. | |
| PQNode< T, X, Y > * | getNextSib (PQNode< T, X, Y > *other) const |
| The function getNextSib() returns one of the siblings of the node. | |
| PQNodeKey< T, X, Y > * | getNodeInfo () const |
| Returns the identification number of a node. | |
| PQNode< T, X, Y > * | getSib (SibDirection side) const |
| The function getSib() returns one of the siblings of the node. | |
| int | identificationNumber () const |
| Returns the identification number of a node. | |
| PQNode< T, X, Y > * | parent () const |
| The function parent() returns a pointer to the parent of a node. | |
| PQNode< T, X, Y > * | parent (PQNode< T, X, Y > *newParent) |
| Sets the parent pointer of a node. | |
| PQNodeType | parentType () const |
| Returns the type of the parent of a node. | |
| void | parentType (PQNodeType newParentType) |
| Sets the type of the parent of a node. | |
| int | pertChildCount () const |
| Returs the number of pertinent children of a node. | |
| void | pertChildCount (int count) |
| Sets the number of pertinent children of a node. | |
| SibDirection | putSibling (PQNode< T, X, Y > *newSib) |
| The default function putSibling() stores a new sibling at a free sibling pointer of the node. | |
| 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. | |
| PQNode< T, X, Y > * | referenceChild () const |
| Returns a pointer to the reference child if node is a P-node. | |
| PQNode< T, X, Y > * | referenceParent () const |
| Returns the pointer to the parent if node is a reference child. | |
| bool | setNodeInfo (PQNodeKey< T, X, Y > *pointerToInfo) |
Sets the pointer m_pointerToInfo to the specified adress of pointerToInfo. | |
| Public Member Functions inherited from ogdf::PQNodeRoot | |
| PQNodeRoot () | |
| virtual | ~PQNodeRoot () |
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(). | |
| PQInternalKey< T, X, Y > * | m_pointerToInternal |
| m_pointerToInternal stores the adress of the corresponding internal information. | |
| PQNodeRoot::PQNodeStatus | m_status |
| m_status is a variable storing the status of a PQInternalNode. | |
| PQNodeRoot::PQNodeType | m_type |
| m_status is a variable storing the status of a PQInternalNode. | |
Additional Inherited Members | |
| Public Types inherited from ogdf::PQNodeRoot | |
| enum class | PQNodeMark { Unmarked = 0 , Queued = 1 , Blocked = 2 , Unblocked = 3 } |
| enum class | PQNodeStatus { Empty = 1 , Partial = 2 , Full = 3 , Pertinent = 4 , ToBeDeleted = 5 , Indicator = 6 , Eliminated = 6 , WhaDelete = 7 , PertRoot = 8 } |
| enum class | PQNodeType { PNode = 1 , QNode = 2 , Leaf = 3 , Undefined = 0 } |
| enum class | SibDirection { NoDir , Left , Right } |
| 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. | |
| int | m_childCount |
| int | m_debugTreeNumber |
| Needed for debuging purposes. | |
| PQNode< T, X, Y > * | m_firstFull |
| Stores a pointer to the first full child of a Q-node. | |
| int | m_identificationNumber |
| Each node that has been introduced once into the tree gets a unique number. | |
| PQNode< T, X, Y > * | m_leftEndmost |
| PQNode< T, X, Y > * | m_parent |
| Is a pointer to the parent. | |
| PQNodeType | m_parentType |
| Stores the type of the parent which can be either a P- or Q-node. | |
| int | m_pertChildCount |
| Stores the number of pertinent children of the node. | |
| int | m_pertLeafCount |
| Stores the number of pertinent leaves in the frontier of the node. | |
| PQNodeKey< T, X, Y > * | m_pointerToInfo |
| Stores a pointer to the corresponding information of the node. | |
| 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. | |
| 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. | |
| PQNode< T, X, Y > * | m_rightEndmost |
| Stores the right endmost child of a Q-node. | |
| PQNode< T, X, Y > * | m_sibLeft |
| Stores a pointer ot the left sibling of PQNode. | |
| PQNode< T, X, Y > * | m_sibRight |
| Stores a pointer ot the right sibling of PQNode. | |
| List< PQNode< T, X, Y > * > * | partialChildren |
| Stores all partial children of a node during a reduction. | |
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.
|
inline |
Definition at line 78 of file PQInternalNode.h.
|
inline |
Definition at line 89 of file PQInternalNode.h.
|
inline |
Definition at line 99 of file PQInternalNode.h.
|
inline |
Definition at line 108 of file PQInternalNode.h.
|
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 127 of file PQInternalNode.h.
|
inlinevirtual |
Returns a pointer to the PQInternalKey information.
Implements ogdf::PQNode< T, X, Y >.
Definition at line 147 of file PQInternalNode.h.
|
inlinevirtual |
Returns 0. An element of type PQInternalNode does not have a PQLeafKey.
Implements ogdf::PQNode< T, X, Y >.
Definition at line 130 of file PQInternalNode.h.
|
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 177 of file PQInternalNode.h.
|
inlinevirtual |
Sets the variable m_mark.
Implements ogdf::PQNode< T, X, Y >.
Definition at line 180 of file PQInternalNode.h.
|
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 160 of file PQInternalNode.h.
|
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 144 of file PQInternalNode.h.
|
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 192 of file PQInternalNode.h.
|
inlinevirtual |
Sets the variable m_status in the derived class PQInternalNode.
Implements ogdf::PQNode< T, X, Y >.
Definition at line 195 of file PQInternalNode.h.
|
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 202 of file PQInternalNode.h.
|
inlinevirtual |
Sets the variable m_type in the derived class PQInternalNode.
Implements ogdf::PQNode< T, X, Y >.
Definition at line 205 of file PQInternalNode.h.
|
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 213 of file PQInternalNode.h.
|
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 225 of file PQInternalNode.h.
|
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 232 of file PQInternalNode.h.
|
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 239 of file PQInternalNode.h.
