DynamicSPQRTree.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/Graph.h>
#include <ogdf/basic/List.h>
#include <ogdf/basic/basic.h>
#include <ogdf/decomposition/DynamicSPQRForest.h>
#include <ogdf/decomposition/DynamicSkeleton.h>
#include <ogdf/decomposition/SPQRTree.h>
 
namespace ogdf {
class PertinentGraph;
class Skeleton;
template<class E>
class SList;
 
class OGDF_EXPORT DynamicSPQRTree : public virtual SPQRTree, public DynamicSPQRForest {
public:
    friend class DynamicSkeleton;
 
    // constructors
 
    explicit 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 override { return m_G; }
 
    const Graph& tree() const override { return m_T; }
 
    edge rootEdge() const override { return m_rootEdge; }
 
    node rootNode() const override { return findSPQR(m_bNode_SPQR[m_B.firstNode()]); }
 
    int numberOfSNodes() const override { return m_bNode_numS[m_B.firstNode()]; }
 
    int numberOfPNodes() const override { return m_bNode_numP[m_B.firstNode()]; }
 
    int numberOfRNodes() const override { return m_bNode_numR[m_B.firstNode()]; }
 
    NodeType typeOf(node v) const override { return (NodeType)m_tNode_type[findSPQR(v)]; }
 
    List<node> nodesOfType(NodeType t) const override;
 
    SList<node>& findPath(node s, node t) {
        return findPathSPQR(m_gNode_hNode[s], m_gNode_hNode[t]);
    }
 
    Skeleton& skeleton(node v) const override {
        v = findSPQR(v);
        if (!m_sk[v]) {
            return createSkeleton(v);
        }
        return *m_sk[v];
    }
 
    const Skeleton& skeletonOfReal(edge e) const override {
        return skeleton(spqrproper(m_gEdge_hEdge[e]));
    }
 
    edge copyOfReal(edge e) const override {
        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) override;
 
    node rootTreeAt(node v) override;
 
    edge updateInsertedEdge(edge e) override;
 
    node updateInsertedNode(edge e, edge f) override;
 
 
protected:
    void init(edge e);
 
    DynamicSkeleton& createSkeleton(node vT) const;
 
    void cpRec(node v, PertinentGraph& Gp) const override {
        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; 
};
 
}