MaxSequencePQTree.h

Go to the documentation of this file.

/*
 * $Revision: 2299 $
 * 
 * last checkin:
 *   $Author: gutwenger $ 
 *   $Date: 2012-05-07 15:57:08 +0200 (Mon, 07 May 2012) $ 
 ***************************************************************/
 
#ifdef _MSC_VER
#pragma once
#endif

#ifndef OGDF_MAX_SEQUENCE_PQTREE_H
#define OGDF_MAX_SEQUENCE_PQTREE_H



#include <string.h>

#include <ogdf/internal/planarity/PQTree.h>
#include <ogdf/internal/planarity/PQLeafKey.h>
#include <ogdf/internal/planarity/whaInfo.h>

namespace ogdf{

    
//Extra node status defines

#define ELIMINATED 6    

#define WHA_DELETE 7    

#define PERTROOT   8    


template<class T,class Y>
class MaxSequencePQTree: public PQTree<T,whaInfo*,Y>
{
public:

    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:


    virtual bool Bubble(
        SListPure<PQLeafKey<T,whaInfo*,Y>*> &leafKeys/*,
        int redNumber = 0*/);

    PQNode<T,whaInfo*,Y>* GetParent(PQNode<T,whaInfo*,Y>* nodePtr);

    SListPure<PQNode<T,whaInfo*,Y>*> cleanUp;

    SListPure<PQNode<edge,whaInfo*,bool>*> eliminatedNodes;

private:

    void findMinWHASequence(StackPure<PQNode<T,whaInfo*,Y>*> &archiv,
                      SList<PQLeafKey<T,whaInfo*,Y>*> &eliminatedKeys);

    int setHchild(PQNode<T,whaInfo*,Y> *h_child1);

    int setAchildren(PQNode<T,whaInfo*,Y> *hChild2,
                     PQNode<T,whaInfo*,Y> *hChild2Sib);

    void markPertinentChildren(PQNode<T,whaInfo*,Y>  *nodePtr,
                               int label,
                               int del_typ);

    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);
};


/************************************************************************
                          Bubble
************************************************************************/ 

template<class T,class Y> 
bool MaxSequencePQTree<T,Y>::Bubble(SListPure<PQLeafKey<T,whaInfo*,Y>*> &leafKeys/*,
                                    int redNumber*/)
{
    // 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 = OGDF_NEW whaInfo;
            PQNodeKey<T,whaInfo*,Y> *infoPtr = OGDF_NEW PQNodeKey<T,whaInfo*,Y>(newInfo);
            checkLeaf->setNodeInfo(infoPtr);
            infoPtr->setNodePointer(checkLeaf);
        }
        checkLeaf->getNodeInfo()->userStructInfo()->m_notVisitedCount = 1;
        checkLeaf->mark(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 = OGDF_NEW whaInfo;
            PQNodeKey<T,whaInfo*,Y> *infoPtr = OGDF_NEW PQNodeKey<T,whaInfo*,Y>(newInfo);
            nodePtr->parent()->setNodeInfo(infoPtr);
            infoPtr->setNodePointer(nodePtr->parent());
        }
        if (nodePtr != this->m_root)
        {
            if (nodePtr->parent()->mark() == UNMARKED)
            {
                processNodes.append(nodePtr->parent());
                cleanUp.pushBack(nodePtr->parent());
                nodePtr->parent()->mark(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(UNMARKED);

    return true;
}



/**************************************************************************************
                        cleanNode
***************************************************************************************/ 

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();
    }
}


/**************************************************************************************
                        clientDefinedEmptyNode   
***************************************************************************************/ 

template<class T,class Y> 
void MaxSequencePQTree<T,Y>::clientDefinedEmptyNode(PQNode<T,whaInfo*,Y>* nodePtr)
{
    if (nodePtr->status() == ELIMINATED)
    {   
        emptyNode(nodePtr);
        nodePtr->status(ELIMINATED);
    }
    else if (nodePtr->status() == PERTROOT)
        emptyNode(nodePtr);
    else {
        // Node has an invalid status?
        OGDF_ASSERT(nodePtr->status() == EMPTY)
        emptyNode(nodePtr);
    }
}


