ogdf::PlanarSubgraphPQTree Class Reference

#include <ogdf/planarity/planar_subgraph_fast/PlanarSubgraphPQTree.h>

Inheritance diagram for ogdf::PlanarSubgraphPQTree:

Public Types
using	PlanarLeafKey = booth_lueker::PlanarLeafKey< whaInfo * >

Public Member Functions
	PlanarSubgraphPQTree ()
virtual	~PlanarSubgraphPQTree ()
virtual int	Initialize (SListPure< PlanarLeafKey * > &leafKeys)
	Initializes a new PQ-tree with a set of leaves. More...
int	Initialize (SListPure< PQLeafKey< edge, whaInfo *, bool > * > &leafKeys) override
	Initializes the PQ-tree with a set of elements. More...
virtual bool	Reduction (SListPure< PlanarLeafKey * > &leafKeys, SList< PQLeafKey< edge, whaInfo *, bool > * > &eliminatedKeys)
	Reduces a set of leaves. More...
bool	Reduction (SListPure< PQLeafKey< edge, whaInfo *, bool > * > &leafKeys) override
	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. More...
void	ReplaceRoot (SListPure< PlanarLeafKey * > &leafKeys)
	Replaces the pertinent subtree by a set of new leaves. More...
Public Member Functions inherited from ogdf::MaxSequencePQTree< edge, bool >
	MaxSequencePQTree ()
	~MaxSequencePQTree ()
virtual void	CleanNode (PQNode< edge, whaInfo *, bool > *nodePtr)
	Frees the memory allocated for the node information class of a node in the PQTree. More...
virtual void	clientDefinedEmptyNode (PQNode< edge, whaInfo *, bool > *nodePtr)
	Does a clean up of a node. Called by emptyAllPertinentNodes. More...
int	determineMinRemoveSequence (SListPure< PQLeafKey< edge, whaInfo *, bool > * > &leafKeys, SList< PQLeafKey< edge, whaInfo *, bool > * > &eliminatedKeys)
	Computes the maximal pertinent sequence S' of elements of the set S, that can be reduced in a PQ-tree. More...
virtual void	emptyAllPertinentNodes ()
	Does a clean up after a reduction. More...
Public Member Functions inherited from ogdf::PQTree< edge, whaInfo *, bool >
	PQTree ()
virtual	~PQTree ()
	Destructor. More...
bool	addNewLeavesToTree (PQInternalNode< edge, whaInfo *, bool > *father, SListPure< PQLeafKey< edge, whaInfo *, bool > * > &leafKeys)
	Adds a set of elements to the already existing set of elements of a PQ-tree. More...
virtual void	Cleanup ()
	Removes the entire PQ-tree. More...
void	emptyNode (PQNode< edge, whaInfo *, bool > *nodePtr)
	Cleans up all stacks, flags and pointers of a pertinent node that has been visited during the reduction process. More...
virtual void	front (PQNode< edge, whaInfo *, bool > *nodePtr, SListPure< PQLeafKey< edge, whaInfo *, bool > * > &leafKeys)
	Returns the keys stored in the leaves of the front of nodePtr. More...
PQNode< edge, whaInfo *, bool > *	root () const
	Returns a pointer of the root node of the PQTree. More...
void	writeGML (const char *fileName)
	The function writeGML() prints the PQ-tree in the GML fileformat. More...
void	writeGML (std::ostream &os)

Private Member Functions
void	removeEliminatedLeaves (SList< PQLeafKey< edge, whaInfo *, bool > * > &eliminatedKeys)
	Removes the leaves that have been marked for elimination from the PQ-tree. More...
void	ReplaceFullRoot (SListPure< PlanarLeafKey * > &leafKeys)
	Replaces a pertinet subtree by a set of new leaves if the root is full. More...
void	ReplacePartialRoot (SListPure< PlanarLeafKey * > &leafKeys)
	Replaces a pertinet subtree by a set of new leaves if the root is partial. More...

