|
|||
|
|
|
|||
|
|
#include <ogdf/internal/planarity/PQTree.h>
Public Member Functions | |
| PQTree () | |
| virtual | ~PQTree () |
| bool | addNewLeavesToTree (PQInternalNode< T, X, Y > *father, SListPure< PQLeafKey< T, X, Y > * > &leafKeys) |
| void | emptyNode (PQNode< T, X, Y > *nodePtr) |
| virtual void | front (PQNode< T, X, Y > *nodePtr, SListPure< PQLeafKey< T, X, Y > * > &leafKeys) |
| virtual void | CleanNode (PQNode< T, X, Y > *) |
| virtual void | Cleanup () |
| virtual void | clientDefinedEmptyNode (PQNode< T, X, Y > *nodePtr) |
| virtual void | emptyAllPertinentNodes () |
| virtual int | Initialize (SListPure< PQLeafKey< T, X, Y > * > &leafKeys) |
| virtual bool | Reduction (SListPure< PQLeafKey< T, X, Y > * > &leafKeys) |
| PQNode< T, X, Y > * | root () const |
| void | writeGML (const char *fileName) |
| void | writeGML (ostream &os) |
Protected Member Functions | |
| virtual bool | Bubble (SListPure< PQLeafKey< T, X, Y > * > &leafKeys) |
| virtual bool | Reduce (SListPure< PQLeafKey< T, X, Y > * > &leafKeys) |
| virtual bool | templateL1 (PQNode< T, X, Y > *nodePtr, bool isRoot) |
| virtual bool | templateP1 (PQNode< T, X, Y > *nodePtr, bool isRoot) |
| virtual bool | templateP2 (PQNode< T, X, Y > **nodePtr) |
| virtual bool | templateP3 (PQNode< T, X, Y > *nodePtr) |
| virtual bool | templateP4 (PQNode< T, X, Y > **nodePtr) |
| virtual bool | templateP5 (PQNode< T, X, Y > *nodePtr) |
| virtual bool | templateP6 (PQNode< T, X, Y > **nodePtr) |
| virtual bool | templateQ1 (PQNode< T, X, Y > *nodePtr, bool isRoot) |
| virtual bool | templateQ2 (PQNode< T, X, Y > *nodePtr, bool isRoot) |
| virtual bool | templateQ3 (PQNode< T, X, Y > *nodePtr) |
| virtual bool | addNodeToNewParent (PQNode< T, X, Y > *parent, PQNode< T, X, Y > *child) |
| virtual bool | addNodeToNewParent (PQNode< T, X, Y > *parent, PQNode< T, X, Y > *child, PQNode< T, X, Y > *leftBrother, PQNode< T, X, Y > *rightBrother) |
| virtual bool | checkIfOnlyChild (PQNode< T, X, Y > *child, PQNode< T, X, Y > *parent) |
| virtual void | destroyNode (PQNode< T, X, Y > *nodePtr) |
| virtual void | exchangeNodes (PQNode< T, X, Y > *oldNode, PQNode< T, X, Y > *newNode) |
| virtual void | linkChildrenOfQnode (PQNode< T, X, Y > *installed, PQNode< T, X, Y > *newChild) |
| virtual void | removeChildFromSiblings (PQNode< T, X, Y > *nodePtr) |
| virtual int | removeNodeFromTree (PQNode< T, X, Y > *parent, PQNode< T, X, Y > *child) |
| List< PQNode< T, X, Y > * > * | fullChildren (PQNode< T, X, Y > *nodePtr) |
| List< PQNode< T, X, Y > * > * | partialChildren (PQNode< T, X, Y > *nodePtr) |
| virtual PQNode< T, X, Y > * | clientLeftEndmost (PQNode< T, X, Y > *nodePtr) const |
| virtual PQNode< T, X, Y > * | clientRightEndmost (PQNode< T, X, Y > *nodePtr) const |
| virtual PQNode< T, X, Y > * | clientNextSib (PQNode< T, X, Y > *nodePtr, PQNode< T, X, Y > *other) const |
| virtual PQNode< T, X, Y > * | clientSibLeft (PQNode< T, X, Y > *nodePtr) const |
| virtual PQNode< T, X, Y > * | clientSibRight (PQNode< T, X, Y > *nodePtr) const |
| virtual int | clientPrintNodeCategorie (PQNode< T, X, Y > *nodePtr) |
| virtual const char * | clientPrintStatus (PQNode< T, X, Y > *nodePtr) |
| virtual const char * | clientPrintType (PQNode< T, X, Y > *nodePtr) |
Protected Attributes | |
| PQNode< T, X, Y > * | m_root |
| is a pointer to the root of the $PQ$-tree. | |
| PQNode< T, X, Y > * | m_pertinentRoot |
| is a pointer to the root of the pertinent subtree. | |
| PQNode< T, X, Y > * | m_pseudoRoot |
| is a pointer to the virtual root of the pertinent subtree, in case that the pertinent root cannot be detected. | |
| int | m_identificationNumber |
| Stores the total number of nodes that have been allocated. | |
| int | m_numberOfLeaves |
| Stores the number of leaves. | |
| List< PQNode< T, X, Y > * > * | m_pertinentNodes |
Private Member Functions | |
| bool | checkChain (PQNode< T, X, Y > *nodePtr, PQNode< T, X, Y > *firstFull, PQNode< T, X, Y > **seqStart, PQNode< T, X, Y > **seqEnd) |
| void | copyFullChildrenToPartial (PQNode< T, X, Y > *nodePtr, PQNode< T, X, Y > *partialChild) |
| PQNode< T, X, Y > * | createNodeAndCopyFullChildren (List< PQNode< T, X, Y > * > *fullNodes) |
| void | printNode (char *filename, int number, PQNode< T, X, Y > *father, PQNode< T, X, Y > *son) |
| void | removeBlock (PQNode< T, X, Y > *nodePtr, bool isRoot) |
| void | sortExceptions (int Exceptions[], int arraySize) |
Definition at line 81 of file PQTree.h.
| ogdf::PQTree< T, X, Y >::PQTree | ( | ) |
| virtual ogdf::PQTree< T, X, Y >::~PQTree | ( | ) | [inline, virtual] |
The function shown here is the destructor of the class template PQTree. In order to free allocated memory, all nodes of the tree have to be deleted, hence their destructors have to be called. This is done in the function Cleanup(). Furthermore all other initialized memory has to be freed which is done as well in the function Cleanup().
| bool ogdf::PQTree< T, X, Y >::addNewLeavesToTree | ( | PQInternalNode< T, X, Y > * | father, | |
| SListPure< PQLeafKey< T, X, Y > * > & | leafKeys | |||
| ) |
The function addNewLeavesToTree() adds a set of elements to the already existing set of elements of a PQ-tree. These elements have to be of type PQLeafKey and are handed to the function in an array leafKeys. The father of the new elements that has to be an existing P- or Q-node, has to be specified and is not allowed to have children.
The above mentioned facts are checked by the function addNodeToNewParent() and the process of adding a child to parent is interrupted with an error message returning 0 as soon none of the facts is fullfilled. The function addNewLeavesToTree() returns 1 if it succeeded in adding the leaves to parent.
Enter the first element as PQLeaf to the [[parent]].
Enter all other elements as leaves to [[parent]].
Set the reference pointers if [[parent]] is a $P$-node.
Set the endmost children if [[parent is a $Q$-node.
| bool ogdf::PQTree< T, X, Y >::addNodeToNewParent | ( | PQNode< T, X, Y > * | parent, | |
| PQNode< T, X, Y > * | child | |||
| ) | [protected, virtual] |
The function addNodeToNewParent() adds a node child as a child to another node specified in parent. The parent of the new node has to be an existing P- or Q-node and is not allowed to have children. In the case, that parent has children, addNewNodeToParent() returns 0 printing an error-message. In this case, use the function addNodeToParent() while specifying the future siblings of child. See addNodeToNewParent2() for more details.
After successfully inserting child to parent the function addNewNodeToParent() returns 1. Otherwise it returns 0.
| bool ogdf::PQTree< T, X, Y >::addNodeToNewParent | ( | PQNode< T, X, Y > * | parent, | |
| PQNode< T, X, Y > * | child, | |||
| PQNode< T, X, Y > * | leftBrother, | |||
| PQNode< T, X, Y > * | rightBrother | |||
| ) | [protected, virtual] |
The function addNodeToNewParent() adds a node child to the children of another node specified in parent. The parent of the new node has to be an existing P- or Q-node and is allowed to have children. In case that parent has children, the siblings of the new introduced child must be specified. If no siblings are specified, the function addNodeToNewParent(PQNode<T,X,Y>*,PQNode<T,X,Y>*) is called by default. If the parent is not specified, the function assumes that child is added as interior child to a Q-node.
The client of this function should observe the following facts:
The above mentioned facts are checked by the function addNodeToNewParent() and the process of adding a child to parent is interrupted with an error message returning 0 as soon none of the facts is fullfilled. The function addNodeToNewParent() returns 1 if it succeeded in adding the child to parent.
| bool ogdf::PQTree< T, X, Y >::Bubble | ( | SListPure< PQLeafKey< T, X, Y > * > & | leafKeys | ) | [protected, virtual] |
The function Bubble() realizes a function described in [Booth]. It bubbles up from the pertinent leaves to the pertinent root in order to make sure that every pertinent node in the pertinent subtree has a valid pointer to its parent. If Bubble() does not succed in doing so, then the set of elements, stored in the leafKeys cannot form a consecutive sequence.
The function Bubble() uses a wide variaty of variables, explained in detail below.
Reimplemented in ogdf::MaxSequencePQTree< T, Y >.
| bool ogdf::PQTree< T, X, Y >::checkChain | ( | PQNode< T, X, Y > * | nodePtr, | |
| PQNode< T, X, Y > * | firstFull, | |||
| PQNode< T, X, Y > ** | seqStart, | |||
| PQNode< T, X, Y > ** | seqEnd | |||
| ) | [private] |
The function checkChain() is used by the function templateQ2() and templateQ3(). It checks whether all full children of a Q-node nodePtr form a consecutive sequence. If the full nodes do so, the procedure returns 1 as a result, otherwise 0.
The pointer firstFull denotes just an arbirtary full child. Starting from this position, checkChain sweeps through the consecutive sequence, halting as soon as a nonfull child is detected. The two pointers seqStart and seqEnd are set within the function checkChain. They denote the first and last node of the consecutive sequence.
The client should observe that it is not possible to avoid the use of such a function. According to the procedure Bubble() children of Q-nodes get unblocked as soon as they are adjacent to any pertinent sibling. This includes that chains of more than two partial children are regarded as unblocked as well. Such chains are of course not reducible and therefore have to be detected by the function checkChain().
Following we give an overview of the variables used in checkChain().
| bool ogdf::PQTree< T, X, Y >::checkIfOnlyChild | ( | PQNode< T, X, Y > * | child, | |
| PQNode< T, X, Y > * | parent | |||
| ) | [protected, virtual] |
The function checkIfOnlyChild() checks if child is the only child of parent. If so, child is connected to its grandparent, as long as parent is not the root of the tree. In case that parent is the root of the tree and child is its only child, the node child becomes the new root of the tree. The parent then is completely removed from the tree and destroyd. The return value of the method checkIfOnlyChild() is 1, if child was the only child of parent. Otherwise the return value is 0. Before applying the function exchangeNodes(), the function removeChildFromSiblings() is applied. This is usefull in case the node parent has some ignored children and has to be reused within some extra algorithmic context.
| virtual void ogdf::PQTree< T, X, Y >::CleanNode | ( | PQNode< T, X, Y > * | ) | [inline, virtual] |
Reimplemented in ogdf::MaxSequencePQTree< T, Y >.
| void ogdf::PQTree< T, X, Y >::Cleanup | ( | ) | [virtual] |
The function Cleanup() removes the entire PQ-tree, stored in the class template PQTree. The function Cleanup() is called by the destructor of the class template PQTree. It scans all nodes of the tree and frees the memory used by the tree. Cleanup() includes the removal of the memory allocated by the following datastructures:
In order to free the allocated memory, all nodes of the tree have to be deleted, hence there destructors are called. In order to achieve this, we start at the root of the tree and go down the tree to the leaves for reaching every node. When a node is processed, (besides the m_root, this will always be the node checkNode) the pointers of all its children are stored in a queue helpqueue and then the processed node is deleted.
The use of a queue helpqueue is a must, since the nodes do not have pointers to all of their children, as the children mostly do not have a pointer to their parent.
It might look weird at the first glance that the function Cleanup() calls the function emptyAllPertinentNodes(), but if some nodes were removed during a reduction, they were stored in the stack m_pertinentNodes. These nodes have to be deleted as well which is provided by the function emptyAllPertinentNodes().
| virtual void ogdf::PQTree< T, X, Y >::clientDefinedEmptyNode | ( | PQNode< T, X, Y > * | nodePtr | ) | [inline, virtual] |
If the user wishes to use different flags in a derived class of PQTree that are not available in this implementation, he can overload the function clientDefinedEmptyNode() in order to make a valid cleanup of the nodes. It will be called per default by the function emptyAllPertinentNodes().
Reimplemented in ogdf::EmbedPQTree, and ogdf::MaxSequencePQTree< T, Y >.
| virtual PQNode<T,X,Y>* ogdf::PQTree< T, X, Y >::clientLeftEndmost | ( | PQNode< T, X, Y > * | nodePtr | ) | const [inline, protected, virtual] |
Reimplemented in ogdf::EmbedPQTree.
| virtual PQNode<T,X,Y>* ogdf::PQTree< T, X, Y >::clientNextSib | ( | PQNode< T, X, Y > * | nodePtr, | |
| PQNode< T, X, Y > * | other | |||
| ) | const [inline, protected, virtual] |
Reimplemented in ogdf::EmbedPQTree.
| int ogdf::PQTree< T, X, Y >::clientPrintNodeCategorie | ( | PQNode< T, X, Y > * | nodePtr | ) | [protected, virtual] |
If the user wishes to use different flags in a derived class of PQTree that are not available in this implementation, he can overload the function clientPrintNodeCategorie(). This function is called per default by the functions printOutCurrentTree() and printNode(). With the help of this function it is possible to influence the layout of the nodes by using new, different lables depicting node categories in the Tree Interface.
| const char * ogdf::PQTree< T, X, Y >::clientPrintStatus | ( | PQNode< T, X, Y > * | nodePtr | ) | [protected, virtual] |
If the user wishes to use different status in a derived class of PQTree that are not available in this implementation, he can overload the function clientPrintStatus(). This function is called per default by the functions printOutCurrentTree() and printNode(). With the help of this function it is possible to influence the information stored at nodes in the Tree Interface that concern the status of a node.
Reimplemented in ogdf::EmbedPQTree.
| const char * ogdf::PQTree< T, X, Y >::clientPrintType | ( | PQNode< T, X, Y > * | nodePtr | ) | [protected, virtual] |
If the user wishes to use different types in a derived class of PQTree that are not available in this implementation, he can overload the function clientPrintType(). This function is called per default by the functions printOutCurrentTree() and printNode(). With the help of this function it is possible to influence the information stored at nodes in the Tree Interface that concern the type of a node.
| virtual PQNode<T,X,Y>* ogdf::PQTree< T, X, Y >::clientRightEndmost | ( | PQNode< T, X, Y > * | nodePtr | ) | const [inline, protected, virtual] |
Reimplemented in ogdf::EmbedPQTree.
| virtual PQNode<T,X,Y>* ogdf::PQTree< T, X, Y >::clientSibLeft | ( | PQNode< T, X, Y > * | nodePtr | ) | const [inline, protected, virtual] |
Reimplemented in ogdf::EmbedPQTree.
| virtual PQNode<T,X,Y>* ogdf::PQTree< T, X, Y >::clientSibRight | ( | PQNode< T, X, Y > * | nodePtr | ) | const [inline, protected, virtual] |
Reimplemented in ogdf::EmbedPQTree.
| void ogdf::PQTree< T, X, Y >::copyFullChildrenToPartial | ( | PQNode< T, X, Y > * | nodePtr, | |
| PQNode< T, X, Y > * | partialChild | |||
| ) | [private] |
The function copyFullChildrenToPartial() copies all full children of nodePtr to a new P-node The node nodePtr has to be a P-node. The new P-node is added to partialChild as an endmost child of partialChild. The node partialChild has to be a Q-node and the new P-node is added to the side of partialChild where the pertinent children are.
The new P-node is allocated by this function and referenced by the variable newNode.
The function copyFullChildrenToPartial() is used by the functions templateP4(), templateP5(), and templateP6().
| PQNode< T, X, Y > * ogdf::PQTree< T, X, Y >::createNodeAndCopyFullChildren | ( | List< PQNode< T, X, Y > * > * | fullNodes | ) | [private] |
The function createNodeAndCopyFullChildren() copies the full children of a P-node that are stored in the stack fullNodes to a new P-node. This new P-node is created by the function and stored in newNode if there is more than one full child. If there is just one full child, it is not necessary to construct a new P-node and the full child is stored in newNode. The newNode is the return value of the procedure.
The function createNodeAndCopyFullChildren() is used by templateP2() templateP3() and the function copyFullChildrenToPartial(). The function createNodeAndCopyFullChildren() uses the following variables.
| virtual void ogdf::PQTree< T, X, Y >::destroyNode | ( | PQNode< T, X, Y > * | nodePtr | ) | [inline, protected, virtual] |
The function destroyNode() marks a node as TO_BE_DELETED. This enables the function emptyAllPertinentNodes() to remove the node and free its memory.
| void ogdf::PQTree< T, X, Y >::emptyAllPertinentNodes | ( | ) | [virtual] |
The function emptyAllPertinentNodes() has to be called after a reduction has been processed. In cleans up all flags that have been set in the pertinent nodes during the reduction process. All pertinent nodes have been stored in the private member stack m_pertinentNodes of the class template PQTree during the Bubble()-phase or when processing one of the templates (see templateL1() to templateQ3()).
Reimplemented in ogdf::EmbedPQTree, ogdf::MaxSequencePQTree< T, Y >, ogdf::PlanarPQTree, and ogdf::MaxSequencePQTree< edge, bool >.
| void ogdf::PQTree< T, X, Y >::emptyNode | ( | PQNode< T, X, Y > * | nodePtr | ) |
The funtion emptyNode() cleans up all stacks, flags and pointers of a pertinent node that has been visited during the reduction process.
| void ogdf::PQTree< T, X, Y >::exchangeNodes | ( | PQNode< T, X, Y > * | oldNode, | |
| PQNode< T, X, Y > * | newNode | |||
| ) | [protected, virtual] |
The function exchangeNodes() replaces the oldNode by the newNode in the tree. This is a function used very often in the template matchings, normally in combination with the construction of a new node which has to conquer the place of an existing node in the tree.
This function can be used in all cases, so the parent of oldNode is allowed to be either a Q-node or a P-node and oldNode may be any child of its parent.
The client should observe, that this function does not reset the pointer m_root. If necessary, this has to be done explicitly by the client himself.
| void ogdf::PQTree< T, X, Y >::front | ( | PQNode< T, X, Y > * | nodePtr, | |
| SListPure< PQLeafKey< T, X, Y > * > & | leafKeys | |||
| ) | [virtual] |
The function front() returns the keys stored in the leaves of the front of nodePtr. A specified node nodePtr of the PQ-tree is handed to the function and front() detects the leaves in the front of this node returning the elements represented by the leaves. These elements are stored in an array of keys named leafKeys. The return value is the numbers of leaves that have been detected. Observe that front() uses leafKeys[0] to store the first key.
| List<PQNode<T,X,Y>*>* ogdf::PQTree< T, X, Y >::fullChildren | ( | PQNode< T, X, Y > * | nodePtr | ) | [inline, protected] |
| int ogdf::PQTree< T, X, Y >::Initialize | ( | SListPure< PQLeafKey< T, X, Y > * > & | leafKeys | ) | [virtual] |
The function Initialize() initializes the PQ-tree with a set of elements. These elements have to be template classes of the class template PQLeafKey and are handed to the function in an array leafKeys. The function constructs the universal PQ-tree. If the numberOfElements > 1, the universal PQ-tree consists of one P-node as root (stored in m_root) and all leaves gathered underneath the P-node, symbolizing all kinds of permutations. If numberOfElements = 1, the universal PQ-tree consists of a single PQLeaf, being the root of the tree.
Observe that the first element has to be stored in leafKeys[0] and the last one in leafKeys[numberOfElements-1]. The function Initialize() returns 1, if the initialization of the PQ-tree was successful.
| void ogdf::PQTree< T, X, Y >::linkChildrenOfQnode | ( | PQNode< T, X, Y > * | installed, | |
| PQNode< T, X, Y > * | newChild | |||
| ) | [protected, virtual] |
The function linkChildrenOfQnode() links the two endmost children of two different Q-nodes via their sibling pointers together. The purpose of doing this is to combine the children of two Q-nodes as children of only one Q-node. This function does not reset the pointers to the endmost children of the Q-node. This has to be done by the client of the function.
| List<PQNode<T,X,Y>*>* ogdf::PQTree< T, X, Y >::partialChildren | ( | PQNode< T, X, Y > * | nodePtr | ) | [inline, protected] |
| void ogdf::PQTree< T, X, Y >::printNode | ( | char * | filename, | |
| int | number, | |||
| PQNode< T, X, Y > * | father, | |||
| PQNode< T, X, Y > * | son | |||
| ) | [private] |
| bool ogdf::PQTree< T, X, Y >::Reduce | ( | SListPure< PQLeafKey< T, X, Y > * > & | leafKeys | ) | [protected, virtual] |
The function Reduce() does the reduction of the pertinent leaves with the help of the template matchings, designed by Booth and Lueker. The reader should observe that this function can only be called after every pertinent node in the pertinent subtree has gotten a valid parent pointer. If this is not the case, the programm will be interrupted by run-time errors such as seqmentation faults. The pertinent nodes can get valid parent pointers by using the function Bubble(). If the function Bubble() returns 1, then it was succesful in giving each pertinent node in the pertinent subtree a valid parent pointer. If the function returns 0, then some nodes do not have a valid parent pointer and the pertinent leaves are not reducable.
The function Reduce() starts with the pertinent leaves and stores them in a queue processNodes. Every time a node is processed, its parent is checked whether all its pertinent children are already processed. If this is the case, the parent is allowed to be processed as well and stored in the queue.
Processing a node means that the function Reduce() tries to apply one of the template matchings. In case that one template matching was successful, the node was reduced and Reduce() tries to reduce the next node. In case that no template matching was successfully applied, the tree is is irreducible. This causes the reduction process to be halted returning 0.
The folllowing variables are used by the function Reduce().
| bool ogdf::PQTree< T, X, Y >::Reduction | ( | SListPure< PQLeafKey< T, X, Y > * > & | leafKeys | ) | [virtual] |
The function Reduction() tests whether permissible permutations of the elements of U exist such that the elements of a subset S of U, stored in leafKeys, form a consecutive sequence. If there exists such a permutation, the PQ-tree is reduced and Reduction() returns 1.
The function Reduction() gets a list of pointers to elements of type PQLeafKey, representing all elements of S.
Reduction() calls the procedure Bubble() and if Bubble() was successful, Reduction() calls the function Reduce().
| void ogdf::PQTree< T, X, Y >::removeBlock | ( | PQNode< T, X, Y > * | nodePtr, | |
| bool | isRoot | |||
| ) | [private] |
This chunk contains the procedure removeBlock. It is used by the functions templateQ2() and templateQ3(). The node nodePtr is expected to be a Q-node with no, one or at most two partial children, such that the partial and full children of nodePtr form a legal consecutive sequence, hence can be reduced.
The function removeBlock() does the following: Of every partial node that is found in the sequence of children of nodePtr, all children are removed from that partial node and included as children of nodePtr, occupying the place of the partial node in the sequence of children of nodePtr. Thereby, removeBlock() takes care, that the newly included full children of nodePtr form a consecutive sequence with the already existing pertinent children of nodePtr. The partial node itself is deleted afterwards.
Pointer to the first partial child
| void ogdf::PQTree< T, X, Y >::removeChildFromSiblings | ( | PQNode< T, X, Y > * | nodePtr | ) | [protected, virtual] |
The function removeChildFromSiblings() removes the node nodePtr from the doubly linked list of its parent. In case that nodePtr is endmost child of an Q-node or child of a P-node equiped with a valid reference pointer referenceParent to its parent (see PQNode), these pointers are considered as well and the adjacent siblings of nodePtr have to cover nodePtr's task.
| int ogdf::PQTree< T, X, Y >::removeNodeFromTree | ( | PQNode< T, X, Y > * | parent, | |
| PQNode< T, X, Y > * | child | |||
| ) | [protected, virtual] |
The function removeNodeFromTree() has to be handled with great care by the user. This function is not used in any of the functions of the class template PQTree and can only be accessed by inheritance.
Its objective is to remove a node child from the PQ-tree. To do so, the parent of the node child has to be known by the user. To indicate this, the parent has to be handed over by her.
This function does not check if parent is the parent node of child. This has to be guaranteed by the user. The reason for this riscfull approach lies in the details of the powerful data structure PQ-tree. In order to reach linear runtime, the internal children of a Q-node normally do not have valid parent pointers. So forcing this function to search the parent would cost in worst case linear runtime for one call of the function removeNodeFromTree(). Its up to the user to do better.
Calling removeNodeFromTree() with a 0-pointer for parent, will always terminate this function with an ERROR-message and returning -1 as value.
The return value is an integer value used to indicate how many children the parent after the removal of child still has. The client should observe that internal nodes in the PQ-tree which have just one or no children at all do not make sense. However, the function removeNodeFromTree() does not check if parent has less than two children after the removal of < child. So in case that parent has less than two children, the user has to check this by herself and remove the parent, probably using the function checkIfOnlyChild().
There are two reasons why the function removeNodeFromTree() does not check if parent has less than two children after the removal of child:
Observe that removeNodeFromTree() does not free the allocated memory of child. This has to be done by the user after calling removeNodeFromTree(). It also offers the opportunity to reuse deleted nodes. Observe that the identification number of a node m_identificationNumber (see PQNode) cannot be changed.
| PQNode<T,X,Y>* ogdf::PQTree< T, X, Y >::root | ( | ) | const [inline] |
| void ogdf::PQTree< T, X, Y >::sortExceptions | ( | int | Exceptions[], | |
| int | arraySize | |||
| ) | [private] |
The function sortExceptions() is only called by the function frontExcept(). It sorts the exceptions before frontExcept() scans the frontier.
| bool ogdf::PQTree< T, X, Y >::templateL1 | ( | PQNode< T, X, Y > * | nodePtr, | |
| bool | isRoot | |||
| ) | [protected, virtual] |
The function templateL1() implements the template matching for leaves. The function requires as input any pointer to a node stored in nodePtr. If the node stored in nodePtr is a PQLeaf, templateL1() considers itself responsible for the node and will apply the template matching for pertinent leaves to nodePtr. If the flag isRoot is set to 1, it signalizes templateL1() that nodePtr is the root of the pertinent subtree. In any other case the flag has to be 0.
If templateL1() was responsible for nodePtr and the reduction was successful, the return value is 1. Otherwise the return value is 0.
The function updates the fullChildren stack of its parent, as long as nodePtr is not the root of the pertinent subtree. Observe that nodePtr needs a valid pointer to its parent. This can be achieved by using the function Bubble() or any other appropriate, user defined function.
| bool ogdf::PQTree< T, X, Y >::templateP1 | ( | PQNode< T, X, Y > * | nodePtr, | |
| bool | isRoot | |||
| ) | [protected, virtual] |
The function templateP1() implements the template matching for P-nodes with only full children. The function requires as input any pointer to a node stored in nodePtr. If the node stored in nodePtr is a P-node with only full children, templateP1() considers itself responsible for the node and will apply the template matching for full P-nodes to nodePtr. If the flag isRoot is set to 1, it signalizes templateP1() that nodePtr is the root of the pertinent subtree. In any other case the flag has to be 0.
If templateP1() was responsible for nodePtr and the reduction was successful, the return value is 1. Otherwise the return value is 0.
If the P-node is not the root of the pertinent subtree, the fullChildren stack of the parent of nodePtr is updated. If the P-node is the root of the pertinent subtree, nothing has to be done.
| bool ogdf::PQTree< T, X, Y >::templateP2 | ( | PQNode< T, X, Y > ** | nodePtr | ) | [protected, virtual] |
The function templateP2() implements the template matching for a P-node with full and empty children that is the root of the pertinent subtree. The function requires as input any pointer to a node stored in \ nodePtr. If the node stored in nodePtr is a P-node with no partial children, templateP2() considers itself responsible for the node and will apply the template matching P2 to nodePtr. Observe that the user calling this function has to make sure that nodePtr is partial and is the root of the pertinent subtree.
If templateP2() was responsible for nodePtr and the reduction was successful, the return value is 1. Otherwise the return value is 0.
The function templateP2() creates a new full P-node that will be the new root of the pertinent subtree. It then copies all full children from nodePtr to the new root of the pertinent subtree.
| bool ogdf::PQTree< T, X, Y >::templateP3 | ( | PQNode< T, X, Y > * | nodePtr | ) | [protected, virtual] |
| bool ogdf::PQTree< T, X, Y >::templateP4 | ( | PQNode< T, X, Y > ** | nodePtr | ) | [protected, virtual] |
The function templateP4() implements the template matching for a P-node with full, empty and exactly one partial children. The P-node has to be the root of the pertinent subtree. The function requires as input any pointer to a node stored in nodePtr. If the node stored in nodePtr is a P-node with one partial child, templateP4() considers itself responsible for the node and will apply the template matching P4 to nodePtr. Observe that the user calling this function has to make sure that nodePtr is the root of the pertinent subtree.
If templateP4() was responsible for nodePtr and the reduction was successful, the return value is 1. Otherwise the return value is 0.
The function templateP4() creates a new full P-node, if neccessary, and copies the full children of nodePtr to this P-node. The new P-node then is made endmost child of partialChild. The node partialChild is used to store the adress of the partial child of nodePtr. The partialChild itself stays child of nodePtr. Most of the here described action is done in the function copyFullChildrenToPartial().
| bool ogdf::PQTree< T, X, Y >::templateP5 | ( | PQNode< T, X, Y > * | nodePtr | ) | [protected, virtual] |
The function templateP5() implements the template matching for a P-node with full, empty children and exactly one partial child. The P-node is not allowed to be the root of the pertinent subtree. The function requires as input any pointer to a node stored in nodePtr. If the node stored in nodePtr is a P-node with one partial child, templateP5() considers itself responsible for the node and will apply the template matching P5 to nodePtr. Observe that the user calling this function has to make sure that nodePtr is not the root of the pertinent subtree.
If templateP5() was responsible for nodePtr and the reduction was successful, the return value is 1. Otherwise the return value is 0.
The function templateP5() uses a few variables.
If neccessary, the function templateP5() creates a new full P-node and copies all full children of nodePtr to this new full P-node. All empty children of nodePtr stay empty children of nodePtr.
The new full P-node and nodePtr will be the new endmost children of partialChild. The partialChild then occupies the position of nodePtr in the PQ-tree.
| bool ogdf::PQTree< T, X, Y >::templateP6 | ( | PQNode< T, X, Y > ** | nodePtr | ) | [protected, virtual] |
The function templateP6() implements the template matching for a P-node with full, empty and exactly two partial children. The P-node must be the root of the pertinent subtree. The function requires as input any pointer to a node stored in nodePtr. If the node stored in nodePtr is a P-node with two partial children, templateP6() considers itself responsible for the node and will apply the template matching P6 to nodePtr. Observe that the user calling this function has to make sure that nodePtr is the root of the pertinent subtree.
If templateP6() was responsible for nodePtr and the reduction was successful, the return value is 1. Otherwise the return value is 0.
The function templateP6() creates, if neccessary, a new full P-node and copies all the full children of nodePtr to the new full P-node, whereas all empty children stay children of nodePtr. The new P-node will be copied to one of the partial children as endmost child of this partial node. The children of the second partial node are copied to the first one, such that the pertinent nodes form a consecutive sequence.
The following variables are used in the function templateP6().
| bool ogdf::PQTree< T, X, Y >::templateQ1 | ( | PQNode< T, X, Y > * | nodePtr, | |
| bool | isRoot | |||
| ) | [protected, virtual] |
The function templateQ1() implements the template matching for Q-nodes with only full children. The function requires as input any pointer to a node stored in nodePtr. If the node stored in nodePtr is a Q-node with only full children, templateQ1() considers itself responsible for the node and will apply the template matching for full Q-nodes to nodePtr. If the flag isRoot is set to 1, it signalizes templateQ1() that nodePtr is the root of the pertinent subtree. In any other case the flag has to be 0.
If templateQ1() was responsible for nodePtr and the reduction was successful, the return value is 1. Otherwise the return value is 0.
Different to the templateP1() for P-nodes, this function is not able to check if Q-node is full by comparing the number of children with the number of full children. The reason is the application of the m_pseudoRoot at certain steps in the matching algorithm. This m_pseudoRoot is used instead of the real root of the pertinent subtree in case that no parent pointer was found. But this implies that changing the number of the children of the pertinent root is not registered by the pertinent root. Hence we are not allowed to use the childCount of Q-nodes.
| bool ogdf::PQTree< T, X, Y >::templateQ2 | ( | PQNode< T, X, Y > * | nodePtr, | |
| bool | isRoot | |||
| ) | [protected, virtual] |
The function templateQ2() implements the template matching for Q-nodes with a pertinent sequence of children on one side of the Q-node. The function requires as input any pointer to a node stored in nodePtr. If the node stored in nodePtr is a Q-node with a pertinent sequence of children on one side of the Q-node, templateQ2() considers itself responsible for the node and will apply the template matching Q2 to nodePtr. If the flag isRoot is set to 1, it signalizes templateQ2() that nodePtr is the root of the pertinent subtree. In any other case the flag has to be 0.
If templateQ2() was responsible for nodePtr and the reduction was successful, the return value is 1. Otherwise the return value is 0.
Below a short description is given of all different cases that may occure and that are handled by the function templateQ2(), regardless whether the Q-node nodePtr is root of the pertinent subtree or not. The description is somewhat trunkated and should be understood as a stenographic description of the labels of the children of nodePtr when running through the children from one side to the other. Of course we leave the mirror-images out.
templateQ2() uses the following variables.
templateQ2() first checks if one of the above mentioned cases occures and then applies the necessary template matching. No special action has to be performed for the full nodes. If there exists a partial child that will be stored in partialChild, its children are made children of nodePtr. So to say, partialChild is lifted up to the Q-node nodePtr and the occurance of the children of partialChild is fixed within the children of nodePtr. (Remember that a partial child is also a Q-node).
| bool ogdf::PQTree< T, X, Y >::templateQ3 | ( | PQNode< T, X, Y > * | nodePtr | ) | [protected, virtual] |
| void ogdf::PQTree< T, X, Y >::writeGML | ( | const char * | fileName | ) |
The function writeGML() prints the PQ-tree in the GML fileformat. The filename is ended by a ".gml" and can be read eg. by the AGD.
| void ogdf::PQTree< T, X, Y >::writeGML | ( | ostream & | os | ) |
int ogdf::PQTree< T, X, Y >::m_identificationNumber [protected] |
int ogdf::PQTree< T, X, Y >::m_numberOfLeaves [protected] |
List<PQNode<T,X,Y>*>* ogdf::PQTree< T, X, Y >::m_pertinentNodes [protected] |
Stores all nodes that have been marked FULL or PARTIAL during a reduction. After the reduction has been finished succesfully, all pertinent nodes are reinitialized and prepared for the next reduction. This list also contains pertinent nodes that have been removed during a reduction. When detected in the stack, their memory is freed.
PQNode<T,X,Y>* ogdf::PQTree< T, X, Y >::m_pertinentRoot [protected] |
PQNode<T,X,Y>* ogdf::PQTree< T, X, Y >::m_pseudoRoot [protected] |
PQNode<T,X,Y>* ogdf::PQTree< T, X, Y >::m_root [protected] |
