|
|||
|
|
|
|||
|
|
#include <ogdf/internal/planarity/PQNode.h>
Public Member Functions | |
| PQNode (int count, PQNodeKey< T, X, Y > *infoPtr) | |
| PQNode (int count) | |
| virtual | ~PQNode () |
| bool | changeEndmost (PQNode< T, X, Y > *oldEnd, PQNode< T, X, Y > *newEnd) |
| bool | changeSiblings (PQNode< T, X, Y > *oldSib, PQNode< T, X, Y > *newSib) |
| bool | endmostChild () |
| PQNode< T, X, Y > * | getEndmost (PQNode< T, X, Y > *other) const |
| PQNode< T, X, Y > * | getEndmost (int side) const |
| PQNodeKey< T, X, Y > * | getNodeInfo () const |
| Returns the identification number of a node. | |
| PQNode< T, X, Y > * | getSib (int side) const |
| PQNode< T, X, Y > * | getNextSib (PQNode< T, X, Y > *other) const |
| int | identificationNumber () const |
| Returns the identification number of a node. | |
| int | childCount () const |
| Returns the number of children of a node. | |
| void | childCount (int count) |
| Sets the number of children of a node. | |
| PQNode< T, X, Y > * | parent () const |
| PQNode< T, X, Y > * | parent (PQNode< T, X, Y > *newParent) |
| int | parentType () const |
| Returns the type of the parent of a node. | |
| void | parentType (int newParentType) |
| 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) |
| SibDirection | putSibling (PQNode< T, X, Y > *newSib, int preference) |
| 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. | |
| virtual PQLeafKey< T, X, Y > * | getKey () const =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. | |
| virtual PQInternalKey< T, X, Y > * | getInternal () const =0 |
| virtual bool | setInternal (PQInternalKey< T, X, Y > *pointerToInternal)=0 |
| virtual int | mark () const =0 |
| virtual void | mark (int)=0 |
| mark() sets the variable m_mark in the derived class PQLeaf and PQInternalNode. | |
| virtual int | status () const =0 |
| Returns the variable m_status in the derived class PQLeaf and PQInternalNode. | |
| virtual void | status (int)=0 |
| Sets the variable m_status in the derived class PQLeaf and PQInternalNode. | |
| virtual PQNodeType | type () const =0 |
| Returns the variable m_type in the derived class PQLeaf and PQInternalNode. | |
| virtual void | type (PQNodeType)=0 |
| Sets the variable m_type in the derived class PQLeaf and PQInternalNode. | |
Protected Attributes | |
| int | m_childCount |
| Stores the number of children of the node. | |
| int | m_debugTreeNumber |
| int | m_identificationNumber |
| int | 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. | |
| PQNode< T, X, Y > * | m_firstFull |
| Stores a pointer to the first full child of a Q-node. | |
| PQNode< T, X, Y > * | m_leftEndmost |
| PQNode< T, X, Y > * | m_parent |
| PQNode< T, X, Y > * | m_referenceChild |
| PQNode< T, X, Y > * | m_referenceParent |
| PQNode< T, X, Y > * | m_rightEndmost |
| Stores the right endmost child of a Q-node. | |
| PQNode< T, X, Y > * | m_sibLeft |
| PQNode< T, X, Y > * | m_sibRight |
| PQNodeKey< T, X, Y > * | m_pointerToInfo |
| Stores a pointer to the corresponding information of the node. | |
| List< PQNode< T, X, Y > * > * | fullChildren |
| Stores all full children of a node during a reduction. | |
| List< PQNode< T, X, Y > * > * | partialChildren |
| Stores all partial children of a node during a reduction. | |
Friends | |
| class | PQTree< T, X, Y > |
| ogdf::PQNode< T, X, Y >::PQNode | ( | int | count, |
| PQNodeKey< T, X, Y > * | infoPtr | ||
| ) |
| ogdf::PQNode< T, X, Y >::PQNode | ( | int | count | ) |
| virtual ogdf::PQNode< T, X, Y >::~PQNode | ( | ) | [inline, virtual] |
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.
| int ogdf::PQNode< T, X, Y >::childCount | ( | ) | const [inline] |
| void ogdf::PQNode< T, X, Y >::childCount | ( | int | count | ) | [inline] |
| bool ogdf::PQNode< T, X, Y >::endmostChild | ( | ) | [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.
| 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).
| PQNode<T,X,Y>* ogdf::PQNode< T, X, Y >::getEndmost | ( | int | side | ) | const [inline] |
| 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 >, ogdf::PQLeaf< T, X, Y >, and ogdf::EmbedIndicator.
| 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 >, ogdf::PQLeaf< T, X, Y >, and ogdf::EmbedIndicator.
| 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).
| PQNodeKey<T,X,Y>* ogdf::PQNode< T, X, Y >::getNodeInfo | ( | ) | const [inline] |
| PQNode<T,X,Y>* ogdf::PQNode< T, X, Y >::getSib | ( | int | side | ) | const [inline] |
| int ogdf::PQNode< T, X, Y >::identificationNumber | ( | ) | const [inline] |
| virtual int ogdf::PQNode< T, X, Y >::mark | ( | ) | const [pure virtual] |
mark() returns the variable 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::EmbedIndicator.
| virtual void ogdf::PQNode< T, X, Y >::mark | ( | int | ) | [pure virtual] |
mark() sets the variable m_mark in the derived class PQLeaf and PQInternalNode.
Implemented in ogdf::PQInternalNode< T, X, Y >, ogdf::PQLeaf< T, X, Y >, and ogdf::EmbedIndicator.
| PQNode<T,X,Y>* ogdf::PQNode< T, X, Y >::parent | ( | ) | const [inline] |
| 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.
| int ogdf::PQNode< T, X, Y >::parentType | ( | ) | const [inline] |
| void ogdf::PQNode< T, X, Y >::parentType | ( | int | newParentType | ) | [inline] |
| int ogdf::PQNode< T, X, Y >::pertChildCount | ( | ) | const [inline] |
| void ogdf::PQNode< T, X, Y >::pertChildCount | ( | int | count | ) | [inline] |
| 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.
| SibDirection ogdf::PQNode< T, X, Y >::putSibling | ( | PQNode< T, X, Y > * | newSib, |
| int | 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.
| PQNode<T,X,Y>* ogdf::PQNode< T, X, Y >::referenceChild | ( | ) | const [inline] |
| PQNode<T,X,Y>* ogdf::PQNode< T, X, Y >::referenceParent | ( | ) | const [inline] |
| virtual bool ogdf::PQNode< T, X, Y >::setInternal | ( | PQInternalKey< T, X, Y > * | pointerToInternal | ) | [pure virtual] |
Implemented in ogdf::PQInternalNode< T, X, Y >, ogdf::PQLeaf< T, X, Y >, and ogdf::EmbedIndicator.
| 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 >, ogdf::PQLeaf< T, X, Y >, and ogdf::EmbedIndicator.
| bool ogdf::PQNode< T, X, Y >::setNodeInfo | ( | PQNodeKey< T, X, Y > * | pointerToInfo | ) | [inline] |
| virtual int ogdf::PQNode< T, X, Y >::status | ( | ) | const [pure virtual] |
Returns the variable 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::EmbedIndicator.
| virtual void ogdf::PQNode< T, X, Y >::status | ( | int | ) | [pure virtual] |
Sets the variable m_status in the derived class PQLeaf and PQInternalNode.
Implemented in ogdf::PQInternalNode< T, X, Y >, ogdf::PQLeaf< T, X, Y >, and ogdf::EmbedIndicator.
| virtual PQNodeType ogdf::PQNode< T, X, Y >::type | ( | ) | const [pure virtual] |
Returns the variable 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 m_type, since it obviously is of type leaf.
Implemented in ogdf::PQInternalNode< T, X, Y >, ogdf::PQLeaf< T, X, Y >, and ogdf::EmbedIndicator.
| virtual void ogdf::PQNode< T, X, Y >::type | ( | PQNodeType | ) | [pure virtual] |
Sets the variable m_type in the derived class PQLeaf and PQInternalNode.
Implemented in ogdf::PQInternalNode< T, X, Y >, ogdf::PQLeaf< T, X, Y >, and ogdf::EmbedIndicator.
friend class PQTree< T, X, Y > [friend] |
List<PQNode<T,X,Y>*>* ogdf::PQNode< T, X, Y >::fullChildren [protected] |
int ogdf::PQNode< T, X, Y >::m_childCount [protected] |
int ogdf::PQNode< T, X, Y >::m_debugTreeNumber [protected] |
PQNode<T,X,Y>* ogdf::PQNode< T, X, Y >::m_firstFull [protected] |
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.
PQNode<T,X,Y>* ogdf::PQNode< T, X, Y >::m_leftEndmost [protected] |
PQNode<T,X,Y>* ogdf::PQNode< T, X, Y >::m_parent [protected] |
int ogdf::PQNode< T, X, Y >::m_parentType [protected] |
int ogdf::PQNode< T, X, Y >::m_pertChildCount [protected] |
int ogdf::PQNode< T, X, Y >::m_pertLeafCount [protected] |
PQNodeKey<T,X,Y>* ogdf::PQNode< T, X, Y >::m_pointerToInfo [protected] |
PQNode<T,X,Y>* ogdf::PQNode< T, X, Y >::m_referenceChild [protected] |
PQNode<T,X,Y>* ogdf::PQNode< T, X, Y >::m_referenceParent [protected] |
PQNode<T,X,Y>* ogdf::PQNode< T, X, Y >::m_rightEndmost [protected] |
PQNode<T,X,Y>* ogdf::PQNode< T, X, Y >::m_sibLeft [protected] |
PQNode<T,X,Y>* ogdf::PQNode< T, X, Y >::m_sibRight [protected] |
List<PQNode<T,X,Y>*>* ogdf::PQNode< T, X, Y >::partialChildren [protected] |
