Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

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 46 of file PlanarSubgraphPQTree.h.

Member Typedef Documentation

◆ PlanarLeafKey

Constructor & Destructor Documentation

◆ PlanarSubgraphPQTree()

ogdf::PlanarSubgraphPQTree::PlanarSubgraphPQTree ( )
inline

Definition at line 50 of file PlanarSubgraphPQTree.h.

◆ ~PlanarSubgraphPQTree()

virtual ogdf::PlanarSubgraphPQTree::~PlanarSubgraphPQTree ( )
inlinevirtual

Definition at line 52 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 57 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 69 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: