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

The datastructure PQ-tree was designed to present a set of permutations on an arbitrary set of elements. More...

#include <ogdf/basic/pqtree/PQLeaf.h>

Inheritance diagram for ogdf::PQLeaf< T, X, Y >:

Public Member Functions
	PQLeaf (int count, PQNodeRoot::PQNodeStatus stat, PQLeafKey< T, X, Y > *keyPtr)
	PQLeaf (int count, PQNodeRoot::PQNodeStatus stat, PQLeafKey< T, X, Y > *keyPtr, PQNodeKey< T, X, Y > *infoPtr)
	The client may choose between two different constructors. More...
virtual	~PQLeaf ()
	The destructor does not delete any accompanying information class as PQLeafKey, PQNodeKey and PQInternalKey. More...
virtual PQInternalKey< T, X, Y > *	getInternal () const
	getInternal() returns 0. More...
virtual PQLeafKey< T, X, Y > *	getKey () const
	getKey() returns a pointer to the PQLeafKey of PQLeaf. More...
virtual PQNodeRoot::PQNodeMark	mark () const
	Returns the variable m_mark. More...
virtual void	mark (PQNodeRoot::PQNodeMark m)
	Sets the variable m_mark. More...
virtual bool	setInternal (PQInternalKey< T, X, Y > *pointerToInternal)
	setInternal() accepts only pointers pointerToInternal = 0. More...
virtual bool	setKey (PQLeafKey< T, X, Y > *pointerToKey)
	setKey() sets the pointer variable m_pointerToKey to the specified address of pointerToKey that is of type PQLeafKey. More...
virtual PQNodeRoot::PQNodeStatus	status () const
	Returns the variable m_status in the derived class PQLeaf. More...
virtual void	status (PQNodeRoot::PQNodeStatus s)
	Sets the variable m_status in the derived class PQLeaf. More...
virtual PQNodeRoot::PQNodeType	type () const
	Returns the variable PQInternalNode::m_type in the derived class PQLeaf. More...
virtual void	type (PQNodeRoot::PQNodeType)
	Sets the variable PQInternalNode::m_type in the derived class PQLeaf. More...
Public Member Functions inherited from ogdf::PQNode< T, X, Y >
	PQNode (int count)
	The (second) constructor is called, if no information is available or neccessary. More...
	PQNode (int count, PQNodeKey< T, X, Y > *infoPtr)
	The (first) constructor combines the node with its information and will automatically set the PQBasicKey::m_nodePointer (see basicKey) of the element of type PQNodeKey. More...
virtual	~PQNode ()
	The destructor does not delete any accompanying information class as PQLeafKey, PQNodeKey and PQInternalKey. More...
bool	changeEndmost (PQNode< T, X, Y > *oldEnd, PQNode< T, X, Y > *newEnd)
	The function changeEndmost() replaces the old endmost child oldEnd of the node by a new child newEnd. More...
bool	changeSiblings (PQNode< T, X, Y > *oldSib, PQNode< T, X, Y > *newSib)
	The function changeSiblings() replaces the old sibling oldSib of the node by a new sibling newSib. More...
int	childCount () const
	Returns the number of children of a node. More...
void	childCount (int count)
	Sets the number of children of a node. More...
bool	endmostChild () const
	The function endmostChild() checks if a node is endmost child of a Q-node. More...
PQNode< T, X, Y > *	getEndmost (PQNode< T, X, Y > *other) const
	Returns one of the endmost children of node, if node is a Q-node. More...
PQNode< T, X, Y > *	getEndmost (SibDirection side) const
	Returns one of the endmost children of node, if node is a Q-node. More...
PQNode< T, X, Y > *	getNextSib (PQNode< T, X, Y > *other) const
	The function getNextSib() returns one of the siblings of the node. More...
PQNodeKey< T, X, Y > *	getNodeInfo () const
	Returns the identification number of a node. More...
PQNode< T, X, Y > *	getSib (SibDirection side) const
	The function getSib() returns one of the siblings of the node. More...
int	identificationNumber () const
	Returns the identification number of a node. More...
virtual void	mark (PQNodeMark)=0
	mark() sets the variable PQLeaf::m_mark in the derived class PQLeaf and PQInternalNode. More...
