ogdf::booth_lueker::EmbedPQTree Class Reference

#include <ogdf/planarity/booth_lueker/EmbedPQTree.h>

Inheritance diagram for ogdf::booth_lueker::EmbedPQTree:

Public Member Functions
	EmbedPQTree ()
virtual	~EmbedPQTree ()
virtual void	clientDefinedEmptyNode (PQNode< edge, IndInfo *, bool > *nodePtr) override
virtual void	emptyAllPertinentNodes () override
	Cleans up all flags that have been set in the pertinent nodes during the reduction process.
virtual void	getFront (PQNode< edge, IndInfo *, bool > *nodePtr, SListPure< PQBasicKey< edge, IndInfo *, bool > * > &leafKeys)
virtual int	Initialize (SListPure< PlanarLeafKey< IndInfo * > * > &leafKeys)
int	Initialize (SListPure< PQLeafKey< edge, IndInfo *, bool > * > &leafKeys) override
virtual bool	Reduction (SListPure< PlanarLeafKey< IndInfo * > * > &leafKeys)
bool	Reduction (SListPure< PQLeafKey< edge, IndInfo *, bool > * > &leafKeys) override
void	ReplaceRoot (SListPure< PlanarLeafKey< IndInfo * > * > &leafKeys, SListPure< edge > &frontier, SListPure< node > &opposed, SListPure< node > &nonOpposed, node v)
PQNode< edge, IndInfo *, bool > *	scanLeftEndmost (PQNode< edge, IndInfo *, bool > *nodePtr) const
PQNode< edge, IndInfo *, bool > *	scanNextSib (PQNode< edge, IndInfo *, bool > *nodePtr, PQNode< edge, IndInfo *, bool > *other)
PQNode< edge, IndInfo *, bool > *	scanRightEndmost (PQNode< edge, IndInfo *, bool > *nodePtr) const
PQNode< edge, IndInfo *, bool > *	scanSibLeft (PQNode< edge, IndInfo *, bool > *nodePtr) const
PQNode< edge, IndInfo *, bool > *	scanSibRight (PQNode< edge, IndInfo *, bool > *nodePtr) const
Public Member Functions inherited from ogdf::PQTree< edge, IndInfo *, bool >
	PQTree ()
virtual	~PQTree ()
	Destructor.
bool	addNewLeavesToTree (PQInternalNode< edge, IndInfo *, bool > *father, SListPure< PQLeafKey< edge, IndInfo *, bool > * > &leafKeys)
	Adds a set of elements to the already existing set of elements of a PQ-tree.
virtual void	CleanNode (PQNode< edge, IndInfo *, bool > *)
virtual void	Cleanup ()
	Removes the entire PQ-tree.
virtual void	clientDefinedEmptyNode (PQNode< edge, IndInfo *, bool > *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.
void	emptyNode (PQNode< edge, IndInfo *, bool > *nodePtr)
	Cleans up all stacks, flags and pointers of a pertinent node that has been visited during the reduction process.
virtual void	front (PQNode< edge, IndInfo *, bool > *nodePtr, SListPure< PQLeafKey< edge, IndInfo *, bool > * > &leafKeys)
	Returns the keys stored in the leaves of the front of nodePtr.
virtual int	Initialize (SListPure< PQLeafKey< edge, IndInfo *, bool > * > &leafKeys)
	Initializes the PQ-tree with a set of elements.
virtual bool	Reduction (SListPure< PQLeafKey< edge, IndInfo *, bool > * > &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< edge, IndInfo *, bool > *	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 PQNode< edge, IndInfo *, bool > *	clientLeftEndmost (PQNode< edge, IndInfo *, bool > *nodePtr) const override
virtual PQNode< edge, IndInfo *, bool > *	clientNextSib (PQNode< edge, IndInfo *, bool > *nodePtr, PQNode< edge, IndInfo *, bool > *other) const override
virtual const char *	clientPrintStatus (PQNode< edge, IndInfo *, bool > *nodePtr) override
virtual PQNode< edge, IndInfo *, bool > *	clientRightEndmost (PQNode< edge, IndInfo *, bool > *nodePtr) const override
virtual PQNode< edge, IndInfo *, bool > *	clientSibLeft (PQNode< edge, IndInfo *, bool > *nodePtr) const override
virtual PQNode< edge, IndInfo *, bool > *	clientSibRight (PQNode< edge, IndInfo *, bool > *nodePtr) const override
virtual void	front (PQNode< edge, IndInfo *, bool > *nodePtr, SListPure< PQBasicKey< edge, IndInfo *, bool > * > &leafKeys)
void	front (PQNode< edge, IndInfo *, bool > *nodePtr, SListPure< PQLeafKey< edge, IndInfo *, bool > * > &leafKeys) override
Protected Member Functions inherited from ogdf::PQTree< edge, IndInfo *, bool >
virtual bool	addNodeToNewParent (PQNode< edge, IndInfo *, bool > *parent, PQNode< edge, IndInfo *, bool > *child)
	Adds a node child as a child to another node specified in parent.
virtual bool	addNodeToNewParent (PQNode< edge, IndInfo *, bool > *parent, PQNode< edge, IndInfo *, bool > *child, PQNode< edge, IndInfo *, bool > *leftBrother, PQNode< edge, IndInfo *, bool > *rightBrother)
	Adds a node child to the children of another node specified in parent.
virtual bool	Bubble (SListPure< PQLeafKey< edge, IndInfo *, bool > * > &leafKeys)
	Realizes a function described in [Booth].
virtual bool	checkIfOnlyChild (PQNode< edge, IndInfo *, bool > *child, PQNode< edge, IndInfo *, bool > *parent)
	Checks if child is the only child of parent.
virtual PQNode< edge, IndInfo *, bool > *	clientLeftEndmost (PQNode< edge, IndInfo *, bool > *nodePtr) const
virtual PQNode< edge, IndInfo *, bool > *	clientNextSib (PQNode< edge, IndInfo *, bool > *nodePtr, PQNode< edge, IndInfo *, bool > *other) const
virtual int	clientPrintNodeCategorie (PQNode< edge, IndInfo *, bool > *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< edge, IndInfo *, bool > *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< edge, IndInfo *, bool > *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< edge, IndInfo *, bool > *	clientRightEndmost (PQNode< edge, IndInfo *, bool > *nodePtr) const
virtual PQNode< edge, IndInfo *, bool > *	clientSibLeft (PQNode< edge, IndInfo *, bool > *nodePtr) const
virtual PQNode< edge, IndInfo *, bool > *	clientSibRight (PQNode< edge, IndInfo *, bool > *nodePtr) const
virtual void	destroyNode (PQNode< edge, IndInfo *, bool > *nodePtr)
	Marks a node as PQNodeRoot::PQNodeStatus::ToBeDeleted.
virtual void	exchangeNodes (PQNode< edge, IndInfo *, bool > *oldNode, PQNode< edge, IndInfo *, bool > *newNode)
	Replaces the oldNode by the newNode in the tree.
List< PQNode< edge, IndInfo *, bool > * > *	fullChildren (PQNode< edge, IndInfo *, bool > *nodePtr)
virtual void	linkChildrenOfQnode (PQNode< edge, IndInfo *, bool > *installed, PQNode< edge, IndInfo *, bool > *newChild)
	Links the two endmost children of two different Q-nodes via their sibling pointers together.
List< PQNode< edge, IndInfo *, bool > * > *	partialChildren (PQNode< edge, IndInfo *, bool > *nodePtr)
virtual bool	Reduce (SListPure< PQLeafKey< edge, IndInfo *, bool > * > &leafKeys)
	Performs the reduction of the pertinent leaves with the help of the template matchings, designed by Booth and Lueker.
virtual void	removeChildFromSiblings (PQNode< edge, IndInfo *, bool > *nodePtr)
	Removes the node nodePtr from the doubly linked list of its parent.
virtual int	removeNodeFromTree (PQNode< edge, IndInfo *, bool > *parent, PQNode< edge, IndInfo *, bool > *child)
	The objective is to remove a node child from the PQ-tree.
virtual bool	templateL1 (PQNode< edge, IndInfo *, bool > *nodePtr, bool isRoot)
	Template matching for leaves.
virtual bool	templateP1 (PQNode< edge, IndInfo *, bool > *nodePtr, bool isRoot)
	Template matching for P-nodes with only full children.
virtual bool	templateP2 (PQNode< edge, IndInfo *, bool > **nodePtr)
	Template matching for a P-node with full and empty children that is the root of the pertinent subtree.
virtual bool	templateP3 (PQNode< edge, IndInfo *, bool > *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< edge, IndInfo *, bool > **nodePtr)
	Template matching for a P-node with full, empty and exactly one partial children.
virtual bool	templateP5 (PQNode< edge, IndInfo *, bool > *nodePtr)
	Template matching for a P-node with full, empty children and exactly one partial child.
virtual bool	templateP6 (PQNode< edge, IndInfo *, bool > **nodePtr)
	Template matching for a P-node with full, empty and exactly two partial children.
virtual bool	templateQ1 (PQNode< edge, IndInfo *, bool > *nodePtr, bool isRoot)
	Template matching for Q-nodes with only full children.
virtual bool	templateQ2 (PQNode< edge, IndInfo *, bool > *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< edge, IndInfo *, bool > *nodePtr)

Private Member Functions
void	ReplaceFullRoot (SListPure< PlanarLeafKey< IndInfo * > * > &leafKeys, SListPure< PQBasicKey< edge, IndInfo *, bool > * > &frontier, node v, bool addIndicator=false, PQNode< edge, IndInfo *, bool > *opposite=nullptr)
void	ReplacePartialRoot (SListPure< PlanarLeafKey< IndInfo * > * > &leafKeys, SListPure< PQBasicKey< edge, IndInfo *, bool > * > &frontier, node v)

Additional Inherited Members
Protected Attributes inherited from ogdf::PQTree< edge, IndInfo *, bool >
int	m_identificationNumber
	Stores the total number of nodes that have been allocated.
int	m_numberOfLeaves
	Stores the number of leaves.
List< PQNode< edge, IndInfo *, bool > * > *	m_pertinentNodes
	Stores all nodes that have been marked PQNodeRoot::PQNodeStatus::Full or PQNodeRoot::PQNodeStatus::Partial during a reduction.
PQNode< edge, IndInfo *, bool > *	m_pertinentRoot
	a pointer to the root of the pertinent subtree.
PQNode< edge, IndInfo *, bool > *	m_pseudoRoot
	a pointer to the virtual root of the pertinent subtree, in case that the pertinent root cannot be detected.
PQNode< edge, IndInfo *, bool > *	m_root
	a pointer to the root of the $PQ$-tree.

Detailed Description

Definition at line 55 of file EmbedPQTree.h.

Constructor & Destructor Documentation

EmbedPQTree()

ogdf::booth_lueker::EmbedPQTree::EmbedPQTree ( )

inline

Definition at line 57 of file EmbedPQTree.h.

~EmbedPQTree()

virtual ogdf::booth_lueker::EmbedPQTree::~EmbedPQTree ( )

inlinevirtual

Definition at line 59 of file EmbedPQTree.h.

Member Function Documentation

clientDefinedEmptyNode()

virtual void ogdf::booth_lueker::EmbedPQTree::clientDefinedEmptyNode ( PQNode< edge, IndInfo *, bool > *  nodePtr )

overridevirtual

clientLeftEndmost()

virtual PQNode< edge, IndInfo *, bool > * ogdf::booth_lueker::EmbedPQTree::clientLeftEndmost ( PQNode< edge, IndInfo *, bool > *  nodePtr ) const

overrideprotectedvirtual

clientNextSib()

virtual PQNode< edge, IndInfo *, bool > * ogdf::booth_lueker::EmbedPQTree::clientNextSib ( PQNode< edge, IndInfo *, bool > *  nodePtr, PQNode< edge, IndInfo *, bool > *  other  ) const

overrideprotectedvirtual

clientPrintStatus()

virtual const char * ogdf::booth_lueker::EmbedPQTree::clientPrintStatus ( PQNode< edge, IndInfo *, bool > *  nodePtr )

overrideprotectedvirtual

clientRightEndmost()

virtual PQNode< edge, IndInfo *, bool > * ogdf::booth_lueker::EmbedPQTree::clientRightEndmost ( PQNode< edge, IndInfo *, bool > *  nodePtr ) const

overrideprotectedvirtual

clientSibLeft()

virtual PQNode< edge, IndInfo *, bool > * ogdf::booth_lueker::EmbedPQTree::clientSibLeft ( PQNode< edge, IndInfo *, bool > *  nodePtr ) const

overrideprotectedvirtual

clientSibRight()

virtual PQNode< edge, IndInfo *, bool > * ogdf::booth_lueker::EmbedPQTree::clientSibRight ( PQNode< edge, IndInfo *, bool > *  nodePtr ) const

overrideprotectedvirtual

emptyAllPertinentNodes()

virtual void ogdf::booth_lueker::EmbedPQTree::emptyAllPertinentNodes ( )

overridevirtual

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 from ogdf::PQTree< edge, IndInfo *, bool >.

front() [1/2]

virtual void ogdf::booth_lueker::EmbedPQTree::front ( PQNode< edge, IndInfo *, bool > *  nodePtr, SListPure< PQBasicKey< edge, IndInfo *, bool > * > &  leafKeys  )

protectedvirtual

front() [2/2]

void ogdf::booth_lueker::EmbedPQTree::front ( PQNode< edge, IndInfo *, bool > *  nodePtr, SListPure< PQLeafKey< edge, IndInfo *, bool > * > &  leafKeys  )

inlineoverrideprotected

Definition at line 124 of file EmbedPQTree.h.

getFront()

virtual void ogdf::booth_lueker::EmbedPQTree::getFront ( PQNode< edge, IndInfo *, bool > *  nodePtr, SListPure< PQBasicKey< edge, IndInfo *, bool > * > &  leafKeys  )

virtual

Initialize() [1/2]

virtual int ogdf::booth_lueker::EmbedPQTree::Initialize ( SListPure< PlanarLeafKey< IndInfo * > * > &  leafKeys )

virtual

Initialize() [2/2]

int ogdf::booth_lueker::EmbedPQTree::Initialize ( SListPure< PQLeafKey< edge, IndInfo *, bool > * > &  leafKeys )

inlineoverride

Definition at line 67 of file EmbedPQTree.h.

Reduction() [1/2]

virtual bool ogdf::booth_lueker::EmbedPQTree::Reduction ( SListPure< PlanarLeafKey< IndInfo * > * > &  leafKeys )

virtual

Reduction() [2/2]

bool ogdf::booth_lueker::EmbedPQTree::Reduction ( SListPure< PQLeafKey< edge, IndInfo *, bool > * > &  leafKeys )

inlineoverride

Definition at line 76 of file EmbedPQTree.h.

ReplaceFullRoot()

void ogdf::booth_lueker::EmbedPQTree::ReplaceFullRoot ( SListPure< PlanarLeafKey< IndInfo * > * > &  leafKeys, SListPure< PQBasicKey< edge, IndInfo *, bool > * > &  frontier, node  v, bool  addIndicator = false, PQNode< edge, IndInfo *, bool > *  opposite = nullptr  )

private

ReplacePartialRoot()

void ogdf::booth_lueker::EmbedPQTree::ReplacePartialRoot ( SListPure< PlanarLeafKey< IndInfo * > * > &  leafKeys, SListPure< PQBasicKey< edge, IndInfo *, bool > * > &  frontier, node  v  )

private

ReplaceRoot()

void ogdf::booth_lueker::EmbedPQTree::ReplaceRoot	(	SListPure< PlanarLeafKey< IndInfo * > * > &	leafKeys,
		SListPure< edge > &	frontier,
		SListPure< node > &	opposed,
		SListPure< node > &	nonOpposed,
		node	v
	)

scanLeftEndmost()

PQNode< edge, IndInfo *, bool > * ogdf::booth_lueker::EmbedPQTree::scanLeftEndmost ( PQNode< edge, IndInfo *, bool > *  nodePtr ) const

inline

Definition at line 88 of file EmbedPQTree.h.

scanNextSib()

PQNode< edge, IndInfo *, bool > * ogdf::booth_lueker::EmbedPQTree::scanNextSib ( PQNode< edge, IndInfo *, bool > *  nodePtr, PQNode< edge, IndInfo *, bool > *  other  )

inline

Definition at line 96 of file EmbedPQTree.h.

scanRightEndmost()

PQNode< edge, IndInfo *, bool > * ogdf::booth_lueker::EmbedPQTree::scanRightEndmost ( PQNode< edge, IndInfo *, bool > *  nodePtr ) const

inline

Definition at line 92 of file EmbedPQTree.h.

scanSibLeft()

PQNode< edge, IndInfo *, bool > * ogdf::booth_lueker::EmbedPQTree::scanSibLeft ( PQNode< edge, IndInfo *, bool > *  nodePtr ) const

inline

Definition at line 80 of file EmbedPQTree.h.

scanSibRight()

PQNode< edge, IndInfo *, bool > * ogdf::booth_lueker::EmbedPQTree::scanSibRight ( PQNode< edge, IndInfo *, bool > *  nodePtr ) const

inline

Definition at line 84 of file EmbedPQTree.h.

---

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

• include/ogdf/planarity/booth_lueker/EmbedPQTree.h