StaticSPQRTree.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/decomposition/SPQRTree.h>
#include <ogdf/decomposition/StaticSkeleton.h>
#include <ogdf/graphalg/Triconnectivity.h>
 
namespace ogdf {
 
class OGDF_EXPORT StaticSPQRTree : public virtual SPQRTree {
public:
    friend class StaticSkeleton;
 
    // constructors
 
    explicit StaticSPQRTree(const Graph& G) : m_skOf(G), m_copyOf(G) {
        OGDF_ASSERT(G.numberOfEdges() > 0);
        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, Triconnectivity& tricComp) : m_skOf(G), m_copyOf(G) {
        m_pGraph = &G;
        init(G.firstEdge(), tricComp);
    }
 
    ~StaticSPQRTree();
 
 
    const Graph& originalGraph() const override { return *m_pGraph; }
 
    const Graph& tree() const override { return m_tree; }
 
    edge rootEdge() const override { return m_rootEdge; }
 
    node rootNode() const override { return m_rootNode; }
 
    int numberOfSNodes() const override { return m_numS; }
 
    int numberOfPNodes() const override { return m_numP; }
 
    int numberOfRNodes() const override { return m_numR; }
 
    NodeType typeOf(node v) const override { return m_type[v]; }
 
    List<node> nodesOfType(NodeType t) const override;
 
    Skeleton& skeleton(node v) const override { 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 override { return *m_skOf[e]; }
 
    edge copyOfReal(edge e) const override { return m_copyOf[e]; }
 
 
    node rootTreeAt(edge e) override;
 
    node rootTreeAt(node v) override;
 
 
protected:
    void init(edge e);
 
    void init(edge eRef, Triconnectivity& tricComp);
 
    void rootRec(node v, edge ef);
 
    void cpRec(node v, PertinentGraph& Gp) const override {
        const Skeleton& S = skeleton(v);
 
        for (edge e : S.getGraph().edges) {
            edge eOrig = S.realEdge(e);
            if (eOrig != nullptr) {
                cpAddEdge(eOrig, Gp);
            }
        }
 
        for (adjEntry adj : v->adjEntries) {
            node w = adj->theEdge()->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; 
};
 
}