#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 43 of file EmbedPQTree.h.

Constructor & Destructor Documentation

◆ EmbedPQTree()

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

inline

Definition at line 45 of file EmbedPQTree.h.

◆ ~EmbedPQTree()

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

inlinevirtual

Definition at line 47 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 112 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 55 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 64 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 76 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 84 of file EmbedPQTree.h.

◆ scanRightEndmost()

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

inline

Definition at line 80 of file EmbedPQTree.h.

◆ scanSibLeft()

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

inline

Definition at line 68 of file EmbedPQTree.h.

◆ scanSibRight()

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

inline

Definition at line 72 of file EmbedPQTree.h.

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

include/ogdf/planarity/booth_lueker/EmbedPQTree.h

OpenGraph DrawingFramework

Public Member Functions

Protected Member Functions

Private Member Functions

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ EmbedPQTree()

◆ ~EmbedPQTree()

Member Function Documentation

◆ clientDefinedEmptyNode()

◆ clientLeftEndmost()

◆ clientNextSib()

◆ clientPrintStatus()

◆ clientRightEndmost()

◆ clientSibLeft()

◆ clientSibRight()

◆ emptyAllPertinentNodes()

◆ front() [1/2]

◆ front() [2/2]

◆ getFront()

◆ Initialize() [1/2]

◆ Initialize() [2/2]

◆ Reduction() [1/2]

◆ Reduction() [2/2]

◆ ReplaceFullRoot()

◆ ReplacePartialRoot()

◆ ReplaceRoot()

◆ scanLeftEndmost()

◆ scanNextSib()

◆ scanRightEndmost()

◆ scanSibLeft()

◆ scanSibRight()

Open
Graph Drawing
Framework