Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::PQTree< T, X, Y > Class Template Reference

#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...
 

Detailed Description

template<class T, class X, class Y>
class ogdf::PQTree< T, X, Y >

Definition at line 45 of file PQNode.h.

Constructor & Destructor Documentation

◆ PQTree()

template<class T , class X , class Y >
ogdf::PQTree< T, X, Y >::PQTree

Definition at line 1701 of file PQTree.h.

◆ ~PQTree()

template<class T , class X , class Y >
virtual ogdf::PQTree< T, X, Y >::~PQTree ( )
inlinevirtual

Destructor.

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().

Definition at line 61 of file PQTree.h.

Member Function Documentation

◆ addNewLeavesToTree()

template<class T , class X , class Y >
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.

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.

Definition at line 817 of file PQTree.h.

◆ addNodeToNewParent() [1/2]

template<class T , class X , class Y >
bool ogdf::PQTree< T, X, Y >::addNodeToNewParent ( PQNode< T, X, Y > *  parent,
PQNode< T, X, Y > *  child 
)
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.

Returns
1 after successfully inserting child to parent, otherwise 0

Definition at line 870 of file PQTree.h.

◆ addNodeToNewParent() [2/2]

template<class T , class X , class Y >
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 
)
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:

  • If 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.
  • If 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.
  • If 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.

Returns
1 if it succeeded in adding the child to parent, otherwise 0

Definition at line 912 of file PQTree.h.

◆ Bubble()

template<class T , class X , class Y >
bool ogdf::PQTree< T, X, Y >::Bubble ( SListPure< PQLeafKey< T, X, Y > * > &  leafKeys)
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 >.

Definition at line 1098 of file PQTree.h.

◆ checkChain()

template<class T , class X , class 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

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().

Definition at line 1384 of file PQTree.h.

◆ checkIfOnlyChild()

template<class T , class X , class Y >
bool ogdf::PQTree< T, X, Y >::checkIfOnlyChild ( PQNode< T, X, Y > *  child,
PQNode< T, X, Y > *  parent 
)
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.

Returns
1, if child was the only child of parent, otherwise 0

Definition at line 1518 of file PQTree.h.

◆ CleanNode()

template<class T , class X , class Y >
virtual void ogdf::PQTree< T, X, Y >::CleanNode ( PQNode< T, X, Y > *  )
inlinevirtual

Reimplemented in ogdf::MaxSequencePQTree< T, Y >, and ogdf::MaxSequencePQTree< edge, bool >.

Definition at line 101 of file PQTree.h.

◆ Cleanup()

template<class T , class X , class Y >
void ogdf::PQTree< T, X, Y >::Cleanup
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:

Definition at line 1543 of file PQTree.h.

◆ clientDefinedEmptyNode()

template<class T , class X , class Y >
virtual void ogdf::PQTree< T, X, Y >::clientDefinedEmptyNode ( PQNode< T, X, Y > *  nodePtr)
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 >.

Definition at line 122 of file PQTree.h.

◆ clientLeftEndmost()

template<class T , class X , class Y >
virtual PQNode<T,X,Y>* ogdf::PQTree< T, X, Y >::clientLeftEndmost ( PQNode< T, X, Y > *  nodePtr) const
inlineprotectedvirtual

Definition at line 683 of file PQTree.h.

◆ clientNextSib()

template<class T , class X , class Y >
virtual PQNode<T,X,Y>* ogdf::PQTree< T, X, Y >::clientNextSib ( PQNode< T, X, Y > *  nodePtr,
PQNode< T, X, Y > *  other 
) const
inlineprotectedvirtual

Definition at line 691 of file PQTree.h.

◆ clientPrintNodeCategorie()

template<class T , class X , class Y >
int ogdf::PQTree< T, X, Y >::clientPrintNodeCategorie ( PQNode< T, X, Y > *  nodePtr)
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.

Definition at line 1683 of file PQTree.h.

◆ clientPrintStatus()

template<class T , class X , class Y >
const char * ogdf::PQTree< T, X, Y >::clientPrintStatus ( PQNode< T, X, Y > *  nodePtr)
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.

Definition at line 1690 of file PQTree.h.

◆ clientPrintType()

template<class T , class X , class Y >
const char * ogdf::PQTree< T, X, Y >::clientPrintType ( PQNode< T, X, Y > *  nodePtr)
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.

Definition at line 1696 of file PQTree.h.

◆ clientRightEndmost()

template<class T , class X , class Y >
virtual PQNode<T,X,Y>* ogdf::PQTree< T, X, Y >::clientRightEndmost ( PQNode< T, X, Y > *  nodePtr) const
inlineprotectedvirtual

Definition at line 687 of file PQTree.h.

◆ clientSibLeft()

template<class T , class X , class Y >
virtual PQNode<T,X,Y>* ogdf::PQTree< T, X, Y >::clientSibLeft ( PQNode< T, X, Y > *  nodePtr) const
inlineprotectedvirtual

Definition at line 696 of file PQTree.h.

◆ clientSibRight()

template<class T , class X , class Y >
virtual PQNode<T,X,Y>* ogdf::PQTree< T, X, Y >::clientSibRight ( PQNode< T, X, Y > *  nodePtr) const
inlineprotectedvirtual

Definition at line 700 of file PQTree.h.

◆ copyFullChildrenToPartial()

template<class T , class X , class Y >
void ogdf::PQTree< T, X, Y >::copyFullChildrenToPartial ( PQNode< T, X, Y > *  nodePtr,
PQNode< T, X, Y > *  partialChild 
)
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().

Definition at line 1714 of file PQTree.h.

◆ createNodeAndCopyFullChildren()

template<class T , class X , class Y >
PQNode< T, X, Y > * ogdf::PQTree< T, X, Y >::createNodeAndCopyFullChildren ( List< PQNode< T, X, Y > * > *  fullNodes)
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().

Definition at line 1754 of file PQTree.h.

◆ destroyNode()

template<class T , class X , class Y >
virtual void ogdf::PQTree< T, X, Y >::destroyNode ( PQNode< T, X, Y > *  nodePtr)
inlineprotectedvirtual

Marks a node as PQNodeRoot::PQNodeStatus::ToBeDeleted.

This enables the function emptyAllPertinentNodes() to remove the node and free its memory.

Definition at line 576 of file PQTree.h.

◆ emptyAllPertinentNodes()

template<class T , class X , class Y >
void ogdf::PQTree< T, X, Y >::emptyAllPertinentNodes
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 >.

Definition at line 1838 of file PQTree.h.

◆ emptyNode()

template<class T , class X , class Y >
void ogdf::PQTree< T, X, Y >::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.

Definition at line 1875 of file PQTree.h.

◆ exchangeNodes()

template<class T , class X , class Y >
void ogdf::PQTree< T, X, Y >::exchangeNodes ( PQNode< T, X, Y > *  oldNode,
PQNode< T, X, Y > *  newNode 
)
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.

Definition at line 1886 of file PQTree.h.

◆ front()

template<class T , class X , class Y >
void ogdf::PQTree< T, X, Y >::front ( PQNode< T, X, Y > *  nodePtr,
SListPure< PQLeafKey< T, X, Y > * > &  leafKeys 
)
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.

Definition at line 1988 of file PQTree.h.

◆ fullChildren()

template<class T , class X , class Y >
List<PQNode<T,X,Y>*>* ogdf::PQTree< T, X, Y >::fullChildren ( PQNode< T, X, Y > *  nodePtr)
inlineprotected

Definition at line 674 of file PQTree.h.

◆ Initialize()

template<class T , class X , class Y >
int ogdf::PQTree< T, X, Y >::Initialize ( SListPure< PQLeafKey< T, X, Y > * > &  leafKeys)
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].

Returns
1 if the initialization of the PQ-tree was successful.

Reimplemented in ogdf::PlanarSubgraphPQTree.

Definition at line 2033 of file PQTree.h.

◆ linkChildrenOfQnode()

template<class T , class X , class Y >
void ogdf::PQTree< T, X, Y >::linkChildrenOfQnode ( PQNode< T, X, Y > *  installed,
PQNode< T, X, Y > *  newChild 
)
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.

Definition at line 2061 of file PQTree.h.

◆ partialChildren()

template<class T , class X , class Y >
List<PQNode<T,X,Y>*>* ogdf::PQTree< T, X, Y >::partialChildren ( PQNode< T, X, Y > *  nodePtr)
inlineprotected

Definition at line 679 of file PQTree.h.

◆ Reduce()

template<class T , class X , class Y >
bool ogdf::PQTree< T, X, Y >::Reduce ( SListPure< PQLeafKey< T, X, Y > * > &  leafKeys)
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.

Definition at line 2288 of file PQTree.h.

◆ Reduction()

template<class T , class X , class Y >
bool ogdf::PQTree< T, X, Y >::Reduction ( SListPure< PQLeafKey< T, X, Y > * > &  leafKeys)
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.

Definition at line 2388 of file PQTree.h.

◆ removeBlock()

template<class T , class X , class Y >
void ogdf::PQTree< T, X, Y >::removeBlock ( PQNode< T, X, Y > *  nodePtr,
bool  isRoot 
)
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

Definition at line 2402 of file PQTree.h.

◆ removeChildFromSiblings()

template<class T , class X , class Y >
void ogdf::PQTree< T, X, Y >::removeChildFromSiblings ( PQNode< T, X, Y > *  nodePtr)
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.

Definition at line 2961 of file PQTree.h.

◆ removeNodeFromTree()

template<class T , class X , class Y >
int ogdf::PQTree< T, X, Y >::removeNodeFromTree ( PQNode< T, X, Y > *  parent,
PQNode< T, X, Y > *  child 
)
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:

  1. The user might keep the node in the tree in order to add new nodes as children to it.
  2. Again, the parent of 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.

Definition at line 3023 of file PQTree.h.

◆ root()

template<class T , class X , class Y >
PQNode<T,X,Y>* ogdf::PQTree< T, X, Y >::root ( ) const
inline