Additional Inherited Members
Protected Member Functions inherited from ogdf::MaxSequencePQTree< edge, bool >
virtual bool	Bubble (SListPure< PQLeafKey< edge, whaInfo *, bool > * > &leafKeys)
	The function Bubble() is an overloaded function of the base template class PQTree. More...
PQNode< edge, whaInfo *, bool > *	GetParent (PQNode< edge, whaInfo *, bool > *nodePtr)
	Computes for the node nodePtr its valid parent in the PQ-tree. More...
Protected Member Functions inherited from ogdf::PQTree< edge, whaInfo *, bool >
virtual bool	addNodeToNewParent (PQNode< edge, whaInfo *, bool > *parent, PQNode< edge, whaInfo *, bool > *child)
	Adds a node child as a child to another node specified in parent. More...
virtual bool	addNodeToNewParent (PQNode< edge, whaInfo *, bool > *parent, PQNode< edge, whaInfo *, bool > *child, PQNode< edge, whaInfo *, bool > *leftBrother, PQNode< edge, whaInfo *, bool > *rightBrother)
	Adds a node child to the children of another node specified in parent. More...
virtual bool	checkIfOnlyChild (PQNode< edge, whaInfo *, bool > *child, PQNode< edge, whaInfo *, bool > *parent)
	Checks if child is the only child of parent. More...
