ClusterPQContainer.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_CLUSTER_PQ_CONTAINER_H
#define OGDF_CLUSTER_PQ_CONTAINER_H

#include <ogdf/cluster/CconnectClusterPlanarEmbed.h>
#include <ogdf/internal/planarity/EmbedPQTree.h>
#include <ogdf/basic/NodeArray.h>
#include <ogdf/basic/EdgeArray.h>


namespace ogdf {

class ClusterPQContainer {

    friend class CconnectClusterPlanarEmbed;


    // Definition
    // incoming edge of v: an edge e = (v,w) with number(v) < number(w)


    // Stores for every node v the keys corresponding to the incoming edges of v 
    NodeArray<SListPure<PlanarLeafKey<indInfo*>* > >* m_inLeaves;

    // Stores for every node v the keys corresponding to the outgoing edges of v 
    NodeArray<SListPure<PlanarLeafKey<indInfo*>* > >* m_outLeaves;
    
    // Stores for every node v the sequence of incoming edges of v according 
    // to the embedding
    NodeArray<SListPure<edge> >* m_frontier;
    
    // Stores for every node v the nodes corresponding to the
    // opposed sink indicators found in the frontier of v.
    NodeArray<SListPure<node> >* m_opposed;
    
    // Stores for every node v the nodes corresponding to the
    // non opposed sink indicators found in the frontier of v.
    NodeArray<SListPure<node> >* m_nonOpposed;
    
    // Table to acces for every edge its corresponding key in the PQTree    
    EdgeArray<PlanarLeafKey<indInfo*>*>* m_edge2Key;

    // Stores for every node its st-number
    NodeArray<int> *m_numbering;

    // Stores for every st-number the node
    Array<node> *m_tableNumber2Node;

    node m_superSink;

    // the subgraph that contains the biconnected component
    // NOT THE COPY OF THE BICONNECTED COMPONENT THAT WAS CONSTRUCTED
    // DURING PLANARITY TESTING. THIS HAS BEEN DELETED.
    Graph                   *m_subGraph; 
    // corresponding PQTree
    EmbedPQTree             *m_T;
    // The leaf correpsonding to the edge (s,t).
    PlanarLeafKey<indInfo*> *m_stEdgeLeaf;

public:

    ClusterPQContainer():
        m_inLeaves(0),m_outLeaves(0),m_frontier(0),
        m_opposed(0),m_nonOpposed(0),m_edge2Key(0),
        m_numbering(0),m_tableNumber2Node(0),
        m_superSink(0),m_subGraph(0),m_T(0), m_stEdgeLeaf(0) {};
    
    ~ClusterPQContainer() {};

    void init(Graph *subGraph){
        m_subGraph = subGraph;
        m_inLeaves 
            = OGDF_NEW NodeArray<SListPure<PlanarLeafKey<indInfo*>* > >(*subGraph);

        m_outLeaves 
            = OGDF_NEW NodeArray<SListPure<PlanarLeafKey<indInfo*>* > >(*subGraph);

        m_frontier
            = OGDF_NEW NodeArray<SListPure<edge> >(*subGraph);

        m_opposed
            = OGDF_NEW NodeArray<SListPure<node> >(*subGraph);

        m_nonOpposed
            = OGDF_NEW NodeArray<SListPure<node> >(*subGraph);  

        m_edge2Key
            = OGDF_NEW EdgeArray<PlanarLeafKey<indInfo*>*>(*subGraph);  

        m_numbering
            = OGDF_NEW NodeArray<int >(*subGraph);

        m_tableNumber2Node 
            = OGDF_NEW Array<node>(subGraph->numberOfNodes()+1);
    }


    void Cleanup() {
        if (m_inLeaves)
            delete m_inLeaves;
        if (m_outLeaves)
        {
            node v;
            forall_nodes(v,*m_subGraph)
            {   
                while (!(*m_outLeaves)[v].empty())
                {
                    PlanarLeafKey<indInfo*>* L = (*m_outLeaves)[v].popFrontRet();
                    delete L;   
                }
            }
            delete m_outLeaves;
        }
        if (m_frontier)
            delete m_frontier;
        if (m_opposed)
            delete m_opposed;
        if (m_nonOpposed)
            delete m_nonOpposed;
        if (m_edge2Key)
            delete m_edge2Key;
        if (m_T)
        {
            m_T->emptyAllPertinentNodes();
            delete m_T;
        }
        if (m_numbering)
            delete m_numbering;
        if (m_tableNumber2Node)
            delete m_tableNumber2Node;

    }
};

}

#endif