DynamicSPQRTree.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_DYNAMIC_SPQR_TREE_H
#define OGDF_DYNAMIC_SPQR_TREE_H


#include <ogdf/decomposition/SPQRTree.h>
#include <ogdf/decomposition/DynamicSPQRForest.h>
#include <ogdf/decomposition/DynamicSkeleton.h>


namespace ogdf {

//---------------------------------------------------------
// DynamicSPQRTree
// SPQR-tree data structure (dynamic environment)
//---------------------------------------------------------

class OGDF_EXPORT DynamicSPQRTree : public virtual SPQRTree, public DynamicSPQRForest
{
public:

    friend class OGDF_EXPORT DynamicSkeleton;


    // constructors

    DynamicSPQRTree (Graph& G) : DynamicSPQRForest(G) { init(G.firstEdge()); }

    DynamicSPQRTree (Graph& G, edge e) : DynamicSPQRForest(G) { init(e); }


    // destructor

    ~DynamicSPQRTree();


    //
    // a) Access operations
    //

    const Graph& originalGraph () const { return m_G; }

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

    edge rootEdge () const { return m_rootEdge; }

    node rootNode () const { return findSPQR(m_bNode_SPQR[m_B.firstNode()]); }

    int numberOfSNodes () const { return m_bNode_numS[m_B.firstNode()]; }

    int numberOfPNodes () const { return m_bNode_numP[m_B.firstNode()]; }

    int numberOfRNodes () const { return m_bNode_numR[m_B.firstNode()]; }

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

    List<node> nodesOfType (NodeType t) const;

    SList<node>& findPath (node s, node t) { return findPathSPQR(m_gNode_hNode[s],m_gNode_hNode[t]); }

    Skeleton& skeleton (node v) const
    {
        v = findSPQR(v);
        if (!m_sk[v]) return createSkeleton(v);
        return *m_sk[v];
    }

    const Skeleton& skeletonOfReal (edge e) const { return skeleton(spqrproper(m_gEdge_hEdge[e])); }

    edge copyOfReal (edge e) const
    {
        e = m_gEdge_hEdge[e];
        skeleton(spqrproper(e));
        return m_skelEdge[e];
    }

    edge skeletonEdge (node v, node w) const
    {
        edge e = virtualEdge(v,w);
        if (!e) return e;
        skeleton(w);
        return m_skelEdge[e];
    }


    //
    // b) Update operations
    //

    node rootTreeAt (edge e);

    node rootTreeAt (node v);

    edge updateInsertedEdge (edge e);

    node updateInsertedNode (edge e, edge f);


protected:

    void init (edge e);

    DynamicSkeleton& createSkeleton (node vT) const;

    void cpRec (node v, PertinentGraph& Gp) const
    {
        v = findSPQR(v);
        for (ListConstIterator<edge> i=m_tNode_hEdges[v].begin(); i.valid(); ++i) {
            edge e = m_hEdge_gEdge[*i];
            if (e) cpAddEdge(e,Gp);
            else if (*i!=m_tNode_hRefEdge[v]) cpRec(spqrproper(*i),Gp);
        }
    }


    edge m_rootEdge;  

    mutable NodeArray<DynamicSkeleton*> m_sk;        
    mutable EdgeArray<edge>             m_skelEdge;  
    mutable NodeArray<node>             m_mapV;      

}; // class DynamicSPQRTree


} // end namespace ogdf


#endif