virtual PQNode< edge, whaInfo *, bool > *	clientLeftEndmost (PQNode< edge, whaInfo *, bool > *nodePtr) const
virtual PQNode< edge, whaInfo *, bool > *	clientNextSib (PQNode< edge, whaInfo *, bool > *nodePtr, PQNode< edge, whaInfo *, bool > *other) const
virtual int	clientPrintNodeCategorie (PQNode< edge, whaInfo *, 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. More...
virtual const char *	clientPrintStatus (PQNode< edge, whaInfo *, 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. More...
virtual const char *	clientPrintType (PQNode< edge, whaInfo *, 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. More...
virtual PQNode< edge, whaInfo *, bool > *	clientRightEndmost (PQNode< edge, whaInfo *, bool > *nodePtr) const
virtual PQNode< edge, whaInfo *, bool > *	clientSibLeft (PQNode< edge, whaInfo *, bool > *nodePtr) const
virtual PQNode< edge, whaInfo *, bool > *	clientSibRight (PQNode< edge, whaInfo *, bool > *nodePtr) const
virtual void	destroyNode (PQNode< edge, whaInfo *, bool > *nodePtr)
	Marks a node as PQNodeRoot::PQNodeStatus::ToBeDeleted. More...
virtual void	exchangeNodes (PQNode< edge, whaInfo *, bool > *oldNode, PQNode< edge, whaInfo *, bool > *newNode)
	Replaces the oldNode by the newNode in the tree. More...
List< PQNode< edge, whaInfo *, bool > * > *	fullChildren (PQNode< edge, whaInfo *, bool > *nodePtr)
virtual void	linkChildrenOfQnode (PQNode< edge, whaInfo *, bool > *installed, PQNode< edge, whaInfo *, bool > *newChild)
	Links the two endmost children of two different Q-nodes via their sibling pointers together. More...
List< PQNode< edge, whaInfo *, bool > * > *	partialChildren (PQNode< edge, whaInfo *, bool > *nodePtr)
virtual bool	Reduce (SListPure< PQLeafKey< edge, whaInfo *, bool > * > &leafKeys)
	Performs the reduction of the pertinent leaves with the help of the template matchings, designed by Booth and Lueker. More...
virtual void	removeChildFromSiblings (PQNode< edge, whaInfo *, bool > *nodePtr)
	Removes the node nodePtr from the doubly linked list of its parent. More...
virtual int	removeNodeFromTree (PQNode< edge, whaInfo *, bool > *parent, PQNode< edge, whaInfo *, bool > *child)
	The objective is to remove a node child from the PQ-tree. More...
virtual bool	templateL1 (PQNode< edge, whaInfo *, bool > *nodePtr, bool isRoot)
	Template matching for leaves. More...
virtual bool	templateP1 (PQNode< edge, whaInfo *, bool > *nodePtr, bool isRoot)
	Template matching for P-nodes with only full children. More...
virtual bool	templateP2 (PQNode< edge, whaInfo *, bool > **nodePtr)
	Template matching for a P-node with full and empty children that is the root of the pertinent subtree. More...
virtual bool	templateP3 (PQNode< edge, whaInfo *, bool > *nodePtr)
	Template matching for a P-node with full and empty children that is not the root of the pertinent subtree. More...
virtual bool	templateP4 (PQNode< edge, whaInfo *, bool > **nodePtr)
	Template matching for a P-node with full, empty and exactly one partial children. More...
virtual bool	templateP5 (PQNode< edge, whaInfo *, bool > *nodePtr)
	Template matching for a P-node with full, empty children and exactly one partial child. More...
virtual bool	templateP6 (PQNode< edge, whaInfo *, bool > **nodePtr)
	Template matching for a P-node with full, empty and exactly two partial children. More...
virtual bool	templateQ1 (PQNode< edge, whaInfo *, bool > *nodePtr, bool isRoot)
	Template matching for Q-nodes with only full children. More...
virtual bool	templateQ2 (PQNode< edge, whaInfo *, bool > *nodePtr, bool isRoot)
	Template matching for Q-nodes with a pertinent sequence of children on one side of the Q-node. More...
virtual bool	templateQ3 (PQNode< edge, whaInfo *, bool > *nodePtr)
Protected Attributes inherited from ogdf::MaxSequencePQTree< edge, bool >
SListPure< PQNode< edge, whaInfo *, bool > * >	cleanUp
	Used to store all pertinent Nodes of the pertinent subtree before removing the minimal pertinent subsequence. More...
SListPure< PQNode< edge, whaInfo *, bool > * >	eliminatedNodes
	Used to store all eliminated nodes (status == PQNodeRoot::PQNodeStatus::Eliminated) of the PQTree. More...
Protected Attributes inherited from ogdf::PQTree< edge, whaInfo *, bool >
int	m_identificationNumber
	Stores the total number of nodes that have been allocated. More...
int	m_numberOfLeaves
	Stores the number of leaves. More...
List< PQNode< edge, whaInfo *, bool > * > *	m_pertinentNodes
	Stores all nodes that have been marked PQNodeRoot::PQNodeStatus::Full or PQNodeRoot::PQNodeStatus::Partial during a reduction. More...
PQNode< edge, whaInfo *, bool > *	m_pertinentRoot
	a pointer to the root of the pertinent subtree. More...
PQNode< edge, whaInfo *, bool > *	m_pseudoRoot
	a pointer to the virtual root of the pertinent subtree, in case that the pertinent root cannot be detected. More...
PQNode< edge, whaInfo *, bool > *	m_root
	a pointer to the root of the $PQ$-tree. More...

Detailed Description

Definition at line 52 of file PlanarSubgraphPQTree.h.

Member Typedef Documentation

PlanarLeafKey

using ogdf::PlanarSubgraphPQTree::PlanarLeafKey = booth_lueker::PlanarLeafKey<whaInfo*>

Definition at line 54 of file PlanarSubgraphPQTree.h.

Constructor & Destructor Documentation

PlanarSubgraphPQTree()

ogdf::PlanarSubgraphPQTree::PlanarSubgraphPQTree ( )

inline

Definition at line 56 of file PlanarSubgraphPQTree.h.

~PlanarSubgraphPQTree()

virtual ogdf::PlanarSubgraphPQTree::~PlanarSubgraphPQTree ( )

inlinevirtual

Definition at line 58 of file PlanarSubgraphPQTree.h.

Member Function Documentation

Initialize() [1/2]

virtual int ogdf::PlanarSubgraphPQTree::Initialize ( SListPure< PlanarLeafKey * > &  leafKeys )

virtual

Initializes a new PQ-tree with a set of leaves.

Initialize() [2/2]

int ogdf::PlanarSubgraphPQTree::Initialize ( SListPure< PQLeafKey< edge, whaInfo *, bool > * > &  leafKeys )

inlineoverridevirtual

Initializes the PQ-tree with a set of elements.

These elements have to be template classes of the class template PQLeafKey and are handed to the function in an array leafKeys. The function constructs the universal PQ-tree. If the numberOfElements > 1, the universal PQ-tree consists of one P-node as root (stored in m_root) and all leaves gathered underneath the P-node, symbolizing all kinds of permutations. If numberOfElements = 1, the universal PQ-tree consists of a single PQLeaf, being the root of the tree.

Observe that the first element has to be stored in leafKeys[0] and the last one in leafKeys[numberOfElements-1].

Returns

1 if the initialization of the PQ-tree was successful.

Reimplemented from ogdf::PQTree< edge, whaInfo *, bool >.

Definition at line 63 of file PlanarSubgraphPQTree.h.

Reduction() [1/2]

virtual bool ogdf::PlanarSubgraphPQTree::Reduction ( SListPure< PlanarLeafKey * > &  leafKeys, SList< PQLeafKey< edge, whaInfo *, bool > * > &  eliminatedKeys  )

virtual

Reduces a set of leaves.

Reduction() [2/2]

bool ogdf::PlanarSubgraphPQTree::Reduction ( SListPure< PQLeafKey< edge, whaInfo *, bool > * > &  leafKeys )

inlineoverridevirtual

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.

If there exists such a permutation, the PQ-tree is reduced and Reduction() returns 1.

This function gets a list leafKeys of pointers to elements of type PQLeafKey, representing all elements of S.

Reimplemented from ogdf::PQTree< edge, whaInfo *, bool >.

Definition at line 74 of file PlanarSubgraphPQTree.h.

removeEliminatedLeaves()

void ogdf::PlanarSubgraphPQTree::removeEliminatedLeaves ( SList< PQLeafKey< edge, whaInfo *, bool > * > &  eliminatedKeys )

private

Removes the leaves that have been marked for elimination from the PQ-tree.

This function handles the difficult task of cleaning up after every reduction.

After a reduction is complete, different kind of garbage has to be handled.

• Pertinent leaves that are not in the maximal pertinent sequence. from the $PQ$-tree in order to get it reducable have to be deleted.
• The memory of some pertinent nodes, that have only pertinent leaves not beeing in the maximal pertinent sequence in their frontier has to be freed.
• Pertinent nodes that have only one child left after the removal of pertinent leaves not beeing in the maximal pertinent sequence have to be deleted.
• The memory of all full nodes has to be freed, since the complete pertinent subtree is replaced by a $P$-node after the reduction.
• Nodes, that have been removed during the call of the function [[Reduce]] of the base class template [[PQTree]] from the $PQ$-tree have to be kept but marked as nonexisting.

ReplaceFullRoot()

void ogdf::PlanarSubgraphPQTree::ReplaceFullRoot ( SListPure< PlanarLeafKey * > &  leafKeys )

private

Replaces a pertinet subtree by a set of new leaves if the root is full.

ReplacePartialRoot()

void ogdf::PlanarSubgraphPQTree::ReplacePartialRoot ( SListPure< PlanarLeafKey * > &  leafKeys )

private

Replaces a pertinet subtree by a set of new leaves if the root is partial.

ReplaceRoot()

void ogdf::PlanarSubgraphPQTree::ReplaceRoot

(

SListPure< PlanarLeafKey * > &

leafKeys

)

Replaces the pertinent subtree by a set of new leaves.

---

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

• include/ogdf/planarity/planar_subgraph_fast/PlanarSubgraphPQTree.h