|
| | PlanarSubgraphPQTree () |
| |
| virtual | ~PlanarSubgraphPQTree () |
| |
| virtual int | Initialize (SListPure< PlanarLeafKey * > &leafKeys) |
| | Initializes a new PQ-tree with a set of leaves.
|
| |
| int | Initialize (SListPure< PQLeafKey< edge, whaInfo *, bool > * > &leafKeys) override |
| |
| virtual bool | Reduction (SListPure< PlanarLeafKey * > &leafKeys, SList< PQLeafKey< edge, whaInfo *, bool > * > &eliminatedKeys) |
| | Reduces a set of leaves.
|
| |
| bool | Reduction (SListPure< PQLeafKey< edge, whaInfo *, bool > * > &leafKeys) override |
| |
| void | ReplaceRoot (SListPure< PlanarLeafKey * > &leafKeys) |
| | Replaces the pertinent subtree by a set of new leaves.
|
| |
| | 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.
|
| |
| virtual void | clientDefinedEmptyNode (PQNode< edge, whaInfo *, bool > *nodePtr) |
| | Does a clean up of a node. Called by emptyAllPertinentNodes.
|
| |
| 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.
|
| |
| virtual void | emptyAllPertinentNodes () |
| | Does a clean up after a reduction.
|
| |
| | PQTree () |
| |
| virtual | ~PQTree () |
| | Destructor.
|
| |
| bool | addNewLeavesToTree (PQInternalNode< T, X, Y > *father, SListPure< PQLeafKey< T, X, Y > * > &leafKeys) |
| | Adds a set of elements to the already existing set of elements of a PQ-tree.
|
| |
| virtual void | CleanNode (PQNode< T, X, Y > *) |
| |
| virtual void | Cleanup () |
| | Removes the entire PQ-tree.
|
| |
| virtual void | clientDefinedEmptyNode (PQNode< T, X, Y > *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< T, X, Y > *nodePtr) |
| | Cleans up all stacks, flags and pointers of a pertinent node that has been visited during the reduction process.
|
| |
| virtual void | front (PQNode< T, X, Y > *nodePtr, SListPure< PQLeafKey< T, X, Y > * > &leafKeys) |
| | Returns the keys stored in the leaves of the front of nodePtr.
|
| |
| virtual int | Initialize (SListPure< PQLeafKey< T, X, Y > * > &leafKeys) |
| | Initializes the PQ-tree with a set of elements.
|
| |
| virtual bool | Reduction (SListPure< PQLeafKey< T, X, Y > * > &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< T, X, Y > * | 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) |
| |
|
| virtual bool | Bubble (SListPure< PQLeafKey< edge, whaInfo *, bool > * > &leafKeys) |
| | The function Bubble() is an overloaded function of the base template class PQTree.
|
| |
| PQNode< edge, whaInfo *, bool > * | GetParent (PQNode< edge, whaInfo *, bool > *nodePtr) |
| | Computes for the node nodePtr its valid parent in the PQ-tree.
|
| |
| virtual bool | addNodeToNewParent (PQNode< T, X, Y > *parent, PQNode< T, X, Y > *child) |
| | Adds a node child as a child to another node specified in parent.
|
| |
| virtual bool | addNodeToNewParent (PQNode< T, X, Y > *parent, PQNode< T, X, Y > *child, PQNode< T, X, Y > *leftBrother, PQNode< T, X, Y > *rightBrother) |
| | Adds a node child to the children of another node specified in parent.
|
| |
| virtual bool | Bubble (SListPure< PQLeafKey< T, X, Y > * > &leafKeys) |
| | Realizes a function described in [Booth].
|
| |
| virtual bool | checkIfOnlyChild (PQNode< T, X, Y > *child, PQNode< T, X, Y > *parent) |
| | Checks if child is the only child of parent.
|
| |
| virtual PQNode< T, X, Y > * | clientLeftEndmost (PQNode< T, X, Y > *nodePtr) const |
| |
| virtual PQNode< T, X, Y > * | clientNextSib (PQNode< T, X, Y > *nodePtr, PQNode< T, X, Y > *other) const |
| |
| virtual int | clientPrintNodeCategorie (PQNode< T, X, Y > *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< T, X, Y > *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< T, X, Y > *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< T, X, Y > * | clientRightEndmost (PQNode< T, X, Y > *nodePtr) const |
| |
| virtual PQNode< T, X, Y > * | clientSibLeft (PQNode< T, X, Y > *nodePtr) const |
| |
| virtual PQNode< T, X, Y > * | clientSibRight (PQNode< T, X, Y > *nodePtr) const |
| |
| virtual void | destroyNode (PQNode< T, X, Y > *nodePtr) |
| | Marks a node as PQNodeRoot::PQNodeStatus::ToBeDeleted.
|
| |
| virtual void | exchangeNodes (PQNode< T, X, Y > *oldNode, PQNode< T, X, Y > *newNode) |
| | Replaces the oldNode by the newNode in the tree.
|
| |
| List< PQNode< T, X, Y > * > * | fullChildren (PQNode< T, X, Y > *nodePtr) |
| |
| virtual void | linkChildrenOfQnode (PQNode< T, X, Y > *installed, PQNode< T, X, Y > *newChild) |
| | Links the two endmost children of two different Q-nodes via their sibling pointers together.
|
| |
| List< PQNode< T, X, Y > * > * | partialChildren (PQNode< T, X, Y > *nodePtr) |
| |
| virtual bool | Reduce (SListPure< PQLeafKey< T, X, Y > * > &leafKeys) |
| | Performs the reduction of the pertinent leaves with the help of the template matchings, designed by Booth and Lueker.
|
| |
| virtual void | removeChildFromSiblings (PQNode< T, X, Y > *nodePtr) |
| | Removes the node nodePtr from the doubly linked list of its parent.
|
| |
| virtual int | removeNodeFromTree (PQNode< T, X, Y > *parent, PQNode< T, X, Y > *child) |
| | The objective is to remove a node child from the PQ-tree.
|
| |
| virtual bool | templateL1 (PQNode< T, X, Y > *nodePtr, bool isRoot) |
| | Template matching for leaves.
|
| |
| virtual bool | templateP1 (PQNode< T, X, Y > *nodePtr, bool isRoot) |
| | Template matching for P-nodes with only full children.
|
| |
| virtual bool | templateP2 (PQNode< T, X, Y > **nodePtr) |
| | Template matching for a P-node with full and empty children that is the root of the pertinent subtree.
|
| |
| virtual bool | templateP3 (PQNode< T, X, Y > *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< T, X, Y > **nodePtr) |
| | Template matching for a P-node with full, empty and exactly one partial children.
|
| |
| virtual bool | templateP5 (PQNode< T, X, Y > *nodePtr) |
| | Template matching for a P-node with full, empty children and exactly one partial child.
|
| |
| virtual bool | templateP6 (PQNode< T, X, Y > **nodePtr) |
| | Template matching for a P-node with full, empty and exactly two partial children.
|
| |
| virtual bool | templateQ1 (PQNode< T, X, Y > *nodePtr, bool isRoot) |
| | Template matching for Q-nodes with only full children.
|
| |
| virtual bool | templateQ2 (PQNode< T, X, Y > *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< T, X, Y > *nodePtr) |
| |
| SListPure< PQNode< edge, whaInfo *, bool > * > | cleanUp |
| | Used to store all pertinent Nodes of the pertinent subtree before removing the minimal pertinent subsequence.
|
| |
| SListPure< PQNode< edge, whaInfo *, bool > * > | eliminatedNodes |
| | Used to store all eliminated nodes (status == PQNodeRoot::PQNodeStatus::Eliminated) of the PQTree.
|
| |
| int | m_identificationNumber |
| | Stores the total number of nodes that have been allocated.
|
| |
| int | m_numberOfLeaves |
| | Stores the number of leaves.
|
| |
| List< PQNode< T, X, Y > * > * | m_pertinentNodes |
| | Stores all nodes that have been marked PQNodeRoot::PQNodeStatus::Full or PQNodeRoot::PQNodeStatus::Partial during a reduction.
|
| |
| PQNode< T, X, Y > * | m_pertinentRoot |
| | a pointer to the root of the pertinent subtree.
|
| |
| PQNode< T, X, Y > * | m_pseudoRoot |
| | a pointer to the virtual root of the pertinent subtree, in case that the pertinent root cannot be detected.
|
| |
| PQNode< T, X, Y > * | m_root |
| | a pointer to the root of the $PQ$-tree.
|
| |
Inheritance diagram for ogdf::PlanarSubgraphPQTree:
