StaticSPQRTree.h

Go to the documentation of this file.

/*
 * $Revision: 2523 $
 *
 * last checkin:
 *   $Author: gutwenger $
 *   $Date: 2012-07-02 20:59:27 +0200 (Mon, 02 Jul 2012) $
 ***************************************************************/

#ifdef _MSC_VER
#pragma once
#endif


#ifndef OGDF_STATIC_SPQR_TREE_H
#define OGDF_STATIC_SPQR_TREE_H


#include <ogdf/decomposition/SPQRTree.h>
#include <ogdf/decomposition/StaticSkeleton.h>


namespace ogdf {

    class TricComp;

//---------------------------------------------------------
// StaticSPQRTree
// SPQR-tree data structure (static environment)
//---------------------------------------------------------

class OGDF_EXPORT StaticSPQRTree : public virtual SPQRTree
{
public:

    friend class StaticSkeleton;


    // constructors

    StaticSPQRTree(const Graph &G) : m_skOf(G), m_copyOf(G) { m_pGraph = &G; init(G.firstEdge()); }

    StaticSPQRTree(const Graph &G, edge e) : m_skOf(G), m_copyOf(G) { m_pGraph = &G; init(e); }

    StaticSPQRTree(const Graph &G, TricComp &tricComp) : m_skOf(G), m_copyOf(G) { m_pGraph = &G; init(G.firstEdge(),tricComp); }


    // destructor

    ~StaticSPQRTree();


    //
    // a) Access operations
    //

    const Graph &originalGraph() const { return *m_pGraph; }

    const Graph &tree() const { return m_tree; }

    edge rootEdge() const { return m_rootEdge; }

    node rootNode() const { return m_rootNode; }

    int numberOfSNodes() const { return m_numS; }

    int numberOfPNodes() const { return m_numP; }

    int numberOfRNodes() const { return m_numR; }

    NodeType typeOf(node v) const { return m_type[v]; }

    List<node> nodesOfType(NodeType t) const;

    Skeleton &skeleton(node v) const { return *m_sk[v]; }

    edge skeletonEdgeSrc(edge e) const { return m_skEdgeSrc[e]; }

    edge skeletonEdgeTgt(edge e) const { return m_skEdgeTgt[e]; }

    const Skeleton &skeletonOfReal(edge e) const { return *m_skOf[e]; }

    edge copyOfReal(edge e) const { return m_copyOf[e]; }


    //
    // b) Update operations
    //

    node rootTreeAt(edge e);

    node rootTreeAt(node v);


protected:

    void init(edge e);

    void init(edge eRef, TricComp &tricComp);

    void rootRec(node v, edge ef);

    void cpRec(node v, PertinentGraph &Gp) const
    {
        edge e;
        const Skeleton &S = skeleton(v);

        forall_edges(e,S.getGraph()) {
            edge eOrig = S.realEdge(e);
            if (eOrig != 0) cpAddEdge(eOrig,Gp);
        }

        forall_adj_edges(e,v) {
            node w = e->target();
            if (w != v) cpRec(w,Gp);
        }
    }


    const Graph *m_pGraph;  
    Graph        m_tree;    

    edge m_rootEdge;  
    node m_rootNode;  

    int m_numS;  
    int m_numP;  
    int m_numR;  

    NodeArray<NodeType> m_type;  

    NodeArray<StaticSkeleton *> m_sk;         
    EdgeArray<edge>             m_skEdgeSrc;  
    EdgeArray<edge>             m_skEdgeTgt;  

    EdgeArray<StaticSkeleton *> m_skOf;    
    EdgeArray<edge>             m_copyOf;  

}; // class StaticSPQRTree


} // end namespace ogdf


#endif