Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
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 charclientPrintStatus (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 charclientPrintStatus (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 charclientPrintType (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: