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.

virtual void	clientDefinedEmptyNode (PQNode< T, whaInfo , Y > nodePtr)
	Does a clean up of a node. Called by emptyAllPertinentNodes.

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.

virtual void	emptyAllPertinentNodes ()
	Does a clean up after a reduction.

Public Member Functions inherited from ogdf::PQTree< T, whaInfo *, Y >
	PQTree ()

virtual	~PQTree ()
	Destructor.

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.

virtual void	Cleanup ()
	Removes the entire PQ-tree.

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.

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

virtual int	Initialize (SListPure< PQLeafKey< T, whaInfo , Y > > &leafKeys)
	Initializes the PQ-tree with a set of elements.

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.

PQNode< T, whaInfo , Y >	root () const
	Returns a pointer of the root node of the PQTree.

void	writeGML (const char *fileName)
	The function writeGML() prints the PQ-tree in the GML fileformat.

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.

PQNode< T, whaInfo , Y >	GetParent (PQNode< T, whaInfo , Y > nodePtr)
	Computes for the node `nodePtr` its valid parent in the PQ-tree.

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

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

virtual bool	Bubble (SListPure< PQLeafKey< T, whaInfo , Y > > &leafKeys)
	Realizes a function described in [Booth].

virtual bool	checkIfOnlyChild (PQNode< T, whaInfo , Y > child, PQNode< T, whaInfo , Y > parent)
	Checks if `child` is the only child of `parent`.

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.

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.

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.

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.

virtual void	exchangeNodes (PQNode< T, whaInfo , Y > oldNode, PQNode< T, whaInfo , Y > newNode)
	Replaces the `oldNode` by the `newNode` in the tree.

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.

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.

virtual void	removeChildFromSiblings (PQNode< T, whaInfo , Y > nodePtr)
	Removes the node `nodePtr` from the doubly linked list of its parent.

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.

virtual bool	templateL1 (PQNode< T, whaInfo , Y > nodePtr, bool isRoot)
	Template matching for leaves.

virtual bool	templateP1 (PQNode< T, whaInfo , Y > nodePtr, bool isRoot)
	Template matching for P-nodes with only full children.

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.

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.

virtual bool	templateP4 (PQNode< T, whaInfo , Y > *nodePtr)
	Template matching for a P-node with full, empty and exactly one partial children.

virtual bool	templateP5 (PQNode< T, whaInfo , Y > nodePtr)
	Template matching for a P-node with full, empty children and exactly one partial child.

virtual bool	templateP6 (PQNode< T, whaInfo , Y > *nodePtr)
	Template matching for a P-node with full, empty and exactly two partial children.

virtual bool	templateQ1 (PQNode< T, whaInfo , Y > nodePtr, bool isRoot)
	Template matching for Q-nodes with only full children.

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.

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.

SListPure< PQNode< T, whaInfo , Y > >	eliminatedNodes
	Used to store all eliminated nodes (status == PQNodeRoot::PQNodeStatus::Eliminated) of the PQTree.

Protected Attributes inherited from ogdf::PQTree< T, whaInfo *, Y >
int	m_identificationNumber
	Stores the total number of nodes that have been allocated.

int	m_numberOfLeaves
	Stores the number of leaves.

List< PQNode< T, whaInfo , Y > > *	m_pertinentNodes
	Stores all nodes that have been marked PQNodeRoot::PQNodeStatus::Full or PQNodeRoot::PQNodeStatus::Partial during a reduction.

PQNode< T, whaInfo , Y >	m_pertinentRoot
	a pointer to the root of the pertinent subtree.

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.

PQNode< T, whaInfo , Y >	m_root
	a pointer to the root of the $PQ$-tree.

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.

void	aNumQnode (PQNode< T, whaInfo , Y > nodePtr, int sumAllW)
	Computes the a-number of the partial Q-node `nodePtr`.

void	findMinWHASequence (ArrayBuffer< PQNode< T, whaInfo , Y > > &archiv, SList< PQLeafKey< T, whaInfo , Y > > &eliminatedKeys)
	Checks the [w,h,a]-number of the pertinent root.

void	haNumPnode (PQNode< T, whaInfo , Y > nodePtr)
	Computes the h- and a-number of a P-node `nodePtr`.

void	haNumQnode (PQNode< T, whaInfo , Y > nodePtr)
	Computes the h- and a-number of the partial Q-node `nodePtr`.

void	hNumQnode (PQNode< T, whaInfo , Y > nodePtr, int sumAllW)
	Computes the h-number of the partial Q-node `nodePtr`.

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.

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.

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.

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.

Detailed Description

template<class T, class Y>
class ogdf::MaxSequencePQTree< T, Y >

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.

Template Parameters

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 97 of file MaxSequencePQTree.h.

Constructor & Destructor Documentation

◆ MaxSequencePQTree()

template<class T , class Y >

ogdf::MaxSequencePQTree< T, Y >::MaxSequencePQTree ( )

inline

Definition at line 101 of file MaxSequencePQTree.h.

◆ ~MaxSequencePQTree()

template<class T , class Y >

ogdf::MaxSequencePQTree< T, Y >::~MaxSequencePQTree ( )

inline

Definition at line 103 of file MaxSequencePQTree.h.

Member Function Documentation

◆ alpha1beta1Number()

template<class T , class Y >

int ogdf::MaxSequencePQTree< T, Y >::alpha1beta1Number	(	PQNode< T, whaInfo , Y >	nodePtr,
		PQNode< T, whaInfo , Y > *	aChild
	)

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 1500 of file MaxSequencePQTree.h.

◆ aNumQnode()

template<class T , class Y >

void ogdf::MaxSequencePQTree< T, Y >::aNumQnode	(	PQNode< T, whaInfo , Y >	nodePtr,
		int	sumAllW
	)

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 1278 of file MaxSequencePQTree.h.

◆ Bubble()

template<class T , class Y >

bool ogdf::MaxSequencePQTree< T, Y >::Bubble ( SListPure< PQLeafKey< T, whaInfo *, Y > * > & leafKeys )

protectedvirtual

The function Bubble() is an overloaded function of the base template class PQTree.

This overloaded version of Bubble() covers several tasks.

It bubbles the tree up from the pertinent leaves, stored in an SListPure of type PQLeafKey, to find all pertinent nodes. Every pertinent node is stored in the stack cleanUp for a valid cleanup after the reduction step.
It makes sure that every pertinent node has a valid parent pointer. (Different to the original Bubble() that only tests if every node has a valid parent pointer)

Parameters

leafKeys a SListPure to the PQLeafKey's of the pertinent leaves.

Definition at line 386 of file MaxSequencePQTree.h.

◆ CleanNode()

template<class T , class Y >

void ogdf::MaxSequencePQTree< T, Y >::CleanNode ( PQNode< T, whaInfo *, Y > * nodePtr )

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 469 of file MaxSequencePQTree.h.

◆ clientDefinedEmptyNode()

template<class T , class Y >

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 477 of file MaxSequencePQTree.h.

◆ determineMinRemoveSequence()

template<class T , class Y >

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 530 of file MaxSequencePQTree.h.

◆ emptyAllPertinentNodes()

template<class T , class Y >

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

PQNodeRoot::PQNodeStatus::WhaDelete: the node had to be removed from the tree in order to get a maximal pertinent sequence. The memory of the nodes has to be freed. Hence mark it as PQNodeRoot::PQNodeStatus::ToBeDeleted.
PQNodeRoot::PQNodeType::Leaf: the node was a full leaf. Delete it immediately, if it was marked PQNodeRoot::PQNodeStatus::WhaDelete, since it is not contained in the m_pertinentNodes stack of the base class.
PQNodeRoot::PQNodeStatus::ToBeDeleted: the node was a partial node in the remaining pertinent subtree and replaced during the template matching algorithm by some other node. For the computation of valid parent pointers during the Bubble phase, the node has to be kept. Hence it is marked as PQNodeRoot::PQNodeStatus::Eliminated, which leaves the node untouched by the base class call of emptyAllPertinentNodes(). Observe that the node is stored in a special stack called eliminatedNodes for a valid cleanup after the termination of the algorithm.
PQNodeRoot::PQNodeStatus::Full: the node is a full node of the pertinent subtree. Since the pertinent subtree is replaced by a single P-node and some leaves representing the incoming edges of a node, this node has to be removed from the tree. Hence it is marked as PQNodeRoot::PQNodeStatus::ToBeDeleted. Observe that the pertinent root was probably marked as PQNodeRoot::PQNodeStatus::PertRoot and therefore is not removed from the tree.

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 491 of file MaxSequencePQTree.h.

◆ findMinWHASequence()

template<class T , class Y >