Returns a pointer of the root node of the PQTree.

Definition at line 169 of file PQTree.h.

◆ sortExceptions()

template<class T , class X , class Y >
void ogdf::PQTree< T, X, Y >::sortExceptions ( int  Exceptions[],
int  arraySize 
)
private

Sorts the exceptions before frontExcept() scans the frontier.

It is only called by the function frontExcept().

Definition at line 3041 of file PQTree.h.

◆ templateL1()

template<class T , class X , class Y >
bool ogdf::PQTree< T, X, Y >::templateL1 ( PQNode< T, X, Y > *  nodePtr,
bool  isRoot 
)
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.

Definition at line 3059 of file PQTree.h.

◆ templateP1()

template<class T , class X , class Y >
bool ogdf::PQTree< T, X, Y >::templateP1 ( PQNode< T, X, Y > *  nodePtr,
bool  isRoot 
)
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.

Definition at line 3072 of file PQTree.h.

◆ templateP2()

template<class T , class X , class Y >
bool ogdf::PQTree< T, X, Y >::templateP2 ( PQNode< T, X, Y > **  nodePtr)
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.

Definition at line 3088 of file PQTree.h.

◆ templateP3()

template<class T , class X , class Y >
bool ogdf::PQTree< T, X, Y >::templateP3 ( PQNode< T, X, Y > *  nodePtr)
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.

Definition at line 3118 of file PQTree.h.

◆ templateP4()

template<class T , class X , class Y >
bool ogdf::PQTree< T, X, Y >::templateP4 ( PQNode< T, X, Y > **  nodePtr)
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().

Definition at line 3185 of file PQTree.h.

◆ templateP5()

template<class T , class X , class Y >
bool ogdf::PQTree< T, X, Y >::templateP5 ( PQNode< T, X, Y > *  nodePtr)
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.

Definition at line 3206 of file PQTree.h.

◆ templateP6()

template<class T , class X , class Y >
bool ogdf::PQTree< T, X, Y >::templateP6 ( PQNode< T, X, Y > **  nodePtr)
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.

Definition at line 3302 of file PQTree.h.

◆ templateQ1()

template<class T , class X , class Y >
bool ogdf::PQTree< T, X, Y >::templateQ1 ( PQNode< T, X, Y > *  nodePtr,
bool  isRoot 
)
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.

Definition at line 3428 of file PQTree.h.

◆ templateQ2()

template<class T , class X , class Y >
bool ogdf::PQTree< T, X, Y >::templateQ2 ( PQNode< T, X, Y > *  nodePtr,
bool  isRoot 
)
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.

  • full, empty
  • full, partial, empty
  • full, partial
  • partial, empty.

Definition at line 3450 of file PQTree.h.

◆ templateQ3()

template<class T , class X , class Y >
bool ogdf::PQTree< T, X, Y >::templateQ3 ( PQNode< T, X, Y > *  nodePtr)
protectedvirtual

Definition at line 3558 of file PQTree.h.

◆ writeGML() [1/2]

template<class T , class X , class Y >
void ogdf::PQTree< T, X, Y >::writeGML ( const char *  fileName)

The function writeGML() prints the PQ-tree in the GML fileformat.

Definition at line 2089 of file PQTree.h.

◆ writeGML() [2/2]

template<class T , class X , class Y >
void ogdf::PQTree< T, X, Y >::writeGML ( std::ostream &  os)

Definition at line 2096 of file PQTree.h.

Member Data Documentation

◆ m_identificationNumber

template<class T , class X , class Y >
int ogdf::PQTree< T, X, Y >::m_identificationNumber
protected

Stores the total number of nodes that have been allocated.

Gives every node that has been used once in the PQ-tree a unique identification number.

Definition at line 194 of file PQTree.h.

◆ m_numberOfLeaves

template<class T , class X , class Y >
int ogdf::PQTree< T, X, Y >::m_numberOfLeaves
protected

Stores the number of leaves.

Definition at line 197 of file PQTree.h.

◆ m_pertinentNodes

template<class T , class X , class Y >
List<PQNode<T,X,Y>*>* ogdf::PQTree< T, X, Y >::m_pertinentNodes
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.

Definition at line 207 of file PQTree.h.

◆ m_pertinentRoot

template<class T , class X , class Y >
PQNode<T,X,Y>* ogdf::PQTree< T, X, Y >::m_pertinentRoot
protected

a pointer to the root of the pertinent subtree.

Definition at line 184 of file PQTree.h.

◆ m_pseudoRoot

template<class T , class X , class Y >
PQNode<T,X,Y>* ogdf::PQTree< T, X, Y >::m_pseudoRoot
protected

a pointer to the virtual root of the pertinent subtree, in case that the pertinent root cannot be detected.

Definition at line 187 of file PQTree.h.

◆ m_root

template<class T , class X , class Y >
PQNode<T,X,Y>* ogdf::PQTree< T, X, Y >::m_root
protected

a pointer to the root of the $PQ$-tree.

Definition at line 181 of file PQTree.h.


The documentation for this class was generated from the following files: