The class template PQBasicKey is an abstract base class. More...

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

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

Public Member Functions
	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...

virtual PQInternalKey< T, X, Y > *	getInternal () const =0
	getInternal() returns a pointer to the PQInternalKey information of a node, in case that the node is supposed to have PQInternalKey information, such as elements of the derived class template PQInternalNode. More...

virtual PQLeafKey< T, X, Y > *	getKey () const =0
	getKey() returns a pointer to the PQLeafKeyof a node, in case that the node is supposed to have a key, such as elements of the derived class template PQLeaf. 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 PQNodeMark	mark () const =0
	mark() returns the variable PQLeaf::m_mark in the derived class PQLeaf and PQInternalNode. 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...

virtual bool	setInternal (PQInternalKey< T, X, Y > *pointerToInternal)=0

virtual bool	setKey (PQLeafKey< T, X, Y > *pointerToKey)=0
	Sets a specified pointer variable in a derived class to the specified adress of `pointerToKey` that is of type PQLeafKey. More...

bool	setNodeInfo (PQNodeKey< T, X, Y > *pointerToInfo)
	Sets the pointer m_pointerToInfo to the specified adress of `pointerToInfo`. More...

virtual PQNodeStatus	status () const =0
	Returns the variable PQLeaf::m_status in the derived class PQLeaf and PQInternalNode. More...

virtual void	status (PQNodeStatus)=0
	Sets the variable PQLeaf::m_status in the derived class PQLeaf and PQInternalNode. More...

virtual PQNodeType	type () const =0
	Returns the variable PQInternalNode::m_type 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...

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

Friends
class	PQTree< T, X, Y >
	All members and member function of PQNode are needed by the class template PQTree. More...

Detailed Description

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

The class template PQBasicKey is an abstract base class.

It enables the user of the PQ-tree to store different informations at every node of the tree.

The implementation of the PQ-tree provides the storage of three different types of information.

General information that is stored at P- and Q-nodes and leaves likewise (see also PQNodeKey).
Information that is only supported for internal nodes (see also internalKey).
The keys of the leaves (see also leafKey). The keys are constructed to carry the elements of a user defined set of any type, where permissible permutations have to be found. In order to use the datastructure PQ-tree as class template PQTree, the user has to specify a set of arbitrary elements that form the leaves of the PQ-tree. The keys function as storage class of the elements of the set.

All three storage classes are derived class templates of PQBasicKey. The class PQBasicKey has a pointer PQBasicKey::m_nodePointer to a PQNode, beeing either a leaf or an internal PQInternalNode. The base class itself does not provide any storage of the informations, it is hidden in the derived classes. PQBasicKey only declares a few pure virtual functions that are overloaded in the derived classes and which give access to the information stored in the derived classes.

The information stored in an element of a derived class of PQBasicKey is assigned to a unique node in the PQ-tree. This unique node can be identified with the PQBasicKey::m_nodePointer. The maintenance of this pointer is left to the user in the derived concrete classes PQNodeKey and internalKey. By keeping the responsibillity for these classes by the client, nodes with certain informations can be accessed by the client in constant time. This makes the adaption of algorithms fast and easy.

Only the derived concrete class template leafKey is treated in a different way by the class template PQTree. When initializing the PQTree with a set of elements of type leafKey, the class template PQTree sets the pointer PQBasicKey::m_nodePointer of every element. This is due to the fact that a PQ-tree is always defined over some set, whose elements are stored in the leaves. Hence the class PQtree expects such a set and supports its maintainance. Storing extra information at every node may be omitted and makes the PQtree easy applicable.

We now give a short overview of the class template declaration PQBasicKey. The class template PQBasicKey is used as a base class template that specifies three different types of information. The type of information used at a node is depending on the type of the node. These informations have to be specified by the user.

The formal type parameters of the class template PQBasicKey are categorized as follows.

T is a formal type parameter for the information stored in leafKey.
X is a formal type parameter for the information stored in PQNodeKey.
Y is a formal type parameter for the information stored in internalKey.

The class template PQBasicKey contains a few pure virtual member functions that are overloaded in the derived class leafKey, PQNodeKey and internalKey. These functions enable the client to access the information stored at a node.

