|
|||
|
|
|
|||
|
|
#include <ogdf/internal/planarity/PQInternalNode.h>
Public Member Functions | |
| PQInternalNode (int count, int typ, int stat, PQInternalKey< T, X, Y > *internalPtr, PQNodeKey< T, X, Y > *infoPtr) | |
| PQInternalNode (int count, int typ, int stat, PQInternalKey< T, X, Y > *internalPtr) | |
| PQInternalNode (int count, int typ, int stat, PQNodeKey< T, X, Y > *infoPtr) | |
| PQInternalNode (int count, PQNodeRoot::PQNodeType typ, int stat) | |
| ~PQInternalNode () | |
| virtual PQLeafKey< T, X, Y > * | getKey () const |
| Returns 0. An element of type PQInternalNode does not have a PQLeafKey. | |
| virtual bool | setKey (PQLeafKey< T, X, Y > *pointerToKey) |
| virtual PQInternalKey< T, X, Y > * | getInternal () const |
| Returns a pointer to the PQInternalKey information. | |
| virtual bool | setInternal (PQInternalKey< T, X, Y > *pointerToInternal) |
| virtual int | mark () const |
| Returns the variable \ m_mark. | |
| virtual void | mark (int m) |
| Sets the variable \ m_mark. | |
| virtual int | status () const |
| Returns the variable m_status in the derived class PQInternalNode. | |
| virtual void | status (int 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. | |
Private Attributes | |
| int | m_mark |
| PQInternalKey< T, X, Y > * | m_pointerToInternal |
| int | m_status |
| PQNodeRoot::PQNodeType | m_type |
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 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 m_nodePointer (see basicKey) of this element of type PQInternalKey to the newly allocated PQInternalNode.
Definition at line 97 of file PQInternalNode.h.
| ogdf::PQInternalNode< T, X, Y >::PQInternalNode | ( | int | count, |
| int | typ, | ||
| int | stat, | ||
| PQInternalKey< T, X, Y > * | internalPtr, | ||
| PQNodeKey< T, X, Y > * | infoPtr | ||
| ) | [inline] |
Definition at line 101 of file PQInternalNode.h.
| ogdf::PQInternalNode< T, X, Y >::PQInternalNode | ( | int | count, |
| int | typ, | ||
| int | stat, | ||
| PQInternalKey< T, X, Y > * | internalPtr | ||
| ) | [inline] |
Definition at line 117 of file PQInternalNode.h.
| ogdf::PQInternalNode< T, X, Y >::PQInternalNode | ( | int | count, |
| int | typ, | ||
| int | stat, | ||
| PQNodeKey< T, X, Y > * | infoPtr | ||
| ) | [inline] |
Definition at line 131 of file PQInternalNode.h.
| ogdf::PQInternalNode< T, X, Y >::PQInternalNode | ( | int | count, |
| PQNodeRoot::PQNodeType | typ, | ||
| int | stat | ||
| ) | [inline] |
Definition at line 144 of file PQInternalNode.h.
| 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 168 of file PQInternalNode.h.
| virtual PQInternalKey<T,X,Y>* ogdf::PQInternalNode< T, X, Y >::getInternal | ( | ) | const [inline, virtual] |
Returns a pointer to the PQInternalKey information.
Implements ogdf::PQNode< T, X, Y >.
Definition at line 192 of file PQInternalNode.h.
| virtual PQLeafKey<T,X,Y>* ogdf::PQInternalNode< T, X, Y >::getKey | ( | ) | const [inline, virtual] |
Returns 0. An element of type PQInternalNode does not have a PQLeafKey.
Implements ogdf::PQNode< T, X, Y >.
Definition at line 172 of file PQInternalNode.h.
| virtual int ogdf::PQInternalNode< T, X, Y >::mark | ( | ) | const [inline, virtual] |
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 224 of file PQInternalNode.h.
| virtual void ogdf::PQInternalNode< T, X, Y >::mark | ( | int | m | ) | [inline, virtual] |
Sets the variable \ m_mark.
Implements ogdf::PQNode< T, X, Y >.
Definition at line 227 of file PQInternalNode.h.
| virtual bool ogdf::PQInternalNode< T, X, Y >::setInternal | ( | PQInternalKey< T, X, Y > * | pointerToInternal | ) | [inline, virtual] |
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 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 205 of file PQInternalNode.h.
| virtual bool ogdf::PQInternalNode< T, X, Y >::setKey | ( | PQLeafKey< T, X, Y > * | pointerToKey | ) | [inline, virtual] |
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 186 of file PQInternalNode.h.
| virtual int ogdf::PQInternalNode< T, X, Y >::status | ( | ) | const [inline, virtual] |
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 239 of file PQInternalNode.h.
| virtual void ogdf::PQInternalNode< T, X, Y >::status | ( | int | s | ) | [inline, virtual] |
Sets the variable m_status in the derived class PQInternalNode.
Implements ogdf::PQNode< T, X, Y >.
Definition at line 242 of file PQInternalNode.h.
| virtual PQNodeRoot::PQNodeType ogdf::PQInternalNode< T, X, Y >::type | ( | ) | const [inline, virtual] |
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 249 of file PQInternalNode.h.
| virtual void ogdf::PQInternalNode< T, X, Y >::type | ( | PQNodeRoot::PQNodeType | t | ) | [inline, virtual] |
Sets the variable m_type in the derived class PQInternalNode.
Implements ogdf::PQNode< T, X, Y >.
Definition at line 252 of file PQInternalNode.h.
int 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 261 of file PQInternalNode.h.
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 273 of file PQInternalNode.h.
int 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 280 of file PQInternalNode.h.
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 287 of file PQInternalNode.h.
