|
|||
|
|
|
|||
|
|
#include <ogdf/basic/pqtree/PQNode.h>
Public Member Functions | |
| PQTree () | |
| virtual | ~PQTree () |
| Destructor. More... | |
| bool | addNewLeavesToTree (PQInternalNode< T, X, Y > *father, SListPure< PQLeafKey< T, X, Y > * > &leafKeys) |
| Adds a set of elements to the already existing set of elements of a PQ-tree. More... | |
| virtual void | CleanNode (PQNode< T, X, Y > *) |
| virtual void | Cleanup () |
| Removes the entire PQ-tree. More... | |
| virtual void | clientDefinedEmptyNode (PQNode< T, X, Y > *nodePtr) |
| If the user wishes to use different flags in a derived class of PQTree that are not available in this implementation, he can overload this function to make a valid cleanup of the nodes. More... | |
| virtual void | emptyAllPertinentNodes () |
| Cleans up all flags that have been set in the pertinent nodes during the reduction process. More... | |
| void | emptyNode (PQNode< T, X, Y > *nodePtr) |
| Cleans up all stacks, flags and pointers of a pertinent node that has been visited during the reduction process. More... | |
| virtual void | front (PQNode< T, X, Y > *nodePtr, SListPure< PQLeafKey< T, X, Y > * > &leafKeys) |
Returns the keys stored in the leaves of the front of nodePtr. More... | |
| virtual int | Initialize (SListPure< PQLeafKey< T, X, Y > * > &leafKeys) |
| Initializes the PQ-tree with a set of elements. More... | |
| virtual bool | Reduction (SListPure< PQLeafKey< T, X, Y > * > &leafKeys) |
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. More... | |
| PQNode< T, X, Y > * | root () const |
| Returns a pointer of the root node of the PQTree. More... | |
| void | writeGML (const char *fileName) |
| The function writeGML() prints the PQ-tree in the GML fileformat. More... | |
| void | writeGML (std::ostream &os) |
Protected Member Functions | |
| virtual bool | addNodeToNewParent (PQNode< T, X, Y > *parent, PQNode< T, X, Y > *child) |
Adds a node child as a child to another node specified in parent. More... | |
| virtual bool | addNodeToNewParent (PQNode< T, X, Y > *parent, PQNode< T, X, Y > *child, PQNode< T, X, Y > *leftBrother, PQNode< T, X, Y > *rightBrother) |
Adds a node child to the children of another node specified in parent. More... | |
| virtual bool | Bubble (SListPure< PQLeafKey< T, X, Y > * > &leafKeys) |
| Realizes a function described in [Booth]. More... | |
| virtual bool | checkIfOnlyChild (PQNode< T, X, Y > *child, PQNode< T, X, Y > *parent) |
Checks if child is the only child of parent. More... | |
| virtual PQNode< T, X, Y > * | clientLeftEndmost (PQNode< T, X, Y > *nodePtr) const |
| virtual PQNode< T, X, Y > * | clientNextSib (PQNode< T, X, Y > *nodePtr, PQNode< T, X, Y > *other) const |
| virtual int | clientPrintNodeCategorie (PQNode< T, X, Y > *nodePtr) |
| If the user wishes to use different flags in a derived class of PQTree that are not available in this implementation, he can overload this function. More... | |
| virtual const char * | clientPrintStatus (PQNode< T, X, Y > *nodePtr) |
| If the user wishes to use different status in a derived class of PQTree that are not available in this implementation, he can overload this function. More... | |
| virtual const char * | clientPrintType (PQNode< T, X, Y > *nodePtr) |
| If the user wishes to use different types in a derived class of PQTree that are not available in this implementation, he can overload this function. More... | |
| virtual PQNode< T, X, Y > * | clientRightEndmost (PQNode< T, X, Y > *nodePtr) 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 void | destroyNode (PQNode< T, X, Y > *nodePtr) |
| Marks a node as PQNodeRoot::PQNodeStatus::ToBeDeleted. More... | |
| virtual void | exchangeNodes (PQNode< T, X, Y > *oldNode, PQNode< T, X, Y > *newNode) |
Replaces the oldNode by the newNode in the tree. More... | |
| List< PQNode< T, X, Y > * > * | fullChildren (PQNode< T, X, Y > *nodePtr) |
| virtual void | linkChildrenOfQnode (PQNode< T, X, Y > *installed, PQNode< T, X, Y > *newChild) |
| Links the two endmost children of two different Q-nodes via their sibling pointers together. More... | |
| List< PQNode< T, X, Y > * > * | partialChildren (PQNode< T, X, Y > *nodePtr) |
| virtual bool | Reduce (SListPure< PQLeafKey< T, X, Y > * > &leafKeys) |
| Performs the reduction of the pertinent leaves with the help of the template matchings, designed by Booth and Lueker. More... | |
| virtual void | removeChildFromSiblings (PQNode< T, X, Y > *nodePtr) |
Removes the node nodePtr from the doubly linked list of its parent. More... | |
| virtual int | removeNodeFromTree (PQNode< T, X, Y > *parent, PQNode< T, X, Y > *child) |
The objective is to remove a node child from the PQ-tree. More... | |
| virtual bool | templateL1 (PQNode< T, X, Y > *nodePtr, bool isRoot) |
| Template matching for leaves. More... | |
| virtual bool | templateP1 (PQNode< T, X, Y > *nodePtr, bool isRoot) |
| Template matching for P-nodes with only full children. More... | |
| virtual bool | templateP2 (PQNode< T, X, Y > **nodePtr) |
| Template matching for a P-node with full and empty children that is the root of the pertinent subtree. More... | |
| virtual bool | templateP3 (PQNode< T, X, Y > *nodePtr) |
| Template matching for a P-node with full and empty children that is not the root of the pertinent subtree. More... | |
| virtual bool | templateP4 (PQNode< T, X, Y > **nodePtr) |
| Template matching for a P-node with full, empty and exactly one partial children. More... | |
| virtual bool | templateP5 (PQNode< T, X, Y > *nodePtr) |
| Template matching for a P-node with full, empty children and exactly one partial child. More... | |
| virtual bool | templateP6 (PQNode< T, X, Y > **nodePtr) |
| Template matching for a P-node with full, empty and exactly two partial children. More... | |
| virtual bool | templateQ1 (PQNode< T, X, Y > *nodePtr, bool isRoot) |
| Template matching for Q-nodes with only full children. More... | |
| virtual bool | templateQ2 (PQNode< T, X, Y > *nodePtr, bool isRoot) |
| Template matching for Q-nodes with a pertinent sequence of children on one side of the Q-node. More... | |
| virtual bool | templateQ3 (PQNode< T, X, Y > *nodePtr) |
Protected Attributes | |
| int | m_identificationNumber |
| Stores the total number of nodes that have been allocated. More... | |
| int | m_numberOfLeaves |
| Stores the number of leaves. More... | |
| List< PQNode< T, X, Y > * > * | m_pertinentNodes |
| Stores all nodes that have been marked PQNodeRoot::PQNodeStatus::Full or PQNodeRoot::PQNodeStatus::Partial during a reduction. More... | |
| PQNode< T, X, Y > * | m_pertinentRoot |
| a pointer to the root of the pertinent subtree. More... | |
| PQNode< T, X, Y > * | m_pseudoRoot |
| a pointer to the virtual root of the pertinent subtree, in case that the pertinent root cannot be detected. More... | |
| PQNode< T, X, Y > * | m_root |
| a pointer to the root of the $PQ$-tree. More... | |
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) |
Checks whether all full children of a Q-node nodePtr form a consecutive sequence. More... | |
| void | copyFullChildrenToPartial (PQNode< T, X, Y > *nodePtr, PQNode< T, X, Y > *partialChild) |
Copies all full children of nodePtr to a new P-node The node nodePtr has to be a P-node. More... | |
| PQNode< T, X, Y > * | createNodeAndCopyFullChildren (List< PQNode< T, X, Y > * > *fullNodes) |
Copies the full children of a P-node that are stored in the stack fullNodes to a new P-node. More... | |
| void | removeBlock (PQNode< T, X, Y > *nodePtr, bool isRoot) |
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. More... | |
| void | sortExceptions (int Exceptions[], int arraySize) |
| Sorts the exceptions before frontExcept() scans the frontier. More... | |
| ogdf::PQTree< T, X, Y >::PQTree |
|
inlinevirtual |
| bool ogdf::PQTree< T, X, Y >::addNewLeavesToTree | ( | PQInternalNode< T, X, Y > * | father, |
| SListPure< PQLeafKey< T, X, Y > * > & | leafKeys | ||
| ) |
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.
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.
|
protectedvirtual |
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 overloaded function specifying the future siblings of child.
child to parent, otherwise 0
|
protectedvirtual |
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:
parent is a P-node, than only one sibling is needed in order to enter the child. If the client specifies two siblings in leftBrother and rightBrother, then an arbitrary one is choosen to be a sibling.parent is a Q-node, two siblings must be specified if child has to become an interior child of the Q-node. If just one sibling is specified, this implies that child is about to become a new endmost child of parent. So either leftBrother or rightBrother must store an existing endmost child of parent.parent is a zero pointer, addNodeToNewParents() assumes that child is added as interior child to a Q-node. In this case both siblings of child have to be specified. Observe however, that it is also legal to specify the parent in this case.The above mentioned facts are checked and the process of adding a child to parent is interrupted with an error message returning 0 as soon none of the facts is fulfilled.
child to parent, otherwise 0
|
protectedvirtual |
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.
Reimplemented in ogdf::MaxSequencePQTree< T, Y >, and ogdf::MaxSequencePQTree< edge, bool >.
|
private |
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 this function. 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().
The function is used by the function templateQ2() and templateQ3().
|
protectedvirtual |
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 destroyed.
Before applying the function exchangeNodes(), the function removeChildFromSiblings() is applied. This is useful in case the node parent has some ignored children and has to be reused within some extra algorithmic context.
child was the only child of parent, otherwise 0
|
inlinevirtual |
Reimplemented in ogdf::MaxSequencePQTree< T, Y >, and ogdf::MaxSequencePQTree< edge, bool >.
|
virtual |
Removes the entire PQ-tree.
It is called by the destructor. It scans all nodes of the tree and frees the memory used by the tree. It removes the memory allocated by the following datastructures:
|
inlinevirtual |
If the user wishes to use different flags in a derived class of PQTree that are not available in this implementation, he can overload this function to make a valid cleanup of the nodes.
It will be called per default by the function emptyAllPertinentNodes().
Reimplemented in ogdf::MaxSequencePQTree< T, Y >, and ogdf::MaxSequencePQTree< edge, bool >.
|
inlineprotectedvirtual |
|
inlineprotectedvirtual |
|
protectedvirtual |
If the user wishes to use different flags in a derived class of PQTree that are not available in this implementation, he can overload this function.
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.
|
protectedvirtual |
If the user wishes to use different status in a derived class of PQTree that are not available in this implementation, he can overload this function.
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.
|
protectedvirtual |
If the user wishes to use different types in a derived class of PQTree that are not available in this implementation, he can overload this function.
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.
|
inlineprotectedvirtual |
|
inlineprotectedvirtual |
|
inlineprotectedvirtual |
|
private |
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().
|
private |
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.
This function is used by templateP2(), templateP3() and copyFullChildrenToPartial().
|
inlineprotectedvirtual |
Marks a node as PQNodeRoot::PQNodeStatus::ToBeDeleted.
This enables the function emptyAllPertinentNodes() to remove the node and free its memory.
|
virtual |
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 during the Bubble() phase or when processing one of the templates (see templateL1() to templateQ3()).
This function has to be called after a reduction has been processed.
Reimplemented in ogdf::booth_lueker::EmbedPQTree, ogdf::booth_lueker::PlanarPQTree, ogdf::MaxSequencePQTree< T, Y >, and ogdf::MaxSequencePQTree< edge, bool >.
| void ogdf::PQTree< T, X, Y >::emptyNode | ( | PQNode< T, X, Y > * | nodePtr | ) |
|
protectedvirtual |
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.
|
virtual |
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. Observe that front() uses leafKeys[0] to store the first key.
|
inlineprotected |
|
virtual |
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].
Reimplemented in ogdf::PlanarSubgraphPQTree.
|
protectedvirtual |
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.
|
inlineprotected |
|
protectedvirtual |
Performs 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 it returns 1, then it was succesful in giving each pertinent node in the pertinent subtree a valid parent pointer. If it 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.
|
virtual |
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.
This function gets a list leafKeys of pointers to elements of type PQLeafKey, representing all elements of S.
Reimplemented in ogdf::PlanarSubgraphPQTree.
|
private |
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.
This function 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.
Pointer to the first partial child
|
protectedvirtual |
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.
|
protectedvirtual |
The 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 has to be handled with great care by the user. It is not used in any of the functions of the class template PQTree and can only be accessed by inheritance.
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 nullptr 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:
parent might not be known to parent, hence removeNodeTree() would have to search, at the cost of linear time consumption, for the parent of parent first before removing parent from the tree.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.
|
inline |
|
private |
|
protectedvirtual |
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.
|
protectedvirtual |
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.
|
protectedvirtual |
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.
|
protectedvirtual |
Template matching for a P-node with full and empty children that is not 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, templateP3() considers itself responsible for the node and will apply the template matching P3 to nodePtr. Observe that the user calling this function has to make sure that nodePtr is partial and is not the root of the pertinent subtree.
If templateP3() was responsible for nodePtr and the reduction was successful, the return value is 1. Otherwise the return value is 0.
The function templateP3() creates a new full P-node, stored in newPnode and copies the full children of nodePtr to newPnode. nodePtr keeps all empty children and will be labeled empty. A new partial Q-node will be created and stored in newQnode. newQnode is placed at the position of nodePtr in the tree and gets two children: nodePtr itself and the newly created newPnode.
|
protectedvirtual |
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().
|
protectedvirtual |
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.
|
protectedvirtual |
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.
|
protectedvirtual |
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.
|
protectedvirtual |
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.
|
protectedvirtual |
| void ogdf::PQTree< T, X, Y >::writeGML | ( | const char * | fileName | ) |
The function writeGML() prints the PQ-tree in the GML fileformat.
| void ogdf::PQTree< T, X, Y >::writeGML | ( | std::ostream & | os | ) |
|
protected |
|
protected |
|
protected |
Stores all nodes that have been marked PQNodeRoot::PQNodeStatus::Full or PQNodeRoot::PQNodeStatus::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.
|
protected |
|
protected |
|
protected |