void ogdf::MaxSequencePQTree< T, Y >::findMinWHASequence	(	ArrayBuffer< PQNode< T, whaInfo , Y > > &	archiv,
		SList< PQLeafKey< T, whaInfo , Y > > &	eliminatedKeys
	)

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 661 of file MaxSequencePQTree.h.

◆ GetParent()

template<class T , class Y >

PQNode< T, whaInfo *, Y > * ogdf::MaxSequencePQTree< T, Y >::GetParent ( PQNode< T, whaInfo *, Y > * nodePtr )

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 1569 of file MaxSequencePQTree.h.

◆ haNumPnode()

template<class T , class Y >

void ogdf::MaxSequencePQTree< T, Y >::haNumPnode ( PQNode< T, whaInfo *, Y > * nodePtr )

private

Computes the h- and a-number of a P-node nodePtr.

Definition at line 1053 of file MaxSequencePQTree.h.

◆ haNumQnode()

template<class T , class Y >

void ogdf::MaxSequencePQTree< T, Y >::haNumQnode ( PQNode< T, whaInfo *, Y > * nodePtr )

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 1141 of file MaxSequencePQTree.h.

◆ hNumQnode()

template<class T , class Y >

void ogdf::MaxSequencePQTree< T, Y >::hNumQnode	(	PQNode< T, whaInfo , Y >	nodePtr,
		int	sumAllW
	)

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 1153 of file MaxSequencePQTree.h.

◆ markPertinentChildren()

template<class T , class Y >

void ogdf::MaxSequencePQTree< T, Y >::markPertinentChildren	(	PQNode< T, whaInfo , Y >	nodePtr,
		PQNodeRoot::PQNodeStatus	label,
		whaType	deleteType
	)

private

Marks all full and/or partial children of nodePtr as either an a-, b-, h- or w-node.

Parameters

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 1019 of file MaxSequencePQTree.h.

◆ setAchildren()

template<class T , class Y >

int ogdf::MaxSequencePQTree< T, Y >::setAchildren	(	PQNode< T, whaInfo , Y >	hChild2,
		PQNode< T, whaInfo , Y >	hChild2Sib
	)

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.

Parameters

hChild2	the first node of the sequence
hChild2Sib	its pertinent sibling It allows immediate scanning of the sequence.

Returns: the number of pertinent children of the Q-node according to the [w,h,a]-numbering.

Definition at line 944 of file MaxSequencePQTree.h.

◆ setHchild()

template<class T , class Y >

int ogdf::MaxSequencePQTree< T, Y >::setHchild ( PQNode< T, whaInfo *, Y > * hChild1 )

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.

Parameters

hChild1 of the Q-node

Returns: number of pertinent children, corresponding to the [w,h,a]-numbering.

Definition at line 887 of file MaxSequencePQTree.h.

◆ sumPertChild()

template<class T , class Y >

int ogdf::MaxSequencePQTree< T, Y >::sumPertChild ( PQNode< T, whaInfo *, Y > * nodePtr )

private

Returns w = sum_{i in P(nodePtr)}w_i, where nodePtr is any pertinent node of the PQ-tree.

Definition at line 1546 of file MaxSequencePQTree.h.

Member Data Documentation

◆ cleanUp

template<class T , class Y >

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 252 of file MaxSequencePQTree.h.

◆ eliminatedNodes

template<class T , class Y >

SListPure<PQNode<T, whaInfo*, Y>*> ogdf::MaxSequencePQTree< T, Y >::eliminatedNodes

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 261 of file MaxSequencePQTree.h.

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

include/ogdf/planarity/planar_subgraph_fast/MaxSequencePQTree.h

OpenGraph DrawingFramework

Public Member Functions

Protected Member Functions

Protected Attributes

Private Member Functions

Detailed Description

Constructor & Destructor Documentation

◆ MaxSequencePQTree()

◆ ~MaxSequencePQTree()

Member Function Documentation

◆ alpha1beta1Number()

◆ aNumQnode()

◆ Bubble()

◆ CleanNode()

◆ clientDefinedEmptyNode()

◆ determineMinRemoveSequence()

◆ emptyAllPertinentNodes()

◆ findMinWHASequence()

◆ GetParent()

◆ haNumPnode()

◆ haNumQnode()

◆ hNumQnode()

◆ markPertinentChildren()

◆ setAchildren()

◆ setHchild()

◆ sumPertChild()

Member Data Documentation

◆ cleanUp

◆ eliminatedNodes

Open
Graph Drawing
Framework