/**************************************************************************************
                        emptyAllPertinentNodes   
***************************************************************************************/ 

template<class T,class Y> 
void MaxSequencePQTree<T,Y>::emptyAllPertinentNodes()
{
    PQNode<T,whaInfo*,Y>* nodePtr = 0;

    while (!cleanUp.empty())
    {
        nodePtr = cleanUp.popFrontRet();
        nodePtr->pertChildCount(0);
        if (nodePtr->status() == WHA_DELETE && nodePtr->type() == PQNodeRoot::leaf)
        {
            CleanNode(nodePtr);
            delete nodePtr;
        }

        else {
            // node must have an Information if contained in cleanUp
            OGDF_ASSERT(nodePtr->getNodeInfo() != 0)
        
            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() == TO_BE_DELETED)
        {
            nodePtr->status(ELIMINATED);
            eliminatedNodes.pushBack(nodePtr);
        } 
        else if (nodePtr->status() == FULL)
            nodePtr->status(TO_BE_DELETED);
        else if (nodePtr->status() == WHA_DELETE)
            nodePtr->status(TO_BE_DELETED);
        else if (nodePtr->getNodeInfo())
            nodePtr->getNodeInfo()->userStructInfo()->defaultValues();
    }
    PQTree<T,whaInfo*,Y>::emptyAllPertinentNodes();
}



/************************************************************************
                          determineMinRemoveSequence
************************************************************************/ 

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            = 0; // dummy
    PQNode<T,whaInfo*,Y>                *checkLeaf          = 0; // 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.
    StackPure<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)
    {
        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::leaf)
        {
            // Compute the $[w,h,a]$-number of a leaf. The computation is trivial.
            nodePtr->status(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(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(PARTIAL);
                if (nodePtr->getNodeInfo()->userStructInfo()->m_pertLeafCount < 
                    maxPertLeafCount)
                    partialChildren(nodePtr->parent())->pushFront(nodePtr);

                if (nodePtr->type() == PQNodeRoot::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.
    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_deleteTyp = H_TYPE;
        else         
            this->m_pertinentRoot->getNodeInfo()->userStructInfo()->m_deleteTyp = A_TYPE;
    }   

    findMinWHASequence(archiv,eliminatedKeys);

    return countDeletedLeaves;
}
   


/************************************************************************
                          findMinWHASequence
************************************************************************/ 

template<class T,class Y> 
void MaxSequencePQTree<T,Y>::
findMinWHASequence(StackPure<PQNode<T,whaInfo*,Y>*> &archiv,
             SList<PQLeafKey<T,whaInfo*,Y>*> &eliminatedKeys)
{
    //a pointer to a pertinent node of the $PQ$-tree that is currently examined.
    PQNode<T,whaInfo*,Y>   *nodePtr     = 0;

    //a pointer to the first child of type $h$ of [[nodePtr]].
    PQNode<T,whaInfo*,Y>   *hChild1     = 0;

    //a pointer to the second child of type $h$ of [[nodePtr]].
    PQNode<T,whaInfo*,Y>   *hChild2     = 0;

    //a pointer to the child of type $a$ of [[nodePtr]].
    PQNode<T,whaInfo*,Y>   *aChild      = 0;

    // pertinent sibling of hChild1
    PQNode<T,whaInfo*,Y>   *hChild2Sib  = 0;

    //counts the number of children of [[nodePtr]].
    int                     childCount  = 0;

    while (!archiv.empty())
    {
        childCount = 0;
        nodePtr = archiv.pop();
        /*
        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() == FULL && 
            (nodePtr->getNodeInfo()->userStructInfo()->m_deleteTyp == H_TYPE ||
             nodePtr->getNodeInfo()->userStructInfo()->m_deleteTyp == A_TYPE))
        {
            nodePtr->getNodeInfo()->userStructInfo()->m_deleteTyp = B_TYPE;
            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::leaf)
        {
            if (nodePtr->getNodeInfo()->userStructInfo()->m_deleteTyp == W_TYPE)
                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_deleteTyp)
        {
            case B_TYPE:
                this->m_pertinentNodes->pushFront(nodePtr);
                break;

            case W_TYPE:
                markPertinentChildren(nodePtr,PERTINENT,W_TYPE);             
                nodePtr->pertChildCount(0);
                this->m_pertinentNodes->pushFront(nodePtr);
                break;
                 
            case H_TYPE:
                if (nodePtr->type() == PQNodeRoot::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,PARTIAL,W_TYPE);
                    markPertinentChildren(nodePtr,FULL,B_TYPE);
                    if (nodePtr->getNodeInfo()->userStructInfo()->m_hChild1)
                    {
                        hChild1 = (PQNode<T,whaInfo*,Y>*)
                            nodePtr->getNodeInfo()->userStructInfo()->m_hChild1;   
                        hChild1->getNodeInfo()->userStructInfo()->m_deleteTyp = H_TYPE;
                        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,PERTINENT,W_TYPE);
                    hChild1 = (PQNode<T,whaInfo*,Y>*)
                        nodePtr->getNodeInfo()->userStructInfo()->m_hChild1;
                    nodePtr->pertChildCount(setHchild(hChild1));
                }
                this->m_pertinentNodes->pushFront(nodePtr);
                break;

                 
            case A_TYPE:
                if (nodePtr->type() == PQNodeRoot::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,PERTINENT,W_TYPE);
                        aChild = (PQNode<T,whaInfo*,Y>*)
                            nodePtr->getNodeInfo()->userStructInfo()->m_aChild;
                        aChild->getNodeInfo()->userStructInfo()->m_deleteTyp = A_TYPE;
                        nodePtr->pertChildCount(1);
                    }
                    else
                    {
                        markPertinentChildren(nodePtr,FULL,B_TYPE);
                        markPertinentChildren(nodePtr,PARTIAL,W_TYPE);
                        if (nodePtr->getNodeInfo()->userStructInfo()->m_hChild1)
                        {
                            hChild1 = (PQNode<T,whaInfo*,Y>*)
                                nodePtr->getNodeInfo()->userStructInfo()->m_hChild1;
                            hChild1->getNodeInfo()->userStructInfo()->m_deleteTyp = H_TYPE;
                            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_deleteTyp = H_TYPE;
                            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 (see \cite{Lei97}).
                    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,PERTINENT,W_TYPE);
                        aChild->getNodeInfo()->userStructInfo()->m_deleteTyp = A_TYPE;
                        nodePtr->pertChildCount(1);
                    }
                    else
                    {
                        markPertinentChildren(nodePtr,PERTINENT,W_TYPE);
                        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(EMPTY);
        nodePtr->getNodeInfo()->userStructInfo()->m_hChild1 = 0;
        nodePtr->getNodeInfo()->userStructInfo()->m_hChild2 = 0;
        nodePtr->getNodeInfo()->userStructInfo()->m_aChild = 0;
        nodePtr->getNodeInfo()->userStructInfo()->m_w = 0;
        nodePtr->getNodeInfo()->userStructInfo()->m_h = 0;
        nodePtr->getNodeInfo()->userStructInfo()->m_a = 0;
        nodePtr->getNodeInfo()->userStructInfo()->m_deleteTyp = B_TYPE;

    }

}
                
   
/************************************************************************
                          setHchild
************************************************************************/ 
   
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         = 0;       // dummy
    PQNode<T,whaInfo*,Y>    *oldSibling          = 0;       // dummy

    if (hChild1 != 0)
        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() == FULL)
       {
          currentNode->getNodeInfo()->userStructInfo()->m_deleteTyp = B_TYPE;
          pertinentChildCount++;
       }

       else
       {
          if (currentNode->status() == PARTIAL)
          {
              currentNode->getNodeInfo()->userStructInfo()->m_deleteTyp = H_TYPE;
              if ((currentNode->getNodeInfo()->userStructInfo()->m_pertLeafCount - 
                   currentNode->getNodeInfo()->userStructInfo()->m_h) > 0)
                 pertinentChildCount++;
          }
          fullLabel = false;
       }
       oldSibling = currentNode;
       currentNode = nextSibling;
    }


    return pertinentChildCount;
}
   


   
/************************************************************************
                          setAchildren
************************************************************************/ 

template<class T,class Y>
int MaxSequencePQTree<T,Y>::
setAchildren(PQNode<T,whaInfo*,Y> *hChild2,
             PQNode<T,whaInfo*,Y> *hChild2Sib)     
{
    // counts the pertinent children of the sequence.
    int                   pertinentChildCount = 0;

    //is [[false]] as long as the end of the sequence is not detected. 
    //[[true]] otherwise.   
    bool                   reachedEnd          = false;

    PQNode<T,whaInfo*,Y>    *currentNode         = hChild2; // dummy
    PQNode<T,whaInfo*,Y>    *nextSibling         = 0;       // dummy
    PQNode<T,whaInfo*,Y>    *oldSibling          = 0;       // dummy
   

    //Mark [[hChild2]] either as $b$- or as $h$-node.
    if (hChild2->status() == FULL)
        hChild2->getNodeInfo()->userStructInfo()->m_deleteTyp = B_TYPE;
    else {
        //1. node of sequence is EMPTY?
        OGDF_ASSERT(hChild2->status() == PARTIAL)
        hChild2->getNodeInfo()->userStructInfo()->m_deleteTyp = H_TYPE;
    }
    
    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 != 0)
    {
        currentNode = nextSibling;
        reachedEnd = false;
        while(!reachedEnd)
        {
            if (currentNode->status() == FULL)
            {
                currentNode->getNodeInfo()->userStructInfo()->m_deleteTyp = B_TYPE;
                pertinentChildCount++;
            }
            else
            {
                if (currentNode->status() == PARTIAL)
                {
                    currentNode->getNodeInfo()->userStructInfo()->m_deleteTyp = H_TYPE;
                    if ((currentNode->getNodeInfo()->userStructInfo()->m_w - 
                        currentNode->getNodeInfo()->userStructInfo()->m_h) > 0)
                    pertinentChildCount++;
                }
                reachedEnd = true;
            }
            if (!reachedEnd)
            {
                nextSibling = currentNode->getNextSib(oldSibling);
                if (nextSibling == 0)
                    reachedEnd = true;
                oldSibling = currentNode;
                currentNode = nextSibling;
            }
        }
    }

    return pertinentChildCount;   
}




