|
|||
|
|
|
|||
|
|
The class template MaxSequencePQTree is designed to compute a maximal consecutive sequence of pertinent leaves in a PQ-tree. More...
#include <ogdf/planarity/planar_subgraph_fast/MaxSequencePQTree.h>
Inheritance diagram for ogdf::MaxSequencePQTree< T, Y >:Public Member Functions | |
| MaxSequencePQTree () | |
| ~MaxSequencePQTree () | |
| virtual void | CleanNode (PQNode< T, whaInfo *, Y > *nodePtr) |
| Frees the memory allocated for the node information class of a node in the PQTree. More... | |
| virtual void | clientDefinedEmptyNode (PQNode< T, whaInfo *, Y > *nodePtr) |
| Does a clean up of a node. Called by emptyAllPertinentNodes. More... | |
| int | determineMinRemoveSequence (SListPure< PQLeafKey< T, whaInfo *, Y > * > &leafKeys, SList< PQLeafKey< T, whaInfo *, Y > * > &eliminatedKeys) |
| Computes the maximal pertinent sequence S' of elements of the set S, that can be reduced in a PQ-tree. More... | |
| virtual void | emptyAllPertinentNodes () |
| Does a clean up after a reduction. More... | |
| Public Member Functions inherited from ogdf::PQTree< T, whaInfo *, Y > | |
| PQTree () | |
| virtual | ~PQTree () |
| Destructor. More... | |
| bool | addNewLeavesToTree (PQInternalNode< T, whaInfo *, Y > *father, SListPure< PQLeafKey< T, whaInfo *, Y > * > &leafKeys) |
| Adds a set of elements to the already existing set of elements of a PQ-tree. More... | |
| virtual void | Cleanup () |
| Removes the entire PQ-tree. More... | |
| void | emptyNode (PQNode< T, whaInfo *, 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, whaInfo *, Y > *nodePtr, SListPure< PQLeafKey< T, whaInfo *, Y > * > &leafKeys) |
Returns the keys stored in the leaves of the front of nodePtr. More... | |
| virtual int | Initialize (SListPure< PQLeafKey< T, whaInfo *, Y > * > &leafKeys) |
| Initializes the PQ-tree with a set of elements. More... | |
| virtual bool | Reduction (SListPure< PQLeafKey< T, whaInfo *, 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, whaInfo *, 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 | Bubble (SListPure< PQLeafKey< T, whaInfo *, Y > * > &leafKeys) |
| The function Bubble() is an overloaded function of the base template class PQTree. More... | |
| PQNode< T, whaInfo *, Y > * | GetParent (PQNode< T, whaInfo *, Y > *nodePtr) |
Computes for the node nodePtr its valid parent in the PQ-tree. More... | |
| Protected Member Functions inherited from ogdf::PQTree< T, whaInfo *, Y > | |
| virtual bool | addNodeToNewParent (PQNode< T, whaInfo *, Y > *parent, PQNode< T, whaInfo *, Y > *child) |
Adds a node child as a child to another node specified in parent. More... | |
| virtual bool | addNodeToNewParent (PQNode< T, whaInfo *, Y > *parent, PQNode< T, whaInfo *, Y > *child, PQNode< T, whaInfo *, Y > *leftBrother, PQNode< T, whaInfo *, Y > *rightBrother) |
Adds a node child to the children of another node specified in parent. More... | |
| virtual bool | checkIfOnlyChild (PQNode< T, whaInfo *, Y > *child, PQNode< T, whaInfo *, Y > *parent) |
Checks if child is the only child of parent. More... | |
| virtual PQNode< T, whaInfo *, Y > * | clientLeftEndmost (PQNode< T, whaInfo *, Y > *nodePtr) const |
| virtual PQNode< T, whaInfo *, Y > * | clientNextSib (PQNode< T, whaInfo *, Y > *nodePtr, PQNode< T, whaInfo *, Y > *other) const |
| virtual int | clientPrintNodeCategorie (PQNode< T, whaInfo *, 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, whaInfo *, 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, whaInfo *, 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, whaInfo *, Y > * | clientRightEndmost (PQNode< T, whaInfo *, Y > *nodePtr) const |
| virtual PQNode< T, whaInfo *, Y > * | clientSibLeft (PQNode< T, whaInfo *, Y > *nodePtr) const |
| virtual PQNode< T, whaInfo *, Y > * | clientSibRight (PQNode< T, whaInfo *, Y > *nodePtr) const |
| virtual void | destroyNode (PQNode< T, whaInfo *, Y > *nodePtr) |
| Marks a node as PQNodeRoot::PQNodeStatus::ToBeDeleted. More... | |
| virtual void | exchangeNodes (PQNode< T, whaInfo *, Y > *oldNode, PQNode< T, whaInfo *, Y > *newNode) |
Replaces the oldNode by the newNode in the tree. More... | |
| List< PQNode< T, whaInfo *, Y > * > * | fullChildren (PQNode< T, whaInfo *, Y > *nodePtr) |
| virtual void | linkChildrenOfQnode (PQNode< T, whaInfo *, Y > *installed, PQNode< T, whaInfo *, Y > *newChild) |
| Links the two endmost children of two different Q-nodes via their sibling pointers together. More... | |
| List< PQNode< T, whaInfo *, Y > * > * | partialChildren (PQNode< T, whaInfo *, Y > *nodePtr) |
| virtual bool | Reduce (SListPure< PQLeafKey< T, whaInfo *, 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, whaInfo *, Y > *nodePtr) |
Removes the node nodePtr from the doubly linked list of its parent. More... | |
| virtual int | removeNodeFromTree (PQNode< T, whaInfo *, Y > *parent, PQNode< T, whaInfo *, Y > *child) |
The objective is to remove a node child from the PQ-tree. More... | |
| virtual bool | templateL1 (PQNode< T, whaInfo *, Y > *nodePtr, bool isRoot) |
| Template matching for leaves. More... | |
| virtual bool | templateP1 (PQNode< T, whaInfo *, Y > *nodePtr, bool isRoot) |
| Template matching for P-nodes with only full children. More... | |
| virtual bool | templateP2 (PQNode< T, whaInfo *, 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, whaInfo *, 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, whaInfo *, Y > **nodePtr) |
| Template matching for a P-node with full, empty and exactly one partial children. More... | |
| virtual bool | templateP5 (PQNode< T, whaInfo *, Y > *nodePtr) |
| Template matching for a P-node with full, empty children and exactly one partial child. More... | |
| virtual bool | templateP6 (PQNode< T, whaInfo *, Y > **nodePtr) |
| Template matching for a P-node with full, empty and exactly two partial children. More... | |
| virtual bool | templateQ1 (PQNode< T, whaInfo *, Y > *nodePtr, bool isRoot) |
| Template matching for Q-nodes with only full children. More... | |
| virtual bool | templateQ2 (PQNode< T, whaInfo *, 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, whaInfo *, Y > *nodePtr) |
Protected Attributes | |
| SListPure< PQNode< T, whaInfo *, Y > * > | cleanUp |
| Used to store all pertinent Nodes of the pertinent subtree before removing the minimal pertinent subsequence. More... | |
| SListPure< PQNode< T, whaInfo *, Y > * > | eliminatedNodes |
| Used to store all eliminated nodes (status == PQNodeRoot::PQNodeStatus::Eliminated) of the PQTree. More... | |
| Protected Attributes inherited from ogdf::PQTree< T, whaInfo *, Y > | |
| 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, whaInfo *, Y > * > * | m_pertinentNodes |
| Stores all nodes that have been marked PQNodeRoot::PQNodeStatus::Full or PQNodeRoot::PQNodeStatus::Partial during a reduction. More... | |
| PQNode< T, whaInfo *, Y > * | m_pertinentRoot |
| a pointer to the root of the pertinent subtree. More... | |
| PQNode< T, whaInfo *, 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, whaInfo *, Y > * | m_root |
| a pointer to the root of the $PQ$-tree. More... | |
Private Member Functions | |
| int | alpha1beta1Number (PQNode< T, whaInfo *, Y > *nodePtr, PQNode< T, whaInfo *, Y > **aChild) |
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. More... | |
| void | aNumQnode (PQNode< T, whaInfo *, Y > *nodePtr, int sumAllW) |
Computes the a-number of the partial Q-node nodePtr. More... | |
| void | findMinWHASequence (ArrayBuffer< PQNode< T, whaInfo *, Y > * > &archiv, SList< PQLeafKey< T, whaInfo *, Y > * > &eliminatedKeys) |
| Checks the [w,h,a]-number of the pertinent root. More... | |
| void | haNumPnode (PQNode< T, whaInfo *, Y > *nodePtr) |
Computes the h- and a-number of a P-node nodePtr. More... | |
| void | haNumQnode (PQNode< T, whaInfo *, Y > *nodePtr) |
Computes the h- and a-number of the partial Q-node nodePtr. More... | |
| void | hNumQnode (PQNode< T, whaInfo *, Y > *nodePtr, int sumAllW) |
Computes the h-number of the partial Q-node nodePtr. More... | |
| void | markPertinentChildren (PQNode< T, whaInfo *, Y > *nodePtr, PQNodeRoot::PQNodeStatus label, whaType deleteType) |
Marks all full and/or partial children of nodePtr as either an a-, b-, h- or w-node. More... | |
| int | setAchildren (PQNode< T, whaInfo *, Y > *hChild2, PQNode< T, whaInfo *, Y > *hChild2Sib) |
| Traces all children of the largest consecutive sequence of pertinent children of a Q-node. More... | |
| int | setHchild (PQNode< T, whaInfo *, Y > *hChild1) |
| 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. More... | |
| int | sumPertChild (PQNode< T, whaInfo *, Y > *nodePtr) |
Returns w = sum_{i in P(nodePtr)}w_i, where nodePtr is any pertinent node of the PQ-tree. More... | |
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 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.
| T | the user-defined type of an element in the above mentioned set U. |
| Y | the user-defined type of the information only available for internal nodes PQInternalKey |
Definition at line 104 of file MaxSequencePQTree.h.
|
inline |
Definition at line 108 of file MaxSequencePQTree.h.
|
inline |
Definition at line 110 of file MaxSequencePQTree.h.
|
private |
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.
Definition at line 1507 of file MaxSequencePQTree.h.
|
private |
Computes the a-number of the partial Q-node nodePtr.
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.
Definition at line 1285 of file MaxSequencePQTree.h.
|
protectedvirtual |
The function Bubble() is an overloaded function of the base template class PQTree.
This overloaded version of Bubble() covers several tasks.
Reimplemented from ogdf::PQTree< T, whaInfo *, Y >.
Definition at line 393 of file MaxSequencePQTree.h.
|
virtual |
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 (by emptyAllPertinentNodes or the destructor).
Reimplemented from ogdf::PQTree< T, whaInfo *, Y >.
Definition at line 476 of file MaxSequencePQTree.h.
|
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 484 of file MaxSequencePQTree.h.
| int ogdf::MaxSequencePQTree< T, Y >::determineMinRemoveSequence | ( | SListPure< PQLeafKey< T, whaInfo *, Y > * > & | leafKeys, |
| SList< PQLeafKey< T, whaInfo *, Y > * > & | eliminatedKeys | ||
| ) |
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 537 of file MaxSequencePQTree.h.
|
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 PQNodeRoot::PQNodeStatus::ToBeDeleted. This causes a valid removal by the function PQTree<T,whaInfo*,Y>::emptyAllPertinentNodes() if the node is contained in the stack m_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.
This function handles another important fact. During the reduction of the maximal pertinent sequence, PQNodeRoot::PQNodeStatus::Partial nodes have been introduced into the PQ-tree, that do not have a node information. This function detects these nodes equipping them with the container class of type PQNodeKey.
Reimplemented from ogdf::PQTree< T, whaInfo *, Y >.
Definition at line 498 of file MaxSequencePQTree.h.
|
private |
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.
The procedure findMinWHASequence() is called by the procedure determineMinRemoveSequence().
Returns an SList eliminatedKeys of pointers to PQLeafKey, describing the leaves that have to be removed.
Definition at line 668 of file MaxSequencePQTree.h.
|
protected |
Computes for the node nodePtr its valid parent in the PQ-tree.
The parent pointer is needed during the Bubble() phase.
In case that nodePtr does not have 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 PQNodeRoot::PQNodeStatus::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 1576 of file MaxSequencePQTree.h.
|
private |
Computes the h- and a-number of a P-node nodePtr.
Definition at line 1060 of file MaxSequencePQTree.h.
|
private |
Computes the h- and a-number of the partial Q-node nodePtr.
Furthermore sets the children aChild, hChild1 and hChild2 of the node information class whaInfo* of nodePtr.
Definition at line 1148 of file MaxSequencePQTree.h.
|
private |
Computes the h-number of the partial Q-node nodePtr.
Furthermore sets the child hChild1 of the node information class whaInfo* of nodePtr.
Definition at line 1160 of file MaxSequencePQTree.h.
|
private |
Marks all full and/or partial children of nodePtr as either an a-, b-, h- or w-node.
| nodePtr | a pointer to the node |
| label | Describes which children have to be marked. Can be either PQNodeRoot::PQNodeStatus::Full, PQNodeRoot::PQNodeStatus::Partial or PQNodeRoot::PQNodeStatus::Pertinent. |
| deleteType | Can be either whaType::W, whaType::B, whaType::H or whaType::A |
The function markPertinentChildren() uses just a pointer currentNode for tracing the pertinent children of nodePtr.
Definition at line 1026 of file MaxSequencePQTree.h.
|
private |
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.
| hChild2 | the first node of the sequence |
| hChild2Sib | its pertinent sibling It allows immediate scanning of the sequence. |
Definition at line 951 of file MaxSequencePQTree.h.
|
private |
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 hChild1 depicts the endmost child of the Q-node, where the sequence starts.
| hChild1 | of the Q-node |
Definition at line 894 of file MaxSequencePQTree.h.
|
private |
Returns w = sum_{i in P(nodePtr)}w_i, where nodePtr is any pertinent node of the PQ-tree.
Definition at line 1553 of file MaxSequencePQTree.h.
|
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 259 of file MaxSequencePQTree.h.
|
protected |
Used to store all eliminated nodes (status == PQNodeRoot::PQNodeStatus::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 268 of file MaxSequencePQTree.h.