PQNode< T, X, Y > *	parent () const
	The function parent() returns a pointer to the parent of a node. More...
PQNode< T, X, Y > *	parent (PQNode< T, X, Y > *newParent)
	Sets the parent pointer of a node. More...
PQNodeType	parentType () const
	Returns the type of the parent of a node. More...
void	parentType (PQNodeType newParentType)
	Sets the type of the parent of a node. More...
int	pertChildCount () const
	Returs the number of pertinent children of a node. More...
void	pertChildCount (int count)
	Sets the number of pertinent children of a node. More...
SibDirection	putSibling (PQNode< T, X, Y > *newSib)
	The default function putSibling() stores a new sibling at a free sibling pointer of the node. More...
SibDirection	putSibling (PQNode< T, X, Y > *newSib, SibDirection preference)
	The function putSibling() with preference stores a new sibling at a free sibling pointer of the node. More...
PQNode< T, X, Y > *	referenceChild () const
	Returns a pointer to the reference child if node is a P-node. More...
PQNode< T, X, Y > *	referenceParent () const
	Returns the pointer to the parent if node is a reference child. More...
bool	setNodeInfo (PQNodeKey< T, X, Y > *pointerToInfo)
	Sets the pointer m_pointerToInfo to the specified adress of pointerToInfo. More...
virtual void	status (PQNodeStatus)=0
	Sets the variable PQLeaf::m_status in the derived class PQLeaf and PQInternalNode. More...
virtual void	type (PQNodeType)=0
	Sets the variable PQInternalNode::m_type in the derived class PQLeaf and PQInternalNode. More...

Private Attributes
PQNodeRoot::PQNodeMark	m_mark
	m_mark is a variable, storing if the PQLeaf is QUEUEUD, BLOCKED or UNBLOCKED (see PQNode) during the first phase of the procedure Bubble(). More...
PQLeafKey< T, X, Y > *	m_pointerToKey
	m_pointerToKey stores the adress of the corresponding PQLeafKey. More...
PQNodeRoot::PQNodeStatus	m_status
	m_status is a variable storing the status of a PQLeaf. More...

Additional Inherited Members
Protected Attributes inherited from ogdf::PQNode< T, X, Y >
List< PQNode< T, X, Y > * > *	fullChildren
	Stores all full children of a node during a reduction. More...
int	m_childCount
int	m_debugTreeNumber
	Needed for debuging purposes. More...
PQNode< T, X, Y > *	m_firstFull
	Stores a pointer to the first full child of a Q-node. More...
int	m_identificationNumber
	Each node that has been introduced once into the tree gets a unique number. More...
PQNode< T, X, Y > *	m_leftEndmost
PQNode< T, X, Y > *	m_parent
	Is a pointer to the parent. More...
PQNodeType	m_parentType
	Stores the type of the parent which can be either a P- or Q-node. More...
int	m_pertChildCount
	Stores the number of pertinent children of the node. More...
int	m_pertLeafCount
	Stores the number of pertinent leaves in the frontier of the node. More...
PQNodeKey< T, X, Y > *	m_pointerToInfo
	Stores a pointer to the corresponding information of the node. More...
PQNode< T, X, Y > *	m_referenceChild
	Stores a pointer to one child, the reference child of the doubly linked cirkular list of children of a P-node. More...
PQNode< T, X, Y > *	m_referenceParent
	Is a pointer to the parent, in case that the parent is a P-node and the node itself is its reference child. More...
PQNode< T, X, Y > *	m_rightEndmost
	Stores the right endmost child of a Q-node. More...
PQNode< T, X, Y > *	m_sibLeft
	Stores a pointer ot the left sibling of PQNode. More...
PQNode< T, X, Y > *	m_sibRight
	Stores a pointer ot the right sibling of PQNode. More...
List< PQNode< T, X, Y > * > *	partialChildren
	Stores all partial children of a node during a reduction. More...

Detailed Description

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

The datastructure PQ-tree was designed to present a set of permutations on an arbitrary set of elements.

These elements are the leafs of a PQ-tree. The client has to specify, what kind of elements he uses. The element of a node is stored in the PQLeafKey of a PQLeaf. The PQLeaf is the only concrete class template of the abstract base class template PQNode that is allowed to have a key.