/************************************************************************
                          markPertinentChildren
************************************************************************/ 
            
template<class T,class Y>
void MaxSequencePQTree<T,Y>::
markPertinentChildren(PQNode<T,whaInfo*,Y>  *nodePtr,
                      int label,
                      int deleteTyp)
{
    //PQNode<T,whaInfo*,Y>  *currentNode = 0;
  
    if (label == PERTINENT)
    {
        ListIterator<PQNode<T,whaInfo*,Y>*> it;
        for (it = partialChildren(nodePtr)->begin(); it.valid(); it++)
            (*it)->getNodeInfo()->userStructInfo()->m_deleteTyp = deleteTyp;
        for (it = fullChildren(nodePtr)->begin(); it.valid(); it++)
            (*it)->getNodeInfo()->userStructInfo()->m_deleteTyp = deleteTyp;
    }
    else if (label == PARTIAL)
    {  
        ListIterator<PQNode<T,whaInfo*,Y>*> it;
        for (it = partialChildren(nodePtr)->begin(); it.valid(); it++)
            (*it)->getNodeInfo()->userStructInfo()->m_deleteTyp = deleteTyp;   
    }
   
    else
    {
        ListIterator<PQNode<T,whaInfo*,Y>*> it;
        for (it = fullChildren(nodePtr)->begin(); it.valid(); it++)
            (*it)->getNodeInfo()->userStructInfo()->m_deleteTyp = deleteTyp;
    }
}
     


