SPQRTree.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/Graph.h>
#include <ogdf/basic/List.h>
#include <ogdf/basic/SList.h>
#include <ogdf/basic/basic.h>
#include <ogdf/decomposition/PertinentGraph.h>
#include <ogdf/decomposition/Skeleton.h>
 
namespace ogdf {
 
class OGDF_EXPORT SPQRTree {
public:
    enum class NodeType { SNode, PNode, RNode };
 
    // destructor
    virtual ~SPQRTree() { }
 
    SPQRTree() {};
    SPQRTree(const SPQRTree& copy) = delete;
    SPQRTree(SPQRTree&& move) = delete;
    SPQRTree& operator=(const SPQRTree& copy) = delete;
    SPQRTree& operator=(SPQRTree&& move) = delete;
 
 
    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 == nullptr) {
            m_cpV = new NodeArray<node>(originalGraph(), nullptr);
        }
        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 != nullptr) {
            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()] = nullptr;
        }
    }
 
 
    virtual node rootTreeAt(edge e) = 0;
 
    virtual node rootTreeAt(node v) = 0;
 
    void directSkEdge(node vT, edge e, node src) {
        OGDF_ASSERT(e != nullptr);
        OGDF_ASSERT(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 == nullptr) {
            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; 
};
 
}