Definition at line 111 of file PQBasicKey.h.

Constructor & Destructor Documentation

◆ PQNode() [1/2]

template<class T , class X , class Y >

ogdf::PQNode< T, X, Y >::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.

Definition at line 556 of file PQNode.h.

◆ PQNode() [2/2]

template<class T , class X , class Y >

ogdf::PQNode< T, X, Y >::PQNode ( int count )

explicit

The (second) constructor is called, if no information is available or neccessary.

Definition at line 585 of file PQNode.h.

◆ ~PQNode()

template<class T , class X , class Y >

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

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 89 of file PQNode.h.

Member Function Documentation

◆ changeEndmost()

template<class T , class X , class Y >

bool ogdf::PQNode< T, X, Y >::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.

If the node is a Q-node, then it must have two valid pointers to its endmost children. If one of the endmost children is oldEnd, it is replaced by newEnd. The function changeEndmost() returns 1 if it succeeded in replacing oldEnd by newEnd. Otherwise the function returns 0, leaving with an error message.

Definition at line 515 of file PQNode.h.

◆ changeSiblings()

template<class T , class X , class Y >

bool ogdf::PQNode< T, X, Y >::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.

If the node has oldSib as sibling, then it changes the sibling pointer that references to oldSib and places newSib at its position. The function changeSiblings() returns 1 if it succeeded in replacing oldSib by newSib. Otherwise the function returns 0, leaving with an error message.

Definition at line 539 of file PQNode.h.

◆ childCount() [1/2]

template<class T , class X , class Y >

int ogdf::PQNode< T, X, Y >::childCount ( ) const

inline

Returns the number of children of a node.

Definition at line 201 of file PQNode.h.

◆ childCount() [2/2]

template<class T , class X , class Y >

void ogdf::PQNode< T, X, Y >::childCount ( int count )

inline

Sets the number of children of a node.

Definition at line 204 of file PQNode.h.

◆ endmostChild()

template<class T , class X , class Y >

bool ogdf::PQNode< T, X, Y >::endmostChild ( ) const

inline

The function endmostChild() checks if a node is endmost child of a Q-node.

This is 1 if one of the sibling pointers m_sibLeft or m_sibRight is 0. If the node is endmost child of a Q-node, then it has a valid parent pointer.

Definition at line 124 of file PQNode.h.

◆ getEndmost() [1/2]

template<class T , class X , class Y >

PQNode<T, X, Y>* ogdf::PQNode< T, X, Y >::getEndmost ( PQNode< T, X, Y > * other ) const

inline

Returns one of the endmost children of node, if node is a Q-node.

The function getEndmost() accepts as input a pointer to a PQNode stored in other. The returned endmost child is unequal to the one specified in other. In case that an arbitrary endmost child should be looked up, set other = 0. This makes the function getEndmost() return an arbitrary endmost child (it returns the left endmost child).

Definition at line 135 of file PQNode.h.

◆ getEndmost() [2/2]

template<class T , class X , class Y >

PQNode<T, X, Y>* ogdf::PQNode< T, X, Y >::getEndmost ( SibDirection side ) const

inline

Returns one of the endmost children of node, if node is a Q-node.

The function accepts an integer denoting a direction causing the function to return either the left or the endmost child.

Definition at line 150 of file PQNode.h.

◆ getInternal()

template<class T , class X , class Y >

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

pure virtual

getInternal() returns a pointer to the PQInternalKey information of a node, in case that the node is supposed to have PQInternalKey information, such as elements of the derived class template PQInternalNode.

The internal information is of type PQInternalKey.

Implemented in ogdf::PQInternalNode< T, X, Y >, and ogdf::PQLeaf< T, X, Y >.

◆ getKey()

template<class T , class X , class Y >

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

pure virtual

getKey() returns a pointer to the PQLeafKeyof a node, in case that the node is supposed to have a key, such as elements of the derived class template PQLeaf.

The key contains information and is of type PQLeafKey.

Implemented in ogdf::PQInternalNode< T, X, Y >, and ogdf::PQLeaf< T, X, Y >.

◆ getNextSib()

template<class T , class X , class Y >

PQNode<T, X, Y>* ogdf::PQNode< T, X, Y >::getNextSib ( PQNode< T, X, Y > * other ) const

inline

The function getNextSib() returns one of the siblings of the node.

The function getNextSib() accepts as input a pointer to a PQNode stored in other. The returned sibling is unequal to the one specified in other. In case that no sibling has been looked up before, set other = 0. This makes the function getNextSib() return an arbitrary sibling (it returns the left sibling).

Definition at line 187 of file PQNode.h.

◆ getNodeInfo()

template<class T , class X , class Y >

PQNodeKey<T, X, Y>* ogdf::PQNode< T, X, Y >::getNodeInfo ( ) const

inline

Returns the identification number of a node.

Definition at line 161 of file PQNode.h.

◆ getSib()

template<class T , class X , class Y >

PQNode<T, X, Y>* ogdf::PQNode< T, X, Y >::getSib ( SibDirection side ) const

inline

The function getSib() returns one of the siblings of the node.

It accepts an integer denoting a dircetion causing the function to return either the left or the right sibling.

Definition at line 168 of file PQNode.h.

◆ identificationNumber()

template<class T , class X , class Y >

int ogdf::PQNode< T, X, Y >::identificationNumber ( ) const

inline

Returns the identification number of a node.

Definition at line 198 of file PQNode.h.

◆ mark() [1/2]

template<class T , class X , class Y >

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

pure virtual

mark() returns the variable PQLeaf::m_mark in the derived class PQLeaf and PQInternalNode.

In a derived class this function has to return the designation used in the first pass of Booth and Luekers algorithm called Bubble(). A node then is either marked BLOCKED, UNBLOCKED or QUEUED (see PQNode).

Implemented in ogdf::PQInternalNode< T, X, Y >, and ogdf::PQLeaf< T, X, Y >.

◆ mark() [2/2]

template<class T , class X , class Y >

virtual void ogdf::PQNode< T, X, Y >::mark ( PQNodeMark )

pure virtual

mark() sets the variable PQLeaf::m_mark in the derived class PQLeaf and PQInternalNode.

Implemented in ogdf::booth_lueker::EmbedIndicator.

◆ parent() [1/2]

template<class T , class X , class Y >

PQNode<T, X, Y>* ogdf::PQNode< T, X, Y >::parent ( ) const

inline

The function parent() returns a pointer to the parent of a node.

Warning: After reducing the PQ-tree, some nodes may not have valid parent pointers anymore. This is no fault, the datastructur was designed this way. See also Booth and Lueker.

Definition at line 213 of file PQNode.h.

◆ parent() [2/2]

template<class T , class X , class Y >

PQNode<T, X, Y>* ogdf::PQNode< T, X, Y >::parent ( PQNode< T, X, Y > * newParent )

inline

Sets the parent pointer of a node.

This function is needed in more ellaborated algorithms implemented as derivation of the class template PQTree. Here, the parent pointer probably is always needed and therefore has to be set within special functions, used in a pre-run before applying the bubble Phase of the PQTree.

Definition at line 222 of file PQNode.h.

◆ parentType() [1/2]

template<class T , class X , class Y >

PQNodeType ogdf::PQNode< T, X, Y >::parentType ( ) const

inline

Returns the type of the parent of a node.

Definition at line 225 of file PQNode.h.

◆ parentType() [2/2]

template<class T , class X , class Y >

void ogdf::PQNode< T, X, Y >::parentType ( PQNodeType newParentType )

inline

Sets the type of the parent of a node.

This does not change the type of the parent!

Definition at line 231 of file PQNode.h.

◆ pertChildCount() [1/2]

template<class T , class X , class Y >

int ogdf::PQNode< T, X, Y >::pertChildCount ( ) const

inline

Returs the number of pertinent children of a node.

Definition at line 234 of file PQNode.h.

◆ pertChildCount() [2/2]

template<class T , class X , class Y >

void ogdf::PQNode< T, X, Y >::pertChildCount ( int count )

inline

Sets the number of pertinent children of a node.

Definition at line 237 of file PQNode.h.

◆ putSibling() [1/2]

template<class T , class X , class Y >

SibDirection ogdf::PQNode< T, X, Y >::putSibling ( PQNode< T, X, Y > * newSib )

inline

The default function putSibling() stores a new sibling at a free sibling pointer of the node.

This is only possible, if the node has at most one sibling. The function then detects a non used sibling pointer and places newSib onto it. putSibling() returns 0 if there have been two siblings detected, occupying the two possible pointers. In this case the new sibling newSib cannot be stored. If there was at a maximum one sibling stored, the function will place newSib on the free pointer and return either LEFT or RIGHT, depending wich pointer has been used.

This function will always scan the pointer to the left brother first.

Definition at line 252 of file PQNode.h.

◆ putSibling() [2/2]

template<class T , class X , class Y >

SibDirection ogdf::PQNode< T, X, Y >::putSibling	(	PQNode< T, X, Y > *	newSib,
		SibDirection	preference
	)

inline

The function putSibling() with preference stores a new sibling at a free sibling pointer of the node.

This is only possible, if the node has at most one sibling. The function then detects a non used sibling pointer and places newSib onto it. putSibling() returns 0 if there have been two siblings detected, occupying the two possible pointers. In this case the new sibling newSib could not be stored. If there was at a maximum one sibling stored, the function will place newSib on the free pointer and return either LEFT or RIGHT, depending wich pointer has been used.

This function scans the brother first, which has been specified in the preference. If the preference has value LEFT, it scans the pointer to the left brother first. If the value is RIGHT, it scans the pointer to the right brother first.

Definition at line 279 of file PQNode.h.

◆ referenceChild()

template<class T , class X , class Y >

PQNode<T, X, Y>* ogdf::PQNode< T, X, Y >::referenceChild ( ) const

inline

Returns a pointer to the reference child if node is a P-node.

Definition at line 297 of file PQNode.h.

◆ referenceParent()

template<class T , class X , class Y >

PQNode<T, X, Y>* ogdf::PQNode< T, X, Y >::referenceParent ( ) const

inline

Returns the pointer to the parent if node is a reference child.

Definition at line 300 of file PQNode.h.

◆ setInternal()

template<class T , class X , class Y >

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

pure virtual

Implemented in ogdf::PQInternalNode< T, X, Y >, and ogdf::PQLeaf< T, X, Y >.

◆ setKey()

template<class T , class X , class Y >

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

pure virtual

Sets a specified pointer variable in a derived class to the specified adress of pointerToKey that is of type PQLeafKey.

If a derived class, such as PQInternalNode, is not supposed to store informations of type PQLeafKey, setKey() ignores the informations as long as pointerToKey = 0. The return value then is 1. In case that pointerToKey != 0, the return value is 0.

If a derived class, such as PQLeaf is supposed to store informations of type PQLeafKey, pointerToKey has to be instantiated by the client. The function setKey() does not instantiate the corresponding variable in the derived class. The return value is always 1 unless pointerKey was equal to 0.

Implemented in ogdf::PQInternalNode< T, X, Y >, and ogdf::PQLeaf< T, X, Y >.

◆ setNodeInfo()

template<class T , class X , class Y >

bool ogdf::PQNode< T, X, Y >::setNodeInfo ( PQNodeKey< T, X, Y > * pointerToInfo )

inline

Sets the pointer m_pointerToInfo to the specified adress of pointerToInfo.

Definition at line 303 of file PQNode.h.

◆ status() [1/2]

template<class T , class X , class Y >

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

pure virtual

Returns the variable PQLeaf::m_status in the derived class PQLeaf and PQInternalNode.

Its objective is to manage 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 is 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 probably has to be overloaded by the client.

Implemented in ogdf::PQInternalNode< T, X, Y >, and ogdf::PQLeaf< T, X, Y >.

◆ status() [2/2]

template<class T , class X , class Y >

virtual void ogdf::PQNode< T, X, Y >::status ( PQNodeStatus )

pure virtual

Sets the variable PQLeaf::m_status in the derived class PQLeaf and PQInternalNode.

Implemented in ogdf::booth_lueker::EmbedIndicator.

◆ type() [1/2]

template<class T , class X , class Y >

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

pure virtual

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

Its objective it to manage the type of a node. node the current node is. The type of a node in the class template PQTree is either PNode, QNode or leaf (see PQNode). There may be of course more types such as sequence indicators.

Observe that the derived class template PQLeaf does not have a variable PQInternalNode::m_type, since it obviously is of type leaf.

Implemented in ogdf::PQInternalNode< T, X, Y >, and ogdf::PQLeaf< T, X, Y >.

◆ type() [2/2]

template<class T , class X , class Y >

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

pure virtual

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

Implemented in ogdf::booth_lueker::EmbedIndicator.

Friends And Related Function Documentation

◆ PQTree< T, X, Y >

template<class T , class X , class Y >

friend class PQTree< T, X, Y >

friend

All members and member function of PQNode are needed by the class template PQTree.

Therefore the class PQTree was made friendof PQNode, since this prevents the use of a large amount of extra public functions.

Definition at line 63 of file PQNode.h.

Member Data Documentation

◆ fullChildren

template<class T , class X , class Y >

List<PQNode<T, X, Y>*>* ogdf::PQNode< T, X, Y >::fullChildren

protected

Stores all full children of a node during a reduction.

Definition at line 498 of file PQNode.h.

◆ m_childCount

template<class T , class X , class Y >

int ogdf::PQNode< T, X, Y >::m_childCount

protected

Definition at line 412 of file PQNode.h.

◆ m_debugTreeNumber

template<class T , class X , class Y >

int ogdf::PQNode< T, X, Y >::m_debugTreeNumber

protected

Needed for debuging purposes.

The PQ-trees can be visualized with the help of the Tree Interface and the m_debugTreeNumber is needed to print out the tree in the correct file format.

Definition at line 420 of file PQNode.h.

◆ m_firstFull

template<class T , class X , class Y >

PQNode<T, X, Y>* ogdf::PQNode< T, X, Y >::m_firstFull

protected

Stores a pointer to the first full child of a Q-node.

Definition at line 445 of file PQNode.h.

◆ m_identificationNumber

template<class T , class X , class Y >

int ogdf::PQNode< T, X, Y >::m_identificationNumber

protected

Each node that has been introduced once into the tree gets a unique number.

If the node is removed from the tree during a reduction or with the help of one of the functions that is provided by the class template PQtree, its number is not reused. This always allows exact identification of nodes during any process that is envoked on the PQ-tree. We strongly recommend users who construct the tree with the help of the construction functions and who instantiate the nodes by them selves to do the same.

Definition at line 433 of file PQNode.h.

◆ m_leftEndmost

template<class T , class X , class Y >

PQNode<T, X, Y>* ogdf::PQNode< T, X, Y >::m_leftEndmost

protected

Definition at line 447 of file PQNode.h.

◆ m_parent

template<class T , class X , class Y >

PQNode<T, X, Y>* ogdf::PQNode< T, X, Y >::m_parent

protected

Is a pointer to the parent.

Observe that this pointer may not be up to date after a few applications of the reduction.

Definition at line 454 of file PQNode.h.

◆ m_parentType

template<class T , class X , class Y >

PQNodeType ogdf::PQNode< T, X, Y >::m_parentType

protected

Stores the type of the parent which can be either a P- or Q-node.

Definition at line 436 of file PQNode.h.

◆ m_pertChildCount

template<class T , class X , class Y >

int ogdf::PQNode< T, X, Y >::m_pertChildCount

protected

Stores the number of pertinent children of the node.

Definition at line 439 of file PQNode.h.

◆ m_pertLeafCount

template<class T , class X , class Y >

int ogdf::PQNode< T, X, Y >::m_pertLeafCount

protected

Stores the number of pertinent leaves in the frontier of the node.

Definition at line 442 of file PQNode.h.

◆ m_pointerToInfo

template<class T , class X , class Y >

PQNodeKey<T, X, Y>* ogdf::PQNode< T, X, Y >::m_pointerToInfo

protected

Stores a pointer to the corresponding information of the node.

Definition at line 494 of file PQNode.h.

◆ m_referenceChild

template<class T , class X , class Y >

PQNode<T, X, Y>* ogdf::PQNode< T, X, Y >::m_referenceChild

protected

Stores a pointer to one child, the reference child of the doubly linked cirkular list of children of a P-node.

With the help of this pointer, it is possible to access the children of the P-node

Definition at line 462 of file PQNode.h.

◆ m_referenceParent

template<class T , class X , class Y >

PQNode<T, X, Y>* ogdf::PQNode< T, X, Y >::m_referenceParent

protected

Is a pointer to the parent, in case that the parent is a P-node and the node itself is its reference child.

The pointer is needed in order to identify the reference child among all children of a P-node.

Definition at line 470 of file PQNode.h.

◆ m_rightEndmost

template<class T , class X , class Y >

PQNode<T, X, Y>* ogdf::PQNode< T, X, Y >::m_rightEndmost

protected

Stores the right endmost child of a Q-node.

Definition at line 473 of file PQNode.h.

◆ m_sibLeft

template<class T , class X , class Y >

PQNode<T, X, Y>* ogdf::PQNode< T, X, Y >::m_sibLeft

protected

Stores a pointer ot the left sibling of PQNode.

If PQNode is child of a Q-node and has no left sibling, m_sibLeft is set to 0. If PQNode is child of a P-node, all children of the P-node are linked in a circular list. In the latter case, m_sibLeft is never 0.

Definition at line 482 of file PQNode.h.

◆ m_sibRight

template<class T , class X , class Y >

PQNode<T, X, Y>* ogdf::PQNode< T, X, Y >::m_sibRight

protected

Stores a pointer ot the right sibling of PQNode.

If PQNode is child of a Q-node and has no right sibling, m_sibRight is set to 0. If PQNode is child of a P-node, all children of the P-node are linked in a circular list. In the latter case, m_sibRight is never 0.

Definition at line 491 of file PQNode.h.

◆ partialChildren

template<class T , class X , class Y >

List<PQNode<T, X, Y>*>* ogdf::PQNode< T, X, Y >::partialChildren

protected

Stores all partial children of a node during a reduction.

Definition at line 501 of file PQNode.h.

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

include/ogdf/basic/pqtree/PQBasicKey.h
include/ogdf/basic/pqtree/PQNode.h

OpenGraph DrawingFramework

Public Member Functions

Protected Attributes

Friends

Detailed Description

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

Constructor & Destructor Documentation

◆ PQNode() [1/2]

◆ PQNode() [2/2]

◆ ~PQNode()

Member Function Documentation

◆ changeEndmost()

◆ changeSiblings()

◆ childCount() [1/2]

◆ childCount() [2/2]

◆ endmostChild()

◆ getEndmost() [1/2]

◆ getEndmost() [2/2]

◆ getInternal()

◆ getKey()

◆ getNextSib()

◆ getNodeInfo()

◆ getSib()

◆ identificationNumber()

◆ mark() [1/2]

◆ mark() [2/2]

◆ parent() [1/2]

◆ parent() [2/2]

◆ parentType() [1/2]

◆ parentType() [2/2]

◆ pertChildCount() [1/2]

◆ pertChildCount() [2/2]

◆ putSibling() [1/2]

◆ putSibling() [2/2]

◆ referenceChild()

◆ referenceParent()

◆ setInternal()

◆ setKey()

◆ setNodeInfo()

◆ status() [1/2]

◆ status() [2/2]

◆ type() [1/2]

◆ type() [2/2]

Friends And Related Function Documentation

◆ PQTree< T, X, Y >

Member Data Documentation

◆ fullChildren

◆ m_childCount

◆ m_debugTreeNumber

◆ m_firstFull

◆ m_identificationNumber

◆ m_leftEndmost

◆ m_parent

◆ m_parentType

◆ m_pertChildCount

◆ m_pertLeafCount

◆ m_pointerToInfo

◆ m_referenceChild

◆ m_referenceParent

◆ m_rightEndmost

◆ m_sibLeft

◆ m_sibRight

◆ partialChildren

Open
Graph Drawing
Framework

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