Definition at line 55 of file PQLeaf.h.

Constructor & Destructor Documentation

PQLeaf() [1/2]

template<class T , class X , class Y >

ogdf::PQLeaf< T, X, Y >::PQLeaf ( int  count, PQNodeRoot::PQNodeStatus  stat, PQLeafKey< T, X, Y > *  keyPtr, PQNodeKey< T, X, Y > *  infoPtr  )

inline

The client may choose between two different constructors.

In both cases the constructor expects an integer value count, setting the value of the variable m_identificationNumber in the base class, an integer value status setting the variable m_status of PQLeaf and a pointer to an element of type PQLeafKey.

One of the constructors expects additional information of type PQNodeKey and will automatically set the PQBasicKey::m_nodePointer (see basicKey) of the element of type PQNodeKey to the newly allocated PQLeaf (see also PQNode). The second constructor is called, if no information for the PQLeaf is available or necessary. Both constructors will automatically set the PQBasicKey::m_nodePointer of the keyPtr to the newly allocated PQLeaf.

Definition at line 73 of file PQLeaf.h.

PQLeaf() [2/2]

template<class T , class X , class Y >

ogdf::PQLeaf< T, X, Y >::PQLeaf ( int  count, PQNodeRoot::PQNodeStatus  stat, PQLeafKey< T, X, Y > *  keyPtr  )

inline

Definition at line 83 of file PQLeaf.h.

~PQLeaf()

template<class T , class X , class Y >

virtual ogdf::PQLeaf< T, X, Y >::~PQLeaf ( )

inlinevirtual

The destructor does not delete any accompanying information class as PQLeafKey, PQNodeKey and PQInternalKey.

This has been avoided, since applications may need the existence of these information classes after the corresponding node has been deleted. If the deletion of an accompanying information class should be performed with the deletion of a node, either derive a new class with an appropriate destructor, or make use of the function CleanNode() of the class template PQTree.

Definition at line 102 of file PQLeaf.h.

Member Function Documentation

getInternal()

template<class T , class X , class Y >

virtual PQInternalKey<T, X, Y>* ogdf::PQLeaf< T, X, Y >::getInternal ( ) const

inlinevirtual

getInternal() returns 0.

The function is designed to return a pointer to the PQInternalKey information of a node, in case that the node is supposed to have internal information. The class template PQLeaf does not have PQInternalKey information.

Implements ogdf::PQNode< T, X, Y >.

Definition at line 142 of file PQLeaf.h.

getKey()

template<class T , class X , class Y >

virtual PQLeafKey<T, X, Y>* ogdf::PQLeaf< T, X, Y >::getKey ( ) const

inlinevirtual

getKey() returns a pointer to the PQLeafKey of PQLeaf.

The adress of the PQLeafKey is stored in the private variable m_pointerToKey. The key contains informations of the element that is represented by the PQLeaf in the PQ-tree and is of type PQLeafKey.

Implements ogdf::PQNode< T, X, Y >.

Definition at line 111 of file PQLeaf.h.

mark() [1/2]

template<class T , class X , class Y >

virtual PQNodeRoot::PQNodeMark ogdf::PQLeaf< T, X, Y >::mark ( ) const

inlinevirtual

Returns the variable m_mark.

The variable m_mark describes the designation used in the first pass of Booth and Luekers algorithm called Bubble(). A PQLeaf is either marked BLOCKED, UNBLOCKED or QUEUED (see PQNode).

Implements ogdf::PQNode< T, X, Y >.

Definition at line 173 of file PQLeaf.h.

mark() [2/2]

template<class T , class X , class Y >

virtual void ogdf::PQLeaf< T, X, Y >::mark ( PQNodeRoot::PQNodeMark  m )

inlinevirtual

Sets the variable m_mark.

Definition at line 176 of file PQLeaf.h.

setInternal()

template<class T , class X , class Y >

virtual bool ogdf::PQLeaf< T, X, Y >::setInternal ( PQInternalKey< T, X, Y > *  pointerToInternal )

inlinevirtual

setInternal() accepts only pointers pointerToInternal = 0.

The function setInternal() is designed to set a specified pointer variable in a derived class of PQNode to the adress stored in pointerToInternal. which is of type PQInternalKey. The class template PQLeaf does not store informations of type PQInternalKey.

setInternal() ignores the informations as long as pointerToInternal = 0. The return value then is 1. In case that pointerToInternal != 0, the return value is 0.

Implements ogdf::PQNode< T, X, Y >.

Definition at line 158 of file PQLeaf.h.

setKey()

template<class T , class X , class Y >

virtual bool ogdf::PQLeaf< T, X, Y >::setKey ( PQLeafKey< T, X, Y > *  pointerToKey )

inlinevirtual

setKey() sets the pointer variable m_pointerToKey to the specified address of pointerToKey that is of type PQLeafKey.

Observe that pointerToKey has to be instantiated by the client. The function setKey() does not instantiate the corresponding variable in the derived class. Using this function will automatically set the PQBasicKey::m_nodePointer of the element of type key (see PQLeafKey) to this PQLeaf. The return value is always 1 unless pointerKey was equal to 0.

Implements ogdf::PQNode< T, X, Y >.

Definition at line 125 of file PQLeaf.h.

status() [1/2]

template<class T , class X , class Y >

virtual PQNodeRoot::PQNodeStatus ogdf::PQLeaf< T, X, Y >::status ( ) const

inlinevirtual

Returns the variable m_status in the derived class PQLeaf.

The functions manage the status of a node in the PQ-tree. A status is any kind of information of the current situation in the frontier of a node (the frontier of a node are all descendant leaves of the node). A status can be anything such as EMPTY, FULL or PARTIAL (see PQNode). Since there might be more than those three possibilities, (e.g. in computing planar subgraphs) this function may to be overloaded by the client.

Implements ogdf::PQNode< T, X, Y >.

Definition at line 189 of file PQLeaf.h.

status() [2/2]

template<class T , class X , class Y >

virtual void ogdf::PQLeaf< T, X, Y >::status ( PQNodeRoot::PQNodeStatus  s )

inlinevirtual

Sets the variable m_status in the derived class PQLeaf.

Definition at line 192 of file PQLeaf.h.

type() [1/2]

template<class T , class X , class Y >

virtual PQNodeRoot::PQNodeType ogdf::PQLeaf< T, X, Y >::type ( ) const

inlinevirtual

Returns the variable PQInternalNode::m_type in the derived class PQLeaf.

The type of a node is either PNode, QNode or leaf (see PQNodeRoot). Since the type of an element of type PQLeaf is leaf every input is ignored and the return value will always be leaf.

Implements ogdf::PQNode< T, X, Y >.

Definition at line 201 of file PQLeaf.h.

type() [2/2]

template<class T , class X , class Y >

virtual void ogdf::PQLeaf< T, X, Y >::type ( PQNodeRoot::PQNodeType  )

inlinevirtual

Sets the variable PQInternalNode::m_type in the derived class PQLeaf.

Definition at line 204 of file PQLeaf.h.

Member Data Documentation

m_mark

template<class T , class X , class Y >

PQNodeRoot::PQNodeMark ogdf::PQLeaf< T, X, Y >::m_mark

private

m_mark is a variable, storing if the PQLeaf is QUEUEUD, BLOCKED or UNBLOCKED (see PQNode) during the first phase of the procedure Bubble().

Definition at line 212 of file PQLeaf.h.

m_pointerToKey

template<class T , class X , class Y >

PQLeafKey<T, X, Y>* ogdf::PQLeaf< T, X, Y >::m_pointerToKey

private

m_pointerToKey stores the adress of the corresponding PQLeafKey.

This PQLeafKey can be overloaded by the client in order to represent different sets of elements, where possible permutations have to be examined by the PQ-tree.

Definition at line 221 of file PQLeaf.h.

m_status

template<class T , class X , class Y >

PQNodeRoot::PQNodeStatus ogdf::PQLeaf< T, X, Y >::m_status

private

m_status is a variable storing the status of a PQLeaf.

A PQLeaf can be either FULL or EMPTY (see PQNode).

Definition at line 227 of file PQLeaf.h.

---

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

• include/ogdf/basic/pqtree/PQLeaf.h