/************************************************************************
                          haNumPnode
************************************************************************/ 

template<class T,class Y> 
void MaxSequencePQTree<T,Y>::haNumPnode(PQNode<T,whaInfo*,Y> *nodePtr)


{
    int                 sumParW   = 0;
    int                 sumMax1    = 0;
    int                 sumMax2    = 0;
    int                 sumHelp    = 0;
    PQNode<T,whaInfo*,Y>  *currentNode = 0;
    PQNode<T,whaInfo*,Y>  *hChild1    = 0;
    PQNode<T,whaInfo*,Y>  *hChild2    = 0;
    PQNode<T,whaInfo*,Y>  *aChild     = 0;
  
    /*
    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;
        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 = 0;
    }

}// haNumPnode
  



/************************************************************************
                          haNumQnode
************************************************************************/ 

template<class T,class Y> 
void MaxSequencePQTree<T,Y>::haNumQnode(PQNode<T,whaInfo*,Y> *nodePtr)               

{
    int sumAllW = sumPertChild(nodePtr);

    hNumQnode(nodePtr,sumAllW);                  
    aNumQnode(nodePtr,sumAllW);
}


/************************************************************************
                          hNumQnode
************************************************************************/ 

template<class T,class Y> 
void MaxSequencePQTree<T,Y>::hNumQnode(PQNode<T,whaInfo*,Y> *nodePtr,
                                       int sumAllW)               

{
    int                  sumLeft     = 0; 
    int                  sumRight    = 0;
    bool                  fullLabel = true;
    PQNode<T,whaInfo*,Y>   *leftChild    = 0;
    PQNode<T,whaInfo*,Y>   *rightChild   = 0;
    PQNode<T,whaInfo*,Y>   *holdSibling  = 0;
    PQNode<T,whaInfo*,Y>   *checkSibling = 0;


   
    //Compute the $h$-number of the $Q$-node [[nodePtr]]

    //Get endmost children of the $Q$-node [[nodePtr]].
    leftChild = nodePtr->getEndmost(0);
    rightChild = nodePtr->getEndmost(leftChild);
    OGDF_ASSERT(leftChild && 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 {\bf or} 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() != FULL)
            fullLabel = false;
        if (leftChild->status() != EMPTY)
        {
            sumLeft = sumLeft +
                        leftChild->getNodeInfo()->userStructInfo()->m_w -
                        leftChild->getNodeInfo()->userStructInfo()->m_h;
            checkSibling = leftChild->getNextSib(holdSibling);
            if (checkSibling == 0)
                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 {\bf or} 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 = 0;           
    checkSibling = 0;           
    fullLabel = true;            
    while (fullLabel)            
    {
        if (rightChild->status() != FULL)
            fullLabel = false;
        if (rightChild->status() != EMPTY)
        {
            sumRight = sumRight +
                    rightChild->getNodeInfo()->userStructInfo()->m_w -
                       rightChild->getNodeInfo()->userStructInfo()->m_h;

            checkSibling = rightChild->getNextSib(holdSibling);

            if (checkSibling == 0)
                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(0);
    rightChild = nodePtr->getEndmost(leftChild);
    if (sumLeft == 0 && sumRight == 0)
    {
        nodePtr->getNodeInfo()->userStructInfo()->m_h = sumAllW;
        nodePtr->getNodeInfo()->userStructInfo()->m_hChild1 = 0;
    }
    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;
    }
}



/************************************************************************
                          aNumQnode
************************************************************************/ 

template<class T,class Y> 
void MaxSequencePQTree<T,Y>::aNumQnode(PQNode<T,whaInfo*,Y> *nodePtr,
                                       int sumAllW)               

{
    PQNode<T,whaInfo*,Y>   *aChild      = 0;
    int                     beta1       = alpha1beta1Number(nodePtr,&aChild);
    int                     beta2       = 0;
    int                     aSum        = 0;     
    int                     aHoldSum    = 0;
    bool                    endReached  = 0;   
    PQNode<T,whaInfo*,Y>   *leftMost      = 0;
    PQNode<T,whaInfo*,Y>   *leftSib       = 0;
    PQNode<T,whaInfo*,Y>   *leftMostHold  = 0;
    PQNode<T,whaInfo*,Y>   *leftSibHold   = 0;
    PQNode<T,whaInfo*,Y>   *actualNode    = 0;
    PQNode<T,whaInfo*,Y>   *currentNode    = 0;
    PQNode<T,whaInfo*,Y>   *lastChild     = 0;
    PQNode<T,whaInfo*,Y>   *holdSibling  = 0;
    PQNode<T,whaInfo*,Y>   *checkSibling = 0;
                                      // pointer to the second endmost child

    SList<PQNode<T,whaInfo*,Y>*> sequence; 
                             
    actualNode   = nodePtr->getEndmost(0);
    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() != EMPTY)
            {
                sequence.pushFront(actualNode);
                leftMost = 0;
                leftSib = 0;
            }
        }
        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() == FULL)
                sequence.pushFront(actualNode);

            else if (actualNode->status() == 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 == 0)
                    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 = 0;
    }
    else
    {
        nodePtr->getNodeInfo()->userStructInfo()->m_a = beta1;
        nodePtr->getNodeInfo()->userStructInfo()->m_hChild2 = 0;
        nodePtr->getNodeInfo()->userStructInfo()->m_hChild2Sib = 0;
        nodePtr->getNodeInfo()->userStructInfo()->m_aChild = aChild;
    }

}


/************************************************************************
                          alpha1beta1Number
************************************************************************/ 
      
template<class T,class Y> 
int MaxSequencePQTree<T,Y>::
alpha1beta1Number(PQNode<T,whaInfo*,Y> *nodePtr,
                  PQNode<T,whaInfo*,Y> **aChild)
                
{
    int                 sumMaxA   = 0;
    int                 sumAllW   = 0;
    int                 sumHelp    = 0;
    PQNode<T,whaInfo*,Y>  *currentNode = 0;
  
    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);

}


/************************************************************************
                          sumPertChild
************************************************************************/ 

template<class T,class Y> 
int MaxSequencePQTree<T,Y>::sumPertChild(PQNode<T,whaInfo*,Y> *nodePtr)

{
    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;
}


/**************************************************************************************
                           GetParent
***************************************************************************************/ 

template<class T,class Y> 
PQNode<T,whaInfo*,Y>* MaxSequencePQTree<T,Y>::
GetParent(PQNode<T,whaInfo*,Y>* nodePtr)

{
    if (nodePtr->parent() == 0)
        return 0;
    else if (nodePtr->parent()->status() != ELIMINATED)
        return nodePtr->parent();
    else
    {
        PQNode<T,whaInfo*,Y>         *nextNode    = nodePtr;
        PQNode<T,whaInfo*,Y>         *currentNode = 0;
        PQNode<T,whaInfo*,Y>         *oldSib      = 0;
        SListPure<PQNode<T,whaInfo*,Y>*> L;

        currentNode = nodePtr->getNextSib(0);
        oldSib = nodePtr;
        L.pushFront(nodePtr);
        while (currentNode->parent()->status() == ELIMINATED)
        {
            L.pushFront(currentNode);
            nextNode = currentNode->getNextSib(oldSib);
            oldSib = currentNode;
            currentNode = nextNode;
        }
        while (!L.empty())
            L.popFrontRet()->parent(currentNode->parent());
        return currentNode->parent();
   }
}



}

#endif