MaxSequencePQTree.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/ArrayBuffer.h>
#include <ogdf/basic/List.h>
#include <ogdf/basic/PQTree.h>
#include <ogdf/basic/Queue.h>
#include <ogdf/basic/SList.h>
#include <ogdf/basic/basic.h>
#include <ogdf/basic/pqtree/PQNode.h>
#include <ogdf/basic/pqtree/PQNodeKey.h>
#include <ogdf/basic/pqtree/PQNodeRoot.h>
#include <ogdf/planarity/planar_subgraph_fast/whaInfo.h>
 
namespace ogdf {
template<class T, class X, class Y>
class PQLeafKey;
 
template<class T, class Y>
class MaxSequencePQTree : public PQTree<T, whaInfo*, Y> {
public:
    using PQTree<T, whaInfo*, Y>::emptyNode;
 
    MaxSequencePQTree() : PQTree<T, whaInfo*, Y>() { }
 
    ~MaxSequencePQTree() {
        while (!eliminatedNodes.empty()) {
            PQNode<T, whaInfo*, Y>* nodePtr = eliminatedNodes.popFrontRet();
            CleanNode(nodePtr);
            delete nodePtr;
        }
    }
 
    virtual void CleanNode(PQNode<T, whaInfo*, Y>* nodePtr);
 
 
    virtual void clientDefinedEmptyNode(PQNode<T, whaInfo*, Y>* nodePtr);
 
 
    virtual void emptyAllPertinentNodes();
 
    int determineMinRemoveSequence(SListPure<PQLeafKey<T, whaInfo*, Y>*>& leafKeys,
            SList<PQLeafKey<T, whaInfo*, Y>*>& eliminatedKeys);
 
protected:
    using PQTree<T, whaInfo*, Y>::fullChildren;
    using PQTree<T, whaInfo*, Y>::partialChildren;
 
    virtual bool Bubble(SListPure<PQLeafKey<T, whaInfo*, Y>*>& leafKeys);
 
    PQNode<T, whaInfo*, Y>* GetParent(PQNode<T, whaInfo*, Y>* nodePtr);
 
    SListPure<PQNode<T, whaInfo*, Y>*> cleanUp;
 
    SListPure<PQNode<T, whaInfo*, Y>*> eliminatedNodes;
 
private:
    void findMinWHASequence(ArrayBuffer<PQNode<T, whaInfo*, Y>*>& archiv,
            SList<PQLeafKey<T, whaInfo*, Y>*>& eliminatedKeys);
 
    int setHchild(PQNode<T, whaInfo*, Y>* hChild1);
 
    int setAchildren(PQNode<T, whaInfo*, Y>* hChild2, PQNode<T, whaInfo*, Y>* hChild2Sib);
 
    void markPertinentChildren(PQNode<T, whaInfo*, Y>* nodePtr, PQNodeRoot::PQNodeStatus label,
            whaType deleteType);
 
    void haNumPnode(PQNode<T, whaInfo*, Y>* nodePtr);
 
    void haNumQnode(PQNode<T, whaInfo*, Y>* nodePtr);
 
    void aNumQnode(PQNode<T, whaInfo*, Y>* nodePtr, int sumAllW);
 
    void hNumQnode(PQNode<T, whaInfo*, Y>* nodePtr, int sumAllW);
 
    int alpha1beta1Number(PQNode<T, whaInfo*, Y>* nodePtr, PQNode<T, whaInfo*, Y>** aChild);
 
    int sumPertChild(PQNode<T, whaInfo*, Y>* nodePtr);
};
 
template<class T, class Y>
bool MaxSequencePQTree<T, Y>::Bubble(SListPure<PQLeafKey<T, whaInfo*, Y>*>& leafKeys) {
    // Queue for storing all pertinent nodes that still have
    // to be processed.
    Queue<PQNode<T, whaInfo*, Y>*> processNodes;
 
    /*
    Enter the [[Full]] leaves into the queue [[processNodes]].
    In a first step the pertinent leaves have to be identified in the tree
    and entered on to the queue [[processNodes]]. The identification of
    the leaves can be done with the help of a pointer stored in every
    [[PQLeafKey]] (see \ref{PQLeafKey}) in constant time for every element.
    */
    SListIterator<PQLeafKey<T, whaInfo*, Y>*> it;
    for (it = leafKeys.begin(); it.valid(); ++it) {
        PQNode<T, whaInfo*, Y>* checkLeaf = (*it)->nodePointer();
        processNodes.append(checkLeaf);
        cleanUp.pushBack(checkLeaf);
        if (!checkLeaf->getNodeInfo()) { // if leaf does not have an information class for storing the [wha]-number allocate one.
            whaInfo* newInfo = new whaInfo;
            PQNodeKey<T, whaInfo*, Y>* infoPtr = new PQNodeKey<T, whaInfo*, Y>(newInfo);
            checkLeaf->setNodeInfo(infoPtr);
            infoPtr->setNodePointer(checkLeaf);
        }
        checkLeaf->getNodeInfo()->userStructInfo()->m_notVisitedCount = 1;
        checkLeaf->mark(PQNodeRoot::PQNodeMark::Queued);
    }
 
    /*
    For every node in [[processNodes]], its father is detected using the
    function [[GetParent]] \ref{GetParent}. The father is placed onto the
    queue as well, if [[_nodePtr]] is its first child, that is popped from
    the queue. In that case, the father is marked as [[Queued]] to
    prevent the node from queue more than once. In any case, the number
    of pertinent children of the father is updated. This is an important
    number for computing the maximal pertinent sequence.
    */
    while (!processNodes.empty()) {
        PQNode<T, whaInfo*, Y>* nodePtr = processNodes.pop();
        nodePtr->parent(GetParent(nodePtr));
        if (nodePtr->parent() && !nodePtr->parent()->getNodeInfo())
        // if the parent does not have an information
        // class for storing the [wha]-number
        // allocate one.
        {
            whaInfo* newInfo = new whaInfo;
            PQNodeKey<T, whaInfo*, Y>* infoPtr = new PQNodeKey<T, whaInfo*, Y>(newInfo);
            nodePtr->parent()->setNodeInfo(infoPtr);
            infoPtr->setNodePointer(nodePtr->parent());
        }
        if (nodePtr != this->m_root) {
            if (nodePtr->parent()->mark() == PQNodeRoot::PQNodeMark::Unmarked) {
                processNodes.append(nodePtr->parent());
                cleanUp.pushBack(nodePtr->parent());
                nodePtr->parent()->mark(PQNodeRoot::PQNodeMark::Queued);
            }
            nodePtr->parent()->getNodeInfo()->userStructInfo()->m_notVisitedCount++;
            int childCount = nodePtr->parent()->pertChildCount();
            nodePtr->parent()->pertChildCount(++childCount);
        }
    }
 
 
    /*
    This chunk belongs to the function [[Bubble]]. After doing some
    cleaning up and resetting the flags that have been left at the
    pertinent nodes during the first bubble up, this chunk computes the
    maximal pertinent sequence by calling the function [[determineMinRemoveSequence]].
    It then removes
    all leaves from the tree that have been marked as [[Eliminated]] and
    possibly some internal nodes of the $PQ$-tree and stores pointers of
    type [[leafKey]] for the pertinent leaves in the maximal sequence in the
    array [[survivedElements]].
    */
 
    SListIterator<PQNode<T, whaInfo*, Y>*> itn;
    for (itn = cleanUp.begin(); itn.valid(); ++itn) {
        (*itn)->mark(PQNodeRoot::PQNodeMark::Unmarked);
    }
 
    return true;
}
 
template<class T, class Y>
void MaxSequencePQTree<T, Y>::CleanNode(PQNode<T, whaInfo*, Y>* nodePtr) {
    if (nodePtr->getNodeInfo()) {
        delete nodePtr->getNodeInfo()->userStructInfo();
        delete nodePtr->getNodeInfo();
    }
}
 
template<class T, class Y>
void MaxSequencePQTree<T, Y>::clientDefinedEmptyNode(PQNode<T, whaInfo*, Y>* nodePtr) {
    if (nodePtr->status() == PQNodeRoot::PQNodeStatus::Eliminated) {
        emptyNode(nodePtr);
        nodePtr->status(PQNodeRoot::PQNodeStatus::Eliminated);
    } else if (nodePtr->status() == PQNodeRoot::PQNodeStatus::PertRoot) {
        emptyNode(nodePtr);
    } else {
        // Node has an invalid status?
        OGDF_ASSERT(nodePtr->status() == PQNodeRoot::PQNodeStatus::Empty);
        emptyNode(nodePtr);
    }
}
 
template<class T, class Y>
void MaxSequencePQTree<T, Y>::emptyAllPertinentNodes() {
    PQNode<T, whaInfo*, Y>* nodePtr = nullptr;
 
    while (!cleanUp.empty()) {
        nodePtr = cleanUp.popFrontRet();
        nodePtr->pertChildCount(0);
        if (nodePtr->status() == PQNodeRoot::PQNodeStatus::WhaDelete
                && nodePtr->type() == PQNodeRoot::PQNodeType::Leaf) {
            CleanNode(nodePtr);
            delete nodePtr;
        }
 
        else {
            // node must have an Information if contained in cleanUp
            OGDF_ASSERT(nodePtr->getNodeInfo() != nullptr);
 
            nodePtr->getNodeInfo()->userStructInfo()->m_notVisitedCount = 0;
            nodePtr->getNodeInfo()->userStructInfo()->m_pertLeafCount = 0;
        }
    }
 
    ListIterator<PQNode<T, whaInfo*, Y>*> it;
    for (it = this->m_pertinentNodes->begin(); it.valid(); ++it) {
        nodePtr = *it;
        if (nodePtr->status() == PQNodeRoot::PQNodeStatus::ToBeDeleted) {
            nodePtr->status(PQNodeRoot::PQNodeStatus::Eliminated);
            eliminatedNodes.pushBack(nodePtr);
        } else if (nodePtr->status() == PQNodeRoot::PQNodeStatus::Full) {
            nodePtr->status(PQNodeRoot::PQNodeStatus::ToBeDeleted);
        } else if (nodePtr->status() == PQNodeRoot::PQNodeStatus::WhaDelete) {
            nodePtr->status(PQNodeRoot::PQNodeStatus::ToBeDeleted);
        } else if (nodePtr->getNodeInfo()) {
            nodePtr->getNodeInfo()->userStructInfo()->defaultValues();
        }
    }
    PQTree<T, whaInfo*, Y>::emptyAllPertinentNodes();
}
 
template<class T, class Y>
int MaxSequencePQTree<T, Y>::determineMinRemoveSequence(
        SListPure<PQLeafKey<T, whaInfo*, Y>*>& leafKeys,
        SList<PQLeafKey<T, whaInfo*, Y>*>& eliminatedKeys) {
    PQNode<T, whaInfo*, Y>* nodePtr = nullptr; // dummy
 
    //Number of leaves that have to be deleted
    int countDeletedLeaves = 0;
    //Number of pertinent leaves
    int maxPertLeafCount = 0;
 
    // A queue storing the nodes whose $[w,h,a]$-number has to be computed next.
    // A node is stored in [[processNodes]], if for all of its children the
    // [w,h,a]-number has been computed.
    Queue<PQNode<T, whaInfo*, Y>*> processNodes;
 
    // A stack storing all nodes where a $[w,h,a]$-number
    // has been computed. This is necessary for a valid cleanup.
    ArrayBuffer<PQNode<T, whaInfo*, Y>*> archiv;
 
    // Compute a valid parent pointer for every pertinent node.
    Bubble(leafKeys);
 
    // Get all pertinent leaves and stores them on [[processNodes]]
    // and [[_archiv]].
    SListIterator<PQLeafKey<T, whaInfo*, Y>*> it;
    for (it = leafKeys.begin(); it.valid(); ++it) {
        PQNode<T, whaInfo*, Y>* checkLeaf = (*it)->nodePointer();
        checkLeaf->getNodeInfo()->userStructInfo()->m_pertLeafCount = 1;
        checkLeaf->getNodeInfo()->userStructInfo()->m_notVisitedCount--;
        processNodes.append(checkLeaf);
        archiv.push(checkLeaf);
 
        maxPertLeafCount++;
    }
 
    while (!processNodes.empty()) {
        nodePtr = processNodes.pop();
        // Compute the $[w,h,a]$ number of [[nodePtr]]. Computing this number is
        // trivial for leaves and full nodes. When considering a partial node, the
        // computation has to distinguish between $P$- and $Q$-nodes.
        if (nodePtr->getNodeInfo()->userStructInfo()->m_pertLeafCount < maxPertLeafCount) {
            // In case that the actual node, depicted by the pointer
            // [[nodePtr]] is not the root, the counts of the pertinent
            // children of [[nodePtr]]'s parent are
            // updated. In case that all pertinent children of the parent of
            // [[nodePtr]] have a valid $[w,h,a]$-number, it is possible to compute
            // the $[w,h,a]$-number of parent. Hence the parent is placed onto
            // [[processNodes]]and [[_archiv]].
            nodePtr->parent()->getNodeInfo()->userStructInfo()->m_pertLeafCount =
                    nodePtr->parent()->getNodeInfo()->userStructInfo()->m_pertLeafCount
                    + nodePtr->getNodeInfo()->userStructInfo()->m_pertLeafCount;
            nodePtr->parent()->getNodeInfo()->userStructInfo()->m_notVisitedCount--;
            if (!nodePtr->parent()->getNodeInfo()->userStructInfo()->m_notVisitedCount) {
                processNodes.append(nodePtr->parent());
                archiv.push(nodePtr->parent());
            }
        }
        if (nodePtr->type() == PQNodeRoot::PQNodeType::Leaf) {
            // Compute the $[w,h,a]$-number of a leaf. The computation is trivial.
            nodePtr->status(PQNodeRoot::PQNodeStatus::Full);
            nodePtr->getNodeInfo()->userStructInfo()->m_w = 1;
            nodePtr->getNodeInfo()->userStructInfo()->m_h = 0;
            nodePtr->getNodeInfo()->userStructInfo()->m_a = 0;
            if (nodePtr->getNodeInfo()->userStructInfo()->m_pertLeafCount < maxPertLeafCount) {
                fullChildren(nodePtr->parent())->pushFront(nodePtr);
            }
        } else {
            // [[nodePtr]] is a $P$- or $Q$-node
            // The $[w,h,a]$ number of $P$- or $Q$-nodes is computed identically.
            // This is done calling the function [[sumPertChild]].
            nodePtr->getNodeInfo()->userStructInfo()->m_w = sumPertChild(nodePtr);
 
            if (fullChildren(nodePtr)->size() == nodePtr->childCount()) {
                // computes the $h$- and $a$-numbers of a full node. The computation
                // is trivial. It also updates the list of full nodes of the parent
                // of [[nodePtr]].
                nodePtr->status(PQNodeRoot::PQNodeStatus::Full);
                if (nodePtr->getNodeInfo()->userStructInfo()->m_pertLeafCount < maxPertLeafCount) {
                    fullChildren(nodePtr->parent())->pushFront(nodePtr);
                }
                nodePtr->getNodeInfo()->userStructInfo()->m_h = 0;
                nodePtr->getNodeInfo()->userStructInfo()->m_a = 0;
            } else {
                // computes the $[w,h,a]$-number of a partial node. The computation is
                // nontrivial for both $P$- and $Q$-nodes and is performed in the
                // function [[haNumPnode]] for $P$-nodes and in the
                // function [[haNumQnode]] for $Q$-nodes.
                // This chunk also updates the partial children stack of the parent.
                nodePtr->status(PQNodeRoot::PQNodeStatus::Partial);
                if (nodePtr->getNodeInfo()->userStructInfo()->m_pertLeafCount < maxPertLeafCount) {
                    partialChildren(nodePtr->parent())->pushFront(nodePtr);
                }
 
                if (nodePtr->type() == PQNodeRoot::PQNodeType::PNode) {
                    haNumPnode(nodePtr);
                } else {
                    haNumQnode(nodePtr);
                }
            }
        }
    }
 
    // Determine the root of the pertinent subtree, which the last processed node
    //[[nodePtr]] and finds the minimum of the $h$- and $a$-number of
    //[[m_pertinentRoot]]. In case that the minimum is equal to $0$, the
    //[[m_pertinentRoot]] stays of type $B$. Otherwise the type is selected
    //according to the minimum.
    OGDF_ASSERT(nodePtr != nullptr);
    this->m_pertinentRoot = nodePtr;
    if (this->m_pertinentRoot->getNodeInfo()->userStructInfo()->m_h
            < this->m_pertinentRoot->getNodeInfo()->userStructInfo()->m_a) {
        countDeletedLeaves = this->m_pertinentRoot->getNodeInfo()->userStructInfo()->m_h;
    } else {
        countDeletedLeaves = this->m_pertinentRoot->getNodeInfo()->userStructInfo()->m_a;
    }
 
    if (countDeletedLeaves > 0) {
        if (this->m_pertinentRoot->getNodeInfo()->userStructInfo()->m_h
                < this->m_pertinentRoot->getNodeInfo()->userStructInfo()->m_a) {
            this->m_pertinentRoot->getNodeInfo()->userStructInfo()->m_deleteType = whaType::H;
        } else {
            this->m_pertinentRoot->getNodeInfo()->userStructInfo()->m_deleteType = whaType::A;
        }
    }
 
    findMinWHASequence(archiv, eliminatedKeys);
 
    return countDeletedLeaves;
}
 
template<class T, class Y>
void MaxSequencePQTree<T, Y>::findMinWHASequence(ArrayBuffer<PQNode<T, whaInfo*, Y>*>& archiv,
        SList<PQLeafKey<T, whaInfo*, Y>*>& eliminatedKeys) {
    //a pointer to the first child of type $h$ of [[nodePtr]].
    PQNode<T, whaInfo*, Y>* hChild1 = nullptr;
 
    //a pointer to the second child of type $h$ of [[nodePtr]].
    PQNode<T, whaInfo*, Y>* hChild2 = nullptr;
 
    //a pointer to the child of type $a$ of [[nodePtr]].
    PQNode<T, whaInfo*, Y>* aChild = nullptr;
 
    // pertinent sibling of hChild1
    PQNode<T, whaInfo*, Y>* hChild2Sib = nullptr;
 
    while (!archiv.empty()) {
        //counts the number of children of [[nodePtr]].
        int childCount = 0;
 
        //a pointer to a pertinent node of the $PQ$-tree that is currently examined.
        PQNode<T, whaInfo*, Y>* nodePtr = archiv.popRet();
 
        /*
        Check if [[nodePtr]] is a full node whose delete type is either of
        type $h$ or type $a$. Since there are no empty leaves in its
        frontier, the node must therefore keep all its pertinent leaves
        in its frontier and is depicted to be of type $b$.
        */
        if (nodePtr->status() == PQNodeRoot::PQNodeStatus::Full
                && (nodePtr->getNodeInfo()->userStructInfo()->m_deleteType == whaType::H
                        || nodePtr->getNodeInfo()->userStructInfo()->m_deleteType == whaType::A)) {
            nodePtr->getNodeInfo()->userStructInfo()->m_deleteType = whaType::B;
            this->m_pertinentNodes->pushFront(nodePtr);
        }
 
        /*
        Check if [[nodePtr]] is a leaf whose delete type is either of type $w$ or
        $b$. In case it is of type $w$, the leaf has to be removed from the
        tree to gain reducibility of the set $S$.
        */
        else if (nodePtr->type() == PQNodeRoot::PQNodeType::Leaf) {
            if (nodePtr->getNodeInfo()->userStructInfo()->m_deleteType == whaType::W) {
                eliminatedKeys.pushBack(nodePtr->getKey());
            } else {
                this->m_pertinentNodes->pushFront(nodePtr);
            }
        }
 
        /*
        Manage the case of [[nodePtr]] being either a partial $P$-node, a partial
        $Q$-node, or a full $P$- or $Q$-node, where in the latter case the
        delete type of [[nodePtr]] is of type $b$.
        */
        else {
            switch (nodePtr->getNodeInfo()->userStructInfo()->m_deleteType) {
            case whaType::B:
                this->m_pertinentNodes->pushFront(nodePtr);
                break;
 
            case whaType::W:
                markPertinentChildren(nodePtr, PQNodeRoot::PQNodeStatus::Pertinent, whaType::W);
                nodePtr->pertChildCount(0);
                this->m_pertinentNodes->pushFront(nodePtr);
                break;
 
            case whaType::H:
                if (nodePtr->type() == PQNodeRoot::PQNodeType::PNode) {
                    /*
                    [[nodePtr]] is a $P$-node of type $h$. Mark all full
                    children of [[nodePtr]] to be of type $b$ (by doing nothing, since
                    the default is type $b$). It furthermore marks all partial children to
                    be of type $w$ except for the child stored in [[hChild1]] of the
                    information class of type [[whaInfo*]] of [[nodePtr]]. This child is
                    marked to be of type $h$.
                    */
                    markPertinentChildren(nodePtr, PQNodeRoot::PQNodeStatus::Partial, whaType::W);
                    markPertinentChildren(nodePtr, PQNodeRoot::PQNodeStatus::Full, whaType::B);
                    if (nodePtr->getNodeInfo()->userStructInfo()->m_hChild1) {
                        hChild1 =
                                (PQNode<T, whaInfo*, Y>*)nodePtr->getNodeInfo()->userStructInfo()->m_hChild1;
                        hChild1->getNodeInfo()->userStructInfo()->m_deleteType = whaType::H;
                        if (hChild1->getNodeInfo()->userStructInfo()->m_h
                                < hChild1->getNodeInfo()->userStructInfo()->m_w) {
                            childCount = 1;
                        }
                    }
                    nodePtr->pertChildCount(nodePtr->pertChildCount() + childCount
                            - partialChildren(nodePtr)->size());
                } else {
                    /*
                    [[nodePtr]] is a $Q$-node. Mark all pertinent children
                    to be of type $w$, except for the full children between the
                    [[hChild1]] and the endmost child of [[nodePtr]]. These full
                    children are marked $b$ while [[hChild1]] is marked to be of type
                    $h$. Setting the type of children to $b$ or $h$ is hidden in the
                    function call [[setHchild]] \label{setHChild}.
                    */
                    markPertinentChildren(nodePtr, PQNodeRoot::PQNodeStatus::Pertinent, whaType::W);
                    hChild1 =
                            (PQNode<T, whaInfo*, Y>*)nodePtr->getNodeInfo()->userStructInfo()->m_hChild1;
                    nodePtr->pertChildCount(setHchild(hChild1));
                }
                this->m_pertinentNodes->pushFront(nodePtr);
                break;
 
            case whaType::A:
                if (nodePtr->type() == PQNodeRoot::PQNodeType::PNode) {
                    /*
                    [[nodePtr]] is a $P$-node of type $a$.
                    Distinguish two main cases, based on the existence of a
                    child of [[nodePtr]] stored in [[aChild]] of the information
                    class of type [[_whaInfo]] of [[nodePtr]].
                    \begin{enumerate}
                    \item
                    If [[aChild]] is not empty, the chunk marks all full
                    and partial children of [[nodePtr]] to be of type $w$ and
                    marks the child [[aChild]] to be of type $a$.
                    \item
                    If [[aChild]] is empty, the chunk
                    marks all full children of [[nodePtr]] to be of type $b$
                    (by doing nothing, since the default is type $b$).
                    It furthermore marks all partial children to be of type $w$
                    except for the children stored in [[hChild1]] and
                    [[hChild2]] of the information class of type [[whaInfo*]] of
                    [[nodePtr]] which are marked to be of type $h$. Observe that
                    we have to distinguish the cases where both, [[_hChild]] and
                    [[hChild2]] are available, just [[_h_Child1]] is available or
                    none of the nodes exist.
                    \end{enumerate}
                    */
                    if (nodePtr->getNodeInfo()->userStructInfo()->m_aChild) {
                        markPertinentChildren(nodePtr, PQNodeRoot::PQNodeStatus::Pertinent,
                                whaType::W);
                        aChild = (PQNode<T, whaInfo*, Y>*)nodePtr->getNodeInfo()->userStructInfo()->m_aChild;
                        aChild->getNodeInfo()->userStructInfo()->m_deleteType = whaType::A;
                        nodePtr->pertChildCount(1);
                    } else {
                        markPertinentChildren(nodePtr, PQNodeRoot::PQNodeStatus::Full, whaType::B);
                        markPertinentChildren(nodePtr, PQNodeRoot::PQNodeStatus::Partial, whaType::W);
                        if (nodePtr->getNodeInfo()->userStructInfo()->m_hChild1) {
                            hChild1 = (PQNode<T, whaInfo*, Y>*)nodePtr->getNodeInfo()
                                              ->userStructInfo()
                                              ->m_hChild1;
                            hChild1->getNodeInfo()->userStructInfo()->m_deleteType = whaType::H;
                            if (hChild1->getNodeInfo()->userStructInfo()->m_h
                                    < hChild1->getNodeInfo()->userStructInfo()->m_w) {
                                childCount = 1;
                            }
                        }
                        if (nodePtr->getNodeInfo()->userStructInfo()->m_hChild2) {
                            hChild2 = (PQNode<T, whaInfo*, Y>*)nodePtr->getNodeInfo()
                                              ->userStructInfo()
                                              ->m_hChild2;
                            hChild2->getNodeInfo()->userStructInfo()->m_deleteType = whaType::H;
                            if (hChild2->getNodeInfo()->userStructInfo()->m_h
                                    < hChild2->getNodeInfo()->userStructInfo()->m_w) {
                                childCount++;
                            }
                        }
                        nodePtr->pertChildCount(nodePtr->pertChildCount() + childCount
                                - partialChildren(nodePtr)->size());
                    }
                } else {
                    /*
                    [[nodePtr]] is a $Q$-node of type $a$.
                    Distinguish two main cases, based on the existence of a child of
                    [[nodePtr]] stored in [[aChild]] of the information class of type
                    [[_whaInfo]] of [[nodePtr]].
                    \begin{enumerate}
                    \item
                    If [[aChild]] is not empty, the chunk marks all full
                    and partial children of [[nodePtr]] to be of type $w$ and marks the
                    child [[aChild]] to be of type $a$.
                    \item
                    If [[aChild]] is empty, the chunk
                    marks all full and partial children of [[nodePtr]] to be of type $w$
                    except for the ones in the largest consecutive sequence of pertinent
                    children. This sequence
                    is depicted by the children [[hChild1]] and [[hChild2]] which may be
                    either full or partial. The children between [[hChild1]] and
                    [[hChild2]] are full and are marked $b$, while [[hChild1]] and
                    [[hChild2]] are marked $b$ or $h$, according to their status.
                    Setting the type of the nodes is hidden in calling the function
                    [[setAchildren]] (see \ref{setAchildren}).
                    \end{enumerate}
                    */
                    if (nodePtr->getNodeInfo()->userStructInfo()->m_aChild) {
                        aChild = (PQNode<T, whaInfo*, Y>*)nodePtr->getNodeInfo()->userStructInfo()->m_aChild;
                        markPertinentChildren(nodePtr, PQNodeRoot::PQNodeStatus::Pertinent,
                                whaType::W);
                        aChild->getNodeInfo()->userStructInfo()->m_deleteType = whaType::A;
                        nodePtr->pertChildCount(1);
                    } else {
                        markPertinentChildren(nodePtr, PQNodeRoot::PQNodeStatus::Pertinent,
                                whaType::W);
                        hChild2 =
                                (PQNode<T, whaInfo*, Y>*)nodePtr->getNodeInfo()->userStructInfo()->m_hChild2;
                        hChild2Sib = (PQNode<T, whaInfo*, Y>*)nodePtr->getNodeInfo()
                                             ->userStructInfo()
                                             ->m_hChild2Sib;
                        nodePtr->pertChildCount(setAchildren(hChild2, hChild2Sib));
                    }
                }
                this->m_pertinentNodes->pushFront(nodePtr);
                break;
            }
        }
 
        /*
        After successfully determining the type of the children of [[nodePtr]],
        this chunk cleans up the information needed during the
        computation at the [[nodePtr]].
        */
        fullChildren(nodePtr)->clear();
        partialChildren(nodePtr)->clear();
        nodePtr->status(PQNodeRoot::PQNodeStatus::Empty);
        nodePtr->getNodeInfo()->userStructInfo()->m_hChild1 = nullptr;
        nodePtr->getNodeInfo()->userStructInfo()->m_hChild2 = nullptr;
        nodePtr->getNodeInfo()->userStructInfo()->m_aChild = nullptr;
        nodePtr->getNodeInfo()->userStructInfo()->m_w = 0;
        nodePtr->getNodeInfo()->userStructInfo()->m_h = 0;
        nodePtr->getNodeInfo()->userStructInfo()->m_a = 0;
        nodePtr->getNodeInfo()->userStructInfo()->m_deleteType = whaType::B;
    }
}
 
template<class T, class Y>
int MaxSequencePQTree<T, Y>::setHchild(PQNode<T, whaInfo*, Y>* hChild1) {
    // counts the number of pertinent children corresponding to the $[w,h,a]$-numbering.
    int pertinentChildCount = 0;
 
    // is [[true]] as long as children with a full label are found, [[false]] otherwise.
    bool fullLabel = false;
 
    PQNode<T, whaInfo*, Y>* currentNode = hChild1; // dummy
    PQNode<T, whaInfo*, Y>* nextSibling = nullptr; // dummy
    PQNode<T, whaInfo*, Y>* oldSibling = nullptr; // dummy
 
    if (hChild1 != nullptr) {
        fullLabel = true;
    }
 
    /*
    Trace the sequence of full children with at most one incident
    pertinent child. It marks all full nodes as $b$-node and the partial
    child, if available as $h$-child. The beginning of the sequence is
    stored in [[currentNode]] which is equal to [[h_child1]] before
    entering the while loop. Observe that this chunk cases if the while
    loop while scanning the sequence has reached the second endmost child
    of the $Q$-node (see [[if (nextSibling == 0)]]). This case may
    appear, if all children of the $Q$-node are pertinent and the second
    endmost child is the only partial child. The value [[fullLabel]] is
    set to [[false]] as soon as the end of the sequence is detected.
    */
    while (fullLabel) {
        nextSibling = currentNode->getNextSib(oldSibling);
        if (!nextSibling) {
            fullLabel = false;
        }
 
        if (currentNode->status() == PQNodeRoot::PQNodeStatus::Full) {
            currentNode->getNodeInfo()->userStructInfo()->m_deleteType = whaType::B;
            pertinentChildCount++;
        }
 
        else {
            if (currentNode->status() == PQNodeRoot::PQNodeStatus::Partial) {
                currentNode->getNodeInfo()->userStructInfo()->m_deleteType = whaType::H;
                if ((currentNode->getNodeInfo()->userStructInfo()->m_pertLeafCount
                            - currentNode->getNodeInfo()->userStructInfo()->m_h)
                        > 0) {
                    pertinentChildCount++;
                }
            }
            fullLabel = false;
        }
        oldSibling = currentNode;
        currentNode = nextSibling;
    }
 
    return pertinentChildCount;
}
 
template<class T, class Y>
int MaxSequencePQTree<T, Y>::setAchildren(PQNode<T, whaInfo*, Y>* hChild2,
        PQNode<T, whaInfo*, Y>* hChild2Sib) {
    /* Variables:
     *   - \a pertinentChildCount
     *   - \a reachedEnd
     *   - \a _sum denotes the number of pertinent leaves in the frontier
     *     of the sequence.
     *   - \a currentNode is the currently examined node of the sequence.
     *   - \a nextSibling is a pointer needed for tracing the sequence.
     *   - \a oldSibling is a pointer needed for tracing the sequence.
     */
    // counts the pertinent children of the sequence.
    int pertinentChildCount = 0;
 
    PQNode<T, whaInfo*, Y>* currentNode = hChild2; // dummy
    PQNode<T, whaInfo*, Y>* nextSibling = nullptr; // dummy
    PQNode<T, whaInfo*, Y>* oldSibling = nullptr; // dummy
 
    //Mark [[hChild2]] either as $b$- or as $h$-node.
    if (hChild2->status() == PQNodeRoot::PQNodeStatus::Full) {
        hChild2->getNodeInfo()->userStructInfo()->m_deleteType = whaType::B;
    } else {
        //1. node of sequence is Empty?
        OGDF_ASSERT(hChild2->status() == PQNodeRoot::PQNodeStatus::Partial);
        hChild2->getNodeInfo()->userStructInfo()->m_deleteType = whaType::H;
    }
 
    if (currentNode->getNodeInfo()->userStructInfo()->m_w
                    - currentNode->getNodeInfo()->userStructInfo()->m_h
            > 0) {
        pertinentChildCount++;
    }
 
    //Trace the sequence of pertinent children, marking the full children as $b$-node.
    //If a partial or empty node is detected, the end of the sequence is
    //reached and the partial node is marked as $h$-node.
    nextSibling = hChild2Sib;
    oldSibling = hChild2;
 
    if (nextSibling != nullptr) {
        currentNode = nextSibling;
 
        // is false]as long as the end of the sequence is not detected; true otherwise.
        bool reachedEnd = false;
 
        while (!reachedEnd) {
            if (currentNode->status() == PQNodeRoot::PQNodeStatus::Full) {
                currentNode->getNodeInfo()->userStructInfo()->m_deleteType = whaType::B;
                pertinentChildCount++;
            } else {
                if (currentNode->status() == PQNodeRoot::PQNodeStatus::Partial) {
                    currentNode->getNodeInfo()->userStructInfo()->m_deleteType = whaType::H;
                    if ((currentNode->getNodeInfo()->userStructInfo()->m_w
                                - currentNode->getNodeInfo()->userStructInfo()->m_h)
                            > 0) {
                        pertinentChildCount++;
                    }
                }
                reachedEnd = true;
            }
            if (!reachedEnd) {
                nextSibling = currentNode->getNextSib(oldSibling);
                if (nextSibling == nullptr) {
                    reachedEnd = true;
                }
                oldSibling = currentNode;
                currentNode = nextSibling;
            }
        }
    }
 
    return pertinentChildCount;
}
 
template<class T, class Y>
void MaxSequencePQTree<T, Y>::markPertinentChildren(PQNode<T, whaInfo*, Y>* nodePtr,
        PQNodeRoot::PQNodeStatus label, whaType deleteType) {
#if 0
    PQNode<T,whaInfo*,Y>  *currentNode = 0;
#endif
 
    if (label == PQNodeRoot::PQNodeStatus::Pertinent) {
        ListIterator<PQNode<T, whaInfo*, Y>*> it;
        for (it = partialChildren(nodePtr)->begin(); it.valid(); ++it) {
            (*it)->getNodeInfo()->userStructInfo()->m_deleteType = deleteType;
        }
        for (it = fullChildren(nodePtr)->begin(); it.valid(); ++it) {
            (*it)->getNodeInfo()->userStructInfo()->m_deleteType = deleteType;
        }
    } else if (label == PQNodeRoot::PQNodeStatus::Partial) {
        ListIterator<PQNode<T, whaInfo*, Y>*> it;
        for (it = partialChildren(nodePtr)->begin(); it.valid(); ++it) {
            (*it)->getNodeInfo()->userStructInfo()->m_deleteType = deleteType;
        }
    }
 
    else {
        ListIterator<PQNode<T, whaInfo*, Y>*> it;
        for (it = fullChildren(nodePtr)->begin(); it.valid(); ++it) {
            (*it)->getNodeInfo()->userStructInfo()->m_deleteType = deleteType;
        }
    }
}
 
template<class T, class Y>
void MaxSequencePQTree<T, Y>::haNumPnode(PQNode<T, whaInfo*, Y>* nodePtr) {
    /* Variables:
     *   - \a sumParW = sum_{i in Par(\p nodePtr)} w_i, where
     *     Par(\p nodePtr) denotes the set of partial children of \p nodePtr.
     *   - \a sumMax1 = max_{i in Par(\p nodePtr)}1 {(w_i - h_i)}
     *     where Par(\p nodePtr) denotes the set of partial children of
     *   - \p nodePtr and max 1 the first maximum.
     *   - \a sumMax2 = max_{i in Par(\p nodePtr)}2 {(w_i - h_i)}
     *     where Par(\p nodePtr) denotes the set of partial children of
     *     \p nodePtr and max2 the second maximum.
     *   - \a currentNode
     *   - \a hChild1 is a pointer to the \a hChild1 of \p nodePtr.
     *   - \a hChild2 is a pointer to the \a hChild2 of \p nodePtr.
     *   - \a aChild is a pointer to the \a aChild of \p nodePtr.
     */
    int sumParW = 0;
    int sumMax1 = 0;
    int sumMax2 = 0;
    PQNode<T, whaInfo*, Y>* currentNode = nullptr;
    PQNode<T, whaInfo*, Y>* hChild1 = nullptr;
    PQNode<T, whaInfo*, Y>* hChild2 = nullptr;
    PQNode<T, whaInfo*, Y>* aChild = nullptr;
 
    /*
    Computes the $h$-number
    \[ h = \sum_{i \in Par(\mbox{[[nodePtr]]})}w_i - \max_{i\in
    Par(\mbox{[[nodePtr]]})}1\left\{(w_i - h_i)\right\}\]
    of the $P$-node [[nodePtr]].
    This is done by scanning all partial children stored in the
    [[partialChildrenStack]] of [[nodePtr]] summing up the $w_i$ for every
    $i \in Par(\mbox{[[nodePtr]]})$ and detecting
    \[\max_{i\in Par(\mbox{[[nodePtr]]})}1\left\{(w_i - h_i)\right\}.\]
    Since this can be simultaneously it also computes
    \[\max_{i\in Par(\mbox{[[nodePtr]]})}2\left\{(w_i - h_i)\right\}\]
    which is needed to determine the $a$-number.
    After successfully determining the $h$-number, the [[hChild1]] and
    [[hChild2]] of [[nodePtr]] are set.
    */
 
    ListIterator<PQNode<T, whaInfo*, Y>*> it;
    for (it = partialChildren(nodePtr)->begin(); it.valid(); ++it) {
        currentNode = (*it);
        sumParW = sumParW + currentNode->getNodeInfo()->userStructInfo()->m_w;
        int sumHelp = currentNode->getNodeInfo()->userStructInfo()->m_w
                - currentNode->getNodeInfo()->userStructInfo()->m_h;
        if (sumMax1 <= sumHelp) {
            sumMax2 = sumMax1;
            hChild2 = hChild1;
            sumMax1 = sumHelp;
            hChild1 = currentNode;
        } else if (sumMax2 <= sumHelp) {
            sumMax2 = sumHelp;
            hChild2 = currentNode;
        }
    }
    nodePtr->getNodeInfo()->userStructInfo()->m_hChild1 = hChild1;
    nodePtr->getNodeInfo()->userStructInfo()->m_hChild2 = hChild2;
    nodePtr->getNodeInfo()->userStructInfo()->m_h = sumParW - sumMax1;
 
    /*
    Compute the $a$-number of the $P$-node [[nodePtr]] where
    \[ a = \min \{ \alpha_1, \alpha_2\}\]
    such that
    \[\alpha_1 = \sum_{i \in P(\mbox{[[nodePtr]]})}w_i - \max_{i\in
    P(\mbox{[[nodePtr]]})}\left\{(w_i - h_i)\right\} \]
    which can be computed calling the function [[alpha1beta1Number]] and
    \[{\alpha}_2 \sum_{i \in Par(\mbox{[[nodePtr]]})}w_i -
    \max_{i\in Par(\mbox{[[nodePtr]]})}1\left\{(w_i - h_i)\right\}
    - \max_{i\in Par(\mbox{[[nodePtr]]})}2\left\{(w_i - h_i)\right\}\]
    This chunk uses two extra variables
    \begin{description}
    \item[[alpha1]] $ = \alpha_1$.
    \item[[alpha2]] $ = \alpha_2$.
    \end{description}
    */
    int alpha2 = sumParW - sumMax1 - sumMax2;
    int alpha1 = alpha1beta1Number(nodePtr, &aChild);
 
    if (alpha1 <= alpha2) {
        nodePtr->getNodeInfo()->userStructInfo()->m_a = alpha1;
        nodePtr->getNodeInfo()->userStructInfo()->m_aChild = aChild;
    } else {
        nodePtr->getNodeInfo()->userStructInfo()->m_a = alpha2;
        nodePtr->getNodeInfo()->userStructInfo()->m_aChild = nullptr;
    }
}
 
template<class T, class Y>
void MaxSequencePQTree<T, Y>::haNumQnode(PQNode<T, whaInfo*, Y>* nodePtr) {
    /* Variables:
     *   - sumAllW = sum_{i in P(\p nodePtr)} w_i, where
     *     P(\p nodePtr) denotes the set of pertinent children of \p nodePtr.
     */
    int sumAllW = sumPertChild(nodePtr);
 
    hNumQnode(nodePtr, sumAllW);
    aNumQnode(nodePtr, sumAllW);
}
 
template<class T, class Y>
void MaxSequencePQTree<T, Y>::hNumQnode(PQNode<T, whaInfo*, Y>* nodePtr, int sumAllW) {
    /* Variables:
     *   - \a sumLeft = sum_{i in P(\p nodePtr)} w_i - sum_{i
     *     in P_L(\p nodePtr)}(w_i - h_i), where
     *     P_L(\p nodePtr) denotes the maximal consecutive sequence
     *     of pertinent children on the left side of the Q-node
     *     \p nodePtr such that only the rightmost node in
     *     P_L(\p nodePtr) may be partial.
     *   - \a sumRight = sum_{i in P(\p [nodePtr)}w_i - sum_{i
     *     in P_L(\p nodePtr)}(w_i - h_i), where
     *     P_L(\p nodePtr) denotes the maximal consecutive sequence
     *     of pertinent children on the left side of the Q-node
     *     \p nodePtr such that only the rightmost node in
     *     P_L(\p nodePtr) may be partial.
     *   - \a fullLabel
     *   - \a aChild is a pointer to the a-child of \p nodePtr.
     *   - \a leftChild is a pointer to the left endmost child of \p nodePtr.
     *   - \a rightChild is a pointer to the right endmost child of \p nodePtr.
     *   - \a holdSibling is a pointer to a child of \p nodePtr, needed
     *     to proceed through sequences of pertinent children.
     *   - \a checkSibling is a pointer to a currently examined child of \p nodePtr.
     */
    int sumLeft = 0;
    int sumRight = 0;
    bool fullLabel = true;
    PQNode<T, whaInfo*, Y>* leftChild = nullptr;
    PQNode<T, whaInfo*, Y>* rightChild = nullptr;
    PQNode<T, whaInfo*, Y>* holdSibling = nullptr;
    PQNode<T, whaInfo*, Y>* checkSibling = nullptr;
 
    //Compute the $h$-number of the $Q$-node [[nodePtr]]
 
    //Get endmost children of the $Q$-node [[nodePtr]].
    leftChild = nodePtr->getEndmost(nullptr);
    rightChild = nodePtr->getEndmost(leftChild);
    OGDF_ASSERT(leftChild);
    OGDF_ASSERT(rightChild);
 
    /*
    Check the left
    side of the $Q$-node [[nodePtr]] for the maximal consecutive sequence
    of full nodes, including at most one partial child at the end of the sequence.
 
    The variable [[fullLabel]] is [[true]] as long as the [[while]]-loop
    has not detected an partial <b>or</b> empty child (see case [[if
    (leftChild->status() != Full)]]. Observe that the
    construction of the [[while]]-loop examines the last child if it is a
    partial child as well (see case [[if (leftChild->status() !=
    Empty)]] where in the computation in [[sumLeft]] we  take advantage
    of the fact, that the $h$-number of a full child is zero).
    */
    while (fullLabel) {
        if (leftChild->status() != PQNodeRoot::PQNodeStatus::Full) {
            fullLabel = false;
        }
        if (leftChild->status() != PQNodeRoot::PQNodeStatus::Empty) {
            sumLeft = sumLeft + leftChild->getNodeInfo()->userStructInfo()->m_w
                    - leftChild->getNodeInfo()->userStructInfo()->m_h;
            checkSibling = leftChild->getNextSib(holdSibling);
            if (checkSibling == nullptr) {
                fullLabel = false;
            }
            holdSibling = leftChild;
            leftChild = checkSibling;
        }
    }
 
    /*
    Check the right
    side of the $Q$-node [[nodePtr]] for the maximal consecutive sequence
    of full nodes, including at most one partial child at the end of the sequence.
 
    The variable [[fullLabel]] is [[true]] as long as the [[while]]-loop
    has not detected an partial <b>or</b> empty child (see case [[if
    (leftChild->status() != Full)]]. Observe that the
    construction of the [[while]]-loop examines the last child if it is a
    partial child as well (see case [[if (leftChild->status() !=
    Empty)]] where in the computation in [[sumLeft]] we  take advantage
    of the fact, that the $h$-number of a full child is zero).
    */
    holdSibling = nullptr;
    checkSibling = nullptr;
    fullLabel = true;
    while (fullLabel) {
        if (rightChild->status() != PQNodeRoot::PQNodeStatus::Full) {
            fullLabel = false;
        }
        if (rightChild->status() != PQNodeRoot::PQNodeStatus::Empty) {
            sumRight = sumRight + rightChild->getNodeInfo()->userStructInfo()->m_w
                    - rightChild->getNodeInfo()->userStructInfo()->m_h;
 
            checkSibling = rightChild->getNextSib(holdSibling);
 
            if (checkSibling == nullptr) {
                fullLabel = false;
            }
 
            holdSibling = rightChild;
            rightChild = checkSibling;
        }
    }
 
    /*
    After computing the number of pertinent leaves that stay in the $PQ$-tree
    when keeping either the left pertinent or the right pertinent side of
    the $Q$-node in the tree, this chunk chooses the side where the
    maximum number of leaves stay in the tree.
    Observe that we have to case the fact, that on both sides of the
    $Q$-node [[nodePtr]] no pertinent children are.
    */
    leftChild = nodePtr->getEndmost(nullptr);
    rightChild = nodePtr->getEndmost(leftChild);
    if (sumLeft == 0 && sumRight == 0) {
        nodePtr->getNodeInfo()->userStructInfo()->m_h = sumAllW;
        nodePtr->getNodeInfo()->userStructInfo()->m_hChild1 = nullptr;
    } else if (sumLeft < sumRight) {
        nodePtr->getNodeInfo()->userStructInfo()->m_h = sumAllW - sumRight;
        nodePtr->getNodeInfo()->userStructInfo()->m_hChild1 = rightChild;
    } else {
        nodePtr->getNodeInfo()->userStructInfo()->m_h = sumAllW - sumLeft;
        nodePtr->getNodeInfo()->userStructInfo()->m_hChild1 = leftChild;
    }
}
 
template<class T, class Y>
void MaxSequencePQTree<T, Y>::aNumQnode(PQNode<T, whaInfo*, Y>* nodePtr, int sumAllW) {
    /* Variables:
     *   - \a beta1 = sum_{i in P(\p nodePtr} w_i - max_{i in P(\p nodePtr)}{(w_i =
     *     a_i)}, where $P(\p nodePtr) denotes the set of all pertinent
     *     children of the Q-node \p nodePtr. Depicts the a-number if just one
     *     child of \p nodePtr is made a-node. Computed by calling the function alpha1beta1Number().
     *   - \a beta2 = sum_{i in P(\p nodePtr)} w_i - max_{P_A(\p nodePtr)}{sum_{i in
     *     P_A(\p nodePtr)}(w_i-h_i)}, where $P_A(\p nodePtr) is a maximal consecutive
     *     sequence of pertinent children of the Q-node \p nodePtr such that all
     *     nodes in P_A(\p nodePtr) except for the leftmost and rightmost ones are
     *     full. Computed by this chunk.
     *   - \a aSum depicts the number of pertinent leaves of the actual visited sequence.
     *   - \a aHoldSum depicts the number of leaves in the actual maximum sequence.
     *   - \a endReached is true if reached the end of the Q-node \p nodePtr and false otherwise.
     *   - \a leftMost pointer to the leftmost end of the actual visited sequence.
     *   - \a leftMostHold pointer to the leftmost end of the current maximum sequence.
     *   - \a actualNode pointer to a child of the Q-node. It is the
     *     node that is actually processed in the sequence of children.
     *   - \a currentNode pointer to a node in a consecutive pertinent
     *     sequence. Needed to process all nodes stored in \a sequence.
     *   - \a lastChild is a pointer to the endmost child of the Q-node
     *     that is opposite to the endmost child, where this chunk starts
     *     processing the sequence of children.
     *   - \a sequence is a SList of type PQNode<T,whaInfo*,Y>* storing
     *     the nodes of a consecutive sequence that is actually processed.
     */
    PQNode<T, whaInfo*, Y>* aChild = nullptr;
    int beta1 = alpha1beta1Number(nodePtr, &aChild);
    int beta2 = 0;
    int aSum = 0;
    int aHoldSum = 0;
    bool endReached = 0;
    PQNode<T, whaInfo*, Y>* leftMost = nullptr;
    PQNode<T, whaInfo*, Y>* leftSib = nullptr;
    PQNode<T, whaInfo*, Y>* leftMostHold = nullptr;
    PQNode<T, whaInfo*, Y>* leftSibHold = nullptr;
    PQNode<T, whaInfo*, Y>* actualNode = nullptr;
    PQNode<T, whaInfo*, Y>* currentNode = nullptr;
    PQNode<T, whaInfo*, Y>* lastChild = nullptr;
    PQNode<T, whaInfo*, Y>* holdSibling = nullptr;
    PQNode<T, whaInfo*, Y>* checkSibling = nullptr;
    // pointer to the second endmost child
 
    SList<PQNode<T, whaInfo*, Y>*> sequence;
 
    actualNode = nodePtr->getEndmost(nullptr);
    lastChild = nodePtr->getEndmost(actualNode);
 
    endReached = false;
    while (!endReached) {
        /*
        Process the children of a $Q$-node [[nodePtr]] from one end of [[nodePtr]] to the
        other, searching for a consecutive sequence of pertinent nodes with
        the maximum number of pertinent leaves, such that all nodes of the
        pertinent sequence are full except possibly the two endmost children
        which are allowed to be partial.
        */
        if (sequence.empty()) {
            /*
            Currently no consecutive sequence of pertinent children
            is detected while scanning the children of the $Q$-node.
            Check the [[actualNode]] if it is the first child of
            such a sequence. If so, place [[actualNode]] on the stack [[sequence]].
            */
            if (actualNode->status() != PQNodeRoot::PQNodeStatus::Empty) {
                sequence.pushFront(actualNode);
                leftMost = nullptr;
                leftSib = nullptr;
            }
        } else {
            /*
            [[actualNode]] is a sibling of a consecutive pertinent sequence that has
            been detected in an earlier step, while scanning the children of the $Q$-node.
            This chunk cases on the status of the [[actualNode]].
 
            In case that the status of
            the [[actualNode]] is [[Full]], [[actualNode]] is included into the
            sequence of pertinent children by pushing it onto the stack
            [[sequence]].
 
            If [[actualNode]] is Empty, we have reached the end of
            the actual consecutive sequence of pertinent children. In this case
            the $a$-numbers of the nodes in the sequence have to be summed up.
 
            If the [[actualNode]] is [[Partial]], the end of the consecutive sequence
            is reached and similar actions to the [[Empty]] have to be
            performed. However, [[actualNode]] might mark the beginning of
            another pertinent sequence. Hence it has to be stored again in [[sequence]].
            */
            if (actualNode->status() == PQNodeRoot::PQNodeStatus::Full) {
                sequence.pushFront(actualNode);
            }
 
            else if (actualNode->status() == PQNodeRoot::PQNodeStatus::Empty) {
                /*
                If [[actualNode]] is Empty, the end of
                the actual consecutive sequence of pertinent children is reached . In
                this case, all nodes of the currently examined consecutive sequence are stored in
                [[sequence]].
                They are removed from the stack and their $a$-numbers are summed up.
                If necessary, the sequence with the largest number of full leaves in
                its frontier is updated.
                */
                aSum = 0;
 
                while (!sequence.empty()) {
                    currentNode = sequence.popFrontRet();
                    aSum = aSum + currentNode->getNodeInfo()->userStructInfo()->m_w
                            - currentNode->getNodeInfo()->userStructInfo()->m_h;
                    if (sequence.size() == 1) {
                        leftSib = currentNode;
                    }
                }
                leftMost = currentNode;
 
                if (aHoldSum < aSum) {
                    aHoldSum = aSum;
                    leftMostHold = leftMost;
                    leftSibHold = leftSib;
                }
 
            } else {
                /*
                If the [[actualNode]] is [[Partial]], the end of the consecutive sequence
                is reached. In
                this case, all nodes of the currently examined consecutive sequence are stored in
                [[sequence]].
                They are removed from the stack and their $a$-numbers are summed up.
                If necessary, the sequence with the largest number of full leaves in
                its frontier is updated.
                However, [[actualNode]] might mark the beginning of
                another pertinent sequence. Hence it has to be stored again in [[sequence]].
                */
                sequence.pushFront(actualNode);
                aSum = 0;
                while (!sequence.empty()) {
                    currentNode = sequence.popFrontRet();
                    aSum = aSum + currentNode->getNodeInfo()->userStructInfo()->m_w
                            - currentNode->getNodeInfo()->userStructInfo()->m_h;
                    if (sequence.size() == 1) {
                        leftSib = currentNode;
                    }
                }
                if (leftSib == nullptr) {
                    leftSib = actualNode;
                }
                leftMost = currentNode;
 
                if (aHoldSum < aSum) {
                    aHoldSum = aSum;
                    leftMostHold = leftMost;
                    leftSibHold = leftSib;
                }
 
                sequence.pushFront(actualNode);
            }
        }
 
        // Get the next sibling
        if (actualNode != lastChild) {
            checkSibling = actualNode->getNextSib(holdSibling);
            holdSibling = actualNode;
            actualNode = checkSibling;
        } else {
            // End of Q-node reached.
            endReached = true;
        }
    }
 
 
    /*
    After processing
    the last child of the $Q$-node, this chunk checks, if this child was
    part of a pertinent consecutive sequence. If this is the case, the
    stack storing this seuquence was not emptied and the number of
    pertinent leaves in its frontier was not computed. Furhtermore the
    last child was not stored in [[sequence]].
    This chunk does the necessary updates for the last consecutive sequence.
    */
    if (!sequence.empty()) {
        aSum = 0;
        while (!sequence.empty()) {
            currentNode = sequence.popFrontRet();
            aSum = aSum + currentNode->getNodeInfo()->userStructInfo()->m_w
                    - currentNode->getNodeInfo()->userStructInfo()->m_h;
            if (sequence.size() == 1) {
                leftSib = currentNode;
            }
        }
        leftMost = currentNode;
 
        if (aHoldSum < aSum) {
            aHoldSum = aSum;
            leftMostHold = leftMost;
            leftSibHold = leftSib;
        }
    }
    /*
    After computing
    ${\beta}_1$ and ${\beta}_2$, describing the number of pertinent leaves
    that have to be deleted when choosing either one node to be an
    $a$-node or a complete sequence, this chunk gets the $a$-number of the
    $Q$-node [[nodePtr]] by choosing
    \[a = \min\{{\beta}_1,{\beta}_2\]
    Also set [[aChild]] and [[hChild2]] of [[nodePtr]] according to the
    chosen minimum.
    */
    beta2 = sumAllW - aHoldSum;
    if (beta2 < beta1) {
        nodePtr->getNodeInfo()->userStructInfo()->m_a = beta2;
        nodePtr->getNodeInfo()->userStructInfo()->m_hChild2 = leftMostHold;
        nodePtr->getNodeInfo()->userStructInfo()->m_hChild2Sib = leftSibHold;
        nodePtr->getNodeInfo()->userStructInfo()->m_aChild = nullptr;
    } else {
        nodePtr->getNodeInfo()->userStructInfo()->m_a = beta1;
        nodePtr->getNodeInfo()->userStructInfo()->m_hChild2 = nullptr;
        nodePtr->getNodeInfo()->userStructInfo()->m_hChild2Sib = nullptr;
        nodePtr->getNodeInfo()->userStructInfo()->m_aChild = aChild;
    }
}
 
template<class T, class Y>
int MaxSequencePQTree<T, Y>::alpha1beta1Number(PQNode<T, whaInfo*, Y>* nodePtr,
        PQNode<T, whaInfo*, Y>** aChild) {
    /* Variables:
     *   - \a sumMaxA = max_{i in P(\p nodePtr)}{(w_i = a_i)}.
     *   - \a sumAllW = w  = sum_{i in P(\p nodePtr)}w_i.
     *   - \a sumHelp is a help variable.
     *   - \a currentNode depicts a currently examined pertinent node.
     *
     * The function uses two while loops over the parial and the full
     * children of \p nodePtr. It hereby computes the values \p w and
     * max_{i in P(\p nodePtr}{(w_i = a_i)}.
     * After finishing the while loops, the function
     * alpha1beta1Number() returns the numbers alpha_1 = beta_1
     * and the \p aChild.
     */
    int sumMaxA = 0;
    int sumAllW = 0;
    int sumHelp = 0;
    PQNode<T, whaInfo*, Y>* currentNode = nullptr;
 
    ListIterator<PQNode<T, whaInfo*, Y>*> it;
    for (it = fullChildren(nodePtr)->begin(); it.valid(); ++it) {
        currentNode = (*it);
        sumAllW = sumAllW + currentNode->getNodeInfo()->userStructInfo()->m_w;
        sumHelp = currentNode->getNodeInfo()->userStructInfo()->m_w
                - currentNode->getNodeInfo()->userStructInfo()->m_a;
        if (sumMaxA < sumHelp) {
            sumMaxA = sumHelp;
            (*aChild) = currentNode;
        }
    }
 
    for (it = partialChildren(nodePtr)->begin(); it.valid(); ++it) {
        currentNode = (*it);
        sumAllW = sumAllW + currentNode->getNodeInfo()->userStructInfo()->m_w;
        sumHelp = currentNode->getNodeInfo()->userStructInfo()->m_w
                - currentNode->getNodeInfo()->userStructInfo()->m_a;
        if (sumMaxA < sumHelp) {
            sumMaxA = sumHelp;
            (*aChild) = currentNode;
        }
    }
    return sumAllW - sumMaxA;
}
 
template<class T, class Y>
int MaxSequencePQTree<T, Y>::sumPertChild(PQNode<T, whaInfo*, Y>* nodePtr) {
    /* Variables:
     *   - \a it depicts a currently examined pertinent node.
     *   - \a sum = \a w  = sum_{i in P(\p nodePtr)}w_i.
     *
     * The function uses two for loops over the parial and the full
     * children of \p nodePtr. It hereby computes the values $w$ stored in \a sum.
     * After finishing the while loops, the function
     * sumPertChild() returns the number \a w.
     */
    int sum = 0;
    ListIterator<PQNode<T, whaInfo*, Y>*> it;
    for (it = fullChildren(nodePtr)->begin(); it.valid(); ++it) {
        sum = sum + (*it)->getNodeInfo()->userStructInfo()->m_w;
    }
    for (it = partialChildren(nodePtr)->begin(); it.valid(); ++it) {
        sum = sum + (*it)->getNodeInfo()->userStructInfo()->m_w;
    }
 
    return sum;
}
 
template<class T, class Y>
PQNode<T, whaInfo*, Y>* MaxSequencePQTree<T, Y>::GetParent(PQNode<T, whaInfo*, Y>* nodePtr) {
    if (nodePtr->parent() == nullptr) {
        return nullptr;
    } else if (nodePtr->parent()->status() != PQNodeRoot::PQNodeStatus::Eliminated) {
        return nodePtr->parent();
    } else {
        PQNode<T, whaInfo*, Y>* nextNode = nodePtr;
        PQNode<T, whaInfo*, Y>* currentNode = nullptr;
        PQNode<T, whaInfo*, Y>* oldSib = nullptr;
        SListPure<PQNode<T, whaInfo*, Y>*> L;
 
        currentNode = nodePtr->getNextSib(nullptr);
        oldSib = nodePtr;
        L.pushFront(nodePtr);
        while (currentNode->parent()->status() == PQNodeRoot::PQNodeStatus::Eliminated) {
            L.pushFront(currentNode);
            nextNode = currentNode->getNextSib(oldSib);
            oldSib = currentNode;
            currentNode = nextNode;
        }
        while (!L.empty()) {
            L.popFrontRet()->parent(currentNode->parent());
        }
        return currentNode->parent();
    }
}
 
}