|
|||
|
|
|
|||
|
|
The class template PQBasicKey is an abstract base class. More...
#include <ogdf/basic/pqtree/PQNode.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. | |
| 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. | |
| 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. | |
| 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. | |
| 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. | |
| virtual PQNodeMark | mark () const =0 |
| mark() returns the variable PQLeaf::m_mark in the derived class PQLeaf and PQInternalNode. | |
| virtual void | mark (PQNodeMark)=0 |
| mark() sets the variable PQLeaf::m_mark in the derived class PQLeaf and PQInternalNode. | |
| 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. | |
| 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. | |
| bool | setNodeInfo (PQNodeKey< T, X, Y > *pointerToInfo) |
Sets the pointer m_pointerToInfo to the specified adress of pointerToInfo. | |
| virtual PQNodeStatus | status () const =0 |
| Returns the variable PQLeaf::m_status in the derived class PQLeaf and PQInternalNode. | |
| virtual void | status (PQNodeStatus)=0 |
| Sets the variable PQLeaf::m_status in the derived class PQLeaf and PQInternalNode. | |
| virtual PQNodeType | type () const =0 |
| Returns the variable PQInternalNode::m_type in the derived class PQLeaf and PQInternalNode. | |
| virtual void | type (PQNodeType)=0 |
| Sets the variable PQInternalNode::m_type in the derived class PQLeaf and PQInternalNode. | |
| Public Member Functions inherited from ogdf::PQNodeRoot | |
| PQNodeRoot () | |
| virtual | ~PQNodeRoot () |
Protected Attributes | |
| 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. | |
Friends | |
| class | PQTree< T, X, Y > |
| All members and member function of PQNode are needed by the class template PQTree. | |
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 } |
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.
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.
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.
| 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.
|
explicit |
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.
| 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.
| 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.
|
inline |
|
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.
|
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).
|
inline |
|
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 >, ogdf::PQLeaf< T, X, Y >, and ogdf::booth_lueker::EmbedIndicator.
|
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 >, ogdf::PQLeaf< T, X, Y >, and ogdf::booth_lueker::EmbedIndicator.
|
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).
|
inline |
|
inline |
|
inline |
|
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 >, ogdf::PQLeaf< T, X, Y >, and ogdf::booth_lueker::EmbedIndicator.
|
pure virtual |
mark() sets the variable PQLeaf::m_mark in the derived class PQLeaf and PQInternalNode.
Implemented in ogdf::booth_lueker::EmbedIndicator, ogdf::PQInternalNode< T, X, Y >, and ogdf::PQLeaf< T, X, Y >.
|
inline |
|
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.
|
inline |
|
inline |
|
inline |
|
inline |
|
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.
|
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.
|
inline |
|
inline |
|
pure virtual |
Implemented in ogdf::PQInternalNode< T, X, Y >, and ogdf::PQLeaf< T, X, Y >.
|
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 >.
|
inline |
Sets the pointer m_pointerToInfo to the specified adress of pointerToInfo.
|
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 >, ogdf::PQLeaf< T, X, Y >, and ogdf::booth_lueker::EmbedIndicator.
|
pure virtual |
Sets the variable PQLeaf::m_status in the derived class PQLeaf and PQInternalNode.
Implemented in ogdf::PQInternalNode< T, X, Y >, ogdf::PQLeaf< T, X, Y >, and ogdf::booth_lueker::EmbedIndicator.
|
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 >, ogdf::PQLeaf< T, X, Y >, and ogdf::booth_lueker::EmbedIndicator.
|
pure virtual |
Sets the variable PQInternalNode::m_type in the derived class PQLeaf and PQInternalNode.
Implemented in ogdf::PQInternalNode< T, X, Y >, ogdf::PQLeaf< T, X, Y >, and ogdf::booth_lueker::EmbedIndicator.
|
protected |
|
protected |
|
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.
|
protected |
|
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.
|
protected |
|
protected |
|
protected |
|
protected |
|
protected |
|
protected |
|
protected |
|
protected |
|
protected |
|
protected |
|
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.
|
protected |
