SPQRTree.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_SPQR_TREE_H
#define OGDF_SPQR_TREE_H


#include <ogdf/decomposition/Skeleton.h>
#include <ogdf/decomposition/PertinentGraph.h>
#include <ogdf/basic/SList.h>


namespace ogdf {

//---------------------------------------------------------
// SPQRTree
// SPQR-tree data structure
//---------------------------------------------------------

class OGDF_EXPORT SPQRTree
{
public:

    enum NodeType { SNode, PNode, RNode };


    // destructor

    virtual ~SPQRTree() { }


    //
    // a) Access operations
    //

    virtual const Graph &originalGraph() const=0;

    virtual const Graph &tree() const=0;

    virtual edge rootEdge() const=0;

    virtual node rootNode() const=0;

    virtual int numberOfSNodes() const=0;

    virtual int numberOfPNodes() const=0;

    virtual int numberOfRNodes() const=0;

    virtual NodeType typeOf(node v) const=0;

    virtual List<node> nodesOfType(NodeType t) const=0;

    virtual Skeleton &skeleton(node v) const=0;

    virtual const Skeleton &skeletonOfReal(edge e) const=0;

    virtual edge copyOfReal(edge e) const=0;

    void pertinentGraph(node v, PertinentGraph &Gp) const
    {
        if (m_cpV == 0) m_cpV = OGDF_NEW NodeArray<node>(originalGraph(),0);
        NodeArray<node> &cpV = *m_cpV;

        Gp.init(v);
        cpRec(v,Gp);

        const Skeleton &S = skeleton(v);

        edge e = Gp.m_skRefEdge = S.referenceEdge();
        if (e != 0) e = Gp.m_P.newEdge(cpV[S.original(e->source())],cpV[S.original(e->target())]);
        Gp.m_vEdge = e;

        while (!m_cpVAdded.empty()) cpV[m_cpVAdded.popFrontRet()] = 0;
    }


    //
    // b) Update operations
    //

    virtual node rootTreeAt(edge e) =0;

    virtual node rootTreeAt(node v) =0;


    void directSkEdge(node vT, edge e, node src)
    {
        OGDF_ASSERT(e != 0 && (src == e->source() || src == e->target()))

        if(e->source() != src) skeleton(vT).getGraph().reverseEdge(e);
    }

    void replaceSkEdgeByPeak(node vT, edge e)
    {
        Graph &M = skeleton(vT).getGraph();
        M.reverseEdge(M.split(e));
    }


protected:

    virtual void cpRec(node v, PertinentGraph &Gp) const=0;

    edge cpAddEdge(edge eOrig, PertinentGraph &Gp) const
    {
        edge eP = Gp.m_P.newEdge(cpAddNode(eOrig->source(),Gp),cpAddNode(eOrig->target(),Gp));
        Gp.m_origE[eP] = eOrig;
        return eP;
    }

    node cpAddNode(node vOrig, PertinentGraph &Gp) const
    {
        node &vP = (*m_cpV)[vOrig];
        if (vP == 0) {
            m_cpVAdded.pushBack(vOrig);
            Gp.m_origV[vP = Gp.m_P.newNode()] = vOrig;
        }
        return vP;
    }


    // auxiliary members used for computing pertinent graphs
    mutable NodeArray<node> *m_cpV;       
    mutable SList<node>      m_cpVAdded;  

}; // class SPQRTree


} // end namespace ogdf


#endif