|
|||
|
|
|
|||
|
|
#include <ogdf/internal/planarity/MaxSequencePQTree.h>
Public Member Functions | |
| MaxSequencePQTree () | |
| ~MaxSequencePQTree () | |
| virtual void | CleanNode (PQNode< T, whaInfo *, Y > *nodePtr) |
| Frees the memory of the information PQNodeInfo of a node. | |
| virtual void | clientDefinedEmptyNode (PQNode< T, whaInfo *, Y > *nodePtr) |
| Does a clean up of a node. Called by emptyAllPertinentNodes. | |
| virtual void | emptyAllPertinentNodes () |
| Does a clean up after a reduction. | |
| int | determineMinRemoveSequence (SListPure< PQLeafKey< T, whaInfo *, Y > * > &leafKeys, SList< PQLeafKey< T, whaInfo *, Y > * > &eliminatedKeys) |
Protected Member Functions | |
| virtual bool | Bubble (SListPure< PQLeafKey< T, whaInfo *, Y > * > &leafKeys) |
| Overloaded function Bubble() of the base class PQTree. | |
| PQNode< T, whaInfo *, Y > * | GetParent (PQNode< T, whaInfo *, Y > *nodePtr) |
| Function that computes for a node its valid parent in the PQTree. | |
Protected Attributes | |
| SListPure< PQNode< T, whaInfo *, Y > * > | cleanUp |
| SListPure< PQNode< edge, whaInfo *, bool > * > | eliminatedNodes |
Private Member Functions | |
| void | findMinWHASequence (StackPure< PQNode< T, whaInfo *, Y > * > &archiv, SList< PQLeafKey< T, whaInfo *, Y > * > &eliminatedKeys) |
| int | setHchild (PQNode< T, whaInfo *, Y > *h_child1) |
| int | setAchildren (PQNode< T, whaInfo *, Y > *hChild2, PQNode< T, whaInfo *, Y > *hChild2Sib) |
| void | markPertinentChildren (PQNode< T, whaInfo *, Y > *nodePtr, int label, int del_typ) |
| void | haNumPnode (PQNode< T, whaInfo *, Y > *nodePtr) |
| void | haNumQnode (PQNode< T, whaInfo *, Y > *nodePtr) |
| void | aNumQnode (PQNode< T, whaInfo *, Y > *nodePtr, int sumAllW) |
| Computes the a-number for function haNumQnode(). | |
| void | hNumQnode (PQNode< T, whaInfo *, Y > *nodePtr, int sumAllW) |
| Computes the h-number for function haNumQnode(). | |
| int | alpha1beta1Number (PQNode< T, whaInfo *, Y > *nodePtr, PQNode< T, whaInfo *, Y > **aChild) |
| int | sumPertChild (PQNode< T, whaInfo *, Y > *nodePtr) |
The class template MaxSequencePQTree is designed to compute a maximal consecutive sequence of pertinent leaves in a PQ-tree. In order to achieve this goal, the class template MaxSequencePQTree is a derived class form the class template PQTree. We assume that the reader is familiar with the data structure of a PQ-Tree and therefore give only a very brief overview of the functionality of this data structure.
The PQ-Tree is a tool to represent the permutations of a set U in which various subsets of U occur consecutively. More precisely, the PQ-tree together with a package of efficient algorithms, all included in this template class PQTree, finds permissible permutations on the set U. The permissible permutations are those, in which certain subsets S of U occur as consecutive subsets. A PQ-tree represents an equivalence class of permissible permutations and as the elements of any subset S are constraint to appear together, the number of permissible permutations is reduced. The corresponding PQ-tree operation is called reduction with respect to S.
In case that a set S of U of pertinent elements is not reducible, it might be a necessary to compute a maximal subset S' of S deleting the elements of S - S' from the PQ-tree such that the elements of S' are reducible in the PQ-tree. The class template MaxSequencePQTree provides the user the functionality of computing a subset S'. In fact, MaxSequencePQTree depicts the user the elements of S - S'$ that have to be deleted in order to get a reducible PQ-tree. However, the class template MaxSequencePQTree does not delete the elements of S - S'. It is up the client using this class to manage the deletion of S - S'.
All computation done by this class to obtain a maximal pertinent sequence is done according to the rules presented in [Jayakumar, Thulasiraman, Swamy, 1989]. For detailed information about the computation, we refer kindly to the authors paper.
The declaration of the template class MaxSequencePQTree. The formal parameter T represents the user defined type of an element in the above mentioned set U. The formal parameter Y represents the user defined type of the information only available for internal nodes PQInternalKey The formal parameter X of the base class template PQTree was designed to hold the general node information PQNodeKey available at every node of the tree. The class template MaxSequencePQTree defines this parameter to be of type whaInfo. This allows the class template to store informations needed during the computation of a maximal pertinent sequence at every node.
Definition at line 146 of file MaxSequencePQTree.h.
| ogdf::MaxSequencePQTree< T, Y >::MaxSequencePQTree | ( | ) | [inline] |
Definition at line 150 of file MaxSequencePQTree.h.
| ogdf::MaxSequencePQTree< T, Y >::~MaxSequencePQTree | ( | ) | [inline] |
Definition at line 152 of file MaxSequencePQTree.h.
| int ogdf::MaxSequencePQTree< T, Y >::alpha1beta1Number | ( | PQNode< T, whaInfo *, Y > * | nodePtr, | |
| PQNode< T, whaInfo *, Y > ** | aChild | |||
| ) | [private] |
alpha1beta1Number() returns alpha_1 = = sum {i in P(nodePtr)} w_i - max_{i in P(nodePtr)} {(w_i = a_i)}, where P(nodePtr) denotes the set of all pertinent children of the node nodePtr regardless whether nodePtr is a P- or a Q-node. Depicts the a-number if just one child of nodePtr is made $a$-node. This child is returned by the function alpha1beta1Number() using the pointer aChild.
The function alpha1beta1Number() returns alpha_1 = beta_1 = sum_{i in P(nodePtr)} w_i - max_{i in P(nodePtr)}{(w_i = a_i)}, where $P(nodePtr) denotes the set of all pertinent children of the node nodePtr regardless whether nodePtr is a P- or a Q-node. Depicts the a-number if just one child of nodePtr is made a-node. This child is returned by the function alpha1beta1Number() using the pointer aChild.
The function uses the following variables.
The function uses two while loops over the parial and the full children of nodePtr. It hereby computes the values w and max_{i in P(nodePtr}{(w_i = a_i)}. After finishing the while loops, the function alpha1beta1Number() returns the numbers alpha_1 = beta_1 and the aChild.
Definition at line 1809 of file MaxSequencePQTree.h.
| void ogdf::MaxSequencePQTree< T, Y >::aNumQnode | ( | PQNode< T, whaInfo *, Y > * | nodePtr, | |
| int | sumAllW | |||
| ) | [private] |
Computes the a-number for function haNumQnode().
The procedure aNumQnode() computes the a-number of the partial Q-node nodePtr. The procedure furthermore sets the children aChild, hChild1 and hChild2 of the node information class whaInfo* of nodePtr.
It Checks for consecutive sequences between all children of the Q-node nodePtr. The children which form a consecutive sequence are stored in a stack called sequence that is emptied, as soon as the end of the sequence is reached. When the stack is emptied, we count for the pertinent leaves in the front of the sequence, and update if necessary the sequence holding the maximum number of pertinent leaves in its frontier.
Observe that if the sequence ends with a partial node, this node may form a consecutive sequence with its other siblings. Hence the partial node is pushed back onto the stack sequence after the stack has been emptied.
This chunk uses a number of extra variables that are explained below.
Definition at line 1542 of file MaxSequencePQTree.h.
| bool ogdf::MaxSequencePQTree< T, Y >::Bubble | ( | SListPure< PQLeafKey< T, whaInfo *, Y > * > & | leafKeys | ) | [protected, virtual] |
Overloaded function Bubble() of the base class PQTree.
This Bubble() ensures that every node in the pertinent subtree has a valid parent pointer. (Different to the original Bubble() that only tests if every node has a valid parent pointer).
The function Bubble() is an overloaded function of the base template class PQTree. This overloaded version of Bubble() covers several task.
The function Bubble() needs the following input:
| redNumber | is an integer value depicting the current iteration of the template matching algorithm. Onlyu needed for debugging purposes. | |
| leafKeys | is a SListPure to the PQleafKey's of the pertinent leaves. |
Reimplemented from ogdf::PQTree< T, whaInfo *, Y >.
Definition at line 312 of file MaxSequencePQTree.h.
| void ogdf::MaxSequencePQTree< T, Y >::CleanNode | ( | PQNode< T, whaInfo *, Y > * | nodePtr | ) | [virtual] |
Frees the memory of the information PQNodeInfo of a node.
Called by emptyAllPertinentNodes() or the destructor.
CleanNode() frees the memory allocated for the node information class of a node in the PQTree. It is an overloaded function of PQTree and called before deallocating the memory of the node nodePtr.
Reimplemented from ogdf::PQTree< T, whaInfo *, Y >.
Definition at line 430 of file MaxSequencePQTree.h.
| void ogdf::MaxSequencePQTree< T, Y >::clientDefinedEmptyNode | ( | PQNode< T, whaInfo *, Y > * | nodePtr | ) | [virtual] |
Does a clean up of a node. Called by emptyAllPertinentNodes.
The function clientDefinedEmptyNode() is the overloaded virtual function of the template base class PQTree called by default by the function emptyAllPertinentNodes() of PQTree. The overloaded function handles the different labels used during the computation and reduction of the maximal pertinent sequence.
Reimplemented from ogdf::PQTree< T, whaInfo *, Y >.
Definition at line 451 of file MaxSequencePQTree.h.
| int ogdf::MaxSequencePQTree< T, Y >::determineMinRemoveSequence | ( | SListPure< PQLeafKey< T, whaInfo *, Y > * > & | leafKeys, | |
| SList< PQLeafKey< T, whaInfo *, Y > * > & | eliminatedKeys | |||
| ) |
determineMinRemoveSequence() computes the maximal pertinent sequence S' of elements of the set S, that can be reduced in a PQ-tree. The set S is stored in an SListPure of type PQLeafKey* called leafKeys. The elements of S - S' are returned in an SList eliminatedKeys. The return value of the function is |S - S'|.
The function determineMinRemoveSequence() computes the maximal pertinent sequence S' of elements of the set S, that can be reduced in a PQ-tree. The function expects the set S stored in an SListPure<PQLeafKey*> called leafKeys. Since the elements of S - S' have to be removed from the PQ-tree by the client, the function determineMinRemoveSequence() returns the elements of S - S' in an array of type PQLeafKey** called EliminatedElements. The return value of the function is |S - S'|.
In order to compute the maximal pertinent sequence the function determineMinRemoveSequence() computes the [w,h,a]-number of every pertinent node in the pertinent subtree of the PQ-tree. If the minimum of the h- and a-number of the root of the pertinent subtree is not 0, then the PQ-tree is not reducible. According to the [w,h,a]-numbering, this procedure computes a minimal number of pertinent leaves that have to be removed from of the PQ-tree to gain reducibility.
The user should observe that removing the leaves from the PQ-tree, depicted by the pointers to their information class stored in EliminatedElements is a necessary but not sufficient action to gain reducibility. The client calling this function has to make sure that nodes, where the complete frontier has been removed during the process must be removed as well. This can easily be done using functions of the base class PQTree such as checkIfOnlyChild().
Definition at line 576 of file MaxSequencePQTree.h.
| void ogdf::MaxSequencePQTree< T, Y >::emptyAllPertinentNodes | ( | ) | [virtual] |
Does a clean up after a reduction.
The function emptyAllPertinentNodes() is the overloaded virtual function of the template base class PQTree. This function handles all necessary cleanup after the computation of the maximal pertinent sequence and the reduction of the maximal pertinent sequence and frees the memory of all nodes that are no longer in the PQ-tree.
Most nodes that are regarded for deletion are marked with the status TO_BE_DELETED. This causes a valid removal by the function PQTree<X,whaInfo*,Y>::emptyAllPertinentNodes() if the node is contained in the stack pertinentNodes of the base template class. Otherwise, the function emptyAllPertinentNodes() has to remove the nodes directly from the tree.
The function emptyAllPertinentNodes() differs the following nodes by their labels or status.
The function emptyAllPertinentNodes() handles another important fact. During the reduction of the maximal pertinent sequence, PARTIAL nodes have been introduced into the PQ-tree, that do not have a node information. The function emptyAllPertinentNodes() detects these nodes equipping them with the container class of type pqNodeKey.
Reimplemented from ogdf::PQTree< T, whaInfo *, Y >.
Definition at line 481 of file MaxSequencePQTree.h.
| void ogdf::MaxSequencePQTree< T, Y >::findMinWHASequence | ( | StackPure< PQNode< T, whaInfo *, Y > * > & | archiv, | |
| SList< PQLeafKey< T, whaInfo *, Y > * > & | eliminatedKeys | |||
| ) | [private] |
findMinWHASequence() is called by the procedure determineMinRemoveSequence(). It checks the [w,h,a]-number of the pertinent root. In case that the min{a,h} = 0, where a, h belong to the pertinent root, the PQ-tree is reducible and nothing needs to be done. In case that min{a,h} > 0, a min{a,h} number of leaves have to be removed from the tree in order to achieve reducibility for the set S. The leaves that have to be removed are returend in the SList eliminatedKeys.
The procedure findMinWHASequence() is called by the procedure determineMinRemoveSequence(). It checks the [w,h,a]-number of the pertinent root. In case that the min{a,h} = 0, where a, h belong to the pertinent root, the PQ-tree is reducible and nothing needs to be done. In case that min{a,h} > 0, a min{a,h} number of leaves have to be removed from the tree in order to achieve reducibility for the set S.
Knowing precisely the [w,h,a] number of every pertinent node, this can be achieved in a top down manner, according to the rules presented in Jayakumar et al. The procedure findMinWHASequence() implements this using the stack of nodes called archiv. This archiv contains all pertinent nodes. Since parents have been stored on top of their children in the stack which supports the top down method of the procedure.
Function findMinWHASequence() returns an SList eliminatedKeys of pointers to PQLeafKey, describing the leaves that have to be removed.
Definition at line 753 of file MaxSequencePQTree.h.
| PQNode< T, whaInfo *, Y > * ogdf::MaxSequencePQTree< T, Y >::GetParent | ( | PQNode< T, whaInfo *, Y > * | nodePtr | ) | [protected] |
Function that computes for a node its valid parent in the PQTree.
The function GetParent() computes for the node nodePtr its parent. The parent pointer is needed during the Bubble() phase.
In case that nodePtr has not a valid pointer to its parent, it points to a node that is not contained in the tree anymore. Since we do not free the memory of such nodes, using the parent pointer of nodePtr does not cause runtime errors. The previous parent of nodePtr itself is marked as ELIMINATED, denoting a node, that has been removed from the tree. Since such a nodePtr with a non valid parent pointer can only appear somewhere between the children of a Q-node, the function GetParent() sweeps through the siblings of nodePtr to get a valid parent pointer from the endmost child, thereby updating the parent pointers of all the siblings between the endmost child and nodePtr. Since the number of children of Q-nodes corresponds to the number of cutvertices in the bushform, the total number of children updated by GetParent() is in O(n) for every call of Bubble(). Hence the complexity of the update procedure is bounded by O(n^2).
Definition at line 1914 of file MaxSequencePQTree.h.
| void ogdf::MaxSequencePQTree< T, Y >::haNumPnode | ( | PQNode< T, whaInfo *, Y > * | nodePtr | ) | [private] |
haNumPnode() computes the h- and a-number of a P-node nodePtr.
The procedure haNumPnode() computes the h- and a-number of a P-node nodePtr.
The procedure haNumPnode uses the following variables.
Definition at line 1256 of file MaxSequencePQTree.h.
| void ogdf::MaxSequencePQTree< T, Y >::haNumQnode | ( | PQNode< T, whaInfo *, Y > * | nodePtr | ) | [private] |
haNumQnode() computes the h- and a-number of the partial Q-node nodePtr. The procedure furthermore sets the children aChild, hChild1 and hChild2 of the node information class whaInfo of nodePtr.
The procedure haNumQnode() computes the h- and a-number of the partial Q-node nodePtr. The procedure furthermore sets the children aChild, hChild1 and hChild2 of the node information class whaInfo* of nodePtr.
The procedure uses the following variables.
Definition at line 1368 of file MaxSequencePQTree.h.
| void ogdf::MaxSequencePQTree< T, Y >::hNumQnode | ( | PQNode< T, whaInfo *, Y > * | nodePtr, | |
| int | sumAllW | |||
| ) | [private] |
Computes the h-number for function haNumQnode().
The procedure hNumQnode() computes the h-number of the partial Q-node nodePtr. The procedure furthermore sets the child hChild1 of the node information class whaInfo* of nodePtr.
The procedure uses the following variables.
Definition at line 1394 of file MaxSequencePQTree.h.
| void ogdf::MaxSequencePQTree< T, Y >::markPertinentChildren | ( | PQNode< T, whaInfo *, Y > * | nodePtr, | |
| int | label, | |||
| int | del_typ | |||
| ) | [private] |
markPertinentChildren() marks all full and/or partial children of nodePtr either as a-, b-, h- or w-node. The parameter label describes which children have to be marked. The label can be either FULL, PARTIAL or PERTINENT. The deleteTyp can be either W_TYPE, B_TYPE, H_TYPE or A_TYPE.
The procedure markPertinentChildren() makes all full and/or partial children of nodePtr either an a-, b-, h- or w-node. The parameter label describes which children have to be marked. The label can be either FULL, PARTIAL or PERTINENT. The deleteTyp can be either W_TYPE, B_TYPE, H_TYPE or A_TYPE (see also MaxSequencePQTree.
The function markPertinentChildren() uses just a pointer currentNode for tracing the pertinent children of nodePtr.
Definition at line 1207 of file MaxSequencePQTree.h.
| int ogdf::MaxSequencePQTree< T, Y >::setAchildren | ( | PQNode< T, whaInfo *, Y > * | hChild2, | |
| PQNode< T, whaInfo *, Y > * | hChild2Sib | |||
| ) | [private] |
setAchildren() traces all children of the largest consecutive sequence of pertinent children of a Q-node. Notice, that it does not mark a single node as a-node, but a sequence of full children with possible a partial child at each end as b-nodes, respectively as h-nodes.
The function setAchildren() traces all children of the largest consecutive sequence of pertinent children of a Q-node. Notice, that it does not mark a single node as a-node, but a sequence of full children with possible a partial child at each end as b-nodes, respectively as h-nodes.
The function setAchildren() needs the first node of the sequence denoted by the pointer hChild2 and its pertinent sibling denoted by hChild2Sib. The latter pointer allows immediate scanning of the sequence.
The return value of the function setAchildren() is the number of pertinent children of the Q-node according to the [w,h,a]-numbering.
The function setAchildren() uses the following variables.
Definition at line 1103 of file MaxSequencePQTree.h.
| int ogdf::MaxSequencePQTree< T, Y >::setHchild | ( | PQNode< T, whaInfo *, Y > * | h_child1 | ) | [private] |
setHchild() processes the children of a Q-node, marking a full sequence of children with at most one incident partial child on one side of the Q-node, as b-nodes respectively as h-node. The pointer h_child1 depicts the endmost child of the Q-node, where the sequence starts. The function gets the h_child1 of the Q-node. Its return value is the number of pertinent children, corresponding the [w,h,a]-numbering.
The function setHchild() processes the children of a Q-node, marking a full sequence of children with at most incident partial child on one side of the Q-node, as b-nodes respectively as h-node. The pointer h_child1 depicts the endmost child of the Q-node, where the sequence starts.
The function gets the hChild1 of the Q-node. Its return value is the number of pertinent children, corresponding the [w,h,a]-numbering. The function uses the following variables.
Definition at line 1021 of file MaxSequencePQTree.h.
| int ogdf::MaxSequencePQTree< T, Y >::sumPertChild | ( | PQNode< T, whaInfo *, Y > * | nodePtr | ) | [private] |
setPertChild() returns w = sum_{i in P(nodePtr)} w_i, where nodePTr is any pertinent node of the PQ-tree.
The function sumPertChild() returns w = sum_{i in P(nodePtr)}w_i, where nodePTr is any pertinent node of the PQ-tree.
The function sunPertChild() uses the following variables.
The function uses two for loops over the parial and the full children of nodePtr. It hereby computes the values $w$ stored in sum. After finishing the while loops, the function sumPertChild() returns the number w.
Definition at line 1879 of file MaxSequencePQTree.h.
SListPure<PQNode<T,whaInfo*,Y>*> ogdf::MaxSequencePQTree< T, Y >::cleanUp [protected] |
Used to store all pertinent Nodes of the pertinent subtree before removing the minimal pertinent subsequence. Necessary for updates and cleanups after a reduction on the maximal pertinent sequence was successful.
Definition at line 205 of file MaxSequencePQTree.h.
SListPure<PQNode<edge,whaInfo*,bool>*> ogdf::MaxSequencePQTree< T, Y >::eliminatedNodes [protected] |
Used to store all eliminated nodes (status == ELIMINATED) of the PQTree. An eliminated node is one that has been removed during the application of the template matching algorithm from the PQ-tree. These nodes are kept (and their memory is not freed) in order to find out if a node has a valid parent pointer.
Definition at line 214 of file MaxSequencePQTree.h.
